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" 34 #include "soplex/spxratiotester.h" 35 36 namespace soplex 37 { 38 39 #define SOPLEX_FASTRT_EPSILON 1e-10 40 41 /**@brief Fast shifting ratio test. 42 @ingroup Algo 43 44 Class SPxFastRT is an implementation class of SPxRatioTester providing 45 fast and stable ratio test. Stability is achieved by allowing some 46 infeasibility to ensure numerical stability such as the Harris procedure. 47 Performance is achieved by skipping the second phase if the first phase 48 already shows a stable enough pivot. 49 50 See SPxRatioTester for a class documentation. 51 */ 52 template <class R> 53 class SPxFastRT : public SPxRatioTester<R> 54 { 55 protected: 56 //------------------------------------- 57 /**@name Data */ 58 ///@{ 59 /// parameter for computing minimum stability requirement 60 R minStab; 61 /// zero tolerance used by the ratio tester 62 R epsilon; 63 /// currently allowed infeasibility. 64 R fastDelta; 65 /// flag used in methods minSelect/maxSelect to retrieve correct basis status 66 bool iscoid; 67 ///@} 68 69 //------------------------------------- 70 /**@name Private helpers */ 71 ///@{ 72 /// resets tolerances (epsilon). 73 void resetTols(); 74 /// return epsilon 75 const R epsilonZero() const 76 { 77 return epsilon; 78 } 79 /// relaxes stability requirements. 80 void relax(); 81 /// tightens stability requirements. 82 void tighten(); 83 /// Compute stability requirement 84 R minStability(R maxabs); 85 86 /// Max phase 1 value. 87 /** Computes the maximum 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 maximum 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 maxDelta(R& val, R& maxabs, UpdateVector<R>& update, 95 const VectorBase<R>& lowBound, const VectorBase<R>& upBound, int start, int incr) const; 96 97 /// 98 int maxDelta(R& val, R& maxabs); 99 100 /// 101 SPxId maxDelta(int& nr, R& val, R& maxabs); 102 103 /// Min phase 1 value. 104 /** Computes the minimum value \p val that could be used for updating \p update 105 such that it would still fulfill the upper and lower bounds \p upBound and 106 \p lowBound, respectively, within #delta. Return value is the index where the 107 minimum value is encountered. At the same time the maximum absolute value 108 of \p update.delta() is computed and returned in \p maxabs. Internally all 109 loops are started at \p start and incremented by \p incr. 110 */ 111 int minDelta(R& val, R& maxabs, UpdateVector<R>& update, 112 const VectorBase<R>& lowBound, const VectorBase<R>& upBound, int start, int incr) const; 113 114 /// 115 int minDelta(R& val, R& maxabs); 116 117 /// 118 SPxId minDelta(int& nr, R& val, R& maxabs); 119 120 /// selects stable index for maximizing ratio test. 121 /** Selects from all update values \p val < \p max the one with the largest 122 value of \p upd.delta() which must be greater than \p stab and is 123 returned in \p stab. The index is returned as well as the corresponding 124 update value \p val. Internally all loops are started at \p start and 125 incremented by \p incr. 126 */ 127 int maxSelect(R& val, R& stab, R& best, R& bestDelta, 128 R max, const UpdateVector<R>& upd, const VectorBase<R>& low, 129 const VectorBase<R>& up, int start = 0, int incr = 1) const; 130 /// 131 int maxSelect(R& val, R& stab, R& bestDelta, R max); 132 /// 133 SPxId maxSelect(int& nr, R& val, R& stab, 134 R& bestDelta, R max); 135 136 /// selects stable index for minimizing ratio test. 137 /** Select from all update values \p val > \p max the one with the largest 138 value of \p upd.delta() which must be greater than \p stab and is 139 returned in \p stab. The index is returned as well as the corresponding 140 update value \p val. Internally all loops are started at \p start and 141 incremented by \p incr. 142 */ 143 int minSelect(R& val, R& stab, R& best, R& bestDelta, 144 R max, const UpdateVector<R>& upd, const VectorBase<R>& low, 145 const VectorBase<R>& up, int start = 0, int incr = 1) const; 146 /// 147 int minSelect(R& val, R& stab, 148 R& bestDelta, R max); 149 /// 150 SPxId minSelect(int& nr, R& val, R& stab, 151 R& bestDelta, R max); 152 153 /// tests for stop after phase 1. 154 /** Tests whether a shortcut after phase 1 is feasible for the 155 selected leave pivot. In this case return the update value in \p sel. 156 */ 157 bool minShortLeave(R& sel, int leave, R maxabs); 158 /// 159 bool maxShortLeave(R& sel, int leave, R maxabs); 160 161 /// numerical stability tests. 162 /** Tests whether the selected leave index needs to be discarded (and do so) 163 and the ratio test is to be recomputed. 164 If \p polish is set to true no shifts are applied. 165 */ 166 bool minReLeave(R& sel, int leave, R maxabs, bool polish = false); 167 /// 168 bool maxReLeave(R& sel, int leave, R maxabs, bool polish = false); 169 170 /// numerical stability check. 171 /** Tests whether the selected enter \p id needs to be discarded (and do so) 172 and the ratio test is to be recomputed. 173 */ 174 bool minReEnter(R& sel, R maxabs, const SPxId& id, int nr, bool polish = false); 175 /// 176 bool maxReEnter(R& sel, R maxabs, const SPxId& id, int nr, bool polish = false); 177 178 /// Tests and returns whether a shortcut after phase 1 is feasible for the 179 /// selected enter pivot. 180 bool shortEnter(const SPxId& enterId, int nr, R max, R maxabs) const; 181 ///@} 182 183 public: 184 185 //------------------------------------- 186 /**@name Construction / destruction */ 187 ///@{ 188 /// default constructor 189 SPxFastRT() 190 : SPxRatioTester<R>("Fast") 191 , minStab(SOPLEX_DEFAULT_BND_VIOL) 192 , epsilon(SOPLEX_DEFAULT_EPS_ZERO) 193 , fastDelta(SOPLEX_DEFAULT_BND_VIOL) 194 , iscoid(false) 195 {} 196 /// copy constructor 197 SPxFastRT(const SPxFastRT& old) 198 : SPxRatioTester<R>(old) 199 , minStab(old.minStab) 200 , epsilon(old.epsilon) 201 , fastDelta(old.fastDelta) 202 , iscoid(false) 203 {} 204 /// assignment operator 205 SPxFastRT& operator=(const SPxFastRT& rhs) 206 { 207 if(this != &rhs) 208 { 209 SPxRatioTester<R>::operator=(rhs); 210 minStab = rhs.minStab; 211 epsilon = rhs.epsilon; 212 fastDelta = rhs.fastDelta; 213 iscoid = false; 214 } 215 216 return *this; 217 } 218 /// bound flipping constructor 219 SPxFastRT(const char* name) 220 : SPxRatioTester<R>(name) 221 , minStab(SOPLEX_DEFAULT_BND_VIOL) 222 , epsilon(SOPLEX_DEFAULT_EPS_ZERO) 223 , fastDelta(SOPLEX_DEFAULT_BND_VIOL) 224 , iscoid(false) 225 {} 226 /// destructor 227 virtual ~SPxFastRT() 228 {} 229 /// clone function for polymorphism 230 inline virtual SPxRatioTester<R>* clone() const 231 { 232 return new SPxFastRT(*this); 233 } 234 ///@} 235 236 //------------------------------------- 237 /**@name Access / modification */ 238 ///@{ 239 /// 240 virtual void load(SPxSolverBase<R>* solver); 241 /// 242 virtual int selectLeave(R& val, R, bool polish = false); 243 /// 244 virtual SPxId selectEnter(R& val, int, bool polish = false); 245 /// 246 virtual void setType(typename SPxSolverBase<R>::Type type); 247 /// 248 virtual void setDelta(R newDelta) 249 { 250 if(newDelta <= this->tolerances()->epsilon()) 251 newDelta = this->tolerances()->epsilon(); 252 253 this->delta = newDelta; 254 fastDelta = newDelta; 255 } 256 /// 257 virtual R getDelta() 258 { 259 return fastDelta; 260 } 261 ///@} 262 }; 263 } // namespace soplex 264 265 #include "spxfastrt.hpp" 266 267 #endif // _SPXFASTRT_H_ 268