Scippy

SoPlex

Sequential object-oriented simPlex

spxscaler.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the class library */
4 /* SoPlex --- the Sequential object-oriented simPlex. */
5 /* */
6 /* Copyright (C) 1996-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SoPlex is distributed under the terms of the ZIB Academic Licence. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SoPlex; see the file COPYING. If not email to soplex@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file spxscaler.h
17  * @brief LP scaling base class.
18  */
19 #ifndef _SPXSCALER_H_
20 #define _SPXSCALER_H_
21 
22 #include <assert.h>
23 
24 #include "soplex/spxdefines.h"
25 #include "soplex/dataarray.h"
26 #include "soplex/vector.h"
27 #include "soplex/svector.h"
28 #include "soplex/svset.h"
29 #include "soplex/dsvector.h"
30 #include "soplex/dvector.h"
31 #include <vector>
32 
33 namespace soplex
34 {
35 
36 template < class R >
37 class SPxLPBase;
38 /**@brief LP scaler abstract base class.
39  @ingroup Algo
40 
41  Instances of classes derived from SPxScaler may be loaded to SoPlex in
42  order to scale LPs before solving them. SoPlex will load() itself to
43  the SPxScaler and then call #scale(). Generally any SPxLP can be
44  loaded to a SPxScaler for #scale()%ing it. The scaling can
45  be undone by calling unscale().
46 
47  Mathematically, the scaling of a constraint matrix A can be written
48  as \f$ A' = R A C \f$, with \f$ R \f$ and \f$ C \f$, being diagonal matrices
49  corresponding to the row and column scale factors, respectively. Besides the
50  constraints matrix, also the upper and lower bounds of both columns and rows
51  need to be scaled.
52 
53  Note that by default scaling is performed both before and after presolving and
54  the former scaling factors are retained during branch-and-bound (persistent scaling).
55  However, while within SoPlex the scaled problem is used, data accessed through
56  the soplex.cpp interface is provided w.r.t. the original problem (i.e., in unscaled form).
57  For instance, consider a scaled constraints matrix A' that is extended by artificial slack
58  variables to the matrix (A',I).
59  A basis \f$ B' = [(A',I)P]_{[1:m][1:m] }\f$ (with P being a permutation matrix)
60  for the scaled problem corresponds to the basis
61  \f$ B = R^{-1} [(A',I)P]_{[1:m][1:m]} [P^{T} \tilde{C}^{-1} P]_{[1:m][1:m] } \f$. In
62  this equation, \f$ \tilde{C} \f$ is of the form
63 
64  \f[
65  \begin{array}{cc}
66  C & 0 \\
67  O & R^{-1}
68  \end{array}
69  \f]
70 
71  Note that in SoPlex only scaling factors \f$ 2^k, k \in \mathbb{Z} \f$ are used.
72 
73 
74 */
75 
76 class SPxScaler
77 {
78 protected:
79 
80  //-------------------------------------
81  /**@name Data */
82  //@{
83  const char* m_name; ///< Name of the scaler
84  DataArray < int >* m_activeColscaleExp; ///< pointer to currently active column scaling factors
85  DataArray < int >* m_activeRowscaleExp; ///< pointer to currently active row scaling factors
86  bool m_colFirst; ///< do column scaling first
87  bool m_doBoth; ///< do columns and rows
88  SPxOut* spxout; ///< message handler
89  //@}
90 
91  //-------------------------------------
92  /**@name Protected helpers */
93  //@{
94 
95  /// clear and setup scaling arrays in the LP
96  virtual void setup(SPxLPBase<Real>& lp);
97  //@}
98 
99 public:
100 
101  /// compute a single scaling vector , e.g. of a newly added row
102  virtual int computeScaleExp(const SVector& vec, const DataArray<int>& oldScaleExp) const;
103 
104  virtual int computeScaleExp(const SVectorBase<Rational>& vec,
105  const DataArray<int>& oldScaleExp) const;
106 
107  /// applies m_colscale and m_rowscale to the \p lp.
108  virtual void applyScaling(SPxLPBase<Real>& lp);
109 
110  friend std::ostream& operator<<(std::ostream& s, const SPxScaler& sc);
111 
112  //-------------------------------------
113  /**@name Construction / destruction */
114  //@{
115  /// constructor
116  explicit SPxScaler(const char* name, bool colFirst = false, bool doBoth = true,
117  SPxOut* spxout = NULL);
118  /// copy constructor
119  SPxScaler(const SPxScaler&);
120  /// assignment operator
121  SPxScaler& operator=(const SPxScaler&);
122  /// destructor.
123  virtual ~SPxScaler();
124  /// clone function for polymorphism
125  virtual SPxScaler* clone() const = 0;
126  //@}
127 
128  //-------------------------------------
129  /**@name Access / modification */
130  //@{
131  /// get name of scaler
132  virtual const char* getName() const;
133  /// set scaling order
134  virtual void setOrder(bool colFirst);
135  /// set wether column and row scaling should be performed
136  virtual void setBoth(bool both);
137  /// set message handler
138  virtual void setOutstream(SPxOut& newOutstream)
139  {
140  spxout = &newOutstream;
141  }
142  /// set real parameter
143  virtual void setRealParam(Real param, const char* name = "realparam");
144  /// set int parameter
145  virtual void setIntParam(int param, const char* name = "intparam");
146  //@}
147 
148  //-------------------------------------
149  /**@name Scaling */
150  //@{
151  /// scale SPxLP.
152  virtual void scale(SPxLPBase<Real>& lp, bool persistent = true) = 0;
153  /// unscale SPxLP
154  virtual void unscale(SPxLPBase<Real>& lp);
155  /// returns scaling factor for column \p i
156  virtual int getColScaleExp(int i) const;
157  /// returns scaling factor for row \p i
158  virtual int getRowScaleExp(int i) const;
159  /// gets unscaled column \p i
160  virtual void getColUnscaled(const SPxLPBase<Real>& lp, int i, DSVector& vec) const;
161  /// returns maximum absolute value of unscaled column \p i
162  virtual Real getColMaxAbsUnscaled(const SPxLPBase<Real>& lp, int i) const;
163  /// returns minumum absolute value of unscaled column \p i
164  virtual Real getColMinAbsUnscaled(const SPxLPBase<Real>& lp, int i) const;
165  /// returns unscaled upper bound \p i
166  virtual Real upperUnscaled(const SPxLPBase<Real>& lp, int i) const;
167  /// returns unscaled upper bound vector of \p lp
168  virtual void getUpperUnscaled(const SPxLPBase<Real>& lp, Vector& vec) const;
169  /// returns unscaled lower bound \p i
170  virtual Real lowerUnscaled(const SPxLPBase<Real>& lp, int i) const;
171  /// gets unscaled lower bound vector
172  virtual void getLowerUnscaled(const SPxLPBase<Real>& lp, Vector& vec) const;
173  /// returns unscaled objective function coefficient of \p i
174  virtual Real maxObjUnscaled(const SPxLPBase<Real>& lp, int i) const;
175  /// gets unscaled objective function
176  virtual void getMaxObjUnscaled(const SPxLPBase<Real>& lp, Vector& vec) const;
177  /// returns unscaled row \p i
178  virtual void getRowUnscaled(const SPxLPBase<Real>& lp, int i, DSVector& vec) const;
179  /// returns maximum absolute value of unscaled row \p i
180  virtual Real getRowMaxAbsUnscaled(const SPxLPBase<Real>& lp, int i) const;
181  /// returns minimum absolute value of unscaled row \p i
182  virtual Real getRowMinAbsUnscaled(const SPxLPBase<Real>& lp, int i) const;
183  /// returns unscaled right hand side \p i
184  virtual Real rhsUnscaled(const SPxLPBase<Real>& lp, int i) const;
185  /// gets unscaled right hand side vector
186  virtual void getRhsUnscaled(const SPxLPBase<Real>& lp, Vector& vec) const;
187  /// returns unscaled left hand side \p i of \p lp
188  virtual Real lhsUnscaled(const SPxLPBase<Real>& lp, int i) const;
189  /// returns unscaled left hand side vector of \p lp
190  virtual void getLhsUnscaled(const SPxLPBase<Real>& lp, Vector& vec) const;
191  /// returns unscaled coefficient of \p lp
192  virtual Real getCoefUnscaled(const SPxLPBase<Real>& lp, int row, int col) const;
193  /// unscale dense primal solution vector given in \p x.
194  virtual void unscalePrimal(const SPxLPBase<Real>& lp, Vector& x) const;
195  /// unscale dense slack vector given in \p s.
196  virtual void unscaleSlacks(const SPxLPBase<Real>& lp, Vector& s) const;
197  /// unscale dense dual solution vector given in \p pi.
198  virtual void unscaleDual(const SPxLPBase<Real>& lp, Vector& pi) const;
199  /// unscale dense reduced cost vector given in \p r.
200  virtual void unscaleRedCost(const SPxLPBase<Real>& lp, Vector& r) const;
201  /// unscale primal ray given in \p ray.
202  virtual void unscalePrimalray(const SPxLPBase<Real>& lp, Vector& ray) const;
203  /// unscale dual ray given in \p ray.
204  virtual void unscaleDualray(const SPxLPBase<Real>& lp, Vector& ray) const;
205  /// apply scaling to objective function vector \p origObj.
206  virtual void scaleObj(const SPxLPBase<Real>& lp, VectorReal& origObj) const;
207  /// returns scaled objective function coefficient \p origObj.
208  virtual Real scaleObj(const SPxLPBase<Real>& lp, int i, Real origObj) const;
209  /// returns scaled LP element in \p row and \p col.
210  virtual Real scaleElement(const SPxLPBase<Real>& lp, int row, int col, Real val) const;
211  /// returns scaled lower bound of column \p col.
212  virtual Real scaleLower(const SPxLPBase<Real>& lp, int col, Real lower) const;
213  /// returns scaled upper bound of column \p col.
214  virtual Real scaleUpper(const SPxLPBase<Real>& lp, int col, Real upper) const;
215  /// returns scaled left hand side of row \p row.
216  virtual Real scaleLhs(const SPxLPBase<Real>& lp, int row, Real lhs) const;
217  /// returns scaled right hand side of row \p row.
218  virtual Real scaleRhs(const SPxLPBase<Real>& lp, int row, Real rhs) const;
219  /// absolute smallest column scaling factor
220  virtual Real minAbsColscale() const;
221  /// absolute biggest column scaling factor
222  virtual Real maxAbsColscale() const;
223  /// absolute smallest row scaling factor
224  virtual Real minAbsRowscale() const;
225  /// absolute biggest row scaling factor
226  virtual Real maxAbsRowscale() const;
227  /// maximum ratio between absolute biggest and smallest element in any column.
228  virtual Real maxColRatio(const SPxLPBase<Real>& lp) const;
229  /// maximum ratio between absolute biggest and smallest element in any row.
230  virtual Real maxRowRatio(const SPxLPBase<Real>& lp) const;
231  /// round vector entries to power of 2
232  void computeExpVec(const std::vector<Real>& vec, DataArray<int>& vecExp);
233  //@}
234 
235  //-------------------------------------
236  /**@name Debugging */
237  //@{
238  /// consistency check
239  virtual bool isConsistent() const;
240  //@}
241 };
242 } // namespace soplex
243 #endif // _SPXSCALER_H_
virtual void unscaleDualray(const SPxLPBase< Real > &lp, Vector &ray) const
unscale dual ray given in ray.
Definition: spxscaler.cpp:674
virtual void setup(SPxLPBase< Real > &lp)
clear and setup scaling arrays in the LP
Definition: spxscaler.cpp:129
virtual void setBoth(bool both)
set wether column and row scaling should be performed
Definition: spxscaler.cpp:117
virtual void setOrder(bool colFirst)
set scaling order
Definition: spxscaler.cpp:111
virtual void unscalePrimal(const SPxLPBase< Real > &lp, Vector &x) const
unscale dense primal solution vector given in x.
Definition: spxscaler.cpp:614
virtual Real lhsUnscaled(const SPxLPBase< Real > &lp, int i) const
returns unscaled left hand side i of lp
Definition: spxscaler.cpp:574
virtual void getRowUnscaled(const SPxLPBase< Real > &lp, int i, DSVector &vec) const
returns unscaled row i
Definition: spxscaler.cpp:468
virtual Real scaleElement(const SPxLPBase< Real > &lp, int row, int col, Real val) const
returns scaled LP element in row and col.
Definition: spxscaler.cpp:710
friend std::ostream & operator<<(std::ostream &s, const SPxScaler &sc)
Definition: spxscaler.cpp:33
virtual void getLhsUnscaled(const SPxLPBase< Real > &lp, Vector &vec) const
returns unscaled left hand side vector of lp
Definition: spxscaler.cpp:590
virtual void unscaleRedCost(const SPxLPBase< Real > &lp, Vector &r) const
unscale dense reduced cost vector given in r.
Definition: spxscaler.cpp:650
virtual Real maxRowRatio(const SPxLPBase< Real > &lp) const
maximum ratio between absolute biggest and smallest element in any row.
Definition: spxscaler.cpp:866
virtual void unscaleDual(const SPxLPBase< Real > &lp, Vector &pi) const
unscale dense dual solution vector given in pi.
Definition: spxscaler.cpp:638
virtual Real scaleUpper(const SPxLPBase< Real > &lp, int col, Real upper) const
returns scaled upper bound of column col.
Definition: spxscaler.cpp:735
virtual ~SPxScaler()
destructor.
Definition: spxscaler.cpp:83
virtual bool isConsistent() const
consistency check
Definition: spxscaler.cpp:914
virtual Real getRowMaxAbsUnscaled(const SPxLPBase< Real > &lp, int i) const
returns maximum absolute value of unscaled row i
Definition: spxscaler.cpp:491
virtual void getUpperUnscaled(const SPxLPBase< Real > &lp, Vector &vec) const
returns unscaled upper bound vector of lp
Definition: spxscaler.cpp:401
virtual Real scaleLhs(const SPxLPBase< Real > &lp, int row, Real lhs) const
returns scaled left hand side of row row.
Definition: spxscaler.cpp:746
Dense vector for linear algebra.
DataArray< int > * m_activeColscaleExp
pointer to currently active column scaling factors
Definition: spxscaler.h:84
virtual void applyScaling(SPxLPBase< Real > &lp)
applies m_colscale and m_rowscale to the lp.
Definition: spxscaler.cpp:177
virtual void setOutstream(SPxOut &newOutstream)
set message handler
Definition: spxscaler.h:138
virtual int computeScaleExp(const SVector &vec, const DataArray< int > &oldScaleExp) const
compute a single scaling vector , e.g. of a newly added row
Definition: spxscaler.cpp:146
double Real
Definition: spxdefines.h:218
virtual SPxScaler * clone() const =0
clone function for polymorphism
virtual void unscale(SPxLPBase< Real > &lp)
unscale SPxLP
Definition: spxscaler.cpp:236
SPxOut * spxout
message handler
Definition: spxscaler.h:88
virtual Real upperUnscaled(const SPxLPBase< Real > &lp, int i) const
returns unscaled upper bound i
Definition: spxscaler.cpp:384
Dynamic vectors.
Wrapper for several output streams. A verbosity level is used to decide which stream to use and wheth...
Definition: spxout.h:63
Sparse vectors.
virtual void getLowerUnscaled(const SPxLPBase< Real > &lp, Vector &vec) const
gets unscaled lower bound vector
Definition: spxscaler.cpp:431
virtual Real maxAbsColscale() const
absolute biggest column scaling factor
Definition: spxscaler.cpp:781
virtual int getColScaleExp(int i) const
returns scaling factor for column i
Definition: spxscaler.cpp:293
virtual void scaleObj(const SPxLPBase< Real > &lp, VectorReal &origObj) const
apply scaling to objective function vector origObj.
Definition: spxscaler.cpp:686
virtual void getRhsUnscaled(const SPxLPBase< Real > &lp, Vector &vec) const
gets unscaled right hand side vector
Definition: spxscaler.cpp:560
virtual Real minAbsColscale() const
absolute smallest column scaling factor
Definition: spxscaler.cpp:768
virtual void setRealParam(Real param, const char *name="realparam")
set real parameter
Definition: spxscaler.cpp:123
virtual Real maxObjUnscaled(const SPxLPBase< Real > &lp, int i) const
returns unscaled objective function coefficient of i
Definition: spxscaler.cpp:443
void computeExpVec(const std::vector< Real > &vec, DataArray< int > &vecExp)
round vector entries to power of 2
Definition: spxscaler.cpp:903
DataArray< int > * m_activeRowscaleExp
pointer to currently active row scaling factors
Definition: spxscaler.h:85
Debugging, floating point type and parameter definitions.
virtual const char * getName() const
get name of scaler
Definition: spxscaler.cpp:105
virtual Real minAbsRowscale() const
absolute smallest row scaling factor
Definition: spxscaler.cpp:795
virtual Real scaleLower(const SPxLPBase< Real > &lp, int col, Real lower) const
returns scaled lower bound of column col.
Definition: spxscaler.cpp:724
virtual void scale(SPxLPBase< Real > &lp, bool persistent=true)=0
scale SPxLP.
Everything should be within this namespace.
virtual Real lowerUnscaled(const SPxLPBase< Real > &lp, int i) const
returns unscaled lower bound i
Definition: spxscaler.cpp:414
virtual Real rhsUnscaled(const SPxLPBase< Real > &lp, int i) const
returns unscaled right hand side i
Definition: spxscaler.cpp:543
virtual Real getColMinAbsUnscaled(const SPxLPBase< Real > &lp, int i) const
returns minumum absolute value of unscaled column i
Definition: spxscaler.cpp:357
bool m_colFirst
do column scaling first
Definition: spxscaler.h:86
SPxScaler(const char *name, bool colFirst=false, bool doBoth=true, SPxOut *spxout=NULL)
constructor
Definition: spxscaler.cpp:57
Dynamic sparse vectors.
LP scaler abstract base class.Instances of classes derived from SPxScaler may be loaded to SoPlex in ...
Definition: spxscaler.h:76
virtual Real getRowMinAbsUnscaled(const SPxLPBase< Real > &lp, int i) const
returns minimum absolute value of unscaled row i
Definition: spxscaler.cpp:517
virtual Real maxAbsRowscale() const
absolute biggest row scaling factor
Definition: spxscaler.cpp:808
virtual int getRowScaleExp(int i) const
returns scaling factor for row i
Definition: spxscaler.cpp:300
Set of sparse vectors.
virtual void getColUnscaled(const SPxLPBase< Real > &lp, int i, DSVector &vec) const
gets unscaled column i
Definition: spxscaler.cpp:306
virtual Real getCoefUnscaled(const SPxLPBase< Real > &lp, int row, int col) const
returns unscaled coefficient of lp
Definition: spxscaler.cpp:602
bool m_doBoth
do columns and rows
Definition: spxscaler.h:87
virtual Real maxColRatio(const SPxLPBase< Real > &lp) const
maximum ratio between absolute biggest and smallest element in any column.
Definition: spxscaler.cpp:825
virtual Real scaleRhs(const SPxLPBase< Real > &lp, int row, Real rhs) const
returns scaled right hand side of row row.
Definition: spxscaler.cpp:757
Save arrays of data objects.
virtual void unscaleSlacks(const SPxLPBase< Real > &lp, Vector &s) const
unscale dense slack vector given in s.
Definition: spxscaler.cpp:626
virtual void unscalePrimalray(const SPxLPBase< Real > &lp, Vector &ray) const
unscale primal ray given in ray.
Definition: spxscaler.cpp:662
virtual Real getColMaxAbsUnscaled(const SPxLPBase< Real > &lp, int i) const
returns maximum absolute value of unscaled column i
Definition: spxscaler.cpp:331
virtual void getMaxObjUnscaled(const SPxLPBase< Real > &lp, Vector &vec) const
gets unscaled objective function
Definition: spxscaler.cpp:456
const char * m_name
Name of the scaler.
Definition: spxscaler.h:83
virtual void setIntParam(int param, const char *name="intparam")
set int parameter
Definition: spxscaler.cpp:126
SPxScaler & operator=(const SPxScaler &)
assignment operator
Definition: spxscaler.cpp:88