Scippy

SoPlex

Sequential object-oriented simPlex

spxfastrt.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-2019 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 spxfastrt.h
17  * @brief Fast shifting ratio test.
18  */
19 #ifndef _SPXFASTRT_H_
20 #define _SPXFASTRT_H_
21 
22 #include <assert.h>
23 
24 #include "soplex/spxdefines.h"
25 #include "soplex/spxratiotester.h"
26 
27 namespace soplex
28 {
29 
30 /**@brief Fast shifting ratio test.
31  @ingroup Algo
32 
33  Class SPxFastRT is an implementation class of SPxRatioTester providing
34  fast and stable ratio test. Stability is achieved by allowing some
35  infeasibility to ensure numerical stability such as the Harris procedure.
36  Performance is achieved by skipping the second phase if the first phase
37  already shows a stable enough pivot.
38 
39  See SPxRatioTester for a class documentation.
40 */
41 class SPxFastRT : public SPxRatioTester
42 {
43 protected:
44  //-------------------------------------
45  /**@name Data */
46  //@{
47  /// parameter for computing minimum stability requirement
49  /// |value| < epsilon is considered 0.
51  /// currently allowed infeasibility.
53  /// flag used in methods minSelect/maxSelect to retrieve correct basis status
54  bool iscoid;
55  //@}
56 
57  //-------------------------------------
58  /**@name Private helpers */
59  //@{
60  /// resets tolerances (epsilon).
61  void resetTols();
62  /// relaxes stability requirements.
63  void relax();
64  /// tightens stability requirements.
65  void tighten();
66  /// Compute stability requirement
67  Real minStability(Real maxabs);
68 
69  /// Max phase 1 value.
70  /** Computes the maximum value \p val that could be used for updating \p update
71  such that it would still fulfill the upper and lower bounds \p upBound and
72  \p lowBound, respectively, within #delta. Return value is the index where the
73  maximum value is encountered. At the same time the maximum absolute value
74  of \p update.delta() is computed and returned in \p maxabs. Internally all
75  loops are started at \p start and incremented by \p incr.
76  */
77  int maxDelta(Real& val, Real& maxabs, UpdateVector& update,
78  const Vector& lowBound, const Vector& upBound, int start, int incr) const;
79 
80  ///
81  int maxDelta(Real& val, Real& maxabs);
82 
83  ///
84  SPxId maxDelta(int& nr, Real& val, Real& maxabs);
85 
86  /// Min phase 1 value.
87  /** Computes the minimum value \p val that could be used for updating \p update
88  such that it would still fulfill the upper and lower bounds \p upBound and
89  \p lowBound, respectively, within #delta. Return value is the index where the
90  minimum value is encountered. At the same time the maximum absolute value
91  of \p update.delta() is computed and returned in \p maxabs. Internally all
92  loops are started at \p start and incremented by \p incr.
93  */
94  int minDelta(Real& val, Real& maxabs, UpdateVector& update,
95  const Vector& lowBound, const Vector& upBound, int start, int incr) const;
96 
97  ///
98  int minDelta(Real& val, Real& maxabs);
99 
100  ///
101  SPxId minDelta(int& nr, Real& val, Real& maxabs);
102 
103  /// selects stable index for maximizing ratio test.
104  /** Selects from all update values \p val < \p max the one with the largest
105  value of \p upd.delta() which must be greater than \p stab and is
106  returned in \p stab. The index is returned as well as the corresponding
107  update value \p val. Internally all loops are started at \p start and
108  incremented by \p incr.
109  */
110  int maxSelect(Real& val, Real& stab, Real& best, Real& bestDelta,
111  Real max, const UpdateVector& upd, const Vector& low,
112  const Vector& up, int start = 0, int incr = 1) const;
113  ///
114  int maxSelect(Real& val, Real& stab, Real& bestDelta, Real max);
115  ///
116  SPxId maxSelect(int& nr, Real& val, Real& stab,
117  Real& bestDelta, Real max);
118 
119  /// selects stable index for minimizing ratio test.
120  /** Select from all update values \p val > \p max the one with the largest
121  value of \p upd.delta() which must be greater than \p stab and is
122  returned in \p stab. The index is returned as well as the corresponding
123  update value \p val. Internally all loops are started at \p start and
124  incremented by \p incr.
125  */
126  int minSelect(Real& val, Real& stab, Real& best, Real& bestDelta,
127  Real max, const UpdateVector& upd, const Vector& low,
128  const Vector& up, int start = 0, int incr = 1) const;
129  ///
130  int minSelect(Real& val, Real& stab,
131  Real& bestDelta, Real max);
132  ///
133  SPxId minSelect(int& nr, Real& val, Real& stab,
134  Real& bestDelta, Real max);
135 
136  /// tests for stop after phase 1.
137  /** Tests whether a shortcut after phase 1 is feasible for the
138  selected leave pivot. In this case return the update value in \p sel.
139  */
140  bool minShortLeave(Real& sel, int leave, Real maxabs);
141  ///
142  bool maxShortLeave(Real& sel, int leave, Real maxabs);
143 
144  /// numerical stability tests.
145  /** Tests whether the selected leave index needs to be discarded (and do so)
146  and the ratio test is to be recomputed.
147  If \p polish is set to true no shifts are applied.
148  */
149  bool minReLeave(Real& sel, int leave, Real maxabs, bool polish = false);
150  ///
151  bool maxReLeave(Real& sel, int leave, Real maxabs, bool polish = false);
152 
153  /// numerical stability check.
154  /** Tests whether the selected enter \p id needs to be discarded (and do so)
155  and the ratio test is to be recomputed.
156  */
157  bool minReEnter(Real& sel, Real maxabs, const SPxId& id, int nr, bool polish = false);
158  ///
159  bool maxReEnter(Real& sel, Real maxabs, const SPxId& id, int nr, bool polish = false);
160 
161  /// Tests and returns whether a shortcut after phase 1 is feasible for the
162  /// selected enter pivot.
163  bool shortEnter(const SPxId& enterId, int nr, Real max, Real maxabs) const;
164  //@}
165 
166 public:
167 
168  //-------------------------------------
169  /**@name Construction / destruction */
170  //@{
171  /// default constructor
173  : SPxRatioTester("Fast")
174  , minStab(DEFAULT_BND_VIOL)
175  , epsilon(DEFAULT_EPS_ZERO)
176  , fastDelta(DEFAULT_BND_VIOL)
177  , iscoid(false)
178  {}
179  /// copy constructor
180  SPxFastRT(const SPxFastRT& old)
181  : SPxRatioTester(old)
182  , minStab(old.minStab)
183  , epsilon(old.epsilon)
184  , fastDelta(old.fastDelta)
185  , iscoid(false)
186  {}
187  /// assignment operator
189  {
190  if(this != &rhs)
191  {
193  minStab = rhs.minStab;
194  epsilon = rhs.epsilon;
195  fastDelta = rhs.fastDelta;
196  iscoid = false;
197  }
198 
199  return *this;
200  }
201  /// bound flipping constructor
202  SPxFastRT(const char* name)
203  : SPxRatioTester(name)
204  , minStab(DEFAULT_BND_VIOL)
205  , epsilon(DEFAULT_EPS_ZERO)
206  , fastDelta(DEFAULT_BND_VIOL)
207  , iscoid(false)
208  {}
209  /// destructor
210  virtual ~SPxFastRT()
211  {}
212  /// clone function for polymorphism
213  inline virtual SPxRatioTester* clone() const
214  {
215  return new SPxFastRT(*this);
216  }
217  //@}
218 
219  //-------------------------------------
220  /**@name Access / modification */
221  //@{
222  ///
223  virtual void load(SPxSolver* solver);
224  ///
225  virtual int selectLeave(Real& val, Real, bool polish = false);
226  ///
227  virtual SPxId selectEnter(Real& val, int, bool polish = false);
228  ///
229  virtual void setType(SPxSolver::Type type);
230  ///
231  virtual void setDelta(Real newDelta)
232  {
233  if(newDelta <= DEFAULT_EPS_ZERO)
234  newDelta = DEFAULT_EPS_ZERO;
235 
236  delta = newDelta;
237  fastDelta = newDelta;
238  }
239  ///
240  virtual Real getDelta()
241  {
242  return fastDelta;
243  }
244  //@}
245 };
246 } // namespace soplex
247 #endif // _SPXFASTRT_H_
virtual ~SPxFastRT()
destructor
Definition: spxfastrt.h:210
bool maxReEnter(Real &sel, Real maxabs, const SPxId &id, int nr, bool polish=false)
Definition: spxfastrt.cpp:1075
#define DEFAULT_BND_VIOL
default allowed bound violation
Definition: spxdefines.h:226
Type
Algorithmic type.
Definition: spxsolver.h:124
bool maxShortLeave(Real &sel, int leave, Real maxabs)
Definition: spxfastrt.cpp:771
int minSelect(Real &val, Real &stab, Real &best, Real &bestDelta, Real max, const UpdateVector &upd, const Vector &low, const Vector &up, int start=0, int incr=1) const
selects stable index for minimizing ratio test.
Definition: spxfastrt.cpp:516
Real delta
allowed bound violation
SPxFastRT(const SPxFastRT &old)
copy constructor
Definition: spxfastrt.h:180
Real fastDelta
currently allowed infeasibility.
Definition: spxfastrt.h:52
Abstract ratio test base class.
virtual void setDelta(Real newDelta)
Definition: spxfastrt.h:231
virtual int selectLeave(Real &val, Real, bool polish=false)
Definition: spxfastrt.cpp:899
Abstract ratio test base class.Class SPxRatioTester is the virtual base class for computing the ratio...
bool minReLeave(Real &sel, int leave, Real maxabs, bool polish=false)
numerical stability tests.
Definition: spxfastrt.cpp:857
Real epsilon
|value| < epsilon is considered 0.
Definition: spxfastrt.h:50
virtual void setType(SPxSolver::Type type)
Definition: spxfastrt.cpp:1493
int maxDelta(Real &val, Real &maxabs, UpdateVector &update, const Vector &lowBound, const Vector &upBound, int start, int incr) const
Max phase 1 value.
Definition: spxfastrt.cpp:104
void relax()
relaxes stability requirements.
Definition: spxfastrt.cpp:82
SPxFastRT()
default constructor
Definition: spxfastrt.h:172
Real minStability(Real maxabs)
Compute stability requirement.
Definition: spxfastrt.cpp:89
Generic Ids for LP rows or columns.Both SPxColIds and SPxRowIds may be treated uniformly as SPxIds: ...
Definition: spxid.h:85
void resetTols()
resets tolerances (epsilon).
Definition: spxfastrt.cpp:48
Fast shifting ratio test.Class SPxFastRT is an implementation class of SPxRatioTester providing fast ...
Definition: spxfastrt.h:41
double Real
Definition: spxdefines.h:218
bool shortEnter(const SPxId &enterId, int nr, Real max, Real maxabs) const
Tests and returns whether a shortcut after phase 1 is feasible for the selected enter pivot...
Definition: spxfastrt.cpp:1285
#define DEFAULT_EPS_ZERO
default allowed additive zero: 1.0 + EPS_ZERO == 1.0
Definition: spxdefines.h:230
Dense vector with semi-sparse vector for updatesIn many algorithms vectors are updated in every itera...
Definition: updatevector.h:53
SPxRatioTester & operator=(const SPxRatioTester &rhs)
assignment operator
virtual Real getDelta()
Definition: spxfastrt.h:240
Debugging, floating point type and parameter definitions.
Sequential object-oriented SimPlex.SPxSolver is an LP solver class using the revised Simplex algorith...
Definition: spxsolver.h:85
bool minReEnter(Real &sel, Real maxabs, const SPxId &id, int nr, bool polish=false)
numerical stability check.
Definition: spxfastrt.cpp:1179
Everything should be within this namespace.
void tighten()
tightens stability requirements.
Definition: spxfastrt.cpp:58
SPxFastRT(const char *name)
bound flipping constructor
Definition: spxfastrt.h:202
bool iscoid
flag used in methods minSelect/maxSelect to retrieve correct basis status
Definition: spxfastrt.h:54
virtual SPxSolver * solver() const
returns loaded LP solver.
int maxSelect(Real &val, Real &stab, Real &best, Real &bestDelta, Real max, const UpdateVector &upd, const Vector &low, const Vector &up, int start=0, int incr=1) const
selects stable index for maximizing ratio test.
Definition: spxfastrt.cpp:597
bool minShortLeave(Real &sel, int leave, Real maxabs)
tests for stop after phase 1.
Definition: spxfastrt.cpp:793
int minDelta(Real &val, Real &maxabs, UpdateVector &update, const Vector &lowBound, const Vector &upBound, int start, int incr) const
Min phase 1 value.
Definition: spxfastrt.cpp:270
bool maxReLeave(Real &sel, int leave, Real maxabs, bool polish=false)
Definition: spxfastrt.cpp:815
virtual void load(SPxSolver *solver)
Definition: spxfastrt.cpp:1487
virtual SPxId selectEnter(Real &val, int, bool polish=false)
Definition: spxfastrt.cpp:1319
SPxFastRT & operator=(const SPxFastRT &rhs)
assignment operator
Definition: spxfastrt.h:188
Real minStab
parameter for computing minimum stability requirement
Definition: spxfastrt.h:48
virtual SPxRatioTester * clone() const
clone function for polymorphism
Definition: spxfastrt.h:213