Scippy

SoPlex

Sequential object-oriented simPlex

spxequilisc.cpp
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 spxequilisc.cpp
17  * @brief Equilibrium row/column scaling.
18  */
19 #include <assert.h>
20 
21 #include "spxequilisc.h"
22 #include "spxout.h"
23 #include "spxlpbase.h"
24 #include "spxlp.h"
25 #include "soplex.h"
26 
27 namespace soplex
28 {
29 static const char* makename(bool doBoth)
30 {
31  return doBoth ? "bi-Equilibrium" : "uni-Equilibrium";
32 }
33 
34 /// maximum ratio between absolute biggest and smallest element in any scaled row/column.
35 static Real maxPrescaledRatio(const SPxLP& lp, const std::vector<Real>& coScaleval, bool rowRatio)
36 {
37  Real pmax = 0.0;
38  const int n = rowRatio ? lp.nRows() : lp.nCols();
39 
40  for( int i = 0; i < n; ++i )
41  {
42  const SVector& vec = rowRatio ? lp.rowVector(i) : lp.colVector(i);
43  Real mini = infinity;
44  Real maxi = 0.0;
45 
46  for( int j = 0; j < vec.size(); ++j )
47  {
48  assert(vec.index(j) >= 0);
49  const Real x = spxAbs(vec.value(j)) * coScaleval[unsigned(vec.index(j))];
50 
51  if( isZero(x) )
52  continue;
53  if( x < mini )
54  mini = x;
55  if( x > maxi )
56  maxi = x;
57  }
58 
59  if( mini == infinity )
60  continue;
61 
62  const Real p = maxi / mini;
63 
64  if( p > pmax )
65  pmax = p;
66  }
67  return pmax;
68 }
69 
70 
71 void SPxEquiliSC::computeEquiExpVec(const SVSet* vecset, const DataArray<int>& coScaleExp, DataArray<int>& scaleExp)
72 {
73  assert(vecset != nullptr);
74 
75  for( int i = 0; i < vecset->num(); ++i )
76  {
77  const SVector& vec = (*vecset)[i];
78 
79  Real maxi = 0.0;
80 
81  for( int j = 0; j < vec.size(); ++j )
82  {
83  const Real x = spxAbs(spxLdexp(vec.value(j), coScaleExp[vec.index(j)]));
84 
85  if( GT(x, maxi) )
86  maxi = x;
87  }
88  // empty rows/cols are possible
89  if( maxi == 0.0 )
90  maxi = 1.0;
91 
92  assert(maxi > 0.0);
93 
94  spxFrexp(1.0 / maxi, &(scaleExp[i]));
95 
96  scaleExp[i] -= 1;
97  }
98 }
99 
100 void SPxEquiliSC::computeEquiExpVec(const SVSet* vecset, const std::vector<Real>& coScaleVal, DataArray<int>& scaleExp)
101 {
102  assert(vecset != nullptr);
103 
104  for( int i = 0; i < vecset->num(); ++i )
105  {
106  const SVector& vec = (*vecset)[i];
107 
108  Real maxi = 0.0;
109 
110  for( int j = 0; j < vec.size(); ++j )
111  {
112  assert(vec.index(j) >= 0);
113  const Real x = spxAbs(vec.value(j) * coScaleVal[unsigned(vec.index(j))]);
114 
115  if( GT(x, maxi) )
116  maxi = x;
117  }
118  // empty rows/cols are possible
119  if( maxi == 0.0 )
120  maxi = 1.0;
121 
122  assert(maxi > 0.0);
123 
124  spxFrexp(1.0 / maxi, &(scaleExp[i]));
125 
126  scaleExp[i] -= 1;
127  }
128 }
129 
130 void SPxEquiliSC::computePostequiExpVecs(const SPxLPBase<Real>& lp, const std::vector<Real>& preRowscale, const std::vector<Real>& preColscale,
131  DataArray<int>& rowscaleExp, DataArray<int>& colscaleExp)
132 {
133  const Real colratio = maxPrescaledRatio(lp, preRowscale, false);
134  const Real rowratio = maxPrescaledRatio(lp, preColscale, true);
135 
136  const bool colFirst = colratio < rowratio;
137 
138  // see SPxEquiliSC::scale for reason behind this branch
139  if( colFirst )
140  {
141  computeEquiExpVec(lp.colSet(), preRowscale, colscaleExp);
142  computeEquiExpVec(lp.rowSet(), colscaleExp, rowscaleExp);
143  }
144  else
145  {
146  computeEquiExpVec(lp.rowSet(), preColscale, rowscaleExp);
147  computeEquiExpVec(lp.colSet(), rowscaleExp, colscaleExp);
148  }
149 }
150 
151 
153  : SPxScaler(makename(doBoth), false, doBoth)
154 {}
155 
157  : SPxScaler(old)
158 {}
159 
161 {
162  if(this != &rhs)
163  {
165  }
166 
167  return *this;
168 }
169 
170 
171 void SPxEquiliSC::scale(SPxLP& lp, bool persistent)
172 {
173 
174  MSG_INFO1( (*spxout), (*spxout) << "Equilibrium scaling LP" << (persistent ? " (persistent)" : "") << std::endl; )
175 
176  setup(lp);
177 
178  /* We want to do the direction first, which has a lower maximal ratio,
179  * since the lowest value in the scaled matrix is bounded from below by
180  * the inverse of the maximum ratio of the direction that is done first
181  * Example:
182  *
183  * Rowratio
184  * 0.1 1 10
185  * 10 1 10
186  *
187  * Colratio 100 1
188  *
189  * Row first => Col next =>
190  * 0.1 1 0.1 1
191  * 1 0.1 1 0.1
192  *
193  * Col first => Row next =>
194  * 0.01 1 0.01 1
195  * 1 1 1 1
196  *
197  */
198  Real colratio = maxColRatio(lp);
199  Real rowratio = maxRowRatio(lp);
200 
201  bool colFirst = colratio < rowratio;
202 
203  MSG_INFO2( (*spxout), (*spxout) << "before scaling:"
204  << " min= " << lp.minAbsNzo()
205  << " max= " << lp.maxAbsNzo()
206  << " col-ratio= " << colratio
207  << " row-ratio= " << rowratio
208  << std::endl; )
209 
210  if (colFirst)
211  {
213 
214  if (m_doBoth)
216  }
217  else
218  {
220 
221  if (m_doBoth)
223  }
224 
225  /* scale */
226  applyScaling(lp);
227 
228  MSG_INFO3( (*spxout), (*spxout) << "Row scaling min= " << minAbsRowscale()
229  << " max= " << maxAbsRowscale()
230  << std::endl
231  << "Col scaling min= " << minAbsColscale()
232  << " max= " << maxAbsColscale()
233  << std::endl; )
234 
235  MSG_INFO2( (*spxout), (*spxout) << "after scaling: "
236  << " min= " << lp.minAbsNzo(false)
237  << " max= " << lp.maxAbsNzo(false)
238  << " col-ratio= " << maxColRatio(lp)
239  << " row-ratio= " << maxRowRatio(lp)
240  << std::endl; )
241 
242 }
243 
244 } // namespace soplex
Rational spxAbs(const Rational &r)
Absolute.
Definition: rational.cpp:3909
virtual void setup(SPxLPBase< Real > &lp)
clear and setup scaling arrays in the LP
Definition: spxscaler.cpp:124
virtual R minAbsNzo(bool unscaled=true) const
Absolute smallest non-zero element in (possibly scaled) LP.
THREADLOCAL const Real infinity
Definition: spxdefines.cpp:26
static const char * makename(bool doBoth)
Definition: spxequilisc.cpp:29
int size() const
Number of used indices.
Definition: svectorbase.h:152
virtual Real maxRowRatio(const SPxLPBase< Real > &lp) const
maximum ratio between absolute biggest and smallest element in any row.
Definition: spxscaler.cpp:855
R & value(int n)
Reference to value of n &#39;th nonzero.
Definition: svectorbase.h:252
SPxEquiliSC(bool doBoth=true)
default constructor (this scaler makes no use of inherited member m_colFirst)
Saving LPs in a form suitable for SoPlex.
Real spxFrexp(Real y, int *exp)
Definition: spxdefines.h:358
Wrapper for different output streams and verbosity levels.
int nRows() const
Returns number of rows in LP.
Definition: spxlpbase.h:151
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:171
Real spxLdexp(Real x, int exp)
returns x * 2^exp
Definition: spxdefines.h:352
double Real
Definition: spxdefines.h:218
SPxOut * spxout
message handler
Definition: spxscaler.h:88
bool GT(Real a, Real b, Real eps=Param::epsilon())
returns true iff a > b + eps
Definition: spxdefines.h:404
int & index(int n)
Reference to index of n &#39;th nonzero.
Definition: svectorbase.h:234
#define MSG_INFO2(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO2.
Definition: spxdefines.h:120
virtual Real maxAbsColscale() const
absolute biggest column scaling factor
Definition: spxscaler.cpp:773
virtual Real minAbsColscale() const
absolute smallest column scaling factor
Definition: spxscaler.cpp:760
Preconfigured SoPlex LP solver.
#define MSG_INFO3(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO3.
Definition: spxdefines.h:122
DataArray< int > * m_activeRowscaleExp
pointer to currently active row scaling factors
Definition: spxscaler.h:85
virtual Real minAbsRowscale() const
absolute smallest row scaling factor
Definition: spxscaler.cpp:787
static Real maxPrescaledRatio(const SPxLP &lp, const std::vector< Real > &coScaleval, bool rowRatio)
maximum ratio between absolute biggest and smallest element in any scaled row/column.
Definition: spxequilisc.cpp:35
static void computePostequiExpVecs(const SPxLPBase< Real > &lp, const std::vector< Real > &preRowscale, const std::vector< Real > &preColscale, DataArray< int > &rowscaleExp, DataArray< int > &colscaleExp)
compute equilibrium scaling rounded to power of 2 for existing Real scaling factors (preRowscale...
Everything should be within this namespace.
Saving LPs in a form suitable for SoPlex.Class SPxLPBase provides the data structures required for sa...
Definition: spxlpbase.h:80
static void computeEquiExpVec(const SVSet *vecset, const DataArray< int > &coScaleExp, DataArray< int > &scaleExp)
compute equilibrium scaling vector rounded to power of two
Definition: spxequilisc.cpp:71
virtual void scale(SPxLPBase< Real > &lp, bool persistent=false) override
Scale the loaded SPxLP.
Saving LPs in a form suitable for SoPlex.
const SVectorBase< R > & rowVector(int i) const
Gets row vector of row i.
Definition: spxlpbase.h:204
LP scaler abstract base class.Instances of classes derived from SPxScaler may be loaded to SoPlex in ...
Definition: spxscaler.h:76
virtual Real maxAbsRowscale() const
absolute biggest row scaling factor
Definition: spxscaler.cpp:800
#define MSG_INFO1(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO1.
Definition: spxdefines.h:118
const SVectorBase< R > & colVector(int i) const
Returns column vector of column i.
Definition: spxlpbase.h:373
int nCols() const
Returns number of columns in LP.
Definition: spxlpbase.h:157
SPxEquiliSC & operator=(const SPxEquiliSC &)
assignment operator
const SVSetBase< R > * colSet() const
Returns the complete SVSetBase.
Definition: lpcolsetbase.h:68
bool isZero(Real a, Real eps=Param::epsilon())
returns true iff |a| <= eps
Definition: spxdefines.h:416
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:817
LP equilibrium scaling.
const SVSetBase< R > * rowSet() const
Returns the complete SVSet.
Definition: lprowsetbase.h:69
Equilibrium row/column scaling.This SPxScaler implementation performs equilibrium scaling of the LPs ...
Definition: spxequilisc.h:35
int num() const
Current number of SVectorBases.
Definition: svsetbase.h:746
virtual R maxAbsNzo(bool unscaled=true) const
Absolute biggest non-zero element in (in rational case possibly scaled) LP.
SPxScaler & operator=(const SPxScaler &)
assignment operator
Definition: spxscaler.cpp:84