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-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.cpp
17  * @brief LP scaling base class.
18  */
19 
20 #include <cmath>
21 
22 #include <iostream>
23 #include <assert.h>
24 
25 #include "spxscaler.h"
26 #include "spxlp.h"
27 #include "dsvector.h"
28 #include "dvector.h"
29 
30 namespace soplex
31 {
32 
33 std::ostream& operator<<(std::ostream& s, const SPxScaler& sc)
34 {
35  const DataArray < int >& colscaleExp = *(sc.m_activeColscaleExp);
36  DataArray < int > rowccaleExp = *(sc.m_activeRowscaleExp);
37 
38  s << sc.getName() << " scaler:" << std::endl;
39  s << "colscale = [ ";
40  for(int ci = 0; ci < colscaleExp.size(); ++ci )
41  s << colscaleExp[ci] << " ";
42  s << "]" << std::endl;
43 
44  s << "rowscale = [ ";
45  for(int ri = 0; ri < rowccaleExp.size(); ++ri )
46  s << rowccaleExp[ri] << " ";
47  s << "]" << std::endl;
48 
49  return s;
50 }
51 
52 
53 SPxScaler::SPxScaler(
54  const char* name,
55  bool colFirst,
56  bool doBoth,
57  SPxOut* outstream)
58  : m_name(name)
59  , m_activeColscaleExp(0)
60  , m_activeRowscaleExp(0)
61  , m_colFirst(colFirst)
62  , m_doBoth(doBoth)
63  , spxout(outstream)
64 {
65  assert(SPxScaler::isConsistent());
66 }
67 
68 SPxScaler::SPxScaler(const SPxScaler& old)
69  : m_name(old.m_name)
70  , m_activeColscaleExp(old.m_activeColscaleExp)
71  , m_activeRowscaleExp(old.m_activeRowscaleExp)
72  , m_colFirst(old.m_colFirst)
73  , m_doBoth(old.m_doBoth)
74  , spxout(old.spxout)
75 {
76  assert(SPxScaler::isConsistent());
77 }
78 
79 SPxScaler::~SPxScaler()
80 {
81  m_name = 0;
82 }
83 
84 SPxScaler& SPxScaler::operator=(const SPxScaler& rhs)
85 {
86  if (this != &rhs)
87  {
88  m_name = rhs.m_name;
89  m_activeColscaleExp = rhs.m_activeColscaleExp;
90  m_activeRowscaleExp = rhs.m_activeRowscaleExp;
91  m_colFirst = rhs.m_colFirst;
92  m_doBoth = rhs.m_doBoth;
93  spxout = rhs.spxout;
94 
95  assert(SPxScaler::isConsistent());
96  }
97  return *this;
98 }
99 
100 const char* SPxScaler::getName() const
101 {
102 
103  return m_name;
104 }
105 
106 void SPxScaler::setOrder(bool colFirst)
107 {
108 
109  m_colFirst = colFirst;
110 }
111 
112 void SPxScaler::setBoth(bool both)
113 {
114 
115  m_doBoth = both;
116 }
117 
118 void SPxScaler::setRealParam(Real param, const char* name)
119 {}
120 
121 void SPxScaler::setIntParam(int param, const char* name)
122 {}
123 
124 void SPxScaler::setup(SPxLP& lp)
125 {
126  assert(lp.isConsistent());
127  m_activeColscaleExp = &lp.LPColSetBase<Real>::scaleExp;
128  m_activeRowscaleExp = &lp.LPRowSetBase<Real>::scaleExp;
129  m_activeColscaleExp->reSize(lp.nCols());
130  m_activeRowscaleExp->reSize(lp.nRows());
131 
132  for( int i = 0; i < lp.nCols(); ++i)
133  (*m_activeColscaleExp)[i] = 0;
134  for( int i = 0; i < lp.nRows(); ++i)
135  (*m_activeRowscaleExp)[i] = 0;
136 
137  lp.lp_scaler = this;
138 }
139 
140 int SPxScaler::computeScaleExp(const SVector& vec, const DataArray<int>& oldScaleExp) const
141 {
142  Real maxi = 0.0;
143 
144  // find largest absolute value after applying existing scaling factors
145  for( int i = 0; i < vec.size(); ++i )
146  {
147  Real x = spxAbs(spxLdexp(vec.value(i), oldScaleExp[vec.index(i)]));
148 
149  if( GT(x, maxi) )
150  maxi = x;
151  }
152  // empty rows/cols are possible
153  if( maxi == 0.0 )
154  return 0;
155  // get exponent corresponding to new scaling factor
156  else
157  {
158  int scaleExp;
159  spxFrexp(1.0 / maxi, &(scaleExp));
160  return scaleExp - 1;
161  }
162 }
163 
164 #ifndef SOPLEX_LEGACY
165 int SPxScaler::computeScaleExp(const SVectorBase<Rational>& vec, const DataArray<int>& oldScaleExp) const
166 {
167  return 0;
168 }
169 #endif
170 
171 void SPxScaler::applyScaling(SPxLPBase<Real>& lp)
172 {
173  assert(lp.nCols() == m_activeColscaleExp->size());
174  assert(lp.nRows() == m_activeRowscaleExp->size());
175 
176  DataArray < int >& colscaleExp = lp.LPColSetBase<Real>::scaleExp;
177  DataArray < int >& rowscaleExp = lp.LPRowSetBase<Real>::scaleExp;
178 
179  for( int i = 0; i < lp.nRows(); ++i )
180  {
181  SVector& vec = lp.rowVector_w(i);
182  int exp1;
183  int exp2 = rowscaleExp[i];
184 
185  for( int j = 0; j < vec.size(); ++j)
186  {
187  exp1 = colscaleExp[vec.index(j)];
188  vec.value(j) = spxLdexp(vec.value(j), exp1 + exp2);
189  }
190 
191  lp.maxRowObj_w(i) = spxLdexp(lp.maxRowObj(i), exp2);
192 
193  if( lp.rhs(i) < infinity )
194  lp.rhs_w(i) = spxLdexp(lp.rhs_w(i), exp2);
195 
196  if( lp.lhs(i) > -infinity )
197  lp.lhs_w(i) = spxLdexp(lp.lhs_w(i), exp2);
198 
199  MSG_DEBUG( std::cout << "DEBUG: rowscaleExp(" << i << "): " << exp2 << std::endl; )
200  }
201 
202  for( int i = 0; i < lp.nCols(); ++i )
203  {
204  SVector& vec = lp.colVector_w(i);
205  int exp1;
206  int exp2 = colscaleExp[i];
207 
208  for( int j = 0; j < vec.size(); ++j)
209  {
210  exp1 = rowscaleExp[vec.index(j)];
211  vec.value(j) = spxLdexp(vec.value(j), exp1 + exp2);
212  }
213 
214  lp.maxObj_w(i) = spxLdexp(lp.maxObj_w(i), exp2);
215 
216  if( lp.upper(i) < infinity )
217  lp.upper_w(i) = spxLdexp(lp.upper_w(i), -exp2);
218 
219  if( lp.lower(i) > -infinity )
220  lp.lower_w(i) = spxLdexp(lp.lower_w(i), -exp2);
221 
222  MSG_DEBUG( std::cout << "DEBUG: colscaleExp(" << i << "): " << exp2 << std::endl; )
223  }
224 
225  lp.setScalingInfo(true);
226  assert(lp.isConsistent());
227 }
228 
229 /// unscale SPxLP
230 void SPxScaler::unscale(SPxLPBase<Real>& lp)
231 {
232  assert(lp.isScaled());
233 
234  const DataArray < int >& colscaleExp = lp.LPColSetBase<Real>::scaleExp;
235  const DataArray < int >& rowscaleExp = lp.LPRowSetBase<Real>::scaleExp;
236 
237  for( int i = 0; i < lp.nRows(); ++i )
238  {
239  SVector& vec = lp.rowVector_w(i);
240 
241  int exp1;
242  int exp2 = rowscaleExp[i];
243 
244  for( int j = 0; j < vec.size(); ++j)
245  {
246  exp1 = colscaleExp[vec.index(j)];
247  vec.value(j) = spxLdexp(vec.value(j), -exp1 - exp2);
248  }
249 
250  lp.maxRowObj_w(i) = spxLdexp(lp.maxRowObj(i), -exp2);
251 
252  if( lp.rhs(i) < infinity )
253  lp.rhs_w(i) = spxLdexp(lp.rhs_w(i), -exp2);
254 
255  if( lp.lhs(i) > -infinity )
256  lp.lhs_w(i) = spxLdexp(lp.lhs_w(i), -exp2);
257  }
258 
259  for( int i = 0; i < lp.nCols(); ++i )
260  {
261  SVector& vec = lp.colVector_w(i);
262 
263  int exp1;
264  int exp2 = colscaleExp[i];
265 
266  for( int j = 0; j < vec.size(); ++j)
267  {
268  exp1 = rowscaleExp[vec.index(j)];
269  vec.value(j) = spxLdexp(vec.value(j), -exp1 - exp2);
270  }
271 
272  lp.maxObj_w(i) = spxLdexp(lp.maxObj_w(i), -exp2);
273 
274  if( lp.upper(i) < infinity )
275  lp.upper_w(i) = spxLdexp(lp.upper_w(i), exp2);
276 
277  if( lp.lower(i) > -infinity )
278  lp.lower_w(i) = spxLdexp(lp.lower_w(i), exp2);
279  }
280 
281  lp._isScaled = false;
282  assert(lp.isConsistent());
283 }
284 
285 /// returns scaling factor for column \p i
286 /// todo pass the LP?!
287 int SPxScaler::getColScaleExp(int i) const
288 {
289  return (*m_activeColscaleExp)[i];
290 }
291 
292 /// returns scaling factor for row \p i
293 /// todo pass the LP?!
294 int SPxScaler::getRowScaleExp(int i) const
295 {
296  return (*m_activeRowscaleExp)[i];
297 }
298 
299 
300 /// gets unscaled column \p i
301 void SPxScaler::getColUnscaled(const SPxLP& lp, int i, DSVector& vec) const
302 {
303  assert(lp.isScaled());
304  assert(i < lp.nCols());
305  assert(i >= 0);
306  const DataArray < int >& colscaleExp = lp.LPColSetBase<Real>::scaleExp;
307  const DataArray < int >& rowscaleExp = lp.LPRowSetBase<Real>::scaleExp;
308 
309  vec = lp.LPColSet::colVector(i);
310 
311  int exp1;
312  int exp2 = colscaleExp[i];
313 
314  const SVectorReal& col = lp.colVector(i);
315  vec.setMax(col.size());
316  vec.clear();
317 
318  for( int j = 0; j < col.size(); j++ )
319  {
320  exp1 = rowscaleExp[col.index(j)];
321  vec.add(col.index(j), spxLdexp(col.value(j), -exp1 - exp2));
322  }
323 }
324 
325 /// returns maximum absolute value of unscaled column \p i
326 Real SPxScaler::getColMaxAbsUnscaled(const SPxLP& lp, int i) const
327 {
328  assert(i < lp.nCols());
329  assert(i >= 0);
330 
331  DataArray < int >& colscaleExp = *m_activeColscaleExp;
332  DataArray < int >& rowscaleExp = *m_activeRowscaleExp;
333  const SVector& colVec = lp.LPColSet::colVector(i);
334 
335  Real max = 0.0;
336  int exp1;
337  int exp2 = colscaleExp[i];
338 
339  for( int j = 0; j < colVec.size(); j++ )
340  {
341  exp1 = rowscaleExp[colVec.index(j)];
342  Real abs = spxAbs(spxLdexp(colVec.value(j), -exp1 - exp2));
343  if( abs > max )
344  max = abs;
345  }
346 
347  return max;
348 }
349 
350 /// returns minimum absolute value of unscaled column \p i
351 Real SPxScaler::getColMinAbsUnscaled(const SPxLP& lp, int i) const
352 {
353  assert(i < lp.nCols());
354  assert(i >= 0);
355 
356  DataArray < int >& colscaleExp = *m_activeColscaleExp;
357  DataArray < int >& rowscaleExp = *m_activeRowscaleExp;
358  const SVector& colVec = lp.LPColSet::colVector(i);
359 
360  Real min = infinity;
361  int exp1;
362  int exp2 = colscaleExp[i];
363 
364  for( int j = 0; j < colVec.size(); j++ )
365  {
366  exp1 = rowscaleExp[colVec.index(j)];
367  Real abs = spxAbs(spxLdexp(colVec.value(j), -exp1 - exp2));
368  if( abs < min )
369  min = abs;
370  }
371 
372  return min;
373 }
374 
375 
376 /// returns unscaled upper bound \p i
377 Real SPxScaler::upperUnscaled(const SPxLPBase<Real>& lp, int i) const
378 {
379  assert(lp.isScaled());
380  assert(i < lp.nCols());
381  assert(i >= 0);
382 
383  if( lp.LPColSet::upper(i) < infinity )
384  {
385  const DataArray < int >& colscaleExp = lp.LPColSetBase<Real>::scaleExp;
386  return spxLdexp(lp.LPColSet::upper(i) , colscaleExp[i]);
387  }
388  else
389  return lp.LPColSet::upper(i);
390 }
391 
392 
393 /// gets unscaled upper bound vector
394 void SPxScaler::getUpperUnscaled(const SPxLPBase<Real>& lp, Vector& vec) const
395 {
396  assert(lp.isScaled());
397  assert(lp.LPColSet::upper().dim() == vec.dim());
398 
399  const DataArray < int >& colscaleExp = lp.LPColSetBase<Real>::scaleExp;
400 
401  for( int i = 0; i < lp.LPColSet::upper().dim(); i++)
402  vec[i] = spxLdexp(lp.LPColSet::upper()[i], colscaleExp[i]);
403 }
404 
405 
406 /// returns unscaled upper bound vector of \p lp
407 Real SPxScaler::lowerUnscaled(const SPxLPBase<Real>& lp, int i) const
408 {
409  assert(lp.isScaled());
410  assert(i < lp.nCols());
411  assert(i >= 0);
412 
413  if( lp.LPColSet::lower(i) > -infinity )
414  {
415  const DataArray < int >& colscaleExp = lp.LPColSetBase<Real>::scaleExp;
416  return spxLdexp(lp.LPColSet::lower(i), colscaleExp[i]);
417  }
418  else
419  return lp.LPColSet::lower(i);
420 }
421 
422 
423 /// returns unscaled lower bound vector of \p lp
424 void SPxScaler::getLowerUnscaled(const SPxLPBase<Real>& lp, Vector& vec) const
425 {
426  assert(lp.isScaled());
427  assert(lp.LPColSet::lower().dim() == vec.dim());
428 
429  const DataArray < int >& colscaleExp = lp.LPColSetBase<Real>::scaleExp;
430 
431  for( int i = 0; i < lp.LPColSet::lower().dim(); i++)
432  vec[i] = spxLdexp(lp.LPColSet::lower()[i], colscaleExp[i]);
433 }
434 
435 /// returns unscaled objective function coefficient of \p i
436 Real SPxScaler::maxObjUnscaled(const SPxLPBase<Real>& lp, int i) const
437 {
438  assert(lp.isScaled());
439  assert(i < lp.nCols());
440  assert(i >= 0);
441 
442  const DataArray < int >& colscaleExp = lp.LPColSetBase<Real>::scaleExp;
443 
444  return spxLdexp(lp.LPColSet::maxObj(i) , -colscaleExp[i]);
445 }
446 
447 
448 /// gets unscaled objective function coefficient of \p i
449 void SPxScaler::getMaxObjUnscaled(const SPxLPBase<Real>& lp, Vector& vec) const
450 {
451  assert(lp.isScaled());
452  assert(lp.LPColSet::maxObj().dim() == vec.dim());
453 
454  const DataArray < int >& colscaleExp = lp.LPColSetBase<Real>::scaleExp;
455 
456  for( int i = 0; i < lp.LPColSet::maxObj().dim(); i++)
457  vec[i] = spxLdexp(lp.LPColSet::maxObj()[i], -colscaleExp[i]);
458 }
459 
460 /// gets unscaled row \p i
461 void SPxScaler::getRowUnscaled(const SPxLP& lp, int i, DSVector& vec) const
462 {
463  assert(lp.isScaled());
464  assert(i < lp.nRows());
465  assert(i >= 0);
466 
467  const DataArray < int >& colscaleExp = lp.LPColSetBase<Real>::scaleExp;
468  const DataArray < int >& rowscaleExp = lp.LPRowSetBase<Real>::scaleExp;
469  int exp1;
470  int exp2 = rowscaleExp[i];
471 
472  const SVectorReal& row = lp.rowVector(i);
473  vec.setMax(row.size());
474  vec.clear();
475 
476  for( int j = 0; j < row.size(); j++ )
477  {
478  exp1 = colscaleExp[row.index(j)];
479  vec.add(row.index(j), spxLdexp(row.value(j), -exp1 - exp2));
480  }
481 }
482 
483 /// returns maximum absolute value of unscaled row \p i
484 Real SPxScaler::getRowMaxAbsUnscaled(const SPxLP& lp, int i) const
485 {
486  assert(i < lp.nRows());
487  assert(i >= 0);
488  DataArray < int >& colscaleExp = *m_activeColscaleExp;
489  DataArray < int >& rowscaleExp = *m_activeRowscaleExp;
490  const SVector& rowVec = lp.LPRowSet::rowVector(i);
491 
492  Real max = 0.0;
493 
494  int exp1;
495  int exp2 = rowscaleExp[i];
496 
497  for( int j = 0; j < rowVec.size(); j++ )
498  {
499  exp1 = colscaleExp[rowVec.index(j)];
500  Real abs = spxAbs(spxLdexp(rowVec.value(j), -exp1 - exp2));
501 
502  if( GT(abs, max) )
503  max = abs;
504  }
505 
506  return max;
507 }
508 
509 /// returns minimum absolute value of unscaled row \p i
510 Real SPxScaler::getRowMinAbsUnscaled(const SPxLP& lp, int i) const
511 {
512  assert(i < lp.nRows());
513  assert(i >= 0);
514  DataArray < int >& colscaleExp = *m_activeColscaleExp;
515  DataArray < int >& rowscaleExp = *m_activeRowscaleExp;
516  const SVector& rowVec = lp.LPRowSet::rowVector(i);
517 
518  Real min = infinity;
519 
520  int exp1;
521  int exp2 = rowscaleExp[i];
522 
523  for( int j = 0; j < rowVec.size(); j++ )
524  {
525  exp1 = colscaleExp[rowVec.index(j)];
526  Real abs = spxAbs(spxLdexp(rowVec.value(j), -exp1 - exp2));
527 
528  if( LT(abs, min) )
529  min = abs;
530  }
531 
532  return min;
533 }
534 
535 /// returns unscaled right hand side \p i
536 Real SPxScaler::rhsUnscaled(const SPxLPBase<Real>& lp, int i) const
537 {
538  assert(lp.isScaled());
539  assert(i < lp.nRows());
540  assert(i >= 0);
541 
542  if( lp.LPRowSet::rhs(i) < infinity )
543  {
544  const DataArray < int >& rowscaleExp = lp.LPRowSetBase<Real>::scaleExp;
545  return spxLdexp(lp.LPRowSet::rhs(i) , -rowscaleExp[i]);
546  }
547  else
548  return lp.LPRowSet::rhs(i);
549 }
550 
551 
552 /// gets unscaled right hand side vector
553 void SPxScaler::getRhsUnscaled(const SPxLPBase<Real>& lp, Vector& vec) const
554 {
555  assert(lp.isScaled());
556  assert(lp.LPRowSet::rhs().dim() == vec.dim());
557 
558  for( int i = 0; i < lp.LPRowSet::rhs().dim(); i++)
559  {
560  const DataArray < int >& rowscaleExp = lp.LPRowSetBase<Real>::scaleExp;
561  vec[i] = spxLdexp(lp.LPRowSet::rhs()[i], -rowscaleExp[i]);
562  }
563 }
564 
565 
566 /// returns unscaled left hand side \p i of \p lp
567 Real SPxScaler::lhsUnscaled(const SPxLPBase<Real>& lp, int i) const
568 {
569  assert(lp.isScaled());
570  assert(i < lp.nRows());
571  assert(i >= 0);
572 
573  if( lp.LPRowSet::lhs(i) > -infinity )
574  {
575  const DataArray < int >& rowscaleExp = lp.LPRowSetBase<Real>::scaleExp;
576  return spxLdexp(lp.LPRowSet::lhs(i) , -rowscaleExp[i]);
577  }
578  else
579  return lp.LPRowSet::lhs(i);
580 }
581 
582 /// returns unscaled left hand side vector of \p lp
583 void SPxScaler::getLhsUnscaled(const SPxLPBase<Real>& lp, Vector& vec) const
584 {
585  assert(lp.isScaled());
586  assert(lp.LPRowSet::lhs().dim() == vec.dim());
587 
588  const DataArray < int >& rowscaleExp = lp.LPRowSetBase<Real>::scaleExp;
589 
590  for( int i = 0; i < lp.LPRowSet::lhs().dim(); i++)
591  vec[i] = spxLdexp(lp.LPRowSet::lhs()[i], -rowscaleExp[i]);
592 }
593 
594 /// returns unscaled coefficient of \p lp
595 Real SPxScaler::getCoefUnscaled(const SPxLPBase<Real>& lp, int row, int col) const
596 {
597  assert(lp.isScaled());
598  assert(row < lp.nRows());
599  assert(col < lp.nCols());
600 
601  const DataArray < int >& rowscaleExp = lp.LPRowSetBase<Real>::scaleExp;
602  const DataArray < int >& colscaleExp = lp.LPColSetBase<Real>::scaleExp;
603 
604  return spxLdexp(lp.colVector(col)[row], - rowscaleExp[row] - colscaleExp[col]);
605 }
606 
607 
608 
609 void SPxScaler::unscalePrimal(const SPxLPBase<Real>& lp, Vector& x) const
610 {
611  assert(lp.isScaled());
612 
613  const DataArray < int >& colscaleExp = lp.LPColSetBase<Real>::scaleExp;
614 
615  assert(x.dim() == colscaleExp.size());
616 
617  for( int j = 0; j < x.dim(); ++j )
618  x[j] = spxLdexp(x[j], colscaleExp[j]);
619 }
620 
621 void SPxScaler::unscaleSlacks(const SPxLPBase<Real>& lp, Vector& s) const
622 {
623  assert(lp.isScaled());
624 
625  const DataArray < int >& rowscaleExp = lp.LPRowSetBase<Real>::scaleExp;
626 
627  assert(s.dim() == rowscaleExp.size());
628 
629  for( int i = 0; i < s.dim(); ++i )
630  s[i] = spxLdexp(s[i], -rowscaleExp[i]);
631 }
632 
633 void SPxScaler::unscaleDual(const SPxLPBase<Real>& lp, Vector& pi) const
634 {
635  assert(lp.isScaled());
636 
637  const DataArray < int >& rowscaleExp = lp.LPRowSetBase<Real>::scaleExp;
638 
639  assert(pi.dim() == rowscaleExp.size());
640 
641  for( int i = 0; i < pi.dim(); ++i )
642  pi[i] = spxLdexp(pi[i], rowscaleExp[i]);
643 }
644 
645 void SPxScaler::unscaleRedCost(const SPxLPBase<Real>& lp, Vector& r) const
646 {
647  assert(lp.isScaled());
648 
649  const DataArray < int >& colscaleExp = lp.LPColSetBase<Real>::scaleExp;
650 
651  assert(r.dim() == colscaleExp.size());
652 
653  for( int j = 0; j < r.dim(); ++j )
654  r[j] = spxLdexp(r[j], -colscaleExp[j]);
655 }
656 
657 void SPxScaler::unscalePrimalray(const SPxLPBase<Real>& lp, Vector& ray) const
658 {
659  assert(lp.isScaled());
660 
661  const DataArray < int >& colscaleExp = lp.LPColSetBase<Real>::scaleExp;
662 
663  assert(ray.dim() == colscaleExp.size());
664 
665  for( int j = 0; j < ray.dim(); ++j )
666  ray[j] = spxLdexp(ray[j], colscaleExp[j]);
667 }
668 
669 void SPxScaler::unscaleDualray(const SPxLPBase<Real>& lp, Vector& ray) const
670 {
671  assert(lp.isScaled());
672 
673  const DataArray < int >& rowscaleExp = lp.LPRowSetBase<Real>::scaleExp;
674 
675  assert(ray.dim() == rowscaleExp.size());
676 
677  for( int i = 0; i < ray.dim(); ++i )
678  ray[i] = spxLdexp(ray[i], rowscaleExp[i]);
679 }
680 
681 void SPxScaler::scaleObj(const SPxLPBase<Real>& lp, VectorReal& origObj) const
682 {
683  assert(lp.isScaled());
684 
685  const DataArray < int >& colscaleExp = lp.LPColSetBase<Real>::scaleExp;
686 
687  for( int i = 0; i < origObj.dim(); ++i )
688  {
689  origObj[i] = spxLdexp(origObj[i], colscaleExp[i]);
690  }
691 }
692 
693 Real SPxScaler::scaleObj(const SPxLPBase<Real>& lp, int i, Real origObj) const
694 {
695  assert(lp.isScaled());
696  assert(i < lp.nCols());
697  assert(i >= 0);
698 
699  const DataArray < int >& colscaleExp = lp.LPColSetBase<Real>::scaleExp;
700  int exp = colscaleExp[i];
701 
702  return spxLdexp(origObj, exp);
703 }
704 
705 Real SPxScaler::scaleElement(const SPxLPBase<Real>& lp, int row, int col, Real val) const
706 {
707  assert(lp.isScaled());
708  assert(col < lp.nCols());
709  assert(col >= 0);
710  assert(row < lp.nRows());
711  assert(row >= 0);
712 
713  const DataArray < int >& colscaleExp = lp.LPColSetBase<Real>::scaleExp;
714  const DataArray < int >& rowscaleExp = lp.LPRowSetBase<Real>::scaleExp;
715 
716  return spxLdexp(val, colscaleExp[col] + rowscaleExp[row]);
717 }
718 
719 Real SPxScaler::scaleLower(const SPxLPBase<Real>& lp, int col, Real lower) const
720 {
721  assert(lp.isScaled());
722  assert(col < lp.nCols());
723  assert(col >= 0);
724 
725  const DataArray < int >& colscaleExp = lp.LPColSetBase<Real>::scaleExp;
726 
727  return spxLdexp(lower, -colscaleExp[col]);
728 }
729 
730 Real SPxScaler::scaleUpper(const SPxLPBase<Real>& lp, int col, Real upper) const
731 {
732  assert(lp.isScaled());
733  assert(col < lp.nCols());
734  assert(col >= 0);
735 
736  const DataArray < int >& colscaleExp = lp.LPColSetBase<Real>::scaleExp;
737 
738  return spxLdexp(upper, -colscaleExp[col]);
739 }
740 
741 Real SPxScaler::scaleLhs(const SPxLPBase<Real>& lp, int row, Real lhs) const
742 {
743  assert(lp.isScaled());
744  assert(row < lp.nRows());
745  assert(row >= 0);
746 
747  const DataArray < int >& rowscaleExp = lp.LPRowSetBase<Real>::scaleExp;
748 
749  return spxLdexp(lhs, rowscaleExp[row]);
750 }
751 
752 Real SPxScaler::scaleRhs(const SPxLPBase<Real>& lp, int row, Real rhs) const
753 {
754  assert(lp.isScaled());
755  assert(row < lp.nRows());
756  assert(row >= 0);
757 
758  const DataArray < int >& rowscaleExp = lp.LPRowSetBase<Real>::scaleExp;
759 
760  return spxLdexp(rhs, rowscaleExp[row]);
761 }
762 
763 Real SPxScaler::minAbsColscale() const
764 {
765  const DataArray < int >& colscaleExp = *m_activeColscaleExp;
766 
767  Real mini = infinity;
768 
769  for( int i = 0; i < colscaleExp.size(); ++i )
770  if( spxAbs(spxLdexp(1.0, colscaleExp[i])) < mini )
771  mini = spxAbs(spxLdexp(1.0, colscaleExp[i]));
772 
773  return mini;
774 }
775 
776 Real SPxScaler::maxAbsColscale() const
777 {
778  const DataArray < int >& colscaleExp = *m_activeColscaleExp;
779 
780  Real maxi = 0.0;
781 
782  for( int i = 0; i < colscaleExp.size(); ++i )
783  if( spxAbs(spxLdexp(1.0, colscaleExp[i])) > maxi )
784  maxi = spxAbs(spxLdexp(1.0, colscaleExp[i]));
785 
786 
787  return maxi;
788 }
789 
790 Real SPxScaler::minAbsRowscale() const
791 {
792  const DataArray < int >& rowscaleExp = *m_activeRowscaleExp;
793 
794  int mini = INT_MAX;
795 
796  for( int i = 0; i < rowscaleExp.size(); ++i )
797  if( rowscaleExp[i] < mini )
798  mini = rowscaleExp[i];
799 
800  return spxLdexp(1.0, mini);
801 }
802 
803 Real SPxScaler::maxAbsRowscale() const
804 {
805  const DataArray < int >& rowscaleExp = *m_activeRowscaleExp;
806 
807  int maxi = -INT_MAX;
808 
809  for( int i = 0; i < rowscaleExp.size(); ++i )
810  if( rowscaleExp[i] > maxi )
811  maxi = rowscaleExp[i];
812 
813  return spxLdexp(1.0, maxi);
814 }
815 
816 /** \f$\max_{j\in\mbox{ cols}}
817  * \left(\frac{\max_{i\in\mbox{ rows}}|a_ij|}
818  * {\min_{i\in\mbox{ rows}}|a_ij|}\right)\f$
819  */
820 Real SPxScaler::maxColRatio(const SPxLP& lp) const
821 {
822 
823  Real pmax = 0.0;
824 
825  for(int i = 0; i < lp.nCols(); ++i )
826  {
827  const SVector& vec = lp.colVector(i);
828  Real mini = infinity;
829  Real maxi = 0.0;
830 
831  for(int j = 0; j < vec.size(); ++j)
832  {
833  Real x = spxAbs(vec.value(j));
834 
835  if( isZero(x) )
836  continue;
837  if( x < mini )
838  mini = x;
839  if( x > maxi )
840  maxi = x;
841  }
842  Real p = maxi / mini;
843 
844  if (p > pmax)
845  pmax = p;
846  }
847  return pmax;
848 }
849 
850 /** \f$\max_{i\in\mbox{ rows}}
851  * \left(\frac{\max_{j\in\mbox{ cols}}|a_ij|}
852  * {\min_{j\in\mbox{ cols}}|a_ij|}\right)\f$
853  */
854 Real SPxScaler::maxRowRatio(const SPxLP& lp) const
855 {
856 
857  Real pmax = 0.0;
858 
859  for(int i = 0; i < lp.nRows(); ++i )
860  {
861  const SVector& vec = lp.rowVector(i);
862  Real mini = infinity;
863  Real maxi = 0.0;
864 
865  for(int j = 0; j < vec.size(); ++j)
866  {
867  Real x = spxAbs(vec.value(j));
868 
869  if( isZero(x) )
870  continue;
871  if( x < mini )
872  mini = x;
873  if( x > maxi )
874  maxi = x;
875  }
876  Real p = maxi / mini;
877 
878  if (p > pmax)
879  pmax = p;
880  }
881  return pmax;
882 }
883 
884 bool SPxScaler::isConsistent() const
885 {
886 #ifdef ENABLE_CONSISTENCY_CHECKS
887  return m_activeColscaleExp->isConsistent() && m_activeRowscaleExp->isConsistent();
888 #else
889  return true;
890 #endif
891 }
892 
893 } // namespace soplex
soplex::SPxLPBase::rhs
const VectorBase< R > & rhs() const
Returns right hand side vector.
Definition: spxlpbase.h:219
soplex::spxAbs
Rational spxAbs(const Rational &r)
Absolute.
Definition: rational.cpp:3909
soplex::SPxScaler::unscaleDualray
virtual void unscaleDualray(const SPxLPBase< Real > &lp, Vector &ray) const
unscale dual ray given in ray.
Definition: spxscaler.cpp:669
soplex::SPxScaler::setup
virtual void setup(SPxLPBase< Real > &lp)
clear and setup scaling arrays in the LP
Definition: spxscaler.cpp:124
soplex::SPxScaler::setBoth
virtual void setBoth(bool both)
set wether column and row scaling should be performed
Definition: spxscaler.cpp:112
soplex::SPxScaler::setOrder
virtual void setOrder(bool colFirst)
set scaling order
Definition: spxscaler.cpp:106
soplex::DataArray::isConsistent
bool isConsistent() const
consistency check
Definition: dataarray.h:288
soplex::SPxScaler::unscalePrimal
virtual void unscalePrimal(const SPxLPBase< Real > &lp, Vector &x) const
unscale dense primal solution vector given in x.
Definition: spxscaler.cpp:609
soplex::SPxLPBase::upper
const VectorBase< R > & upper() const
Returns upper bound vector.
Definition: spxlpbase.h:456
soplex::infinity
THREADLOCAL const Real infinity
Definition: spxdefines.cpp:26
soplex::SPxLPBase::_isScaled
bool _isScaled
true, if scaling has been performed
Definition: spxlpbase.h:113
soplex::SPxScaler::lhsUnscaled
virtual Real lhsUnscaled(const SPxLPBase< Real > &lp, int i) const
returns unscaled left hand side i of lp
Definition: spxscaler.cpp:567
soplex::SPxScaler::getRowUnscaled
virtual void getRowUnscaled(const SPxLPBase< Real > &lp, int i, DSVector &vec) const
returns unscaled row i
Definition: spxscaler.cpp:461
soplex::SPxScaler::scaleElement
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
soplex::SPxLPBase::maxObj_w
R & maxObj_w(int i)
Returns objective value of column i for maximization problem.
Definition: spxlpbase.h:1881
soplex::SVectorBase::size
int size() const
Number of used indices.
Definition: svectorbase.h:152
soplex::SPxLPBase::isScaled
bool isScaled() const
Returns true if and only if the LP is scaled.
Definition: spxlpbase.h:139
soplex::LT
bool LT(Real a, Real b, Real eps=Param::epsilon())
returns true iff a < b + eps
Definition: spxdefines.h:387
soplex::SPxScaler::getLhsUnscaled
virtual void getLhsUnscaled(const SPxLPBase< Real > &lp, Vector &vec) const
returns unscaled left hand side vector of lp
Definition: spxscaler.cpp:583
soplex::SPxScaler::unscaleRedCost
virtual void unscaleRedCost(const SPxLPBase< Real > &lp, Vector &r) const
unscale dense reduced cost vector given in r.
Definition: spxscaler.cpp:645
soplex::SPxScaler::maxRowRatio
virtual Real maxRowRatio(const SPxLPBase< Real > &lp) const
maximum ratio between absolute biggest and smallest element in any row.
Definition: spxscaler.cpp:854
soplex::SPxScaler::unscaleDual
virtual void unscaleDual(const SPxLPBase< Real > &lp, Vector &pi) const
unscale dense dual solution vector given in pi.
Definition: spxscaler.cpp:633
soplex::SPxScaler::scaleUpper
virtual Real scaleUpper(const SPxLPBase< Real > &lp, int col, Real upper) const
returns scaled upper bound of column col.
Definition: spxscaler.cpp:730
soplex::SVectorBase::value
R & value(int n)
Reference to value of n &#39;th nonzero.
Definition: svectorbase.h:254
soplex::SPxScaler::~SPxScaler
virtual ~SPxScaler()
destructor.
Definition: spxscaler.cpp:79
soplex::SPxScaler::isConsistent
virtual bool isConsistent() const
consistency check
Definition: spxscaler.cpp:884
soplex::SPxLPBase::rhs_w
R & rhs_w(int i)
Returns right hand side of row i.
Definition: spxlpbase.h:1863
soplex::SPxScaler::getRowMaxAbsUnscaled
virtual Real getRowMaxAbsUnscaled(const SPxLPBase< Real > &lp, int i) const
returns maximum absolute value of unscaled row i
Definition: spxscaler.cpp:484
soplex::SPxScaler::getUpperUnscaled
virtual void getUpperUnscaled(const SPxLPBase< Real > &lp, Vector &vec) const
returns unscaled upper bound vector of lp
Definition: spxscaler.cpp:394
soplex::SPxScaler::scaleLhs
virtual Real scaleLhs(const SPxLPBase< Real > &lp, int row, Real lhs) const
returns scaled left hand side of row row.
Definition: spxscaler.cpp:741
soplex::SPxLPBase::rowVector_w
SVectorBase< R > & rowVector_w(int i)
Definition: spxlpbase.h:2091
soplex::spxFrexp
Real spxFrexp(Real y, int *exp)
Definition: spxdefines.h:353
soplex::SPxLPBase::nRows
int nRows() const
Returns number of rows in LP.
Definition: spxlpbase.h:151
soplex::DSVectorBase::add
void add(const SVectorBase< S > &vec)
Append nonzeros of sv.
Definition: dsvectorbase.h:216
soplex::SPxScaler::m_activeColscaleExp
DataArray< int > * m_activeColscaleExp
pointer to currently active column scaling factors
Definition: spxscaler.h:83
soplex::SPxScaler::applyScaling
virtual void applyScaling(SPxLPBase< Real > &lp)
applies m_colscale and m_rowscale to the lp.
Definition: spxscaler.cpp:171
soplex::spxLdexp
Real spxLdexp(Real x, int exp)
returns x * 2^exp
Definition: spxdefines.h:347
soplex::SPxScaler::computeScaleExp
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
soplex::Real
double Real
Definition: spxdefines.h:215
MSG_DEBUG
#define MSG_DEBUG(x)
Definition: spxdefines.h:129
soplex::SPxScaler::unscale
virtual void unscale(SPxLPBase< Real > &lp)
unscale SPxLP
Definition: spxscaler.cpp:230
soplex::SPxScaler::spxout
SPxOut * spxout
message handler
Definition: spxscaler.h:87
soplex::GT
bool GT(Real a, Real b, Real eps=Param::epsilon())
returns true iff a > b + eps
Definition: spxdefines.h:399
soplex::SVectorBase::index
int & index(int n)
Reference to index of n &#39;th nonzero.
Definition: svectorbase.h:236
soplex::operator<<
std::ostream & operator<<(std::ostream &s, const VectorBase< R > &vec)
Output operator.
Definition: basevectors.h:1151
soplex::SPxScaler::upperUnscaled
virtual Real upperUnscaled(const SPxLPBase< Real > &lp, int i) const
returns unscaled upper bound i
Definition: spxscaler.cpp:377
dvector.h
Dynamic vectors.
soplex::SPxOut
Wrapper for several output streams. A verbosity level is used to decide which stream to use and wheth...
Definition: spxout.h:63
soplex::SPxScaler::getLowerUnscaled
virtual void getLowerUnscaled(const SPxLPBase< Real > &lp, Vector &vec) const
gets unscaled lower bound vector
Definition: spxscaler.cpp:424
soplex::SPxLPBase::lhs
const VectorBase< R > & lhs() const
Returns left hand side vector.
Definition: spxlpbase.h:253
soplex::SPxLPBase::lower_w
R & lower_w(int i)
Returns lower bound of column i.
Definition: spxlpbase.h:1893
soplex::SPxScaler::maxAbsColscale
virtual Real maxAbsColscale() const
absolute biggest column scaling factor
Definition: spxscaler.cpp:776
soplex::SPxScaler::getColScaleExp
virtual int getColScaleExp(int i) const
returns scaling factor for column i
Definition: spxscaler.cpp:287
soplex::SPxScaler::scaleObj
virtual void scaleObj(const SPxLPBase< Real > &lp, VectorReal &origObj) const
apply scaling to objective function vector origObj.
Definition: spxscaler.cpp:681
soplex::LPColSetBase::LPColSetBase
LPColSetBase(int pmax=-1, int pmemmax=-1)
Default constructor.
Definition: lpcolsetbase.h:585
soplex::SPxScaler::getRhsUnscaled
virtual void getRhsUnscaled(const SPxLPBase< Real > &lp, Vector &vec) const
gets unscaled right hand side vector
Definition: spxscaler.cpp:553
soplex::SPxScaler::minAbsColscale
virtual Real minAbsColscale() const
absolute smallest column scaling factor
Definition: spxscaler.cpp:763
soplex::SPxScaler::setRealParam
virtual void setRealParam(Real param, const char *name="realparam")
set real parameter
Definition: spxscaler.cpp:118
soplex::SPxLPBase::maxRowObj
const VectorBase< R > & maxRowObj() const
Definition: spxlpbase.h:297
soplex::SPxScaler::maxObjUnscaled
virtual Real maxObjUnscaled(const SPxLPBase< Real > &lp, int i) const
returns unscaled objective function coefficient of i
Definition: spxscaler.cpp:436
soplex::SPxScaler::m_activeRowscaleExp
DataArray< int > * m_activeRowscaleExp
pointer to currently active row scaling factors
Definition: spxscaler.h:84
soplex::SPxLPBase::setScalingInfo
void setScalingInfo(bool scaled)
set whether the LP is scaled or not
Definition: spxlpbase.h:145
soplex::SPxLPBase::maxRowObj_w
R & maxRowObj_w(int i)
Returns objective function value of row i.
Definition: spxlpbase.h:1875
soplex::SPxScaler::getName
virtual const char * getName() const
get name of scaler
Definition: spxscaler.cpp:100
soplex::SPxScaler::minAbsRowscale
virtual Real minAbsRowscale() const
absolute smallest row scaling factor
Definition: spxscaler.cpp:790
soplex::SPxScaler::scaleLower
virtual Real scaleLower(const SPxLPBase< Real > &lp, int col, Real lower) const
returns scaled lower bound of column col.
Definition: spxscaler.cpp:719
soplex::VectorBase::dim
int dim() const
Dimension of vector.
Definition: vectorbase.h:215
soplex
Everything should be within this namespace.
soplex::SPxScaler::lowerUnscaled
virtual Real lowerUnscaled(const SPxLPBase< Real > &lp, int i) const
returns unscaled lower bound i
Definition: spxscaler.cpp:407
soplex::SPxScaler::rhsUnscaled
virtual Real rhsUnscaled(const SPxLPBase< Real > &lp, int i) const
returns unscaled right hand side i
Definition: spxscaler.cpp:536
soplex::SVectorBase::clear
void clear()
Remove all indices.
Definition: svectorbase.h:396
soplex::SPxScaler::getColMinAbsUnscaled
virtual Real getColMinAbsUnscaled(const SPxLPBase< Real > &lp, int i) const
returns minumum absolute value of unscaled column i
Definition: spxscaler.cpp:351
soplex::SPxLPBase::upper_w
R & upper_w(int i)
Returns upper bound of column i.
Definition: spxlpbase.h:1887
soplex::SPxLPBase::lp_scaler
SPxScaler * lp_scaler
points to the scaler if the lp has been scaled, to 0 otherwise
Definition: spxlpbase.h:114
soplex::SPxScaler::m_colFirst
bool m_colFirst
do column scaling first
Definition: spxscaler.h:85
spxscaler.h
LP scaling base class.
soplex::SPxScaler::SPxScaler
SPxScaler(const char *name, bool colFirst=false, bool doBoth=true, SPxOut *spxout=NULL)
constructor
Definition: spxscaler.cpp:53
spxlp.h
Saving LPs in a form suitable for SoPlex.
soplex::SPxLPBase::rowVector
const SVectorBase< R > & rowVector(int i) const
Gets row vector of row i.
Definition: spxlpbase.h:204
dsvector.h
Dynamic sparse vectors.
soplex::SPxScaler
LP scaler abstract base class.Instances of classes derived from SPxScaler may be loaded to SoPlex in ...
Definition: spxscaler.h:75
soplex::LPRowSetBase::LPRowSetBase
LPRowSetBase(int pmax=-1, int pmemmax=-1)
Default constructor.
Definition: lprowsetbase.h:668
soplex::SPxScaler::getRowMinAbsUnscaled
virtual Real getRowMinAbsUnscaled(const SPxLPBase< Real > &lp, int i) const
returns minimum absolute value of unscaled row i
Definition: spxscaler.cpp:510
soplex::SPxScaler::maxAbsRowscale
virtual Real maxAbsRowscale() const
absolute biggest row scaling factor
Definition: spxscaler.cpp:803
soplex::DataArray::size
int size() const
return nr. of elements.
Definition: dataarray.h:211
soplex::SPxLPBase::isConsistent
bool isConsistent() const
Consistency check.
Definition: spxlpbase.h:1810
soplex::SPxScaler::getRowScaleExp
virtual int getRowScaleExp(int i) const
returns scaling factor for row i
Definition: spxscaler.cpp:294
soplex::SPxLPBase::colVector
const SVectorBase< R > & colVector(int i) const
Returns column vector of column i.
Definition: spxlpbase.h:373
soplex::SPxScaler::getColUnscaled
virtual void getColUnscaled(const SPxLPBase< Real > &lp, int i, DSVector &vec) const
gets unscaled column i
Definition: spxscaler.cpp:301
soplex::SPxLPBase::nCols
int nCols() const
Returns number of columns in LP.
Definition: spxlpbase.h:157
soplex::SPxScaler::getCoefUnscaled
virtual Real getCoefUnscaled(const SPxLPBase< Real > &lp, int row, int col) const
returns unscaled coefficient of lp
Definition: spxscaler.cpp:595
soplex::isZero
bool isZero(Real a, Real eps=Param::epsilon())
returns true iff |a| <= eps
Definition: spxdefines.h:411
soplex::SPxScaler::m_doBoth
bool m_doBoth
do columns and rows
Definition: spxscaler.h:86
soplex::SPxScaler::maxColRatio
virtual Real maxColRatio(const SPxLPBase< Real > &lp) const
maximum ratio between absolute biggest and smallest element in any column.
Definition: spxscaler.cpp:820
soplex::SPxScaler::scaleRhs
virtual Real scaleRhs(const SPxLPBase< Real > &lp, int row, Real rhs) const
returns scaled right hand side of row row.
Definition: spxscaler.cpp:752
soplex::SPxLPBase::colVector_w
SVectorBase< R > & colVector_w(int i)
Returns the LP as an LPRowSet.
Definition: spxlpbase.h:2085
soplex::SPxScaler::unscaleSlacks
virtual void unscaleSlacks(const SPxLPBase< Real > &lp, Vector &s) const
unscale dense slack vector given in s.
Definition: spxscaler.cpp:621
soplex::SPxScaler::unscalePrimalray
virtual void unscalePrimalray(const SPxLPBase< Real > &lp, Vector &ray) const
unscale primal ray given in ray.
Definition: spxscaler.cpp:657
soplex::SPxScaler::getColMaxAbsUnscaled
virtual Real getColMaxAbsUnscaled(const SPxLPBase< Real > &lp, int i) const
returns maximum absolute value of unscaled column i
Definition: spxscaler.cpp:326
soplex::SPxScaler::getMaxObjUnscaled
virtual void getMaxObjUnscaled(const SPxLPBase< Real > &lp, Vector &vec) const
gets unscaled objective function
Definition: spxscaler.cpp:449
soplex::DataArray::reSize
void reSize(int newsize)
reset size to newsize.
Definition: dataarray.h:223
soplex::SPxScaler::m_name
const char * m_name
Name of the scaler.
Definition: spxscaler.h:82
soplex::SPxLPBase::lower
const VectorBase< R > & lower() const
Returns (internal and possibly scaled) lower bound vector.
Definition: spxlpbase.h:483
soplex::SPxScaler::setIntParam
virtual void setIntParam(int param, const char *name="intparam")
set int parameter
Definition: spxscaler.cpp:121
soplex::SPxScaler::operator=
SPxScaler & operator=(const SPxScaler &)
assignment operator
Definition: spxscaler.cpp:84
soplex::DSVectorBase::setMax
void setMax(int newmax=1)
Reset nonzero memory to >= newmax.
Definition: dsvectorbase.h:248
soplex::SPxLPBase::lhs_w
R & lhs_w(int i)
Returns left hand side of row i.
Definition: spxlpbase.h:1869