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