Scippy

SoPlex

Sequential object-oriented simPlex

spxscaler.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 spxscaler.cpp
17  * @brief LP scaling base class.
18  */
19 
20 #define BITSHIFTSCALING
21 
22 #ifdef BITSHIFTSCALING
23 #include <cmath>
24 #endif
25 
26 #include <iostream>
27 #include <assert.h>
28 
29 #include "spxscaler.h"
30 #include "spxlp.h"
31 
32 namespace soplex
33 {
34 
35 std::ostream& operator<<(std::ostream& s, const SPxScaler& sc)
36 {
37  s << sc.getName() << " scaler:" << std::endl;
38  s << "colscale = [ ";
39  for(int ci = 0; ci < sc.m_colscale.size(); ++ci )
40  s << sc.m_colscale[ci] << " ";
41  s << "]" << std::endl;
42 
43  s << "rowscale = [ ";
44  for(int ri = 0; ri < sc.m_rowscale.size(); ++ri )
45  s << sc.m_rowscale[ri] << " ";
46  s << "]" << std::endl;
47 
48  return s;
49 }
50 
52  const char* name,
53  bool colFirst,
54  bool doBoth,
55  SPxOut* outstream)
56  : m_name(name)
57  , m_colFirst(colFirst)
58  , m_doBoth(doBoth)
59  , spxout(outstream)
60 {
61  assert(SPxScaler::isConsistent());
62 }
63 
65  : m_name(old.m_name)
66  , m_colscale(old.m_colscale)
67  , m_rowscale(old.m_rowscale)
68  , m_colFirst(old.m_colFirst)
69  , m_doBoth(old.m_doBoth)
70  , spxout(old.spxout)
71 {
72  assert(SPxScaler::isConsistent());
73 }
74 
76 {
77  m_name = 0;
78 }
79 
81 {
82  if (this != &rhs)
83  {
84  m_name = rhs.m_name;
85  m_colscale = rhs.m_colscale;
86  m_rowscale = rhs.m_rowscale;
87  m_colFirst = rhs.m_colFirst;
88  m_doBoth = rhs.m_doBoth;
89  spxout = rhs.spxout;
90 
91  assert(SPxScaler::isConsistent());
92  }
93  return *this;
94 }
95 
96 
97 const char* SPxScaler::getName() const
98 {
99 
100  return m_name;
101 }
102 
103 void SPxScaler::setOrder(bool colFirst)
104 {
105 
106  m_colFirst = colFirst;
107 }
108 
109 void SPxScaler::setBoth(bool both)
110 {
111 
112  m_doBoth = both;
113 }
114 
116 {
117 
118  assert(lp.isConsistent());
119 
120  m_colscale.reSize(lp.nCols());
121  m_rowscale.reSize(lp.nRows());
122 
123  int i;
124 
125  for(i = 0; i < lp.nCols(); ++i )
126  m_colscale[i] = 1.0;
127 
128  for(i = 0; i < lp.nRows(); ++i )
129  m_rowscale[i] = 1.0;
130 }
131 
132 /** This function is used by computeScaleVecs and has to be overridden.
133  */
134 Real SPxScaler::computeScale(Real /*mini*/, Real /*maxi*/) const
135 {
136 
137  return 1.0;
138 }
139 
141  const SVSet* vecset,
142  const DataArray<Real>& coScaleval,
143  DataArray<Real>& scaleval)
144 {
145 
146  Real pmax = 0.0;
147 
148  for(int i = 0; i < vecset->num(); ++i )
149  {
150  const SVector& vec = (*vecset)[i];
151 
152  Real maxi = 0.0;
153  Real mini = infinity;
154 
155  for( int j = 0; j < vec.size(); ++j)
156  {
157  Real x = spxAbs(vec.value(j) * coScaleval[vec.index(j)]);
158 
159  if (!isZero(x))
160  {
161  if (x > maxi)
162  maxi = x;
163  if (x < mini)
164  mini = x;
165  }
166  }
167  // empty rows/cols are possible
168  if (mini == infinity || maxi == 0.0)
169  {
170  mini = 1.0;
171  maxi = 1.0;
172  }
173  assert(mini < infinity);
174  assert(maxi > 0.0);
175 
176  scaleval[i] = 1.0 / computeScale(mini, maxi);
177 
178  Real p = maxi / mini;
179 
180  if (p > pmax)
181  pmax = p;
182  }
183  return pmax;
184 }
185 
187 {
188 
189  int i;
190 
191  for(i = 0; i < lp.nRows(); ++i )
192  {
193  SVector& vec = lp.rowVector_w(i);
194 #ifdef BITSHIFTSCALING
195  int exp1,exp2;
196  for( int j = 0; j < vec.size(); ++j)
197  {
198  spxFrexp(m_colscale[vec.index(j)], &exp1);
199  spxFrexp(m_rowscale[i], &exp2);
200  vec.value(j) = spxLdexp(vec.value(j), exp1 + exp2 - 2);
201  }
202  if (lp.rhs(i) < infinity)
203  {
204  spxFrexp(m_rowscale[i], &exp1);
205  lp.rhs_w(i) = spxLdexp(lp.rhs_w(i), exp1 - 1);
206  }
207  if (lp.lhs(i) > -infinity)
208  {
209  spxFrexp(m_rowscale[i], &exp1);
210  lp.lhs_w(i) = spxLdexp(lp.lhs_w(i), exp1 - 1);
211  }
212 #else
213  for( int j = 0; j < vec.size(); ++j)
214  vec.value(j) *= m_colscale[vec.index(j)] * m_rowscale[i];
215 
216  if (lp.rhs(i) < infinity)
217  lp.rhs_w(i) *= m_rowscale[i];
218  if (lp.lhs(i) > -infinity)
219  lp.lhs_w(i) *= m_rowscale[i];
220 #endif
221  }
222  for(i = 0; i < lp.nCols(); ++i )
223  {
224  SVector& vec = lp.colVector_w(i);
225 #ifdef BITSHIFTSCALING
226  int exp1,exp2;
227  for( int j = 0; j < vec.size(); ++j)
228  {
229  spxFrexp(m_rowscale[vec.index(j)], &exp1);
230  spxFrexp(m_colscale[i], &exp2);
231  vec.value(j) = spxLdexp(vec.value(j), exp1 + exp2 - 2);
232  }
233 
234  spxFrexp(m_colscale[i], &exp1);
235  lp.maxObj_w(i) = spxLdexp(lp.maxObj_w(i), exp1 - 1);
236 
237  if (lp.upper(i) < infinity)
238  {
239  spxFrexp(m_colscale[i], &exp1);
240  lp.upper_w(i) = spxLdexp(lp.upper_w(i), -exp1 + 1);
241  }
242  if (lp.lower(i) > -infinity)
243  {
244  spxFrexp(m_colscale[i], &exp1);
245  lp.lower_w(i) = spxLdexp(lp.lower_w(i), -exp1 + 1);
246  }
247 #else
248  for( int j = 0; j < vec.size(); ++j)
249  vec.value(j) *= m_rowscale[vec.index(j)] * m_colscale[i];
250 
251  lp.maxObj_w(i) *= m_colscale[i];
252 
253  if (lp.upper(i) < infinity)
254  lp.upper_w(i) /= m_colscale[i];
255  if (lp.lower(i) > -infinity)
256  lp.lower_w(i) /= m_colscale[i];
257 #endif
258  }
259  assert(lp.isConsistent());
260 }
261 
263 {
264 
265  assert(x.dim() == m_colscale.size());
266 #ifdef BITSHIFTSCALING
267  int exp1;
268  for(int j = 0; j < x.dim(); ++j)
269  {
270  spxFrexp(m_colscale[j], &exp1);
271  x[j] = spxLdexp(x[j], exp1 - 1);
272  }
273 #else
274  for(int j = 0; j < x.dim(); ++j)
275  x[j] *= m_colscale[j];
276 #endif
277 }
278 
280 {
281 
282  assert(s.dim() == m_rowscale.size());
283 #ifdef BITSHIFTSCALING
284  int exp1;
285  for(int i = 0; i < s.dim(); ++i)
286  {
287  spxFrexp(m_rowscale[i], &exp1);
288  s[i] = spxLdexp(s[i], -exp1 + 1);
289  }
290 #else
291  for(int i = 0; i < s.dim(); ++i)
292  s[i] /= m_rowscale[i];
293 #endif
294 }
295 
297 {
298 
299  assert(pi.dim() == m_rowscale.size());
300 #ifdef BITSHIFTSCALING
301  int exp1;
302  for(int i = 0; i < pi.dim(); ++i)
303  {
304  spxFrexp(m_rowscale[i], &exp1);
305  pi[i] = spxLdexp(pi[i], exp1 - 1);
306  }
307 #else
308  for(int i = 0; i < pi.dim(); ++i)
309  pi[i] *= m_rowscale[i];
310 #endif
311 }
312 
314 {
315 
316  assert(r.dim() == m_colscale.size());
317 #ifdef BITSHIFTSCALING
318  int exp1;
319  for(int j = 0; j < r.dim(); ++j)
320  {
321  spxFrexp(m_colscale[j], &exp1);
322  r[j] = spxLdexp(r[j], -exp1 + 1);
323  }
324 #else
325  for(int j = 0; j < r.dim(); ++j)
326  r[j] /= m_colscale[j];
327 #endif
328 }
329 
331 {
332 
333  Real mini = infinity;
334 
335  for(int i = 0; i < m_colscale.size(); ++i)
336  if (spxAbs(m_colscale[i]) < mini)
337  mini = spxAbs(m_colscale[i]);
338 #ifdef BITSHIFTSCALING
339  int exp;
340  spxFrexp(mini, &exp);
341  mini = spxLdexp(2.0, exp - 1);
342 #endif
343  return mini;
344 }
345 
347 {
348 
349  Real maxi = 0.0;
350 
351  for(int i = 0; i < m_colscale.size(); ++i)
352  if (spxAbs(m_colscale[i]) > maxi)
353  maxi = spxAbs(m_colscale[i]);
354 
355 #ifdef BITSHIFTSCALING
356  int exp;
357  spxFrexp(maxi, &exp);
358  maxi = spxLdexp(2.0, exp - 1);
359 #endif
360  return maxi;
361 }
362 
364 {
365 
366  Real mini = infinity;
367 
368  for(int i = 0; i < m_rowscale.size(); ++i)
369  if (spxAbs(m_rowscale[i]) < mini)
370  mini = spxAbs(m_rowscale[i]);
371 #ifdef BITSHIFTSCALING
372  int exp;
373  spxFrexp(mini, &exp);
374  mini = spxLdexp(2.0, exp - 1);
375 #endif
376  return mini;
377 }
378 
380 {
381 
382  Real maxi = 0.0;
383 
384  for(int i = 0; i < m_rowscale.size(); ++i)
385  if (spxAbs(m_rowscale[i]) > maxi)
386  maxi = spxAbs(m_rowscale[i]);
387 #ifdef BITSHIFTSCALING
388  int exp;
389  spxFrexp(maxi, &exp);
390  maxi = spxLdexp(2.0, exp - 1);
391 #endif
392  return maxi;
393 }
394 
395 /** \f$\max_{j\in\mbox{ cols}}
396  * \left(\frac{\max_{i\in\mbox{ rows}}|a_ij|}
397  * {\min_{i\in\mbox{ rows}}|a_ij|}\right)\f$
398  */
400 {
401 
402  Real pmax = 0.0;
403 
404  for(int i = 0; i < lp.nCols(); ++i )
405  {
406  const SVector& vec = lp.colVector(i);
407  Real mini = infinity;
408  Real maxi = 0.0;
409 
410  for(int j = 0; j < vec.size(); ++j)
411  {
412  Real x = spxAbs(vec.value(j));
413 
414  if (x < mini)
415  mini = x;
416  if (x > maxi)
417  maxi = x;
418  }
419  Real p = maxi / mini;
420 
421  if (p > pmax)
422  pmax = p;
423  }
424  return pmax;
425 }
426 
427 /** \f$\max_{i\in\mbox{ rows}}
428  * \left(\frac{\max_{j\in\mbox{ cols}}|a_ij|}
429  * {\min_{j\in\mbox{ cols}}|a_ij|}\right)\f$
430  */
432 {
433 
434  Real pmax = 0.0;
435 
436  for(int i = 0; i < lp.nRows(); ++i )
437  {
438  const SVector& vec = lp.rowVector(i);
439  Real mini = infinity;
440  Real maxi = 0.0;
441 
442  for(int j = 0; j < vec.size(); ++j)
443  {
444  Real x = spxAbs(vec.value(j));
445 
446  if (x < mini)
447  mini = x;
448  if (x > maxi)
449  maxi = x;
450  }
451  Real p = maxi / mini;
452 
453  if (p > pmax)
454  pmax = p;
455  }
456  return pmax;
457 }
458 
460 {
461 #ifdef ENABLE_CONSISTENCY_CHECKS
462 
464 #else
465  return true;
466 #endif
467 }
468 
469 } // namespace soplex
Rational spxAbs(const Rational &r)
Absolute.
Definition: rational.cpp:3925
virtual void setBoth(bool both)
set wether column and row scaling should be performed.
Definition: spxscaler.cpp:109
virtual void setOrder(bool colFirst)
set scaling order.
Definition: spxscaler.cpp:103
virtual void unscaleSlacks(Vector &s) const
unscale dense slack vector given in s.
Definition: spxscaler.cpp:279
R & maxObj_w(int i)
Returns objective value of column i for maximization problem.
Definition: spxlpbase.h:1824
const SVectorBase< R > & colVector(int i) const
Returns column vector of column i.
Definition: spxlpbase.h:341
int size() const
Number of used indices.
Definition: svectorbase.h:152
const VectorBase< R > & lower() const
Returns lower bound vector.
Definition: spxlpbase.h:420
virtual void unscaleDual(Vector &pi) const
unscale dense dual solution vector given in pi.
Definition: spxscaler.cpp:296
R & value(int n)
Reference to value of n &#39;th nonzero.
Definition: svectorbase.h:254
virtual void applyScaling(SPxLP &lp)
applies m_colscale and m_rowscale to the lp.
Definition: spxscaler.cpp:186
virtual ~SPxScaler()
destructor.
Definition: spxscaler.cpp:75
R & rhs_w(int i)
Returns right hand side of row i.
Definition: spxlpbase.h:1806
virtual Real maxColRatio(const SPxLP &lp) const
maximum ratio between absolute biggest and smallest element in any column.
Definition: spxscaler.cpp:399
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 VectorBase< R > & upper() const
Returns upper bound vector.
Definition: spxlpbase.h:402
SVectorBase< R > & rowVector_w(int i)
Definition: spxlpbase.h:2036
Real spxFrexp(Real y, int *exp)
Definition: spxdefines.h:349
bool isConsistent() const
consistency check
Definition: dataarray.h:288
int num() const
Current number of SVectorBases.
Definition: svsetbase.h:746
Real spxLdexp(Real x, int exp)
returns x * 2^exp
Definition: spxdefines.h:343
double Real
SOPLEX_DEBUG.
Definition: spxdefines.h:200
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
int & index(int n)
Reference to index of n &#39;th nonzero.
Definition: svectorbase.h:236
std::ostream & operator<<(std::ostream &s, const VectorBase< R > &vec)
Output operator.
Definition: basevectors.h:1087
Wrapper for several output streams. A verbosity level is used to decide which stream to use and wheth...
Definition: spxout.h:63
int nCols() const
Returns number of columns in LP.
Definition: spxlpbase.h:133
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
int size() const
return nr. of elements.
Definition: dataarray.h:211
R & lower_w(int i)
Returns lower bound of column i.
Definition: spxlpbase.h:1836
virtual void unscalePrimal(Vector &x) const
unscale dense primal solution vector given in x.
Definition: spxscaler.cpp:262
virtual bool isConsistent() const
consistency check
Definition: spxscaler.cpp:459
int dim() const
Dimension of vector.
Definition: vectorbase.h:174
virtual Real computeScale(Real mini, Real maxi) const
computes scaling value for a minimum and maximum pair.
Definition: spxscaler.cpp:134
DataArray< Real > m_rowscale
row scaling factors
Definition: spxscaler.h:48
int nRows() const
Returns number of rows in LP.
Definition: spxlpbase.h:127
virtual void unscaleRedCost(Vector &r) const
unscale dense reduced cost vector given in r.
Definition: spxscaler.cpp:313
const VectorBase< R > & lhs() const
Returns left hand side vector.
Definition: spxlpbase.h:242
Everything should be within this namespace.
bool isConsistent() const
Consistency check.
Definition: spxlpbase.h:1753
R & upper_w(int i)
Returns upper bound of column i.
Definition: spxlpbase.h:1830
bool m_colFirst
do column scaling first
Definition: spxscaler.h:49
LP scaling base class.
SPxScaler(const char *name, bool colFirst=false, bool doBoth=true, SPxOut *spxout=NULL)
constructor
Definition: spxscaler.cpp:51
Saving LPs in a form suitable for SoPlex.
LP scaler abstract base class.Instances of classes derived from SPxScaler may be loaded to SoPlex in ...
Definition: spxscaler.h:39
const Real infinity
Definition: spxdefines.cpp:26
const VectorBase< R > & rhs() const
Returns right hand side vector.
Definition: spxlpbase.h:224
virtual void setup(SPxLP &lp)
setup scale array for the LP.
Definition: spxscaler.cpp:115
const SVectorBase< R > & rowVector(int i) const
Gets row vector of row i.
Definition: spxlpbase.h:212
virtual Real minAbsRowscale() const
absolute smallest row scaling factor
Definition: spxscaler.cpp:363
bool isZero(Real a, Real eps=Param::epsilon())
returns true iff |a| <= eps
Definition: spxdefines.h:407
bool m_doBoth
do columns and rows
Definition: spxscaler.h:50
SVectorBase< R > & colVector_w(int i)
Returns the LP as an LPRowSet.
Definition: spxlpbase.h:2030
virtual const char * getName() const
get name of scaler.
Definition: spxscaler.cpp:97
virtual Real maxAbsColscale() const
absolute biggest column scaling factor
Definition: spxscaler.cpp:346
void reSize(int newsize)
reset size to newsize.
Definition: dataarray.h:223
const char * m_name
Name of the scaler.
Definition: spxscaler.h:46
SPxScaler & operator=(const SPxScaler &)
assignment operator
Definition: spxscaler.cpp:80
R & lhs_w(int i)
Returns left hand side of row i.
Definition: spxlpbase.h:1812