Scippy

SoPlex

Sequential object-oriented simPlex

spxquality.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 #include <assert.h>
17 #include <iostream>
18 
19 #include "spxdefines.h"
20 #include "spxsolver.h"
21 
22 namespace soplex
23 {
24 
25 void SPxSolver::qualConstraintViolation(Real& maxviol, Real& sumviol) const
26 {
27  maxviol = 0.0;
28  sumviol = 0.0;
29 
30  DVector solu( nCols() );
31 
32  getPrimal( solu );
33 
34  for( int row = 0; row < nRows(); ++row )
35  {
36  const SVector& rowvec = rowVector( row );
37 
38  Real val = 0.0;
39 
40  for( int col = 0; col < rowvec.size(); ++col )
41  val += rowvec.value( col ) * solu[rowvec.index( col )];
42 
43  Real viol = 0.0;
44 
45  assert(lhs( row ) <= rhs( row ) + (100 * epsilon()));
46 
47  if (val < lhs( row ))
48  viol = spxAbs(val - lhs( row ));
49  else
50  if (val > rhs( row ))
51  viol = spxAbs(val - rhs( row ));
52 
53  if (viol > maxviol)
54  maxviol = viol;
55 
56  sumviol += viol;
57  }
58 }
59 
61  Real& maxviol, Real& sumviol) const
62 {
63  maxviol = 0.0;
64  sumviol = 0.0;
65 
66  DVector solu( nCols() );
67 
68  getPrimal( solu );
69 
70  for( int col = 0; col < nCols(); ++col )
71  {
72  assert(lower( col ) <= upper( col ) + (100 * epsilon()));
73 
74  Real viol = 0.0;
75 
76  if (solu[col] < lower( col ))
77  viol = spxAbs( solu[col] - lower( col ));
78  else
79  if (solu[col] > upper( col ))
80  viol = spxAbs( solu[col] - upper( col ));
81 
82  if (viol > maxviol)
83  maxviol = viol;
84 
85  sumviol += viol;
86  }
87 }
88 
89 void SPxSolver::qualSlackViolation(Real& maxviol, Real& sumviol) const
90 {
91  maxviol = 0.0;
92  sumviol = 0.0;
93 
94  DVector solu( nCols() );
95  DVector slacks( nRows() );
96 
97  getPrimal( solu );
98  getSlacks( slacks );
99 
100  for( int row = 0; row < nRows(); ++row )
101  {
102  const SVector& rowvec = rowVector( row );
103 
104  Real val = 0.0;
105 
106  for( int col = 0; col < rowvec.size(); ++col )
107  val += rowvec.value( col ) * solu[rowvec.index( col )];
108 
109  Real viol = spxAbs(val - slacks[row]);
110 
111  if (viol > maxviol)
112  maxviol = viol;
113 
114  sumviol += viol;
115  }
116 }
117 
118 void SPxSolver::qualRedCostViolation(Real& maxviol, Real& sumviol) const
119 {
120  maxviol = 0.0;
121  sumviol = 0.0;
122 
123  int i;
124  // TODO: y = c_B * B^-1 => coSolve(y, c_B)
125  // redcost = c_N - yA_N
126  // solve system "x = e_i^T * B^-1" to get i'th row of B^-1
127  // DVector y( nRows() );
128  // basis().coSolve( x, spx->unitVector( i ) );
129  // DVector rdcost( nCols() );
130 #if 0 // un-const
131  if (lastUpdate() > 0)
132  factorize();
133 
134  computePvec();
135 
136  if (type() == ENTER)
137  computeTest();
138 #endif
139  if (type() == ENTER)
140  {
141  for(i = 0; i < dim(); ++i)
142  {
143  Real x = coTest()[i];
144 
145  if (x < 0.0)
146  {
147  sumviol -= x;
148 
149  if (x < maxviol)
150  maxviol = x;
151  }
152  }
153  for(i = 0; i < coDim(); ++i)
154  {
155  Real x = test()[i];
156 
157  if (x < 0.0)
158  {
159  sumviol -= x;
160 
161  if (x < maxviol)
162  maxviol = x;
163  }
164  }
165  }
166  else
167  {
168  assert(type() == LEAVE);
169 
170  for(i = 0; i < dim(); ++i)
171  {
172  Real x = fTest()[i];
173 
174  if (x < 0.0)
175  {
176  sumviol -= x;
177 
178  if (x < maxviol)
179  maxviol = x;
180  }
181  }
182  }
183  maxviol *= -1;
184 }
185 
186 } // namespace soplex
const VectorBase< Real > & rhs() const
Returns right hand side vector.
Definition: spxlpbase.h:219
Rational spxAbs(const Rational &r)
Absolute.
Definition: rational.cpp:3909
const VectorBase< Real > & upper() const
Returns upper bound vector.
Definition: spxlpbase.h:456
const Vector & fTest() const
Violations of fVec.
Definition: spxsolver.h:1357
virtual Status getPrimal(Vector &vector) const
get solution vector for primal variables.
Definition: spxsolve.cpp:1562
virtual void qualRedCostViolation(Real &maxviol, Real &sumviol) const
get violation of optimality criterion.
Definition: spxquality.cpp:118
int size() const
Number of used indices.
Definition: svectorbase.h:152
void computeTest()
compute test vector in ENTERing Simplex.
Definition: enter.cpp:102
virtual void qualBoundViolation(Real &maxviol, Real &sumviol) const
get violations of bounds.
Definition: spxquality.cpp:60
int lastUpdate() const
returns number of basis changes since last refactorization.
Definition: spxbasis.h:539
int dim() const
dimension of basis matrix.
Definition: spxsolver.h:1047
R & value(int n)
Reference to value of n &#39;th nonzero.
Definition: svectorbase.h:254
int nRows() const
Returns number of rows in LP.
Definition: spxlpbase.h:151
Entering Simplex.
Definition: spxsolver.h:134
Leaving Simplex.
Definition: spxsolver.h:143
double Real
Definition: spxdefines.h:215
int & index(int n)
Reference to index of n &#39;th nonzero.
Definition: svectorbase.h:236
main LP solver class
virtual void qualSlackViolation(Real &maxviol, Real &sumviol) const
get the residuum |Ax-b|.
Definition: spxquality.cpp:89
const VectorBase< Real > & lhs() const
Returns left hand side vector.
Definition: spxlpbase.h:253
const Vector & test() const
Violations of pVec.
Definition: spxsolver.h:1503
Real epsilon() const
values are considered to be 0.
Definition: spxsolver.h:758
Debugging, floating point type and parameter definitions.
Everything should be within this namespace.
const SVectorBase< Real > & rowVector(int i) const
Gets row vector of row i.
Definition: spxlpbase.h:204
const Vector & coTest() const
violations of coPvec.
Definition: spxsolver.h:1437
Type type() const
return current Type.
Definition: spxsolver.h:475
int coDim() const
codimension.
Definition: spxsolver.h:1052
int nCols() const
Returns number of columns in LP.
Definition: spxlpbase.h:157
virtual void qualConstraintViolation(Real &maxviol, Real &sumviol) const
get violation of constraints.
Definition: spxquality.cpp:25
void computePvec()
compute entire pVec().
Definition: spxvecs.cpp:498
const VectorBase< Real > & lower() const
Returns (internal and possibly scaled) lower bound vector.
Definition: spxlpbase.h:483
virtual void factorize()
Factorize basis matrix.
Definition: spxsolver.cpp:547
virtual Status getSlacks(Vector &vector) const
get vector of slack variables.
Definition: spxsolve.cpp:1721