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 spxscaler.h 26 * @brief LP scaling base class. 27 */ 28 #ifndef _SPXSCALER_H_ 29 #define _SPXSCALER_H_ 30 31 #include <assert.h> 32 33 #include "soplex/spxdefines.h" 34 #include "soplex/dataarray.h" 35 #include "soplex/vector.h" 36 #include "soplex/svector.h" 37 #include "soplex/svset.h" 38 #include "soplex/dsvector.h" 39 #include "soplex/dvector.h" 40 #include <vector> 41 42 namespace soplex 43 { 44 45 template < class R > 46 class SPxLPBase; 47 /**@brief LP scaler abstract base class. 48 @ingroup Algo 49 50 Instances of classes derived from SPxScaler may be loaded to SoPlex in 51 order to scale LPs before solving them. SoPlex will load() itself to 52 the SPxScaler and then call #scale(). Generally any SPxLP can be 53 loaded to a SPxScaler for #scale()%ing it. The scaling can 54 be undone by calling unscale(). 55 56 Mathematically, the scaling of a constraint matrix A can be written 57 as \f$ A' = R A C \f$, with \f$ R \f$ and \f$ C \f$, being diagonal matrices 58 corresponding to the row and column scale factors, respectively. Besides the 59 constraints matrix, also the upper and lower bounds of both columns and rows 60 need to be scaled. 61 62 Note that by default scaling is performed both before and after presolving and 63 the former scaling factors are retained during branch-and-bound (persistent scaling). 64 However, while within SoPlex the scaled problem is used, data accessed through 65 the soplex.cpp interface is provided w.r.t. the original problem (i.e., in unscaled form). 66 For instance, consider a scaled constraints matrix A' that is extended by artificial slack 67 variables to the matrix (A',I). 68 A basis \f$ B' = [(A',I)P]_{[1:m][1:m] }\f$ (with P being a permutation matrix) 69 for the scaled problem corresponds to the basis 70 \f$ B = R^{-1} [(A',I)P]_{[1:m][1:m]} [P^{T} \tilde{C}^{-1} P]_{[1:m][1:m] } \f$. In 71 this equation, \f$ \tilde{C} \f$ is of the form 72 73 \f[ 74 \begin{array}{cc} 75 C & 0 \\ 76 O & R^{-1} 77 \end{array} 78 \f] 79 80 Note that in SoPlex only scaling factors \f$ 2^k, k \in \mathbb{Z} \f$ are used. 81 82 83 */ 84 85 template <class R> 86 class SPxScaler 87 { 88 protected: 89 90 //------------------------------------- 91 /**@name Data */ 92 ///@{ 93 const char* m_name; ///< Name of the scaler 94 DataArray < int >* m_activeColscaleExp; ///< pointer to currently active column scaling factors 95 DataArray < int >* m_activeRowscaleExp; ///< pointer to currently active row scaling factors 96 bool m_colFirst; ///< do column scaling first 97 bool m_doBoth; ///< do columns and rows 98 SPxOut* spxout; ///< message handler 99 std::shared_ptr<Tolerances> _tolerances; ///< the tolerances 100 ///@} 101 102 //------------------------------------- 103 /**@name Protected helpers */ 104 ///@{ 105 106 /// clear and setup scaling arrays in the LP 107 virtual void setup(SPxLPBase<R>& lp); 108 ///@} 109 110 public: 111 112 /// compute a single scaling vector , e.g. of a newly added row 113 virtual int computeScaleExp(const SVectorBase<R>& vec, const DataArray<int>& oldScaleExp) const; 114 115 // The following is now redundant because of the above function. 116 // virtual int computeScaleExp(const SVectorBase<Rational>& vec, const DataArray<int>& oldScaleExp) const; 117 118 /// applies m_colscale and m_rowscale to the \p lp. 119 virtual void applyScaling(SPxLPBase<R>& lp); 120 121 122 template <class T> 123 friend std::ostream& operator<<(std::ostream& s, const SPxScaler<T>& sc); 124 125 //------------------------------------- 126 /**@name Construction / destruction */ 127 ///@{ 128 /// constructor 129 explicit SPxScaler(const char* name, bool colFirst = false, bool doBoth = true, 130 SPxOut* spxout = NULL); 131 /// copy constructor 132 SPxScaler(const SPxScaler&); 133 /// assignment operator 134 SPxScaler& operator=(const SPxScaler&); 135 /// destructor. 136 virtual ~SPxScaler(); 137 /// clone function for polymorphism 138 virtual SPxScaler* clone() const = 0; 139 ///@} 140 141 //------------------------------------- 142 /**@name Access / modification */ 143 ///@{ 144 /// get name of scaler 145 virtual const char* getName() const; 146 /// set scaling order 147 virtual void setOrder(bool colFirst); 148 /// set wether column and row scaling should be performed 149 virtual void setBoth(bool both); 150 /// set message handler 151 virtual void setOutstream(SPxOut& newOutstream) 152 { 153 spxout = &newOutstream; 154 } 155 /// set R parameter 156 virtual void setRealParam(R param, const char* name = "realparam"); 157 /// set int parameter 158 virtual void setIntParam(int param, const char* name = "intparam"); 159 /// set tolerances 160 virtual void setTolerances(std::shared_ptr<Tolerances>& tolerances) 161 { 162 _tolerances = tolerances; 163 } 164 /// get the _tolerances member variable 165 const std::shared_ptr<Tolerances> tolerances() const 166 { 167 return _tolerances; 168 } 169 ///@} 170 171 //------------------------------------- 172 /**@name Scaling */ 173 ///@{ 174 /// scale SPxLP. 175 virtual void scale(SPxLPBase<R>& lp, bool persistent = true) = 0; 176 /// unscale SPxLP 177 virtual void unscale(SPxLPBase<R>& lp); 178 /// returns scaling factor for column \p i 179 virtual int getColScaleExp(int i) const; 180 /// returns scaling factor for row \p i 181 virtual int getRowScaleExp(int i) const; 182 /// gets unscaled column \p i 183 virtual void getColUnscaled(const SPxLPBase<R>& lp, int i, DSVectorBase<R>& vec) const; 184 /// returns maximum absolute value of unscaled column \p i 185 virtual R getColMaxAbsUnscaled(const SPxLPBase<R>& lp, int i) const; 186 /// returns minumum absolute value of unscaled column \p i 187 virtual R getColMinAbsUnscaled(const SPxLPBase<R>& lp, int i) const; 188 /// returns unscaled upper bound \p i 189 virtual R upperUnscaled(const SPxLPBase<R>& lp, int i) const; 190 /// returns unscaled upper bound vector of \p lp 191 virtual void getUpperUnscaled(const SPxLPBase<R>& lp, VectorBase<R>& vec) const; 192 /// returns unscaled lower bound \p i 193 virtual R lowerUnscaled(const SPxLPBase<R>& lp, int i) const; 194 /// gets unscaled lower bound vector 195 virtual void getLowerUnscaled(const SPxLPBase<R>& lp, VectorBase<R>& vec) const; 196 /// returns unscaled objective function coefficient of \p i 197 virtual R maxObjUnscaled(const SPxLPBase<R>& lp, int i) const; 198 /// gets unscaled objective function 199 virtual void getMaxObjUnscaled(const SPxLPBase<R>& lp, VectorBase<R>& vec) const; 200 /// returns unscaled row \p i 201 virtual void getRowUnscaled(const SPxLPBase<R>& lp, int i, DSVectorBase<R>& vec) const; 202 /// returns maximum absolute value of unscaled row \p i 203 virtual R getRowMaxAbsUnscaled(const SPxLPBase<R>& lp, int i) const; 204 /// returns minimum absolute value of unscaled row \p i 205 virtual R getRowMinAbsUnscaled(const SPxLPBase<R>& lp, int i) const; 206 /// returns unscaled right hand side \p i 207 virtual R rhsUnscaled(const SPxLPBase<R>& lp, int i) const; 208 /// gets unscaled right hand side vector 209 virtual void getRhsUnscaled(const SPxLPBase<R>& lp, VectorBase<R>& vec) const; 210 /// returns unscaled left hand side \p i of \p lp 211 virtual R lhsUnscaled(const SPxLPBase<R>& lp, int i) const; 212 /// returns unscaled left hand side vector of \p lp 213 virtual void getLhsUnscaled(const SPxLPBase<R>& lp, VectorBase<R>& vec) const; 214 /// returns unscaled coefficient of \p lp 215 virtual R getCoefUnscaled(const SPxLPBase<R>& lp, int row, int col) const; 216 /// unscale dense primal solution vector given in \p x. 217 virtual void unscalePrimal(const SPxLPBase<R>& lp, VectorBase<R>& x) const; 218 /// unscale dense slack vector given in \p s. 219 virtual void unscaleSlacks(const SPxLPBase<R>& lp, VectorBase<R>& s) const; 220 /// unscale dense dual solution vector given in \p pi. 221 virtual void unscaleDual(const SPxLPBase<R>& lp, VectorBase<R>& pi) const; 222 /// unscale dense reduced cost vector given in \p r. 223 virtual void unscaleRedCost(const SPxLPBase<R>& lp, VectorBase<R>& r) const; 224 /// unscale primal ray given in \p ray. 225 virtual void unscalePrimalray(const SPxLPBase<R>& lp, VectorBase<R>& ray) const; 226 /// unscale dual ray given in \p ray. 227 virtual void unscaleDualray(const SPxLPBase<R>& lp, VectorBase<R>& ray) const; 228 /// apply scaling to objective function vector \p origObj. 229 virtual void scaleObj(const SPxLPBase<R>& lp, VectorBase<R>& origObj) const; 230 /// returns scaled objective function coefficient \p origObj. 231 virtual R scaleObj(const SPxLPBase<R>& lp, int i, R origObj) const; 232 /// returns scaled LP element in \p row and \p col. 233 virtual R scaleElement(const SPxLPBase<R>& lp, int row, int col, R val) const; 234 /// returns scaled lower bound of column \p col. 235 virtual R scaleLower(const SPxLPBase<R>& lp, int col, R lower) const; 236 /// returns scaled upper bound of column \p col. 237 virtual R scaleUpper(const SPxLPBase<R>& lp, int col, R upper) const; 238 /// returns scaled left hand side of row \p row. 239 virtual R scaleLhs(const SPxLPBase<R>& lp, int row, R lhs) const; 240 /// returns scaled right hand side of row \p row. 241 virtual R scaleRhs(const SPxLPBase<R>& lp, int row, R rhs) const; 242 /// absolute smallest column scaling factor 243 virtual R minAbsColscale() const; 244 /// absolute biggest column scaling factor 245 virtual R maxAbsColscale() const; 246 /// absolute smallest row scaling factor 247 virtual R minAbsRowscale() const; 248 /// absolute biggest row scaling factor 249 virtual R maxAbsRowscale() const; 250 /// maximum ratio between absolute biggest and smallest element in any column. 251 virtual R maxColRatio(const SPxLPBase<R>& lp) const; 252 /// maximum ratio between absolute biggest and smallest element in any row. 253 virtual R maxRowRatio(const SPxLPBase<R>& lp) const; 254 /// round vector entries to power of 2 255 void computeExpVec(const std::vector<R>& vec, DataArray<int>& vecExp); 256 ///@} 257 258 //------------------------------------- 259 /**@name Debugging */ 260 ///@{ 261 /// consistency check 262 virtual bool isConsistent() const; 263 ///@} 264 }; 265 } // namespace soplex 266 267 // General templated definitions 268 #include "spxscaler.hpp" 269 270 #endif // _SPXSCALER_H_ 271