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 spxsteeppr.h 27 * @brief Steepest edge pricer. 28 */ 29 #ifndef _SPXSTEEPPR_H_ 30 #define _SPXSTEEPPR_H_ 31 32 33 #include <assert.h> 34 35 #include "soplex/spxdefines.h" 36 #include "soplex/spxpricer.h" 37 #include "soplex/random.h" 38 39 namespace soplex 40 { 41 42 /**@brief Steepest edge pricer. 43 @ingroup Algo 44 45 Class SPxSteepPR implements a steepest edge pricer to be used with 46 SoPlex. 47 48 See SPxPricer for a class documentation. 49 */ 50 template <class R> 51 class SPxSteepPR : public SPxPricer<R> 52 { 53 public: 54 55 //------------------------------------- 56 /**@name Types */ 57 ///@{ 58 /// How to setup the direction multipliers. 59 /** Possible settings are #EXACT for starting with exactly computed 60 values, or #DEFAULT for starting with multipliers set to 1. The 61 latter is the default. 62 */ 63 enum Setup 64 { 65 EXACT, ///< starting with exactly computed values 66 DEFAULT ///< starting with multipliers set to 1 67 }; 68 ///@} 69 /// setup steepest edge weights 70 void setupWeights(typename SPxSolverBase<R>::Type type); 71 72 private: 73 74 //------------------------------------- 75 /**@name Data */ 76 ///@{ 77 /// working vector 78 SSVectorBase<R> workVec; 79 /// working vector 80 SSVectorBase<R> workRhs; 81 /// temporary array of precomputed pricing values 82 Array<typename SPxPricer<R>::IdxElement> prices; 83 /// temporary array of precomputed pricing values 84 Array<typename SPxPricer<R>::IdxElement> pricesCo; 85 /// array of best pricing candidates 86 DIdxSet bestPrices; 87 /// array of best pricing candidates 88 DIdxSet bestPricesCo; 89 /// 90 R pi_p; 91 /// setup type. 92 Setup setup; 93 /// has a refinement step already been tried? 94 bool refined; 95 ///@} 96 97 //------------------------------------- 98 /// prepare data structures for hyper sparse pricing 99 int buildBestPriceVectorLeave(R feastol); 100 /// implementation of full pricing 101 int selectLeaveX(R tol); 102 /// implementation of sparse pricing in the leaving Simplex 103 int selectLeaveSparse(R tol); 104 /// implementation of hyper sparse pricing in the leaving Simplex 105 int selectLeaveHyper(R tol); 106 /// build up vector of pricing values for later use 107 SPxId buildBestPriceVectorEnterDim(R& best, R feastol); 108 SPxId buildBestPriceVectorEnterCoDim(R& best, R feastol); 109 /// choose the best entering index among columns and rows but prefer sparsity 110 SPxId selectEnterX(R tol); 111 /// implementation of sparse pricing for the entering Simplex (slack variables) 112 SPxId selectEnterSparseDim(R& best, R tol); 113 /// implementation of sparse pricing for the entering Simplex 114 SPxId selectEnterSparseCoDim(R& best, R tol); 115 /// implementation of selectEnter() in dense case (slack variables) 116 SPxId selectEnterDenseDim(R& best, R tol); 117 /// implementation of selectEnter() in dense case 118 SPxId selectEnterDenseCoDim(R& best, R tol); 119 /// implementation of hyper sparse pricing in the entering Simplex 120 SPxId selectEnterHyperDim(R& best, R feastol); 121 /// implementation of hyper sparse pricing in the entering Simplex 122 SPxId selectEnterHyperCoDim(R& best, R feastol); 123 124 public: 125 126 //------------------------------------- 127 /**@name Construction / destruction */ 128 ///@{ 129 /// 130 SPxSteepPR(const char* name = "Steep", Setup mode = DEFAULT) 131 : SPxPricer<R>(name) 132 , workVec(0, 0) 133 , workRhs(0, 0) 134 , pi_p(1.0) 135 , setup(mode) 136 , refined(false) 137 { 138 assert(isConsistent()); 139 } 140 /// copy constructor 141 SPxSteepPR(const SPxSteepPR& old) 142 : SPxPricer<R>(old) 143 , workVec(old.workVec) 144 , workRhs(old.workRhs) 145 , pi_p(old.pi_p) 146 , setup(old.setup) 147 , refined(old.refined) 148 { 149 assert(isConsistent()); 150 } 151 /// assignment operator 152 SPxSteepPR& operator=(const SPxSteepPR& rhs) 153 { 154 if(this != &rhs) 155 { 156 SPxPricer<R>::operator=(rhs); 157 workVec = rhs.workVec; 158 workRhs = rhs.workRhs; 159 pi_p = rhs.pi_p; 160 setup = rhs.setup; 161 refined = rhs.refined; 162 163 assert(isConsistent()); 164 } 165 166 return *this; 167 } 168 /// destructor 169 virtual ~SPxSteepPR() 170 {} 171 /// clone function for polymorphism 172 inline virtual SPxPricer<R>* clone() const 173 { 174 return new SPxSteepPR(*this); 175 } 176 ///@} 177 178 //------------------------------------- 179 /**@name Access / modification */ 180 ///@{ 181 /// sets the solver 182 virtual void load(SPxSolverBase<R>* base); 183 /// clear solver and preferences 184 virtual void clear(); 185 /// set entering/leaving algorithm 186 virtual void setType(typename SPxSolverBase<R>::Type); 187 /// set row/column representation 188 virtual void setRep(typename SPxSolverBase<R>::Representation rep); 189 /// 190 virtual int selectLeave(); 191 /// 192 virtual void left4(int n, SPxId id); 193 /// 194 virtual SPxId selectEnter(); 195 /// 196 virtual void entered4(SPxId id, int n); 197 /// \p n vectors have been added to loaded LP. 198 virtual void addedVecs(int n); 199 /// \p n covectors have been added to loaded LP. 200 virtual void addedCoVecs(int n); 201 /// \p the i'th vector has been removed from the loaded LP. 202 virtual void removedVec(int i); 203 /// \p the i'th covector has been removed from the loaded LP. 204 virtual void removedCoVec(int i); 205 /// \p n vectors have been removed from loaded LP. 206 virtual void removedVecs(const int perm[]); 207 /// \p n covectors have been removed from loaded LP. 208 virtual void removedCoVecs(const int perm[]); 209 ///@} 210 211 //------------------------------------- 212 /**@name Consistency check */ 213 ///@{ 214 /// 215 virtual bool isConsistent() const; 216 ///@} 217 }; 218 219 } // namespace soplex 220 #endif // _SPXSTEEPPR_H_ 221