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-2016 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 */
52 {
53 private:
54  /**@name substructures */
55  //@{
56  /** enumerator to remember which vector we have been searching to find a breakpoint
57  */
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  */
77  {
78  public:
79  /** constructor
80  */
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) */
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) */
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,
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,
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
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
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
209  {
210  if(this != &rhs)
211  {
213  }
214 
215  enableBoundFlips = rhs.enableBoundFlips;
216  enableRowBoundFlips = rhs.enableRowBoundFlips;
217  flipPotential = rhs.flipPotential;
218 
219  return *this;
220  }
221  /// destructor
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_
Rational spxAbs(const Rational &r)
Absolute.
Definition: rational.cpp:3925
Fast shifting ratio test.
Bound flipping ratio test ("long step dual") for SoPlex.Class SPxBoundFlippingRT provides an implemen...
void collectBreakpointsMax(int &nBp, int &minIdx, const int *idx, int nnz, const Real *upd, const Real *vec, const Real *upp, const Real *low, BreakpointSource src)
Safe arrays of data objects.Class DataArray provides safe arrays of Data Objects. For general C++ obj...
Definition: dataarray.h:63
SPxBoundFlippingRT(const SPxBoundFlippingRT &old)
copy constructor
Abstract ratio test base class.
Abstract ratio test base class.Class SPxRatioTester is the virtual base class for computing the ratio...
virtual int selectLeave(Real &val, Real enterTest)
virtual ~SPxBoundFlippingRT()
destructor
virtual SPxRatioTester * clone() const
clone function for polymorphism
void collectBreakpointsMin(int &nBp, int &minIdx, const int *idx, int nnz, const Real *upd, const Real *vec, const Real *upp, const Real *low, BreakpointSource src)
Generic Ids for LP rows or columns.Both SPxColIds and SPxRowIds may be treated uniformly as SPxIds: ...
Definition: spxid.h:85
Fast shifting ratio test.Class SPxFastRT is an implementation class of SPxRatioTester providing fast ...
Definition: spxfastrt.h:41
double Real
SOPLEX_DEBUG.
Definition: spxdefines.h:200
Debugging, floating point type and parameter definitions.
SPxBoundFlippingRT()
default constructor
Everything should be within this namespace.
bool getData(Real &val, SPxId &enterId, int idx, Real stab, Real degeneps, const Real *upd, const Real *vec, const Real *low, const Real *upp, BreakpointSource src, Real max)
SPxFastRT & operator=(const SPxFastRT &rhs)
assignment operator
Definition: spxfastrt.h:187
DataArray< Breakpoint > breakpoints
SPxBoundFlippingRT & operator=(const SPxBoundFlippingRT &rhs)
assignment operator
static bool isSmaller(Breakpoint x, Breakpoint y)
virtual SPxId selectEnter(Real &val, int leaveIdx)