Scippy

SoPlex

Sequential object-oriented simPlex

spxbounds.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 /** Setting up the feasiblity bound for normal primal variables is
25  straightforward. However, slack variables need some more details
26  on how we treat them. This is slightly different from usual
27  textbook versions. Let \f$l_i \le A_i^T x \le u_i\f$. This can be
28  transformed to \f$A_i^Tx + s_i = 0\f$, with \f$-u_i \le s_i \le
29  -l_i\f$. Hence, with this definition of slack variables \f$s_i\f$, we
30  can directly use vectors \f$l\f$ and \f$u\f$ as feasibility bounds.
31  */
33 {
34 
37 
38  if (rep() == ROW)
39  {
40  theURbound = rhs();
41  theLRbound = lhs();
42  }
43  else
44  {
45  theURbound = lhs();
46  theLRbound = rhs();
47  theURbound *= -1.0;
48  theLRbound *= -1.0;
49  }
50 }
51 
52 /** Setting up the basis for dual simplex requires to install upper and lower
53  feasibility bounds for dual variables (|Lbound| and |Ubound|). Here is a
54  list of how these must be set for inequalities of type \f$l \le a^Tx \le u\f$:
55 
56  \f[
57  \begin{tabular}{cccc}
58  $l$ & $u$ & |Lbound| & |Ubound| \\
59  \hline
60  $-\infty=l$ & $u=\infty$ & 0 & 0 \\
61  $-\infty<l$ & $u=\infty$ & 0 & $\infty$ \\
62  $-\infty=l$ & $u<\infty$ & $-\infty$ & 0 \\
63  \multicolumn{2}{c}{
64  $-\infty<l \ne u<\infty$} & 0 & 0 \\
65  \multicolumn{2}{c}{
66  $-\infty<l = u<\infty$} & $-\infty$ & $\infty$ \\
67  \end{tabular}
68  \f]
69  The case \f$l = -\infty\f$, \f$u = \infty\f$ occurs for unbounded primal variables.
70  Such must be treated differently from the general case.
71 
72  Given possible upper and lower bounds to a dual variable with |Status stat|,
73  this function clears the bounds according to |stat| by setting them to
74  \f$\infty\f$ or \f$-\infty\f$, respectively.
75  */
78  Real& upp,
79  Real& lw) const
80 {
81 
82  switch (stat)
83  {
86  upp = infinity;
87  lw = -infinity;
88  break;
91  upp = infinity;
92  break;
95  lw = -infinity;
96  break;
97 
98  default:
99  break;
100  }
101 }
102 
104 {
105 
106  assert(rep() == COLUMN);
107 
108  const SPxBasis::Desc& ds = desc();
109 
110  int i;
111 
112  for(i = 0; i < nRows(); ++i)
113  {
114  theURbound[i] = maxRowObj(i);
115  theLRbound[i] = maxRowObj(i);
116 
118  }
119 
120  for(i = 0; i < nCols(); ++i)
121  {
122  theUCbound[i] = -maxObj(i);
123  theLCbound[i] = -maxObj(i);
124 
125  // exchanged ... due to definition of slacks!
127 
128  theUCbound[i] *= -1.0;
129  theLCbound[i] *= -1.0;
130  }
131 }
132 
134 {
135 
136  assert(rep() == ROW);
137 
138  int i;
139 
140  for(i = 0; i < nRows(); ++i)
141  {
142  theURbound[i] = 0.0;
143  theLRbound[i] = 0.0;
144 
146  }
147 
148  for(i = 0; i < nCols(); ++i)
149  {
150  theUCbound[i] = 0.0;
151  theLCbound[i] = 0.0;
152 
154  }
155 }
156 
157 
158 /** This sets up the bounds for basic variables for entering simplex algorithms.
159  It requires, that all upper lower feasibility bounds have allready been
160  setup. Method |setEnterBound4Row(i, n)| does so for the |i|-th basis
161  variable being row index |n|. Equivalently, method
162  |setEnterBound4Col(i, n)| does so for the |i|-th basis variable being
163  column index |n|.
164  */
166 {
167  assert(baseId(i).isSPxRowId());
168  assert(number(SPxRowId(baseId(i))) == n);
169  switch (desc().rowStatus(n))
170  {
172  theLBbound[i] = -infinity;
173  theUBbound[i] = theURbound[n];
174  break;
176  theLBbound[i] = theLRbound[n];
177  theUBbound[i] = infinity;
178  break;
180  theLBbound[i] = -infinity;
181  theUBbound[i] = infinity;
182  break;
183  default:
184  theUBbound[i] = theURbound[n];
185  theLBbound[i] = theLRbound[n];
186  break;
187  }
188 }
189 
191 {
192  assert(baseId(i).isSPxColId());
193  assert(number(SPxColId(baseId(i))) == n);
194  switch (desc().colStatus(n))
195  {
197  theLBbound[i] = -infinity;
198  theUBbound[i] = theUCbound[n];
199  break;
201  theLBbound[i] = theLCbound[n];
202  theUBbound[i] = infinity;
203  break;
205  theLBbound[i] = -infinity;
206  theUBbound[i] = infinity;
207  break;
208  default:
209  theUBbound[i] = theUCbound[n];
210  theLBbound[i] = theLCbound[n];
211  break;
212  }
213 }
214 
216 {
217 
218  for (int i = 0; i < dim(); ++i)
219  {
220  SPxId base_id = baseId(i);
221 
222  if (base_id.isSPxRowId())
223  setEnterBound4Row(i, number(SPxRowId(base_id)));
224  else
225  setEnterBound4Col(i, number(SPxColId(base_id)));
226  }
227 }
228 
229 
230 /** This sets up the bounds for basic variables for leaving simplex algorithms.
231  While method |setLeaveBound4Row(i,n)| does so for the |i|-th basic variable
232  being the |n|-th row, |setLeaveBound4Col(i,n)| does so for the |i|-th basic
233  variable being the |n|-th column.
234  */
236 {
237  assert(baseId(i).isSPxRowId());
238  assert(number(SPxRowId(baseId(i))) == n);
239  switch (desc().rowStatus(n))
240  {
242  theLBbound[i] = -infinity;
243  theUBbound[i] = -maxRowObj(n);
244  break;
246  theLBbound[i] = -maxRowObj(n);
247  theUBbound[i] = infinity;
248  break;
250  theLBbound[i] = -infinity;
251  theUBbound[i] = infinity;
252  break;
254  theLBbound[i] = -maxRowObj(n);
255  theUBbound[i] = -maxRowObj(n);
256  break;
257 
258  default:
259  assert(rep() == COLUMN);
260  theLBbound[i] = -rhs(n); // slacks !
261  theUBbound[i] = -lhs(n); // slacks !
262  break;
263  }
264 }
265 
267 {
268 
269  assert(baseId(i).isSPxColId());
270  assert(number(SPxColId(baseId(i))) == n);
271 
272  switch (desc().colStatus(n))
273  {
275  theLBbound[i] = -infinity;
276  theUBbound[i] = 0;
277  break;
279  theLBbound[i] = 0;
280  theUBbound[i] = infinity;
281  break;
283  theLBbound[i] = -infinity;
284  theUBbound[i] = infinity;
285  break;
287  theLBbound[i] = theUBbound[i] = 0;
288  break;
289 
290  default:
291  theUBbound[i] = SPxLP::upper(n);
292  theLBbound[i] = SPxLP::lower(n);
293  break;
294  }
295 }
296 
298 {
299 
300  for (int i = 0; i < dim(); ++i)
301  {
302  SPxId base_id = baseId(i);
303 
304  if (base_id.isSPxRowId())
305  setLeaveBound4Row(i, number(SPxRowId(base_id)));
306  else
307  setLeaveBound4Col(i, number(SPxColId(base_id)));
308  }
309 }
310 
312 {
313 
314  if (type() == ENTER)
315  {
316  Real viol_max = (1 + iterCount) * entertol();
317  int nlinesprinted = 0;
318  int m = dim();
319 
320  for(int i = 0; i < m; ++i )
321  {
322  // Minor bound violations happen frequently, so print these
323  // warnings only with verbose level INFO2 and higher.
324  if ((*theFvec)[i] > theUBbound[i] + viol_max) //@ && theUBbound[i] != theLBbound[i])
325  {
326  MSG_INFO2( (*spxout), (*spxout) << "WBOUND01 Invalid upper enter bound " << i
327  << " Fvec: " << (*theFvec)[i]
328  << " UBbound: " << theUBbound[i]
329  << " tolerance: " << viol_max
330  << " violation: " << (*theFvec)[i] - theUBbound[i] << std::endl; )
331  nlinesprinted++;
332  }
333  if ((*theFvec)[i] < theLBbound[i] - viol_max) //@ && theUBbound[i] != theLBbound[i])
334  {
335  MSG_INFO2( (*spxout), (*spxout) << "WBOUND02 Invalid lower enter bound " << i
336  << " Fvec: " << (*theFvec)[i]
337  << " LBbound: " << theLBbound[i]
338  << " tolerance: " << viol_max
339  << " violation: " << theLBbound[i] - (*theFvec)[i] << std::endl; )
340  nlinesprinted++;
341  }
342  if( nlinesprinted >= 3 )
343  {
344  MSG_INFO2( (*spxout), (*spxout) << "WBOUND10 suppressing further warnings of type WBOUND{01,02} in this round" << std::endl );
345  break;
346  }
347  }
348  }
349  else
350  {
351  Real viol_max = (1 + iterCount) * leavetol();
352  int nlinesprinted = 0;
353  int m = dim();
354  int n = coDim();
355 
356  for(int i = 0; i < m; ++i )
357  {
358  if ((*theCoPvec)[i] > (*theCoUbound)[i] + viol_max) // && (*theCoUbound)[i] != (*theCoLbound)[i])
359  {
360  MSG_INFO2( (*spxout), (*spxout) << "WBOUND03 Invalid upper cobound " << i
361  << " CoPvec: " << (*theCoPvec)[i]
362  << " CoUbound: " << (*theCoUbound)[i]
363  << " tolerance: " << viol_max
364  << " violation: " << (*theCoPvec)[i] - (*theCoUbound)[i] << std::endl; )
365  nlinesprinted++;
366  }
367  if ((*theCoPvec)[i] < (*theCoLbound)[i] - viol_max) // && (*theCoUbound)[i] != (*theCoLbound)[i])
368  {
369  MSG_INFO2( (*spxout), (*spxout) << "WBOUND04 Invalid lower cobound " << i
370  << " CoPvec: " << (*theCoPvec )[i]
371  << " CoLbound: " << (*theCoLbound)[i]
372  << " tolerance: " << viol_max
373  << " violation: " << (*theCoLbound)[i] - (*theCoPvec)[i] << std::endl; )
374  nlinesprinted++;
375  }
376  if( nlinesprinted >= 3 )
377  {
378  MSG_INFO2( (*spxout), (*spxout) << "WBOUND11 suppressing further warnings of type WBOUND{03,04} in this round" << std::endl );
379  break;
380  }
381  }
382 
383  nlinesprinted = 0;
384  for(int i = 0; i < n; ++i )
385  {
386  if ((*thePvec)[i] > (*theUbound)[i] + viol_max) // && (*theUbound)[i] != (*theLbound)[i])
387  {
388  MSG_INFO2( (*spxout), (*spxout) << "WBOUND05 Invalid upper bound " << i
389  << " Pvec: " << (*thePvec)[i]
390  << " Ubound: " << (*theUbound)[i]
391  << " tolerance: " << viol_max
392  << " violation: " << (*thePvec)[i] - (*theUbound)[i] << std::endl; )
393  nlinesprinted++;
394  }
395  if ((*thePvec)[i] < (*theLbound)[i] - viol_max) // && (*theUbound)[i] != (*theLbound)[i])
396  {
397  MSG_INFO2( (*spxout), (*spxout) << "WBOUND06 Invalid lower bound " << i
398  << " Pvec: " << (*thePvec)[i]
399  << " Lbound: " << (*theLbound)[i]
400  << " tolerance: " << viol_max
401  << " violation: " << (*theLbound)[i] - (*thePvec)[i] << std::endl; )
402  nlinesprinted++;
403  }
404  if( nlinesprinted >= 3 )
405  {
406  MSG_INFO2( (*spxout), (*spxout) << "WBOUND12 suppressing further warnings of type WBOUND{05,06} in this round" << std::endl );
407  break;
408  }
409  }
410  }
411 }
412 } // namespace soplex
const VectorBase< Real > & rhs() const
Returns right hand side vector.
Definition: spxlpbase.h:219
void setEnterBound4Col(int, int)
Definition: spxbounds.cpp:190
primal variable is fixed to both bounds
Definition: spxbasis.h:190
const VectorBase< Real > & upper() const
Returns upper bound vector.
Definition: spxlpbase.h:456
Desc::Status dualColStatus(int i) const
dual Status for the i&#39;th column variable of the loaded LP.
Definition: spxbasis.cpp:69
SPxOut * spxout
message handler
Definition: spxsolver.h:427
THREADLOCAL const Real infinity
Definition: spxdefines.cpp:26
DVector * theUbound
Upper bound for vars.
Definition: spxsolver.h:353
void testBounds() const
Definition: spxbounds.cpp:311
Real leavetol() const
feasibility tolerance maintained by ratio test during LEAVE algorithm.
Definition: spxsolver.h:770
DVector * theCoUbound
Upper bound for covars.
Definition: spxsolver.h:355
Status & rowStatus(int i)
Definition: spxbasis.h:239
void clearDualBounds(SPxBasis::Desc::Status, Real &, Real &) const
Definition: spxbounds.cpp:76
int number(const SPxRowId &id) const
Returns the row number of the row with identifier id.
Definition: spxlpbase.h:522
int dim() const
dimension of basis matrix.
Definition: spxsolver.h:1047
void setPrimalBounds()
setup feasibility bounds for entering algorithm
Definition: spxbounds.cpp:32
void setLeaveBound4Col(int i, int n)
Definition: spxbounds.cpp:266
Ids for LP columns.Class SPxColId provides DataKeys for the column indices of an SPxLP.
Definition: spxid.h:36
rowwise representation.
Definition: spxsolver.h:107
Desc::Status dualRowStatus(int i) const
dual Status for the i&#39;th row variable of the loaded LP.
Definition: spxbasis.cpp:46
dual variable is left free, but unset
Definition: spxbasis.h:191
int nRows() const
Returns number of rows in LP.
Definition: spxlpbase.h:151
Entering Simplex.
Definition: spxsolver.h:134
primal variable is set to its upper bound
Definition: spxbasis.h:188
Generic Ids for LP rows or columns.Both SPxColIds and SPxRowIds may be treated uniformly as SPxIds: ...
Definition: spxid.h:85
double Real
Definition: spxdefines.h:215
DVector * theLbound
Lower bound for vars.
Definition: spxsolver.h:354
Real entertol() const
feasibility tolerance maintained by ratio test during ENTER algorithm.
Definition: spxsolver.h:763
UpdateVector * thePvec
Definition: spxsolver.h:346
#define MSG_INFO2(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO2.
Definition: spxdefines.h:117
virtual void setLeaveBounds()
Definition: spxbounds.cpp:297
dual variable is set to its upper bound
Definition: spxbasis.h:192
DVector theLBbound
Lower Basic Feasibility bound.
Definition: spxsolver.h:339
main LP solver class
primal variable is left free, but unset
Definition: spxbasis.h:189
const VectorBase< Real > & lhs() const
Returns left hand side vector.
Definition: spxlpbase.h:253
Basis descriptor.
Definition: spxbasis.h:104
DVector theURbound
Upper Row Feasibility bound.
Definition: spxsolver.h:328
const VectorBase< Real > & maxRowObj() const
Definition: spxlpbase.h:297
Status & colStatus(int i)
Definition: spxbasis.h:254
SPxId & baseId(int i)
Definition: spxbasis.h:503
DVector theUBbound
Upper Basic Feasibility bound.
Definition: spxsolver.h:338
DVector * theCoLbound
Lower bound for covars.
Definition: spxsolver.h:356
Debugging, floating point type and parameter definitions.
DVector theLRbound
Lower Row Feasibility bound.
Definition: spxsolver.h:329
DVector theUCbound
Upper Column Feasibility bound.
Definition: spxsolver.h:330
void setDualColBounds()
Definition: spxbounds.cpp:103
Everything should be within this namespace.
UpdateVector * theFvec
Definition: spxsolver.h:342
primal variable is set to its lower bound
Definition: spxbasis.h:187
const VectorBase< Real > & maxObj() const
Returns objective vector for maximization problem.
Definition: spxlpbase.h:429
void setEnterBound4Row(int, int)
Definition: spxbounds.cpp:165
DVector theLCbound
Lower Column Feasibility bound.
Definition: spxsolver.h:331
void setDualRowBounds()
Definition: spxbounds.cpp:133
bool isSPxRowId() const
is id a row id?
Definition: spxid.h:160
dual variable is set to its lower bound
Definition: spxbasis.h:193
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 setEnterBounds()
Definition: spxbounds.cpp:215
Ids for LP rows.Class SPxRowId provides DataKeys for the row indices of an SPxLP. ...
Definition: spxid.h:55
UpdateVector * theCoPvec
Definition: spxsolver.h:345
int iterCount
number of calls to change() since last manipulation
Definition: spxbasis.h:388
Status
Status of a variable.
Definition: spxbasis.h:185
void setLeaveBound4Row(int i, int n)
Definition: spxbounds.cpp:235
const VectorBase< Real > & lower() const
Returns (internal and possibly scaled) lower bound vector.
Definition: spxlpbase.h:483
const Desc & desc() const
Definition: spxbasis.h:463
Representation rep() const
return the current basis representation.
Definition: spxsolver.h:469
columnwise representation.
Definition: spxsolver.h:108