Scippy

SoPlex

Sequential object-oriented simPlex

spxgeometsc.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-2016 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 spxgeometsc.cpp
17  * @brief Geometric mean row/column scaling.
18  */
19 #include <assert.h>
20 
21 #include "spxgeometsc.h"
22 #include "spxout.h"
23 
24 namespace soplex
25 {
26 /**@param maxIters arbitrary small number, we choose 8
27  @param minImpr Bixby said Fourer said in MP 23, 274 ff. that 0.9 is a good value.
28  @param goodEnough if the max/min ratio is allready less then 1000/1 we do not scale.
29 */
30 SPxGeometSC::SPxGeometSC(int maxIters, Real minImpr, Real goodEnough)
31  : SPxScaler("Geometric")
32  , m_maxIterations(maxIters)
33  , m_minImprovement(minImpr)
34  , m_goodEnoughRatio(goodEnough)
35 {}
36 
38  : SPxScaler(old)
42 {}
43 
45 {
46  if (this != &rhs)
47  {
49  }
50 
51  return *this;
52 }
53 
55 {
56 
57  return spxSqrt(mini * maxi);
58 }
59 
61 {
62 
63  MSG_INFO1( (*spxout), (*spxout) << "Geometric scaling LP" << std::endl; )
64 
65  Real pstart = 0.0;
66  Real p0 = 0.0;
67  Real p1 = 0.0;
68 
69  setup(lp);
70 
71  /* We want to do that direction first, with the lower ratio.
72  * See SPxEquiliSC::scale() for a reasoning.
73  */
74  Real colratio = maxColRatio(lp);
75  Real rowratio = maxRowRatio(lp);
76 
77  bool colFirst = colratio < rowratio;
78 
79  MSG_INFO2( (*spxout), (*spxout) << "LP scaling statistics:"
80  << " min= " << lp.minAbsNzo()
81  << " max= " << lp.maxAbsNzo()
82  << " col-ratio= " << colratio
83  << " row-ratio= " << rowratio
84  << std::endl; )
85 
86  // We make at most m_maxIterations.
87  for(int count = 0; count < m_maxIterations; count++)
88  {
89  if (colFirst)
90  {
93  }
94  else
95  {
98  }
99  MSG_INFO3( (*spxout), (*spxout) << "Geometric scaling round " << count
100  << " col-ratio= " << (colFirst ? p0 : p1)
101  << " row-ratio= " << (colFirst ? p1 : p0)
102  << std::endl; )
103 
104  // record start value, this is done with m_col/rowscale = 1.0, so it is the
105  // value frome the "original" (as passed to the scaler) LP.
106  if (count == 0)
107  {
108  pstart = p0;
109  // are we allready good enough ?
110  if (pstart < m_goodEnoughRatio)
111  break;
112  }
113  else // do not test at the first iteration, then abort if no improvement.
114  if (p1 > m_minImprovement * p0)
115  break;
116  }
117 
118  // we scale only if either:
119  // - we had at the beginng a ratio worse then 1000/1
120  // - we have at least a 15% improvement.
121  if (pstart < m_goodEnoughRatio || p1 > pstart * m_minImprovement)
122  {
123  // reset m_colscale/m_rowscale to 1.0
124  setup(lp);
125 
126  MSG_INFO2( (*spxout), (*spxout) << "No scaling done." << std::endl; )
127  }
128  else
129  {
130  applyScaling(lp);
131 
132  MSG_INFO3( (*spxout), (*spxout) << "Row scaling min= " << minAbsRowscale()
133  << " max= " << maxAbsRowscale()
134  << std::endl
135  << "IGEOSC06 Col scaling min= " << minAbsColscale()
136  << " max= " << maxAbsColscale()
137  << std::endl; )
138 
139  MSG_INFO2( (*spxout), (*spxout) << "LP scaling statistics:"
140  << " min= " << lp.minAbsNzo()
141  << " max= " << lp.maxAbsNzo()
142  << " col-ratio= " << maxColRatio(lp)
143  << " row-ratio= " << maxRowRatio(lp)
144  << std::endl; )
145  }
146 }
147 
148 } // namespace soplex
R minAbsNzo() const
Absolute smallest non-zero element in LP.
Definition: spxlpbase.h:150
const Real m_goodEnoughRatio
no scaling needed if ratio is less than this.
Definition: spxgeometsc.h:44
const int m_maxIterations
maximum number of scaling iterations.
Definition: spxgeometsc.h:42
Geometric mean row/column scaling.This SPxScaler implementation performs geometric mean scaling of th...
Definition: spxgeometsc.h:35
LP geometric mean scaling.
virtual void scale(SPxLP &lp)
Scale the loaded SPxLP.
Definition: spxgeometsc.cpp:60
SPxGeometSC(int maxIters=8, Real minImpr=0.85, Real goodEnough=1e3)
default constructor (this scaler makes no use of inherited members m_colFirst and m_doBoth) ...
Definition: spxgeometsc.cpp:30
virtual void applyScaling(SPxLP &lp)
applies m_colscale and m_rowscale to the lp.
Definition: spxscaler.cpp:186
virtual Real maxColRatio(const SPxLP &lp) const
maximum ratio between absolute biggest and smallest element in any column.
Definition: spxscaler.cpp:399
R maxAbsNzo() const
Absolute biggest non-zero element in LP.
Definition: spxlpbase.h:169
virtual Real computeScalingVecs(const SVSet *vecset, const DataArray< Real > &coScaleval, DataArray< Real > &scaleval)
iterates through vecset and calls computeScale() for each vector.
Definition: spxscaler.cpp:140
const SVSetBase< R > * rowSet() const
Returns the complete SVSet.
Definition: lprowsetbase.h:67
Wrapper for different output streams and verbosity levels.
const SVSetBase< R > * colSet() const
Returns the complete SVSetBase.
Definition: lpcolsetbase.h:66
double Real
SOPLEX_DEBUG.
Definition: spxdefines.h:200
#define MSG_INFO2(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO2.
Definition: spxdefines.h:115
virtual Real minAbsColscale() const
absolute smallest column scaling factor
Definition: spxscaler.cpp:330
SPxOut * spxout
message handler
Definition: spxscaler.h:51
DataArray< Real > m_colscale
column scaling factors
Definition: spxscaler.h:47
virtual Real maxAbsRowscale() const
absolute biggest row scaling factor
Definition: spxscaler.cpp:379
virtual Real maxRowRatio(const SPxLP &lp) const
maximum ratio between absolute biggest and smallest element in any row.
Definition: spxscaler.cpp:431
SPxGeometSC & operator=(const SPxGeometSC &)
assignment operator
Definition: spxgeometsc.cpp:44
Real spxSqrt(Real a)
returns square root
Definition: spxdefines.h:325
#define MSG_INFO1(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO1.
Definition: spxdefines.h:113
DataArray< Real > m_rowscale
row scaling factors
Definition: spxscaler.h:48
Everything should be within this namespace.
virtual Real computeScale(Real mini, Real maxi) const
Returns .
Definition: spxgeometsc.cpp:54
LP scaler abstract base class.Instances of classes derived from SPxScaler may be loaded to SoPlex in ...
Definition: spxscaler.h:39
virtual void setup(SPxLP &lp)
setup scale array for the LP.
Definition: spxscaler.cpp:115
virtual Real minAbsRowscale() const
absolute smallest row scaling factor
Definition: spxscaler.cpp:363
#define MSG_INFO3(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO3.
Definition: spxdefines.h:117
virtual Real maxAbsColscale() const
absolute biggest column scaling factor
Definition: spxscaler.cpp:346
const Real m_minImprovement
improvement nesseccary to carry on.
Definition: spxgeometsc.h:43
SPxScaler & operator=(const SPxScaler &)
assignment operator
Definition: spxscaler.cpp:80