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 spxsimplifier.h 26 * @brief LP simplification base class. 27 */ 28 #ifndef _SPXSIMPLIFIER_H_ 29 #define _SPXSIMPLIFIER_H_ 30 31 #include <assert.h> 32 33 #include "soplex/spxdefines.h" 34 #include "soplex/timerfactory.h" 35 #include "soplex/spxlp.h" 36 #include "soplex/spxsolver.h" 37 38 namespace soplex 39 { 40 /**@brief LP simplification abstract base class. 41 @ingroup Algo 42 43 Instances of classes derived from SPxSimplifier may be loaded to SoPlex in 44 order to simplify LPs before solving them. SoPlex will call #simplify() 45 on itself. Generally any SPxLP can be given to 46 a SPxSimplifier for #simplify()%ing it. The simplification cannot be undone, 47 but given an primal/dual solution for the simplified SPxLP, the simplifier 48 can reconstruct the primal/dual solution of the unsimplified LP. 49 */ 50 template <class R> 51 class SPxSimplifier 52 { 53 protected: 54 //------------------------------------- 55 /**@name Protected Data */ 56 ///@{ 57 /// name of the simplifier 58 const char* m_name; 59 /// user time used for simplification 60 Timer* m_timeUsed; 61 Timer::TYPE m_timerType; 62 /// number of removed rows 63 int m_remRows; 64 /// number of removed columns 65 int m_remCols; 66 /// number of removed nonzero coefficients 67 int m_remNzos; 68 /// number of changed bounds 69 int m_chgBnds; 70 /// number of change right-hand sides 71 int m_chgLRhs; 72 /// number of kept bounds 73 int m_keptBnds; 74 /// number of kept left- and right-hand sides 75 int m_keptLRhs; 76 /// objective offset 77 R m_objoffset; 78 /// minimal reduction (sum of removed rows/cols) to continue simplification 79 R m_minReduction; 80 /// message handler 81 SPxOut* spxout; 82 ///< tolerances used by the solver 83 std::shared_ptr<Tolerances> _tolerances; 84 ///@} 85 86 public: 87 88 //------------------------------------- 89 /**@name Types */ 90 ///@{ 91 /// Result of the simplification. 92 enum Result 93 { 94 OKAY = 0, ///< simplification could be done 95 INFEASIBLE = 1, ///< primal infeasibility was detected 96 DUAL_INFEASIBLE = 2, ///< dual infeasibility was detected 97 UNBOUNDED = 3, ///< primal unboundedness was detected 98 VANISHED = 4 ///< the problem was so much simplified that it vanished 99 }; 100 ///@} 101 102 //------------------------------------- 103 /**@name Types */ 104 ///@{ 105 /// constructor 106 explicit SPxSimplifier(const char* p_name, Timer::TYPE ttype = Timer::USER_TIME) 107 : m_name(p_name) 108 , m_timeUsed(0) 109 , m_timerType(ttype) 110 , m_remRows(0) 111 , m_remCols(0) 112 , m_remNzos(0) 113 , m_chgBnds(0) 114 , m_chgLRhs(0) 115 , m_keptBnds(0) 116 , m_keptLRhs(0) 117 , m_objoffset(0.0) 118 , m_minReduction(1e-4) 119 , spxout(0) 120 { 121 assert(isConsistent()); 122 123 m_timeUsed = TimerFactory::createTimer(ttype); 124 } 125 /// copy constructor 126 SPxSimplifier(const SPxSimplifier& old) 127 : m_name(old.m_name) 128 , m_timerType(old.m_timerType) 129 , m_remRows(old.m_remRows) 130 , m_remCols(old.m_remCols) 131 , m_remNzos(old.m_remNzos) 132 , m_chgBnds(old.m_chgBnds) 133 , m_chgLRhs(old.m_chgLRhs) 134 , m_keptBnds(old.m_keptBnds) 135 , m_keptLRhs(old.m_keptLRhs) 136 , m_objoffset(old.m_objoffset) 137 , m_minReduction(old.m_minReduction) 138 , spxout(old.spxout) 139 { 140 m_timeUsed = TimerFactory::createTimer(m_timerType); 141 assert(isConsistent()); 142 } 143 /// assignment operator 144 SPxSimplifier& operator=(const SPxSimplifier& rhs) 145 { 146 if(this != &rhs) 147 { 148 m_name = rhs.m_name; 149 *m_timeUsed = *(rhs.m_timeUsed); 150 m_timerType = rhs.m_timerType; 151 m_remRows = rhs.m_remRows; 152 m_remCols = rhs.m_remCols; 153 m_remNzos = rhs.m_remNzos; 154 m_chgBnds = rhs.m_chgBnds; 155 m_chgLRhs = rhs.m_chgLRhs; 156 m_keptBnds = rhs.m_keptBnds; 157 m_keptLRhs = rhs.m_keptLRhs; 158 m_objoffset = rhs.m_objoffset; 159 m_minReduction = rhs.m_minReduction; 160 spxout = rhs.spxout; 161 162 assert(isConsistent()); 163 } 164 165 return *this; 166 } 167 /// destructor. 168 virtual ~SPxSimplifier() 169 { 170 m_name = nullptr; 171 m_timeUsed->~Timer(); 172 spx_free(m_timeUsed); 173 } 174 /// clone function for polymorphism 175 virtual SPxSimplifier* clone() const = 0; 176 ///@} 177 178 //------------------------------------- 179 /**@name Access / modfication */ 180 ///@{ 181 /// get name of simplifier. 182 virtual const char* getName() const 183 { 184 return m_name; 185 } 186 virtual R timeUsed() const 187 { 188 return m_timeUsed->time(); 189 } 190 ///@} 191 192 //------------------------------------- 193 /**@name Simplifying / unsimplifying */ 194 ///@{ 195 /// simplify SPxLP \p lp 196 virtual Result simplify(SPxLPBase<R>& lp, Real remainingTime, 197 bool keepbounds = false, uint32_t seed = 0) = 0; 198 /// reconstructs an optimal solution for the unsimplified LP. 199 virtual void unsimplify(const VectorBase<R>&, const VectorBase<R>&, const VectorBase<R>&, 200 const VectorBase<R>&, 201 const typename SPxSolverBase<R>::VarStatus[], const typename SPxSolverBase<R>::VarStatus[], 202 bool isOptimal = true) = 0; 203 /// returns result status of the simplification 204 virtual Result result() const = 0; 205 /// specifies whether an optimal solution has already been unsimplified. 206 virtual bool isUnsimplified() const 207 { 208 return false; 209 } 210 /// returns a reference to the unsimplified primal solution. 211 virtual const VectorBase<R>& unsimplifiedPrimal() = 0; 212 213 /// returns a reference to the unsimplified dual solution. 214 virtual const VectorBase<R>& unsimplifiedDual() = 0; 215 216 /// returns a reference to the unsimplified slack values. 217 virtual const VectorBase<R>& unsimplifiedSlacks() = 0; 218 219 /// returns a reference to the unsimplified reduced costs. 220 virtual const VectorBase<R>& unsimplifiedRedCost() = 0; 221 222 /// gets basis status for a single row. 223 virtual typename SPxSolverBase<R>::VarStatus getBasisRowStatus(int) const = 0; 224 225 /// gets basis status for a single column. 226 virtual typename SPxSolverBase<R>::VarStatus getBasisColStatus(int) const = 0; 227 228 /// get optimal basis. 229 virtual void getBasis(typename SPxSolverBase<R>::VarStatus[], 230 typename SPxSolverBase<R>::VarStatus[], const int rowsSize = -1, const int colsSize = -1) const = 0; 231 232 /// get objective offset. 233 virtual R getObjoffset() const 234 { 235 return m_objoffset; 236 } 237 238 /// add objective offset. 239 virtual void addObjoffset(const R val) 240 { 241 m_objoffset += val; 242 } 243 244 /// set minimal reduction threshold to continue simplification 245 virtual void setMinReduction(const R minRed) 246 { 247 m_minReduction = minRed; 248 } 249 250 ///@} 251 252 //------------------------------------- 253 /**@name Consistency check */ 254 ///@{ 255 /// consistency check 256 virtual bool isConsistent() const 257 { 258 return true; 259 } 260 ///@} 261 262 void setOutstream(SPxOut& newOutstream) 263 { 264 spxout = &newOutstream; 265 } 266 267 /// set the _tolerances member variable 268 virtual void setTolerances(std::shared_ptr<Tolerances> newTolerances) 269 { 270 this->_tolerances = newTolerances; 271 } 272 /// get the _tolerances member variable 273 const std::shared_ptr<Tolerances> tolerances() const 274 { 275 return _tolerances; 276 } 277 278 }; 279 280 /// Pretty-printing of simplifier status 281 template <class R> 282 std::ostream& operator<<(std::ostream& os, const typename SPxSimplifier<R>::Result& status); 283 284 } // namespace soplex 285 #endif // _SPXSIMPLIFIER_H_ 286