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-2022 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 "soplex/spxdefines.h"
27 #include "soplex/spxratiotester.h"
28 #include "soplex/spxfastrt.h"
29 
30 namespace soplex
31 {
32 
33 /**@brief Bound flipping ratio test ("long step dual") for SoPlex.
34  @ingroup Algo
35 
36  Class SPxBoundFlippingRT provides an implementation of the bound flipping
37  ratio test as a derived class of SPxRatioTester. Dual step length is
38  increased beyond some breakpoints and corresponding primal nonbasic
39  variables are set to their other bound to handle the resulting dual infeasibility.
40 
41  The implementation mostly follows the papers
42  - I. Maros, "A generalized dual phase-2 simplex algorithm",
43  European Journal of Operational Research Vol 149, Issue 1, pp. 1-16, 2003
44  - A. Koberstein, "Progress in the dual simplex algorithm for solving large scale LP problems:
45  techniques for a fast and stable implementation",
46  Computational Optimization and Applications Vol 41, Nr 2, pp. 185-204, 2008
47 
48  See SPxRatioTester for a class documentation.
49 */
50 template <class R>
51 class SPxBoundFlippingRT : public SPxFastRT<R>
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  R 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 
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  R
104  flipPotential; /**< tracks bound flip history and decides which ratio test to use */
105  int relax_count; /**< count rounds of ratio test */
106  Array<Breakpoint> breakpoints; /**< array of breakpoints */
108  updPrimRhs; /**< right hand side vector of additional system to be solved after the ratio test */
110  updPrimVec; /**< allocation of memory for additional solution vector */
111  ///@}
112 
113  /** store all available pivots/breakpoints in an array (positive pivot search direction) */
115  int& nBp, /**< number of found breakpoints so far */
116  int& minIdx, /**< index to current minimal breakpoint */
117  const int* idx, /**< pointer to indices of current vector */
118  int nnz, /**< number of nonzeros in current vector */
119  const R* upd, /**< pointer to update values of current vector */
120  const R* vec, /**< pointer to values of current vector */
121  const R* upp, /**< pointer to upper bound/rhs of current vector */
122  const R* low, /**< pointer to lower bound/lhs of current vector */
123  BreakpointSource src /**< type of vector (pVec or coPvec)*/
124  );
125 
126  /** store all available pivots/breakpoints in an array (negative pivot search direction) */
128  int& nBp, /**< number of found breakpoints so far */
129  int& minIdx, /**< index to current minimal breakpoint */
130  const int* idx, /**< pointer to indices of current vector */
131  int nnz, /**< number of nonzeros in current vector */
132  const R* upd, /**< pointer to update values of current vector */
133  const R* vec, /**< pointer to values of current vector */
134  const R* upp, /**< pointer to upper bound/rhs of current vector */
135  const R* low, /**< pointer to lower bound/lhs of current vector */
136  BreakpointSource src /**< type of vector (pVec or coPvec)*/
137  );
138 
139  /** get values for entering index and perform shifts if necessary */
140  bool getData(
141  R& val,
142  SPxId& enterId,
143  int idx,
144  R stab,
145  R degeneps,
146  const R* upd,
147  const R* vec,
148  const R* low,
149  const R* upp,
151  R max
152  );
153 
154  /** get values for leaving index and perform shifts if necessary */
155  bool getData(
156  R& val,
157  int& leaveIdx,
158  int idx,
159  R stab,
160  R degeneps,
161  const R* upd,
162  const R* vec,
163  const R* low,
164  const R* upp,
166  R max
167  );
168 
169  /** perform necessary bound flips to restore dual feasibility */
170  void flipAndUpdate(
171  int& usedBp /**< number of bounds that should be flipped */
172  );
173 
174  /** comparison method for breakpoints */
175  static bool isSmaller(
176  Breakpoint x,
177  Breakpoint y
178  )
179  {
180  return (spxAbs(x.val) < spxAbs(y.val));
181  };
182 
183 public:
184 
185  //-------------------------------------
186  /**@name Construction / destruction */
187  ///@{
188  /// default constructor
190  : SPxFastRT<R>("Bound Flipping")
191  , enableBoundFlips(true)
192  , enableRowBoundFlips(false)
193  , flipPotential(1)
194  , relax_count(0)
195  , breakpoints(10)
196  , updPrimRhs(0)
197  , updPrimVec(0)
198  {}
199  /// copy constructor
201  : SPxFastRT<R>(old)
202  , enableBoundFlips(old.enableBoundFlips)
203  , enableRowBoundFlips(old.enableRowBoundFlips)
204  , flipPotential(1)
205  , relax_count(0)
206  , breakpoints(10)
207  , updPrimRhs(0)
208  , updPrimVec(0)
209  {}
210  /// assignment operator
212  {
213  if(this != &rhs)
214  {
216  }
217 
218  enableBoundFlips = rhs.enableBoundFlips;
219  enableRowBoundFlips = rhs.enableRowBoundFlips;
221 
222  return *this;
223  }
224  /// destructor
226  {}
227  /// clone function for polymorphism
228  inline virtual SPxRatioTester<R>* clone() const
229  {
230  return new SPxBoundFlippingRT(*this);
231  }
232  ///@}
233 
234  //-------------------------------------
235  /**@name Select enter/leave */
236  ///@{
237  ///
238  virtual int selectLeave(
239  R& val,
240  R enterTest,
241  bool polish = false
242  );
243  ///
244  virtual SPxId selectEnter(
245  R& val,
246  int leaveIdx,
247  bool polish = false
248  );
249 
250  void useBoundFlips(bool bf)
251  {
252  enableBoundFlips = bf;
253  }
254 
255  void useBoundFlipsRow(bool bf)
256  {
257  enableRowBoundFlips = bf;
258  }
259  ///@}
260 };
261 
262 } // namespace soplex
263 
264 #include "spxboundflippingrt.hpp"
265 
266 #endif // _SPXBOUNDFLIPPINGRT_H_
Fast shifting ratio test.
Bound flipping ratio test ("long step dual") for SoPlex.Class SPxBoundFlippingRT provides an implemen...
SPxBoundFlippingRT(const SPxBoundFlippingRT &old)
copy constructor
Array< Breakpoint > breakpoints
virtual int selectLeave(R &val, R enterTest, bool polish=false)
Abstract ratio test base class.
Safe arrays of arbitrary types.Class Array provides safe arrays of arbitrary type. Array elements are accessed just like ordinary C++ array elements by means of the index operator[](). Safety is provided by.
Definition: array.h:63
Abstract ratio test base class.Class SPxRatioTester is the virtual base class for computing the ratio...
void collectBreakpointsMax(int &nBp, int &minIdx, const int *idx, int nnz, const R *upd, const R *vec, const R *upp, const R *low, BreakpointSource src)
bool getData(R &val, SPxId &enterId, int idx, R stab, R degeneps, const R *upd, const R *vec, const R *low, const R *upp, BreakpointSource src, R max)
virtual ~SPxBoundFlippingRT()
destructor
Semi sparse vector.This class implements semi-sparse vectors. Such are VectorBases where the indices ...
Definition: dsvectorbase.h:29
virtual SPxId selectEnter(R &val, int leaveIdx, bool polish=false)
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:42
virtual SPxRatioTester< R > * clone() const
clone function for polymorphism
void collectBreakpointsMin(int &nBp, int &minIdx, const int *idx, int nnz, const R *upd, const R *vec, const R *upp, const R *low, BreakpointSource src)
Debugging, floating point type and parameter definitions.
SPxBoundFlippingRT()
default constructor
Everything should be within this namespace.
SPxFastRT & operator=(const SPxFastRT &rhs)
assignment operator
Definition: spxfastrt.h:189
void flipAndUpdate(int &usedBp)
R spxAbs(R a)
Definition: spxdefines.h:338
SPxBoundFlippingRT & operator=(const SPxBoundFlippingRT &rhs)
assignment operator
static bool isSmaller(Breakpoint x, Breakpoint y)
R operator()(Breakpoint i, Breakpoint j) const