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 spxdevexpr.h 26 * @brief Devex pricer. 27 */ 28 #ifndef _SPXDEVEXPR_H_ 29 #define _SPXDEVEXPR_H_ 30 31 #include <assert.h> 32 33 #include "soplex/spxdefines.h" 34 #include "soplex/spxpricer.h" 35 36 namespace soplex 37 { 38 39 /**@brief Devex pricer. 40 @ingroup Algo 41 42 The Devex Pricer for SoPlex implements an approximate steepest edge pricing, 43 that does without solving an extra linear system and computing the scalar 44 products. 45 46 See SPxPricer for a class documentation. 47 48 @todo There seem to be problems with this pricer especially on the 49 greenbe[ab] problems with the entering algorithm 50 (row representation?). 51 */ 52 template <class R> 53 class SPxDevexPR : public SPxPricer<R> 54 { 55 private: 56 57 //------------------------------------- 58 /**@name Data */ 59 ///@{ 60 R last; ///< penalty, selected at last iteration. 61 Array<typename SPxPricer<R>::IdxElement> 62 prices; ///< temporary array of precomputed pricing values 63 Array<typename SPxPricer<R>::IdxElement> 64 pricesCo; ///< temporary array of precomputed pricing values 65 DIdxSet bestPrices; ///< set of best pricing candidates 66 DIdxSet bestPricesCo; ///< set of best pricing candidates 67 bool refined; ///< has a refinement step already been tried? 68 ///@} 69 70 //------------------------------------- 71 /**@name Private helpers */ 72 ///@{ 73 /// set entering/leaving algorithm 74 void setupWeights(typename SPxSolverBase<R>::Type); 75 /// build up vector of pricing values for later use 76 int buildBestPriceVectorLeave(R feastol); 77 /// internal implementation of SPxPricer::selectLeave() 78 int selectLeaveX(R feastol, int start = 0, int incr = 1); 79 /// implementation of sparse pricing in the leaving Simplex 80 int selectLeaveSparse(R feastol); 81 /// implementation of hyper sparse pricing in the leaving Simplex 82 int selectLeaveHyper(R feastol); 83 /// build up vector of pricing values for later use 84 SPxId buildBestPriceVectorEnterDim(R& best, R feastol); 85 SPxId buildBestPriceVectorEnterCoDim(R& best, R feastol); 86 /// choose the best entering index among columns and rows but prefer sparsity 87 SPxId selectEnterX(R tol); 88 /// implementation of sparse pricing in the entering Simplex (slack variables) 89 SPxId selectEnterSparseDim(R& best, R feastol); 90 /// implementation of sparse pricing in the entering Simplex 91 SPxId selectEnterSparseCoDim(R& best, R feastol); 92 /// SPxPricer::selectEnter() in dense case (slack variabels) 93 SPxId selectEnterDenseDim(R& best, R feastol, int start = 0, int incr = 1); 94 /// SPxPricer::selectEnter() in dense case 95 SPxId selectEnterDenseCoDim(R& best, R feastol, int start = 0, int incr = 1); 96 /// implementation of hyper sparse pricing in the entering Simplex 97 SPxId selectEnterHyperDim(R& best, R feastol); 98 /// implementation of hyper sparse pricing in the entering Simplex 99 SPxId selectEnterHyperCoDim(R& best, R feastol); 100 ///@} 101 102 public: 103 104 //------------------------------------- 105 /**@name Construction / destruction */ 106 ///@{ 107 /// default constructor 108 SPxDevexPR() 109 : SPxPricer<R>("Devex") 110 , last(0) 111 , refined(false) 112 {} 113 /// copy constructor 114 SPxDevexPR(const SPxDevexPR& old) 115 : SPxPricer<R>(old) 116 , last(old.last) 117 , refined(false) 118 {} 119 /// assignment operator 120 SPxDevexPR& operator=(const SPxDevexPR& rhs) 121 { 122 if(this != &rhs) 123 { 124 SPxPricer<R>::operator=(rhs); 125 last = rhs.last; 126 } 127 128 return *this; 129 } 130 /// destructor 131 virtual ~SPxDevexPR() 132 {} 133 /// clone function for polymorphism 134 inline virtual SPxPricer<R>* clone() const 135 { 136 return new SPxDevexPR(*this); 137 } 138 ///@} 139 140 //------------------------------------- 141 /**@name Access / modification */ 142 ///@{ 143 /// sets the solver 144 virtual void load(SPxSolverBase<R>* base); 145 /// set entering/leaving algorithm 146 virtual void setType(typename SPxSolverBase<R>::Type); 147 /// set row/column representation 148 virtual void setRep(typename SPxSolverBase<R>::Representation); 149 /// 150 virtual int selectLeave(); 151 /// 152 virtual SPxId selectEnter(); 153 /// 154 virtual void left4(int n, SPxId id); 155 /// 156 virtual void entered4(SPxId id, int n); 157 /// \p n vectors have been added to loaded LP. 158 virtual void addedVecs(int n); 159 /// \p n covectors have been added to loaded LP. 160 virtual void addedCoVecs(int n); 161 ///@} 162 163 //------------------------------------- 164 /**@name Consistency check */ 165 ///@{ 166 /// consistency check 167 virtual bool isConsistent() const; 168 ///@} 169 }; 170 171 } // namespace soplex 172 173 #include "spxdevexpr.hpp" 174 175 #endif // _SPXDEVEXPR_H_ 176