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 spxratiotester.h 26 * @brief Abstract ratio test base class. 27 */ 28 #ifndef _SPXRATIOTESTER_H_ 29 #define _SPXRATIOTESTER_H_ 30 31 32 #include <assert.h> 33 34 #include "soplex/spxdefines.h" 35 #include "soplex/spxsolver.h" 36 37 namespace soplex 38 { 39 40 /**@brief Abstract ratio test base class. 41 @ingroup Algo 42 43 Class SPxRatioTester is the virtual base class for computing the ratio 44 test within the Simplex algorithm driven by SoPlex. After a SoPlex 45 solver has been #load()%ed to an SPxRatioTester, the solver calls 46 #selectLeave() for computing the ratio test for the entering simplex and 47 #selectEnter() for computing the ratio test in leaving simplex. 48 */ 49 template <class R> 50 class SPxRatioTester 51 { 52 protected: 53 54 //------------------------------------- 55 /**@name Data */ 56 ///@{ 57 /// the solver 58 SPxSolverBase<R>* thesolver; 59 /// name of the ratio tester 60 const char* m_name; 61 /// internal storage of type 62 typename SPxSolverBase<R>::Type m_type; 63 /// allowed bound violation 64 R delta; 65 /// tolerances used by the solver 66 std::shared_ptr<Tolerances> _tolerances; 67 ///@} 68 69 public: 70 71 //------------------------------------- 72 /**@name Access / modification */ 73 ///@{ 74 /// get name of ratio tester. 75 virtual const char* getName() const 76 { 77 return m_name; 78 } 79 /// loads LP. 80 /** Load the solver and LP for which pricing steps are to be performed. 81 */ 82 virtual void load(SPxSolverBase<R>* p_solver) 83 { 84 thesolver = p_solver; 85 } 86 87 /// unloads LP. 88 virtual void clear() 89 { 90 thesolver = nullptr; 91 } 92 93 /// returns loaded LP solver. 94 virtual SPxSolverBase<R>* solver() const 95 { 96 return thesolver; 97 } 98 99 /// set allowed bound violation 100 virtual void setDelta(R newDelta) 101 { 102 if(newDelta <= this->tolerances()->epsilon()) 103 delta = this->tolerances()->epsilon(); 104 else 105 delta = newDelta; 106 } 107 108 /// get allowed bound violation 109 virtual R getDelta() 110 { 111 return delta; 112 } 113 114 /// set the _tolerances member variable 115 virtual void setTolerances(std::shared_ptr<Tolerances> newTolerances) 116 { 117 this->_tolerances = newTolerances; 118 } 119 /// get the _tolerances member variable 120 const std::shared_ptr<Tolerances> tolerances() const 121 { 122 return _tolerances; 123 } 124 ///@} 125 126 //------------------------------------- 127 /**@name Entering / leaving */ 128 ///@{ 129 /// selects index to leave the basis. 130 /** Method #selectLeave() is called by the loaded SoPlex solver when 131 computing the entering simplex algorithm. Its task is to select and 132 return the index of the basis variable that is to leave the basis. 133 When being called, 134 \ref SPxSolverBase<R>::fVec() "fVec()" fullfills the basic bounds 135 \ref SPxSolverBase<R>::lbBound() "lbBound()" and 136 \ref SPxSolverBase<R>::ubBound() "ubBound()" within 137 \ref SPxSolverBase<R>::entertol() "entertol()". 138 fVec().delta() is the vector by 139 which fVec() will be updated in this simplex step. Its nonzero 140 indices are stored in sorted order in fVec().idx(). 141 142 If \p val > 0, \p val is the maximum allowed update value for fVec(), 143 otherwise the minimum. Method #selectLeave() must chose \p val of the 144 same sign as passed, such that updating fVec() by \p val yields a 145 new vector that satisfies all basic bounds (within entertol). The 146 returned index, must be the index of an element of fVec(), that 147 reaches one of its bounds with this update. 148 */ 149 virtual int selectLeave(R& val, R enterTest, bool polish = false) = 0; 150 151 /// selects variable Id to enter the basis. 152 /** Method #selectEnter() is called by the loaded SoPlex solver, when 153 computing the leaving simplex algorithm. It's task is to select and 154 return the Id of the basis variable that is to enter the basis. 155 When being called, 156 \ref SPxSolverBase<R>::pVec() "pVec()" fullfills the bounds 157 \ref SPxSolverBase<R>::lbBound() "lbBound()" and 158 \ref SPxSolverBase<R>::ubBound() "ubBound()" within 159 \ref SPxSolverBase<R>::leavetol() "leavetol()". 160 Similarly, 161 \ref SPxSolverBase<R>::coPvec() "coPvec()" fulfills the bounds 162 \ref SPxSolverBase<R>::lbBound() "lbBound()" and 163 \ref SPxSolverBase<R>::ubBound() "ubBound()" within 164 \ref SPxSolverBase<R>::leavetol() "leavetol()". 165 pVec().delta() and coPvec().delta() are 166 the vectors by which pVec() and coPvec() will be updated in this 167 simplex step. Their nonzero indices are stored in sorted order in 168 pVec().idx() and coPvec().idx(). 169 170 If \p val > 0, \p val is the maximum allowed update value for pVec() 171 and coPvec(), otherwise the minimum. Method #selectEnter() must 172 chose \p val of the same sign as passed, such that updating pVec() 173 and coPvec() by \p val yields a new vector that satisfies all basic 174 bounds (within leavetol). The returned Id must be the Id of an 175 element of pVec() or coPvec(), that reaches one of its bounds 176 with this update. 177 */ 178 virtual SPxId selectEnter(R& val, int leaveIdx, bool polish = false) = 0; 179 180 /// sets Simplex type. 181 /** Informs pricer about (a change of) the loaded SoPlex's Type. In 182 the sequel, only the corresponding select methods may be called. 183 */ 184 virtual void setType(typename SPxSolverBase<R>::Type) 185 {} 186 ///@} 187 188 //------------------------------------- 189 /**@name Construction / destruction */ 190 ///@{ 191 /// default constructor 192 explicit SPxRatioTester(const char* name) 193 : thesolver(0) 194 , m_name(name) 195 , m_type(SPxSolverBase<R>::LEAVE) 196 , delta(1e-6) 197 {} 198 /// copy constructor 199 SPxRatioTester(const SPxRatioTester& old) 200 : thesolver(old.thesolver) 201 , m_name(old.m_name) 202 , m_type(old.m_type) 203 , delta(old.delta) 204 {} 205 /// assignment operator 206 SPxRatioTester& operator=(const SPxRatioTester& rhs) 207 { 208 if(this != &rhs) 209 { 210 m_name = rhs.m_name; 211 thesolver = rhs.thesolver; 212 m_type = rhs.m_type; 213 delta = rhs.delta; 214 } 215 216 return *this; 217 } 218 /// destructor. 219 virtual ~SPxRatioTester() 220 { 221 thesolver = nullptr; 222 m_name = nullptr; 223 } 224 /// clone function for polymorphism 225 virtual SPxRatioTester* clone() const = 0; 226 ///@} 227 228 }; 229 230 231 } // namespace soplex 232 #endif // _SPXRATIOTESTER_H_ 233