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 26 /**@file spxpricer.h 27 * @brief Abstract pricer base class. 28 */ 29 #ifndef _SPXPRICE_H_ 30 #define _SPXPRICE_H_ 31 32 #include <assert.h> 33 34 #include "soplex/spxdefines.h" 35 #include "soplex/spxsolver.h" 36 #include "soplex/sorter.h" 37 38 namespace soplex 39 { 40 41 /**@brief Abstract pricer base class. 42 @ingroup Algo 43 44 Class SPxPricer is a pure virtual class defining the interface for pricer 45 classes to be used by SoPlex. The pricer's task is to select a vector to 46 enter or leave the simplex basis, depending on the chosen simplex type. 47 48 An SPxPricer first #load%s the SoPlex object for which pricing is to 49 be performed. Then, depending of the SPxSolverBase<R>::Type, methods 50 #selectEnter() and #entered4() (for entering Simplex) or #selectLeave() 51 and #left4() (for leaving Simplex) are called by SoPlex. The SPxPricer 52 object is informed of a change of the SPxSolverBase<R>::Type by calling method 53 #setType(). 54 */ 55 template <class R> 56 class SPxPricer 57 { 58 protected: 59 60 //------------------------------------- 61 /**@name Data */ 62 ///@{ 63 /// name of the pricer 64 const char* m_name; 65 /// the solver 66 67 SPxSolverBase<R>* 68 thesolver; //@todo The template type should be identified? Do I have to defined two of them? 69 /// violation bound 70 R thetolerance; 71 /// tolerances used by the solver 72 std::shared_ptr<Tolerances> _tolerances; 73 ///@} 74 75 76 struct IdxElement 77 { 78 int idx; 79 R val; 80 }; 81 82 /// Compare class to sort idx/val pairs, used for hypersparse pricing leaving 83 struct IdxCompare 84 { 85 public: 86 /// constructor 87 IdxCompare() 88 : elements(0) 89 {} 90 91 const IdxElement* elements; 92 93 R operator()( 94 IdxElement a, 95 IdxElement b 96 ) const 97 { 98 //the first case is needed to handle inf-values 99 return (a.val == b.val) ? 0 : b.val - a.val; 100 } 101 }; 102 103 IdxCompare compare; 104 105 public: 106 107 // violation types used for (hyper) sparse pricing 108 enum ViolationType 109 { 110 NOT_VIOLATED = 0, 111 VIOLATED = 1, 112 VIOLATED_AND_CHECKED = 2 113 }; 114 115 //------------------------------------- 116 /**@name Initialization */ 117 ///@{ 118 /// get name of pricer. 119 virtual const char* getName() const 120 { 121 return m_name; 122 } 123 124 /// loads LP. 125 /** Loads the solver and LP for which pricing steps are to be performed. 126 */ 127 virtual void load(SPxSolverBase<R>* p_solver) 128 { 129 thesolver = p_solver; 130 } 131 132 /// unloads LP. 133 virtual void clear() 134 { 135 thesolver = 0; 136 } 137 138 /// returns loaded SPxSolverBase object. 139 virtual SPxSolverBase<R>* solver() const 140 { 141 return thesolver; 142 } 143 144 /// sets pricing tolerance. 145 /** Inequality violations are accepted, if their size is less than \p tol. 146 */ 147 virtual void setPricingTolerance(R tol) 148 { 149 assert(tol >= 0.0); 150 151 thetolerance = tol; 152 } 153 /// returns the pricing tolerance 154 virtual R pricingTolerance() const 155 { 156 return thetolerance; 157 } 158 159 160 /// set the _tolerances member variable 161 virtual void setTolerances(std::shared_ptr<Tolerances> newTolerances) 162 { 163 this->_tolerances = newTolerances; 164 } 165 166 /// sets pricing type. 167 /** Informs pricer about (a change of) the loaded SoPlex's Type. In 168 the sequel, only the corresponding select methods may be called. 169 */ 170 virtual void setType(typename SPxSolverBase<R>::Type) 171 { 172 this->thesolver->weights.reDim(0); 173 this->thesolver->coWeights.reDim(0); 174 this->thesolver->weightsAreSetup = false; 175 } 176 177 /// sets basis representation. 178 /** Informs pricer about (a change of) the loaded SoPlex's 179 Representation. 180 */ 181 virtual void setRep(typename SPxSolverBase<R>::Representation) 182 {} 183 ///@} 184 185 //------------------------------------- 186 /**@name Pivoting */ 187 ///@{ 188 /// returns selected index to leave basis. 189 /** Selects the index of a vector to leave the basis. The selected index 190 i, say, must be in the range 0 <= i < solver()->dim() and its 191 tested value must fullfill solver()->test()[i] < -#tolerance(). 192 */ 193 virtual int selectLeave() = 0; 194 195 /// performs leaving pivot. 196 /** Method #left4() is called after each simplex iteration in LEAVE 197 mode. It informs the SPxPricer that the \p n 'th variable has left 198 the basis for \p id to come in at this position. When being called, 199 all vectors of SoPlex involved in such an entering update are 200 setup correctly and may be accessed via the corresponding methods 201 (\ref SPxSolverBase<R>::fVec() "fVec()", \ref SPxSolverBase<R>::pVec() "pVec()", 202 etc.). In general, argument \p n will be the one returned by the 203 SPxPricer at the previous call to #selectLeave(). However, one can not 204 rely on this. 205 */ 206 virtual void left4(int /*n*/, SPxId /*id*/) {} 207 208 /// selects Id to enter basis. 209 /** Selects the SPxId of a vector to enter the basis. The selected 210 id, must not represent a basic index (i.e. solver()->isBasic(id) must 211 be false). However, the corresponding test value needs not to be less 212 than -#tolerance(). If not, SoPlex will discard the pivot. 213 214 Note: 215 When method #selectEnter() is called by the loaded SoPlex 216 object, all values from \ref SPxSolverBase<R>::coTest() "coTest()" are 217 up to date. However, whether the elements of 218 \ref SPxSolverBase<R>::test() "test()" are up to date depends on the 219 SPxSolverBase<R>::Pricing type. 220 */ 221 virtual SPxId selectEnter() = 0; 222 223 /// performs entering pivot. 224 /** Method #entered4() is called after each simplex iteration in ENTER 225 mode. It informs the SPxPricer that variable \p id has entered 226 at the \p n 'th position. When being called, all vectors of SoPlex 227 involved in such an entering update are setup correctly and may be 228 accessed via the corresponding methods 229 (\ref SPxSolverBase<R>::fVec() "fVec()", \ref SPxSolverBase<R>::pVec() "pVec()", 230 etc.). In general, argument \p id will be the one returned by the 231 SPxPricer at the previous call to #selectEnter(). However, one can not 232 rely on this. 233 */ 234 virtual void entered4(SPxId /*id*/, int /*n*/) 235 {} 236 ///@} 237 238 239 //------------------------------------- 240 /**@name Extension */ 241 ///@{ 242 /// \p n vectors have been added to loaded LP. 243 virtual void addedVecs(int /*n*/) 244 {} 245 /// \p n covectors have been added to loaded LP. 246 virtual void addedCoVecs(int /*n*/) 247 {} 248 ///@} 249 250 //------------------------------------- 251 /**@name Shrinking */ 252 ///@{ 253 /// vector \p i was removed from loaded LP. 254 virtual void removedVec(int /*i*/) 255 {} 256 /// vectors given by \p perm have been removed from loaded LP. 257 virtual void removedVecs(const int* /*perm*/) 258 {} 259 /// covector \p i was removed from loaded LP. 260 virtual void removedCoVec(int /*i*/) 261 {} 262 /// covectors given by \p perm have been removed from loaded LP. 263 virtual void removedCoVecs(const int* /*perm*/) 264 {} 265 ///@} 266 267 //------------------------------------- 268 /**@name Debugging */ 269 ///@{ 270 virtual bool isConsistent() const 271 { 272 #ifdef ENABLE_CONSISTENCY_CHECKS 273 return thesolver != 0; 274 #else 275 return true; 276 #endif 277 } 278 ///@} 279 280 //------------------------------------- 281 /**@name Constructors / Destructors */ 282 ///@{ 283 /// constructor 284 explicit SPxPricer(const char* p_name) 285 : m_name(p_name) 286 , thesolver(0) 287 , thetolerance(0.0) 288 {} 289 290 /// copy constructor 291 SPxPricer(const SPxPricer& old) 292 : m_name(old.m_name) 293 , thesolver(old.thesolver) 294 , thetolerance(old.thetolerance) 295 {} 296 297 /// assignment operator 298 SPxPricer& operator=(const SPxPricer& rhs) 299 { 300 if(this != &rhs) 301 { 302 m_name = rhs.m_name; 303 thesolver = rhs.thesolver; 304 thetolerance = rhs.thetolerance; 305 assert(isConsistent()); 306 } 307 308 return *this; 309 } 310 311 /// destructor. 312 virtual ~SPxPricer() 313 { 314 m_name = 0; 315 thesolver = 0; 316 } 317 318 /// clone function for polymorphism 319 virtual SPxPricer* clone() const = 0; 320 ///@} 321 322 }; 323 324 325 } // namespace soplex 326 #endif // _SPXPRICER_H_ 327