Scippy

SoPlex

Sequential object-oriented simPlex

spxboundflippingrt.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the class library */
4 /* SoPlex --- the Sequential object-oriented simPlex. */
5 /* */
6 /* Copyright (C) 1996-2015 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SoPlex is distributed under the terms of the ZIB Academic Licence. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SoPlex; see the file COPYING. If not email to soplex@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file spxboundflippingrt.h
17  * @brief Bound flipping ratio test (long step dual) for SoPlex.
18  * @author Matthias Miltenberger
19  * @author Eva Ramlow
20  */
21 #ifndef _SPXBOUNDFLIPPINGRT_H_
22 #define _SPXBOUNDFLIPPINGRT_H_
23 
24 
25 #include <assert.h>
26 #include "spxdefines.h"
27 #include "spxratiotester.h"
28 #include "spxfastrt.h"
29 
30 namespace soplex
31 {
32 struct Compare;
33 
34 /**@brief Bound flipping ratio test ("long step dual") for SoPlex.
35  @ingroup Algo
36 
37  Class SPxBoundFlippingRT provides an implementation of the bound flipping
38  ratio test as a derived class of SPxRatioTester. Dual step length is
39  increased beyond some breakpoints and corresponding primal nonbasic
40  variables are set to their other bound to handle the resulting dual infeasibility.
41 
42  The implementation mostly follows the papers
43  - I. Maros, "A generalized dual phase-2 simplex algorithm",
44  European Journal of Operational Research Vol 149, Issue 1, pp. 1-16, 2003
45  - A. Koberstein, "Progress in the dual simplex algorithm for solving large scale LP problems:
46  techniques for a fast and stable implementation",
47  Computational Optimization and Applications Vol 41, Nr 2, pp. 185-204, 2008
48 
49  See SPxRatioTester for a class documentation.
50 */
51 class SPxBoundFlippingRT : public SPxFastRT
52 {
53 private:
54  /**@name substructures */
55  //@{
56  /** enumerator to remember which vector we have been searching to find a breakpoint
57  */
58  enum BreakpointSource
59  {
60  FVEC = -1,
61  PVEC = 0,
62  COPVEC = 1
63  };
64 
65  /** breakpoint structure
66  */
67  struct Breakpoint
68  {
69  Real val; /**< breakpoint value (step length) */
70  int idx; /**< index of corresponding row/column */
71  BreakpointSource src; /**< origin of breakpoint, i.e. vector which was searched */
72  };
73 
74  /** Compare class for breakpoints
75  */
76  struct BreakpointCompare
77  {
78  public:
79  /** constructor
80  */
81  BreakpointCompare()
82  : entry(0)
83  {
84  }
85 
86  const Breakpoint* entry;
87 
88  Real operator() (
89  Breakpoint i,
90  Breakpoint j
91  ) const
92  {
93  return i.val - j.val;
94  }
95  };
96  //@}
97 
98  /**@name Data
99  */
100  //@{
101  bool enableBoundFlips; /**< enable or disable long steps in BoundFlippingRT */
102  bool enableRowBoundFlips;/**< enable bound flips also for row representation */
103  Real flipPotential; /**< tracks bound flip history and decides which ratio test to use */
104  int relax_count; /**< count rounds of ratio test */
105  DataArray<Breakpoint> breakpoints; /**< array of breakpoints */
106  SSVector updPrimRhs; /**< right hand side vector of additional system to be solved after the ratio test */
107  SSVector updPrimVec; /**< allocation of memory for additional solution vector */
108  //@}
109 
110  /** store all available pivots/breakpoints in an array (positive pivot search direction) */
111  void collectBreakpointsMax(
112  int& nBp, /**< number of found breakpoints so far */
113  int& minIdx, /**< index to current minimal breakpoint */
114  const int* idx, /**< pointer to indices of current vector */
115  int nnz, /**< number of nonzeros in current vector */
116  const Real* upd, /**< pointer to update values of current vector */
117  const Real* vec, /**< pointer to values of current vector */
118  const Real* upp, /**< pointer to upper bound/rhs of current vector */
119  const Real* low, /**< pointer to lower bound/lhs of current vector */
120  BreakpointSource src /**< type of vector (pVec or coPvec)*/
121  );
122 
123  /** store all available pivots/breakpoints in an array (negative pivot search direction) */
124  void collectBreakpointsMin(
125  int& nBp, /**< number of found breakpoints so far */
126  int& minIdx, /**< index to current minimal breakpoint */
127  const int* idx, /**< pointer to indices of current vector */
128  int nnz, /**< number of nonzeros in current vector */
129  const Real* upd, /**< pointer to update values of current vector */
130  const Real* vec, /**< pointer to values of current vector */
131  const Real* upp, /**< pointer to upper bound/rhs of current vector */
132  const Real* low, /**< pointer to lower bound/lhs of current vector */
133  BreakpointSource src /**< type of vector (pVec or coPvec)*/
134  );
135 
136  /** get values for entering index and perform shifts if necessary */
137  bool getData(
138  Real& val,
139  SPxId& enterId,
140  int idx,
141  Real stab,
142  Real degeneps,
143  const Real* upd,
144  const Real* vec,
145  const Real* low,
146  const Real* upp,
147  BreakpointSource src,
148  Real max
149  );
150 
151  /** get values for leaving index and perform shifts if necessary */
152  bool getData(
153  Real& val,
154  int& leaveIdx,
155  int idx,
156  Real stab,
157  Real degeneps,
158  const Real* upd,
159  const Real* vec,
160  const Real* low,
161  const Real* upp,
162  BreakpointSource src,
163  Real max
164  );
165 
166  /** perform necessary bound flips to restore dual feasibility */
167  void flipAndUpdate(
168  int& usedBp /**< number of bounds that should be flipped */
169  );
170 
171  /** comparison method for breakpoints */
172  static bool isSmaller(
173  Breakpoint x,
174  Breakpoint y
175  )
176  {
177  return (spxAbs(x.val) < spxAbs(y.val));
178  };
179 
180 public:
181 
182  //-------------------------------------
183  /**@name Construction / destruction */
184  //@{
185  /// default constructor
186  SPxBoundFlippingRT()
187  : SPxFastRT("Bound Flipping")
188  , enableBoundFlips(true)
189  , enableRowBoundFlips(false)
190  , flipPotential(1)
191  , relax_count(0)
192  , breakpoints(10)
193  , updPrimRhs(0)
194  , updPrimVec(0)
195  {}
196  /// copy constructor
197  SPxBoundFlippingRT(const SPxBoundFlippingRT& old)
198  : SPxFastRT(old)
199  , enableBoundFlips(old.enableBoundFlips)
200  , enableRowBoundFlips(old.enableRowBoundFlips)
201  , flipPotential(1)
202  , relax_count(0)
203  , breakpoints(10)
204  , updPrimRhs(0)
205  , updPrimVec(0)
206  {}
207  /// assignment operator
208  SPxBoundFlippingRT& operator=( const SPxBoundFlippingRT& rhs)
209  {
210  if(this != &rhs)
211  {
212  SPxFastRT::operator=(rhs);
213  }
214 
215  enableBoundFlips = rhs.enableBoundFlips;
216  enableRowBoundFlips = rhs.enableRowBoundFlips;
217  flipPotential = rhs.flipPotential;
218 
219  return *this;
220  }
221  /// destructor
222  virtual ~SPxBoundFlippingRT()
223  {}
224  /// clone function for polymorphism
225  inline virtual SPxRatioTester* clone() const
226  {
227  return new SPxBoundFlippingRT(*this);
228  }
229  //@}
230 
231  //-------------------------------------
232  /**@name Select enter/leave */
233  //@{
234  ///
235  virtual int selectLeave(
236  Real& val,
237  Real enterTest
238  );
239  ///
240  virtual SPxId selectEnter(
241  Real& val,
242  int leaveIdx
243  );
244 
245  void useBoundFlips(bool bf)
246  {
247  enableBoundFlips = bf;
248  }
249 
250  void useBoundFlipsRow(bool bf)
251  {
252  enableRowBoundFlips = bf;
253  }
254  //@}
255 };
256 
257 } // namespace soplex
258 #endif // _SPXBOUNDFLIPPINGRT_H_