SoPlex Documentation
Loading...
Searching...
No Matches
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-2023 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SoPlex; see the file LICENSE. If not email to soplex@zib.de. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file spxfastrt.h
26 * @brief Fast shifting ratio test.
27 */
28#ifndef _SPXFASTRT_H_
29#define _SPXFASTRT_H_
30
31#include <assert.h>
32
33#include "soplex/spxdefines.h"
35
36namespace soplex
37{
38
39/**@brief Fast shifting ratio test.
40 @ingroup Algo
41
42 Class SPxFastRT is an implementation class of SPxRatioTester providing
43 fast and stable ratio test. Stability is achieved by allowing some
44 infeasibility to ensure numerical stability such as the Harris procedure.
45 Performance is achieved by skipping the second phase if the first phase
46 already shows a stable enough pivot.
47
48 See SPxRatioTester for a class documentation.
49*/
50template <class R>
51class SPxFastRT : public SPxRatioTester<R>
52{
53protected:
54 //-------------------------------------
55 /**@name Data */
56 ///@{
57 /// parameter for computing minimum stability requirement
59 /// |value| < epsilon is considered 0.
61 /// currently allowed infeasibility.
63 /// flag used in methods minSelect/maxSelect to retrieve correct basis status
64 bool iscoid;
65 ///@}
66
67 //-------------------------------------
68 /**@name Private helpers */
69 ///@{
70 /// resets tolerances (epsilon).
71 void resetTols();
72 /// relaxes stability requirements.
73 void relax();
74 /// tightens stability requirements.
75 void tighten();
76 /// Compute stability requirement
77 R minStability(R maxabs);
78
79 /// Max phase 1 value.
80 /** Computes the maximum value \p val that could be used for updating \p update
81 such that it would still fulfill the upper and lower bounds \p upBound and
82 \p lowBound, respectively, within #delta. Return value is the index where the
83 maximum value is encountered. At the same time the maximum absolute value
84 of \p update.delta() is computed and returned in \p maxabs. Internally all
85 loops are started at \p start and incremented by \p incr.
86 */
87 int maxDelta(R& val, R& maxabs, UpdateVector<R>& update,
88 const VectorBase<R>& lowBound, const VectorBase<R>& upBound, int start, int incr) const;
89
90 ///
91 int maxDelta(R& val, R& maxabs);
92
93 ///
94 SPxId maxDelta(int& nr, R& val, R& maxabs);
95
96 /// Min phase 1 value.
97 /** Computes the minimum value \p val that could be used for updating \p update
98 such that it would still fulfill the upper and lower bounds \p upBound and
99 \p lowBound, respectively, within #delta. Return value is the index where the
100 minimum value is encountered. At the same time the maximum absolute value
101 of \p update.delta() is computed and returned in \p maxabs. Internally all
102 loops are started at \p start and incremented by \p incr.
103 */
104 int minDelta(R& val, R& maxabs, UpdateVector<R>& update,
105 const VectorBase<R>& lowBound, const VectorBase<R>& upBound, int start, int incr) const;
106
107 ///
108 int minDelta(R& val, R& maxabs);
109
110 ///
111 SPxId minDelta(int& nr, R& val, R& maxabs);
112
113 /// selects stable index for maximizing ratio test.
114 /** Selects from all update values \p val < \p max the one with the largest
115 value of \p upd.delta() which must be greater than \p stab and is
116 returned in \p stab. The index is returned as well as the corresponding
117 update value \p val. Internally all loops are started at \p start and
118 incremented by \p incr.
119 */
120 int maxSelect(R& val, R& stab, R& best, R& bestDelta,
121 R max, const UpdateVector<R>& upd, const VectorBase<R>& low,
122 const VectorBase<R>& up, int start = 0, int incr = 1) const;
123 ///
124 int maxSelect(R& val, R& stab, R& bestDelta, R max);
125 ///
126 SPxId maxSelect(int& nr, R& val, R& stab,
127 R& bestDelta, R max);
128
129 /// selects stable index for minimizing ratio test.
130 /** Select from all update values \p val > \p max the one with the largest
131 value of \p upd.delta() which must be greater than \p stab and is
132 returned in \p stab. The index is returned as well as the corresponding
133 update value \p val. Internally all loops are started at \p start and
134 incremented by \p incr.
135 */
136 int minSelect(R& val, R& stab, R& best, R& bestDelta,
137 R max, const UpdateVector<R>& upd, const VectorBase<R>& low,
138 const VectorBase<R>& up, int start = 0, int incr = 1) const;
139 ///
140 int minSelect(R& val, R& stab,
141 R& bestDelta, R max);
142 ///
143 SPxId minSelect(int& nr, R& val, R& stab,
144 R& bestDelta, R max);
145
146 /// tests for stop after phase 1.
147 /** Tests whether a shortcut after phase 1 is feasible for the
148 selected leave pivot. In this case return the update value in \p sel.
149 */
150 bool minShortLeave(R& sel, int leave, R maxabs);
151 ///
152 bool maxShortLeave(R& sel, int leave, R maxabs);
153
154 /// numerical stability tests.
155 /** Tests whether the selected leave index needs to be discarded (and do so)
156 and the ratio test is to be recomputed.
157 If \p polish is set to true no shifts are applied.
158 */
159 bool minReLeave(R& sel, int leave, R maxabs, bool polish = false);
160 ///
161 bool maxReLeave(R& sel, int leave, R maxabs, bool polish = false);
162
163 /// numerical stability check.
164 /** Tests whether the selected enter \p id needs to be discarded (and do so)
165 and the ratio test is to be recomputed.
166 */
167 bool minReEnter(R& sel, R maxabs, const SPxId& id, int nr, bool polish = false);
168 ///
169 bool maxReEnter(R& sel, R maxabs, const SPxId& id, int nr, bool polish = false);
170
171 /// Tests and returns whether a shortcut after phase 1 is feasible for the
172 /// selected enter pivot.
173 bool shortEnter(const SPxId& enterId, int nr, R max, R maxabs) const;
174 ///@}
175
176public:
177
178 //-------------------------------------
179 /**@name Construction / destruction */
180 ///@{
181 /// default constructor
189 /// copy constructor
197 /// assignment operator
199 {
200 if(this != &rhs)
201 {
203 minStab = rhs.minStab;
204 epsilon = rhs.epsilon;
205 fastDelta = rhs.fastDelta;
206 iscoid = false;
207 }
208
209 return *this;
210 }
211 /// bound flipping constructor
212 SPxFastRT(const char* name)
213 : SPxRatioTester<R>(name)
217 , iscoid(false)
218 {}
219 /// destructor
220 virtual ~SPxFastRT()
221 {}
222 /// clone function for polymorphism
223 inline virtual SPxRatioTester<R>* clone() const
224 {
225 return new SPxFastRT(*this);
226 }
227 ///@}
228
229 //-------------------------------------
230 /**@name Access / modification */
231 ///@{
232 ///
234 ///
235 virtual int selectLeave(R& val, R, bool polish = false);
236 ///
237 virtual SPxId selectEnter(R& val, int, bool polish = false);
238 ///
239 virtual void setType(typename SPxSolverBase<R>::Type type);
240 ///
241 virtual void setDelta(R newDelta)
242 {
245
246 this->delta = newDelta;
248 }
249 ///
250 virtual R getDelta()
251 {
252 return fastDelta;
253 }
254 ///@}
255};
256} // namespace soplex
257
258#include "spxfastrt.hpp"
259
260#endif // _SPXFASTRT_H_
Safe arrays of data objects.
Definition dataarray.h:75
Fast shifting ratio test.
Definition spxfastrt.h:52
virtual void setType(typename SPxSolverBase< R >::Type type)
int maxSelect(R &val, R &stab, R &best, R &bestDelta, R max, const UpdateVector< R > &upd, const VectorBase< R > &low, const VectorBase< R > &up, int start=0, int incr=1) const
selects stable index for maximizing ratio test.
virtual SPxRatioTester< R > * clone() const
clone function for polymorphism
Definition spxfastrt.h:223
virtual void setDelta(R newDelta)
Definition spxfastrt.h:241
SPxId maxDelta(int &nr, R &val, R &maxabs)
virtual ~SPxFastRT()
destructor
Definition spxfastrt.h:220
void relax()
relaxes stability requirements.
void tighten()
tightens stability requirements.
R fastDelta
currently allowed infeasibility.
Definition spxfastrt.h:62
int minSelect(R &val, R &stab, R &bestDelta, R max)
SPxFastRT(const char *name)
bound flipping constructor
Definition spxfastrt.h:212
bool minReLeave(R &sel, int leave, R maxabs, bool polish=false)
numerical stability tests.
int maxDelta(R &val, R &maxabs)
bool minShortLeave(R &sel, int leave, R maxabs)
tests for stop after phase 1.
int minDelta(R &val, R &maxabs, UpdateVector< R > &update, const VectorBase< R > &lowBound, const VectorBase< R > &upBound, int start, int incr) const
Min phase 1 value.
bool iscoid
flag used in methods minSelect/maxSelect to retrieve correct basis status
Definition spxfastrt.h:64
SPxId minDelta(int &nr, R &val, R &maxabs)
virtual void load(SPxSolverBase< R > *solver)
virtual int selectLeave(R &val, R, bool polish=false)
SPxId minSelect(int &nr, R &val, R &stab, R &bestDelta, R max)
SPxFastRT(const SPxFastRT &old)
copy constructor
Definition spxfastrt.h:190
bool maxShortLeave(R &sel, int leave, R maxabs)
int maxDelta(R &val, R &maxabs, UpdateVector< R > &update, const VectorBase< R > &lowBound, const VectorBase< R > &upBound, int start, int incr) const
Max phase 1 value.
virtual SPxId selectEnter(R &val, int, bool polish=false)
bool shortEnter(const SPxId &enterId, int nr, R max, R maxabs) const
Tests and returns whether a shortcut after phase 1 is feasible for the selected enter pivot.
virtual R getDelta()
Definition spxfastrt.h:250
int maxSelect(R &val, R &stab, R &bestDelta, R max)
int minSelect(R &val, R &stab, R &best, R &bestDelta, R max, const UpdateVector< R > &upd, const VectorBase< R > &low, const VectorBase< R > &up, int start=0, int incr=1) const
selects stable index for minimizing ratio test.
void resetTols()
resets tolerances (epsilon).
bool maxReEnter(R &sel, R maxabs, const SPxId &id, int nr, bool polish=false)
SPxFastRT()
default constructor
Definition spxfastrt.h:182
int minDelta(R &val, R &maxabs)
SPxFastRT & operator=(const SPxFastRT &rhs)
assignment operator
Definition spxfastrt.h:198
SPxId maxSelect(int &nr, R &val, R &stab, R &bestDelta, R max)
R minStability(R maxabs)
Compute stability requirement.
R epsilon
|value| < epsilon is considered 0.
Definition spxfastrt.h:60
bool maxReLeave(R &sel, int leave, R maxabs, bool polish=false)
R minStab
parameter for computing minimum stability requirement
Definition spxfastrt.h:58
bool minReEnter(R &sel, R maxabs, const SPxId &id, int nr, bool polish=false)
numerical stability check.
Generic Ids for LP rows or columns.
Definition spxid.h:95
Abstract ratio test base class.
R delta
allowed bound violation
virtual SPxSolverBase< R > * solver() const
returns loaded LP solver.
SPxRatioTester & operator=(const SPxRatioTester &rhs)
assignment operator
Type
Algorithmic type.
Definition spxsolver.h:143
Everything should be within this namespace.
Debugging, floating point type and parameter definitions.
#define DEFAULT_BND_VIOL
default allowed bound violation
Definition spxdefines.h:274
#define DEFAULT_EPS_ZERO
default allowed additive zero: 1.0 + EPS_ZERO == 1.0
Definition spxdefines.h:278
Abstract ratio test base class.