SoPlex Doxygen Documentation
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-2012 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 "spxdefines.h"
25 #include "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
48  Real minStab;
49  /// |value| < epsilon is considered 0.
50  Real epsilon;
51  /// currently allowed infeasibility.
52  Real fastDelta;
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  */
148  bool minReLeave(Real& sel, int leave, Real maxabs);
149  ///
150  bool maxReLeave(Real& sel, int leave, Real maxabs);
151 
152  /// numerical stability check.
153  /** Tests whether the selected enter \p id needs to be discarded (and do so)
154  and the ratio test is to be recomputed.
155  */
156  bool minReEnter(Real& sel, Real maxabs, const SPxId& id, int nr);
157  ///
158  bool maxReEnter(Real& sel, Real maxabs, const SPxId& id, int nr);
159 
160  /// Tests and returns whether a shortcut after phase 1 is feasible for the
161  /// selected enter pivot.
162  bool shortEnter(const SPxId& enterId, int nr, Real max, Real maxabs) const;
163  //@}
164 
165 public:
166 
167  //-------------------------------------
168  /**@name Construction / destruction */
169  //@{
170  /// default constructor
171  SPxFastRT()
172  : SPxRatioTester("Fast")
173  , iscoid(false)
174  {}
175  /// copy constructor
176  SPxFastRT(const SPxFastRT& old)
177  : SPxRatioTester(old)
178  , minStab(old.minStab)
179  , epsilon(old.epsilon)
180  , fastDelta(old.fastDelta)
181  , iscoid(false)
182  {}
183  /// assignment operator
184  SPxFastRT& operator=( const SPxFastRT& rhs)
185  {
186  if(this != &rhs)
187  {
188  SPxRatioTester::operator=(rhs);
189  minStab = rhs.minStab;
190  epsilon = rhs.epsilon;
191  fastDelta = rhs.fastDelta;
192  iscoid = false;
193  }
194 
195  return *this;
196  }
197  /// bound flipping constructor
198  SPxFastRT(const char* name)
199  : SPxRatioTester(name)
200  , iscoid(false)
201  {}
202  /// destructor
203  virtual ~SPxFastRT()
204  {}
205  /// clone function for polymorphism
206  inline virtual SPxRatioTester* clone() const
207  {
208  return new SPxFastRT(*this);
209  }
210  //@}
211 
212  //-------------------------------------
213  /**@name Access / modification */
214  //@{
215  ///
216  virtual void load(SPxSolver* solver);
217  ///
218  virtual int selectLeave(Real& val, SPxId);
219  ///
220  virtual SPxId selectEnter(Real& val, int);
221  ///
222  virtual void setType(SPxSolver::Type type);
223  ///
224  virtual void setDelta(Real newDelta)
225  {
226  if( newDelta <= DEFAULT_EPS_ZERO )
227  newDelta = DEFAULT_EPS_ZERO;
228  delta = newDelta;
229  fastDelta = newDelta;
230  }
231  ///
232  virtual Real getDelta()
233  {
234  return fastDelta;
235  }
236  //@}
237 };
238 } // namespace soplex
239 #endif // _SPXFASTRT_H_
240 
241 //-----------------------------------------------------------------------------
242 //Emacs Local Variables:
243 //Emacs mode:c++
244 //Emacs c-basic-offset:3
245 //Emacs tab-width:8
246 //Emacs indent-tabs-mode:nil
247 //Emacs End:
248 //-----------------------------------------------------------------------------
© 2003-2013 by Zuse Institute Berlin (ZIB), Imprint Generated on Wed Jan 9 2013 for SoPlex by doxygen