SoPlex Documentation
Loading...
Searching...
No Matches
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-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
42namespace soplex
43{
44
45template < class R >
46class 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
85template <class R>
87{
88protected:
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 ///@}
100
101 //-------------------------------------
102 /**@name Protected helpers */
103 ///@{
104
105 /// clear and setup scaling arrays in the LP
106 virtual void setup(SPxLPBase<R>& lp);
107 ///@}
108
109public:
110
111 /// compute a single scaling vector , e.g. of a newly added row
112 virtual int computeScaleExp(const SVectorBase<R>& vec, const DataArray<int>& oldScaleExp) const;
113
114 // The following is now redundant because of the above function.
115 // virtual int computeScaleExp(const SVectorBase<Rational>& vec, const DataArray<int>& oldScaleExp) const;
116
117 /// applies m_colscale and m_rowscale to the \p lp.
119
120
121 template <class T>
122 friend std::ostream& operator<<(std::ostream& s, const SPxScaler<T>& sc);
123
124 //-------------------------------------
125 /**@name Construction / destruction */
126 ///@{
127 /// constructor
128 explicit SPxScaler(const char* name, bool colFirst = false, bool doBoth = true,
129 SPxOut* spxout = NULL);
130 /// copy constructor
132 /// assignment operator
134 /// destructor.
135 virtual ~SPxScaler();
136 /// clone function for polymorphism
137 virtual SPxScaler* clone() const = 0;
138 ///@}
139
140 //-------------------------------------
141 /**@name Access / modification */
142 ///@{
143 /// get name of scaler
144 virtual const char* getName() const;
145 /// set scaling order
146 virtual void setOrder(bool colFirst);
147 /// set wether column and row scaling should be performed
148 virtual void setBoth(bool both);
149 /// set message handler
151 {
153 }
154 /// set R parameter
155 virtual void setRealParam(R param, const char* name = "realparam");
156 /// set int parameter
157 virtual void setIntParam(int param, const char* name = "intparam");
158 ///@}
159
160 //-------------------------------------
161 /**@name Scaling */
162 ///@{
163 /// scale SPxLP.
164 virtual void scale(SPxLPBase<R>& lp, bool persistent = true) = 0;
165 /// unscale SPxLP
166 virtual void unscale(SPxLPBase<R>& lp);
167 /// returns scaling factor for column \p i
168 virtual int getColScaleExp(int i) const;
169 /// returns scaling factor for row \p i
170 virtual int getRowScaleExp(int i) const;
171 /// gets unscaled column \p i
172 virtual void getColUnscaled(const SPxLPBase<R>& lp, int i, DSVectorBase<R>& vec) const;
173 /// returns maximum absolute value of unscaled column \p i
174 virtual R getColMaxAbsUnscaled(const SPxLPBase<R>& lp, int i) const;
175 /// returns minumum absolute value of unscaled column \p i
176 virtual R getColMinAbsUnscaled(const SPxLPBase<R>& lp, int i) const;
177 /// returns unscaled upper bound \p i
178 virtual R upperUnscaled(const SPxLPBase<R>& lp, int i) const;
179 /// returns unscaled upper bound vector of \p lp
180 virtual void getUpperUnscaled(const SPxLPBase<R>& lp, VectorBase<R>& vec) const;
181 /// returns unscaled lower bound \p i
182 virtual R lowerUnscaled(const SPxLPBase<R>& lp, int i) const;
183 /// gets unscaled lower bound vector
184 virtual void getLowerUnscaled(const SPxLPBase<R>& lp, VectorBase<R>& vec) const;
185 /// returns unscaled objective function coefficient of \p i
186 virtual R maxObjUnscaled(const SPxLPBase<R>& lp, int i) const;
187 /// gets unscaled objective function
188 virtual void getMaxObjUnscaled(const SPxLPBase<R>& lp, VectorBase<R>& vec) const;
189 /// returns unscaled row \p i
190 virtual void getRowUnscaled(const SPxLPBase<R>& lp, int i, DSVectorBase<R>& vec) const;
191 /// returns maximum absolute value of unscaled row \p i
192 virtual R getRowMaxAbsUnscaled(const SPxLPBase<R>& lp, int i) const;
193 /// returns minimum absolute value of unscaled row \p i
194 virtual R getRowMinAbsUnscaled(const SPxLPBase<R>& lp, int i) const;
195 /// returns unscaled right hand side \p i
196 virtual R rhsUnscaled(const SPxLPBase<R>& lp, int i) const;
197 /// gets unscaled right hand side vector
198 virtual void getRhsUnscaled(const SPxLPBase<R>& lp, VectorBase<R>& vec) const;
199 /// returns unscaled left hand side \p i of \p lp
200 virtual R lhsUnscaled(const SPxLPBase<R>& lp, int i) const;
201 /// returns unscaled left hand side vector of \p lp
202 virtual void getLhsUnscaled(const SPxLPBase<R>& lp, VectorBase<R>& vec) const;
203 /// returns unscaled coefficient of \p lp
204 virtual R getCoefUnscaled(const SPxLPBase<R>& lp, int row, int col) const;
205 /// unscale dense primal solution vector given in \p x.
206 virtual void unscalePrimal(const SPxLPBase<R>& lp, VectorBase<R>& x) const;
207 /// unscale dense slack vector given in \p s.
208 virtual void unscaleSlacks(const SPxLPBase<R>& lp, VectorBase<R>& s) const;
209 /// unscale dense dual solution vector given in \p pi.
210 virtual void unscaleDual(const SPxLPBase<R>& lp, VectorBase<R>& pi) const;
211 /// unscale dense reduced cost vector given in \p r.
212 virtual void unscaleRedCost(const SPxLPBase<R>& lp, VectorBase<R>& r) const;
213 /// unscale primal ray given in \p ray.
214 virtual void unscalePrimalray(const SPxLPBase<R>& lp, VectorBase<R>& ray) const;
215 /// unscale dual ray given in \p ray.
216 virtual void unscaleDualray(const SPxLPBase<R>& lp, VectorBase<R>& ray) const;
217 /// apply scaling to objective function vector \p origObj.
218 virtual void scaleObj(const SPxLPBase<R>& lp, VectorBase<R>& origObj) const;
219 /// returns scaled objective function coefficient \p origObj.
220 virtual R scaleObj(const SPxLPBase<R>& lp, int i, R origObj) const;
221 /// returns scaled LP element in \p row and \p col.
222 virtual R scaleElement(const SPxLPBase<R>& lp, int row, int col, R val) const;
223 /// returns scaled lower bound of column \p col.
224 virtual R scaleLower(const SPxLPBase<R>& lp, int col, R lower) const;
225 /// returns scaled upper bound of column \p col.
226 virtual R scaleUpper(const SPxLPBase<R>& lp, int col, R upper) const;
227 /// returns scaled left hand side of row \p row.
228 virtual R scaleLhs(const SPxLPBase<R>& lp, int row, R lhs) const;
229 /// returns scaled right hand side of row \p row.
230 virtual R scaleRhs(const SPxLPBase<R>& lp, int row, R rhs) const;
231 /// absolute smallest column scaling factor
232 virtual R minAbsColscale() const;
233 /// absolute biggest column scaling factor
234 virtual R maxAbsColscale() const;
235 /// absolute smallest row scaling factor
236 virtual R minAbsRowscale() const;
237 /// absolute biggest row scaling factor
238 virtual R maxAbsRowscale() const;
239 /// maximum ratio between absolute biggest and smallest element in any column.
240 virtual R maxColRatio(const SPxLPBase<R>& lp) const;
241 /// maximum ratio between absolute biggest and smallest element in any row.
242 virtual R maxRowRatio(const SPxLPBase<R>& lp) const;
243 /// round vector entries to power of 2
244 void computeExpVec(const std::vector<R>& vec, DataArray<int>& vecExp);
245 ///@}
246
247 //-------------------------------------
248 /**@name Debugging */
249 ///@{
250 /// consistency check
251 virtual bool isConsistent() const;
252 ///@}
253};
254} // namespace soplex
255
256// General templated definitions
257#include "spxscaler.hpp"
258
259#endif // _SPXSCALER_H_
Safe arrays of data objects.
Definition dataarray.h:75
Wrapper for several output streams. A verbosity level is used to decide which stream to use and wheth...
Definition spxout.h:73
LP scaler abstract base class.
Definition spxscaler.h:87
virtual void getUpperUnscaled(const SPxLPBase< R > &lp, VectorBase< R > &vec) const
returns unscaled upper bound vector of lp
DataArray< int > * m_activeColscaleExp
pointer to currently active column scaling factors
Definition spxscaler.h:94
virtual void setBoth(bool both)
set wether column and row scaling should be performed
SPxScaler(const char *name, bool colFirst=false, bool doBoth=true, SPxOut *spxout=NULL)
constructor
virtual R maxColRatio(const SPxLPBase< R > &lp) const
maximum ratio between absolute biggest and smallest element in any column.
virtual void scaleObj(const SPxLPBase< R > &lp, VectorBase< R > &origObj) const
apply scaling to objective function vector origObj.
void computeExpVec(const std::vector< R > &vec, DataArray< int > &vecExp)
round vector entries to power of 2
virtual R rhsUnscaled(const SPxLPBase< R > &lp, int i) const
returns unscaled right hand side i
bool m_colFirst
do column scaling first
Definition spxscaler.h:96
SPxOut * spxout
message handler
Definition spxscaler.h:98
virtual void unscaleRedCost(const SPxLPBase< R > &lp, VectorBase< R > &r) const
unscale dense reduced cost vector given in r.
virtual R scaleObj(const SPxLPBase< R > &lp, int i, R origObj) const
returns scaled objective function coefficient origObj.
virtual R getColMinAbsUnscaled(const SPxLPBase< R > &lp, int i) const
returns minumum absolute value of unscaled column i
virtual void unscaleSlacks(const SPxLPBase< R > &lp, VectorBase< R > &s) const
unscale dense slack vector given in s.
virtual const char * getName() const
get name of scaler
virtual void setup(SPxLPBase< R > &lp)
clear and setup scaling arrays in the LP
virtual R scaleLower(const SPxLPBase< R > &lp, int col, R lower) const
returns scaled lower bound of column col.
SPxScaler & operator=(const SPxScaler &)
assignment operator
virtual R getRowMaxAbsUnscaled(const SPxLPBase< R > &lp, int i) const
returns maximum absolute value of unscaled row i
virtual R minAbsColscale() const
absolute smallest column scaling factor
virtual void setRealParam(R param, const char *name="realparam")
set R parameter
virtual void unscaleDualray(const SPxLPBase< R > &lp, VectorBase< R > &ray) const
unscale dual ray given in ray.
virtual void getColUnscaled(const SPxLPBase< R > &lp, int i, DSVectorBase< R > &vec) const
gets unscaled column i
DataArray< int > * m_activeRowscaleExp
pointer to currently active row scaling factors
Definition spxscaler.h:95
virtual R maxAbsRowscale() const
absolute biggest row scaling factor
virtual void getRowUnscaled(const SPxLPBase< R > &lp, int i, DSVectorBase< R > &vec) const
returns unscaled row i
virtual int getRowScaleExp(int i) const
returns scaling factor for row i
virtual R getRowMinAbsUnscaled(const SPxLPBase< R > &lp, int i) const
returns minimum absolute value of unscaled row i
virtual bool isConsistent() const
consistency check
bool m_doBoth
do columns and rows
Definition spxscaler.h:97
virtual R scaleRhs(const SPxLPBase< R > &lp, int row, R rhs) const
returns scaled right hand side of row row.
virtual int getColScaleExp(int i) const
returns scaling factor for column i
virtual R maxAbsColscale() const
absolute biggest column scaling factor
virtual R scaleUpper(const SPxLPBase< R > &lp, int col, R upper) const
returns scaled upper bound of column col.
virtual R minAbsRowscale() const
absolute smallest row scaling factor
virtual void unscalePrimalray(const SPxLPBase< R > &lp, VectorBase< R > &ray) const
unscale primal ray given in ray.
virtual void applyScaling(SPxLPBase< R > &lp)
applies m_colscale and m_rowscale to the lp.
virtual R lowerUnscaled(const SPxLPBase< R > &lp, int i) const
returns unscaled lower bound i
const char * m_name
Name of the scaler.
Definition spxscaler.h:93
virtual void scale(SPxLPBase< R > &lp, bool persistent=true)=0
scale SPxLP.
virtual void setIntParam(int param, const char *name="intparam")
set int parameter
virtual R maxObjUnscaled(const SPxLPBase< R > &lp, int i) const
returns unscaled objective function coefficient of i
virtual int computeScaleExp(const SVectorBase< R > &vec, const DataArray< int > &oldScaleExp) const
compute a single scaling vector , e.g. of a newly added row
virtual SPxScaler * clone() const =0
clone function for polymorphism
virtual R upperUnscaled(const SPxLPBase< R > &lp, int i) const
returns unscaled upper bound i
virtual R getCoefUnscaled(const SPxLPBase< R > &lp, int row, int col) const
returns unscaled coefficient of lp
virtual R maxRowRatio(const SPxLPBase< R > &lp) const
maximum ratio between absolute biggest and smallest element in any row.
virtual void unscalePrimal(const SPxLPBase< R > &lp, VectorBase< R > &x) const
unscale dense primal solution vector given in x.
virtual void getLhsUnscaled(const SPxLPBase< R > &lp, VectorBase< R > &vec) const
returns unscaled left hand side vector of lp
SPxScaler(const SPxScaler &)
copy constructor
virtual void setOrder(bool colFirst)
set scaling order
friend std::ostream & operator<<(std::ostream &s, const SPxScaler< T > &sc)
virtual void unscaleDual(const SPxLPBase< R > &lp, VectorBase< R > &pi) const
unscale dense dual solution vector given in pi.
virtual void getLowerUnscaled(const SPxLPBase< R > &lp, VectorBase< R > &vec) const
gets unscaled lower bound vector
virtual R scaleLhs(const SPxLPBase< R > &lp, int row, R lhs) const
returns scaled left hand side of row row.
virtual R lhsUnscaled(const SPxLPBase< R > &lp, int i) const
returns unscaled left hand side i of lp
virtual void getRhsUnscaled(const SPxLPBase< R > &lp, VectorBase< R > &vec) const
gets unscaled right hand side vector
virtual R getColMaxAbsUnscaled(const SPxLPBase< R > &lp, int i) const
returns maximum absolute value of unscaled column i
virtual R scaleElement(const SPxLPBase< R > &lp, int row, int col, R val) const
returns scaled LP element in row and col.
virtual void getMaxObjUnscaled(const SPxLPBase< R > &lp, VectorBase< R > &vec) const
gets unscaled objective function
virtual void setOutstream(SPxOut &newOutstream)
set message handler
Definition spxscaler.h:150
virtual ~SPxScaler()
destructor.
virtual void unscale(SPxLPBase< R > &lp)
unscale SPxLP
Save arrays of data objects.
Dynamic sparse vectors.
Dynamic vectors.
Everything should be within this namespace.
Debugging, floating point type and parameter definitions.
Sparse vectors.
Set of sparse vectors.
Dense vector for linear algebra.