Scippy

SoPlex

Sequential object-oriented simPlex

leave.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 /* Updating the Basis for Leaving Variables
17  */
18 #include <assert.h>
19 #include <stdio.h>
20 
21 #include "spxdefines.h"
22 #include "spxpricer.h"
23 #include "spxsolver.h"
24 #include "spxratiotester.h"
25 #include "spxout.h"
26 #include "exceptions.h"
27 
28 namespace soplex
29 {
30 static const Real reject_leave_tol = 1e-10; // = LOWSTAB as defined in spxfastrt.cpp
31 
32 /*
33  Vector |fTest| gives the feasibility test of all basic variables. For its
34  computation |fVec|, |theUBbound| and |theLBbound| must be setup correctly.
35  Values of |fTest| $<0$ represent infeasible variables, which are eligible
36  for leaving the basis in the simplex loop.
37  */
39 {
40 
41  assert(type() == LEAVE);
42 
43  Real theeps = entertol();
44  m_pricingViolUpToDate = true;
46  m_pricingViol = 0;
47  m_pricingViolCo = 0;
49  int ninfeasibilities = 0;
50  int sparsitythreshold = (int) (sparsePricingFactor * dim());
51 
52  for( int i = 0; i < dim(); ++i )
53  {
54  theCoTest[i] = ((*theFvec)[i] > theUBbound[i])
55  ? theUBbound[i] - (*theFvec)[i]
56  : (*theFvec)[i] - theLBbound[i];
57 
58  if( remainingRoundsLeave == 0 )
59  {
60  if( theCoTest[i] < -theeps )
61  {
65  ++ninfeasibilities;
66  }
67  else
69  if( ninfeasibilities > sparsitythreshold )
70  {
71  MSG_INFO2( (*spxout), (*spxout) << " --- using dense pricing"
72  << std::endl; )
74  sparsePricingLeave = false;
75  ninfeasibilities = 0;
76  }
77  }
78  else if( theCoTest[i] < -theeps )
80  }
81 
82  if( ninfeasibilities == 0 && !sparsePricingLeave )
83  {
85  }
86  else if( ninfeasibilities <= sparsitythreshold && !sparsePricingLeave )
87  {
88  MSG_INFO2( (*spxout),
89  std::streamsize prec = spxout->precision();
90  if( hyperPricingLeave )
91  (*spxout) << " --- using hypersparse pricing, ";
92  else
93  (*spxout) << " --- using sparse pricing, ";
94  (*spxout) << "sparsity: "
95  << std::setw(6) << std::fixed << std::setprecision(4)
96  << (Real) ninfeasibilities/dim()
97  << std::scientific << std::setprecision(int(prec))
98  << std::endl;
99  )
100  sparsePricingLeave = true;
101  }
102 }
103 
105 {
106  const IdxSet& idx = theFvec->idx();
107  Vector& ftest = theCoTest; // |== fTest()|
108  assert(&ftest == &fTest());
109 
110  assert(type() == LEAVE);
111 
112  updateViols.clear();
113  Real theeps = entertol();
114  for (int j = idx.size() - 1; j >= 0; --j)
115  {
116  int i = idx.index(j);
117 
118  if( m_pricingViolUpToDate && ftest[i] < -theeps )
119  m_pricingViol += ftest[i];
120 
121  ftest[i] = ((*theFvec)[i] > theUBbound[i])
122  ? theUBbound[i] - (*theFvec)[i]
123  : (*theFvec)[i] - theLBbound[i];
124 
125 
126  if( sparsePricingLeave && ftest[i] < -theeps )
127  {
128  assert(remainingRoundsLeave == 0);
130  m_pricingViol -= ftest[i];
132  {
133  // this can cause problems - we cannot keep on adding indeces to infeasibilities,
134  // because they are not deleted in hyper mode...
135 // if( !hyperPricingLeave )
138  }
139  if( hyperPricingLeave )
140  updateViols.addIdx(i);
141  }
142  else if( m_pricingViolUpToDate && ftest[i] < -theeps )
143  m_pricingViol -= ftest[i];
144 
145  }
146  // if boundflips were performed, we need to update these indices as well
147  if( boundflips > 0 )
148  {
149  Real eps = epsilon();
150  for( int j = 0; j < solveVector3->size(); ++j )
151  {
152  if( spxAbs(solveVector3->value(j)) > eps )
153  {
154  int i = solveVector3->index(j);
155 
156  if( m_pricingViolUpToDate && ftest[i] < -theeps )
157  m_pricingViol += ftest[i];
158 
159  ftest[i] = ((*theFvec)[i] > theUBbound[i]) ? theUBbound[i] - (*theFvec)[i] : (*theFvec)[i] - theLBbound[i];
160 
161  if( sparsePricingLeave && ftest[i] < -theeps )
162  {
163  assert(remainingRoundsLeave == 0);
165  m_pricingViol -= ftest[i];
166  if( !isInfeasible[i] )
167  {
169  isInfeasible[i] = true;
170  }
171  }
172  else if( m_pricingViolUpToDate && ftest[i] < -theeps )
173  m_pricingViol -= ftest[i];
174  }
175  }
176  }
177 }
178 
179 
180 /* compute statistics on leaving variable
181  Compute a set of statistical values on the variable selected for leaving the
182  basis.
183  */
185  int leaveIdx,
186  SPxBasis::Desc::Status& leaveStat,
187  SPxId& leaveId,
188  Real& leaveMax,
189  Real& leavebound,
190  int& leaveNum,
191  Real& objChange)
192 {
193  SPxBasis::Desc& ds = desc();
194  leaveId = baseId(leaveIdx);
195 
196  if (leaveId.isSPxRowId())
197  {
198  leaveNum = number(SPxRowId(leaveId));
199  leaveStat = ds.rowStatus(leaveNum);
200 
201  assert(isBasic(leaveStat));
202  switch (leaveStat)
203  {
205  assert( rep() == ROW );
206  ds.rowStatus(leaveNum) = dualRowStatus(leaveNum);
207  leavebound = 0;
208  leaveMax = -infinity;
209  break;
211  assert( rep() == ROW );
212  ds.rowStatus(leaveNum) = dualRowStatus(leaveNum);
213  leavebound = 0;
214  leaveMax = infinity;
215  break;
217  assert( rep() == ROW );
218  throw SPxInternalCodeException("XLEAVE01 This should never happen.");
220  assert( rep() == COLUMN );
221  ds.rowStatus(leaveNum) = SPxBasis::Desc::P_FIXED;
222  assert(lhs(leaveNum) == rhs(leaveNum));
223  leavebound = -rhs(leaveNum);
224  if ((*theFvec)[leaveIdx] < theLBbound[leaveIdx])
225  leaveMax = infinity;
226  else
227  leaveMax = -infinity;
228  break;
230  assert( rep() == COLUMN );
231  ds.rowStatus(leaveNum) = SPxBasis::Desc::P_ON_UPPER;
232  leavebound = -rhs(leaveNum); // slack !!
233  leaveMax = infinity;
234  objChange += theLRbound[leaveNum] * rhs(leaveNum);
235  break;
237  assert( rep() == COLUMN );
238  ds.rowStatus(leaveNum) = SPxBasis::Desc::P_ON_LOWER;
239  leavebound = -lhs(leaveNum); // slack !!
240  leaveMax = -infinity;
241  objChange += theURbound[leaveNum] * lhs(leaveNum);
242  break;
244  assert( rep() == COLUMN );
245  if ((*theFvec)[leaveIdx] > theLBbound[leaveIdx])
246  {
247  ds.rowStatus(leaveNum) = SPxBasis::Desc::P_ON_LOWER;
248  theLRbound[leaveNum] = -infinity;
249  leavebound = -lhs(leaveNum); // slack !!
250  leaveMax = -infinity;
251  objChange += theURbound[leaveNum] * lhs(leaveNum);
252  }
253  else
254  {
255  ds.rowStatus(leaveNum) = SPxBasis::Desc::P_ON_UPPER;
256  theURbound[leaveNum] = infinity;
257  leavebound = -rhs(leaveNum); // slack !!
258  leaveMax = infinity;
259  objChange += theLRbound[leaveNum] * rhs(leaveNum);
260  }
261  break;
262 
263  default:
264  throw SPxInternalCodeException("XLEAVE02 This should never happen.");
265  }
266  MSG_DEBUG( std::cout << "DLEAVE51 SPxSolver::getLeaveVals() : row " << leaveNum
267  << ": " << leaveStat
268  << " -> " << ds.rowStatus(leaveNum)
269  << " objChange: " << objChange
270  << std::endl; )
271  }
272 
273  else
274  {
275  assert(leaveId.isSPxColId());
276  leaveNum = number(SPxColId(leaveId));
277  leaveStat = ds.colStatus(leaveNum);
278 
279  assert(isBasic(leaveStat));
280  switch (leaveStat)
281  {
283  assert( rep() == ROW );
284  ds.colStatus(leaveNum) = dualColStatus(leaveNum);
285  leavebound = 0;
286  leaveMax = -infinity;
287  break;
289  assert( rep() == ROW );
290  ds.colStatus(leaveNum) = dualColStatus(leaveNum);
291  leavebound = 0;
292  leaveMax = infinity;
293  break;
295  assert( rep() == ROW );
296  ds.colStatus(leaveNum) = dualColStatus(leaveNum);
297  if ((*theFvec)[leaveIdx] < theLBbound[leaveIdx])
298  {
299  leavebound = theLBbound[leaveIdx];
300  leaveMax = -infinity;
301  }
302  else
303  {
304  leavebound = theUBbound[leaveIdx];
305  leaveMax = infinity;
306  }
307  break;
308 
310  assert( rep() == COLUMN );
311  assert(SPxLP::upper(leaveNum) == SPxLP::lower(leaveNum));
312  ds.colStatus(leaveNum) = SPxBasis::Desc::P_FIXED;
313  leavebound = SPxLP::upper(leaveNum);
314  objChange += maxObj(leaveNum) * leavebound;
315  if ((*theFvec)[leaveIdx] < theLBbound[leaveIdx])
316  leaveMax = infinity;
317  else
318  leaveMax = -infinity;
319  break;
321  assert( rep() == COLUMN );
322  ds.colStatus(leaveNum) = SPxBasis::Desc::P_ON_UPPER;
323  leavebound = SPxLP::upper(leaveNum);
324  objChange += theUCbound[leaveNum] * leavebound;
325  leaveMax = -infinity;
326  break;
328  assert( rep() == COLUMN );
329  ds.colStatus(leaveNum) = SPxBasis::Desc::P_ON_LOWER;
330  leavebound = SPxLP::lower(leaveNum);
331  objChange += theLCbound[leaveNum] * leavebound;
332  leaveMax = infinity;
333  break;
335  assert( rep() == COLUMN );
336  if ((*theFvec)[leaveIdx] > theUBbound[leaveIdx])
337  {
338  leaveMax = -infinity;
339  leavebound = SPxLP::upper(leaveNum);
340  objChange += theUCbound[leaveNum] * leavebound;
341  theLCbound[leaveNum] = -infinity;
342  ds.colStatus(leaveNum) = SPxBasis::Desc::P_ON_UPPER;
343  }
344  else
345  {
346  leaveMax = infinity;
347  leavebound = SPxLP::lower(leaveNum);
348  objChange += theLCbound[leaveNum] * leavebound;
349  theUCbound[leaveNum] = infinity;
350  ds.colStatus(leaveNum) = SPxBasis::Desc::P_ON_LOWER;
351  }
352  break;
353  default:
354  throw SPxInternalCodeException("XLEAVE03 This should never happen.");
355  }
356  MSG_DEBUG( std::cout << "DLEAVE52 SPxSolver::getLeaveVals() : col " << leaveNum
357  << ": " << leaveStat
358  << " -> " << ds.colStatus(leaveNum)
359  << " objChange: " << objChange
360  << std::endl; )
361  }
362 }
363 
365  Real leaveMax,
366  SPxId enterId,
367  Real& enterBound,
368  Real& newUBbound,
369  Real& newLBbound,
370  Real& newCoPrhs,
371  Real& objChange
372 )
373 {
374  SPxBasis::Desc& ds = desc();
375 
376  enterBound = 0;
377  if (enterId.isSPxRowId())
378  {
379  int idx = number(SPxRowId(enterId));
380  SPxBasis::Desc::Status enterStat = ds.rowStatus(idx);
381 
382  switch (enterStat)
383  {
385  assert(rep() == ROW);
386  if (thePvec->delta()[idx] * leaveMax < 0)
387  newCoPrhs = theLRbound[idx];
388  else
389  newCoPrhs = theURbound[idx];
390  newUBbound = infinity;
391  newLBbound = -infinity;
393  break;
395  assert(rep() == ROW);
396  newUBbound = 0;
397  newLBbound = -infinity;
399  newCoPrhs = theLRbound[idx];
400  break;
402  assert(rep() == ROW);
403  newUBbound = infinity;
404  newLBbound = 0;
406  newCoPrhs = theURbound[idx];
407  break;
409  assert(rep() == ROW);
410  if (leaveMax * thePvec->delta()[idx] < 0)
411  {
412  newUBbound = 0;
413  newLBbound = -infinity;
415  newCoPrhs = theLRbound[idx];
416  }
417  else
418  {
419  newUBbound = infinity;
420  newLBbound = 0;
422  newCoPrhs = theURbound[idx];
423  }
424  break;
425 
427  assert(rep() == COLUMN);
428  ds.rowStatus(idx) = dualRowStatus(idx);
429  if (lhs(idx) > -infinity)
430  theURbound[idx] = theLRbound[idx];
431  newCoPrhs = theLRbound[idx]; // slack !!
432  newUBbound = -lhs(idx);
433  newLBbound = -rhs(idx);
434  enterBound = -rhs(idx);
435  objChange -= newCoPrhs * rhs(idx);
436  break;
438  assert(rep() == COLUMN);
439  ds.rowStatus(idx) = dualRowStatus(idx);
440  if (rhs(idx) < infinity)
441  theLRbound[idx] = theURbound[idx];
442  newCoPrhs = theURbound[idx]; // slack !!
443  newLBbound = -rhs(idx);
444  newUBbound = -lhs(idx);
445  enterBound = -lhs(idx);
446  objChange -= newCoPrhs * lhs(idx);
447  break;
449  assert(rep() == COLUMN);
450 #if 1
451  throw SPxInternalCodeException("XLEAVE04 This should never happen.");
452 #else
453  MSG_ERROR( std::cerr << "ELEAVE53 ERROR: not yet debugged!" << std::endl; )
454  ds.rowStatus(idx) = dualRowStatus(idx);
455  newCoPrhs = theURbound[idx]; // slack !!
456  newUBbound = infinity;
457  newLBbound = -infinity;
458  enterBound = 0;
459 #endif
460  break;
462  assert(rep() == COLUMN);
463  MSG_ERROR( std::cerr << "ELEAVE54 "
464  << "ERROR! Tried to put a fixed row variable into the basis: "
465  << "idx=" << idx
466  << ", lhs=" << lhs(idx)
467  << ", rhs=" << rhs(idx) << std::endl; )
468  throw SPxInternalCodeException("XLEAVE05 This should never happen.");
469 
470  default:
471  throw SPxInternalCodeException("XLEAVE06 This should never happen.");
472  }
473  MSG_DEBUG( std::cout << "DLEAVE55 SPxSolver::getLeaveVals2(): row " << idx
474  << ": " << enterStat
475  << " -> " << ds.rowStatus(idx)
476  << " objChange: " << objChange
477  << std::endl; )
478  }
479 
480  else
481  {
482  assert(enterId.isSPxColId());
483  int idx = number(SPxColId(enterId));
484  SPxBasis::Desc::Status enterStat = ds.colStatus(idx);
485 
486  switch (enterStat)
487  {
489  assert(rep() == ROW);
490  newUBbound = 0;
491  newLBbound = -infinity;
493  newCoPrhs = theLCbound[idx];
494  break;
496  assert(rep() == ROW);
497  newUBbound = infinity;
498  newLBbound = 0;
500  newCoPrhs = theUCbound[idx];
501  break;
503  assert(rep() == ROW);
504  newUBbound = infinity;
505  newLBbound = -infinity;
506  newCoPrhs = theLCbound[idx];
508  break;
510  assert(rep() == ROW);
511  if (leaveMax * theCoPvec->delta()[idx] < 0)
512  {
513  newUBbound = 0;
514  newLBbound = -infinity;
516  newCoPrhs = theLCbound[idx];
517  }
518  else
519  {
520  newUBbound = infinity;
521  newLBbound = 0;
523  newCoPrhs = theUCbound[idx];
524  }
525  break;
526 
528  assert(rep() == COLUMN);
529  ds.colStatus(idx) = dualColStatus(idx);
530  if (SPxLP::lower(idx) > -infinity)
531  theLCbound[idx] = theUCbound[idx];
532  newCoPrhs = theUCbound[idx];
533  newUBbound = SPxLP::upper(idx);
534  newLBbound = SPxLP::lower(idx);
535  enterBound = SPxLP::upper(idx);
536  objChange -= newCoPrhs * enterBound;
537  break;
539  assert(rep() == COLUMN);
540  ds.colStatus(idx) = dualColStatus(idx);
541  if (SPxLP::upper(idx) < infinity)
542  theUCbound[idx] = theLCbound[idx];
543  newCoPrhs = theLCbound[idx];
544  newUBbound = SPxLP::upper(idx);
545  newLBbound = SPxLP::lower(idx);
546  enterBound = SPxLP::lower(idx);
547  objChange -= newCoPrhs * enterBound;
548  break;
550  assert(rep() == COLUMN);
551  ds.colStatus(idx) = dualColStatus(idx);
552  if (thePvec->delta()[idx] * leaveMax > 0)
553  newCoPrhs = theUCbound[idx];
554  else
555  newCoPrhs = theLCbound[idx];
556  newUBbound = SPxLP::upper(idx);
557  newLBbound = SPxLP::lower(idx);
558  enterBound = 0;
559  break;
561  assert(rep() == COLUMN);
562  MSG_ERROR( std::cerr << "ELEAVE56 "
563  << "ERROR! Tried to put a fixed column variable into the basis. "
564  << "idx=" << idx
565  << ", lower=" << lower(idx)
566  << ", upper=" << upper(idx) << std::endl; )
567  throw SPxInternalCodeException("XLEAVE07 This should never happen.");
568  default:
569  throw SPxInternalCodeException("XLEAVE08 This should never happen.");
570  }
571 
572  MSG_DEBUG( std::cout << "DLEAVE57 SPxSolver::getLeaveVals2(): col " << idx
573  << ": " << enterStat
574  << " -> " << ds.colStatus(idx)
575  << " objChange: " << objChange
576  << std::endl; )
577  }
578 
579 }
580 
582  int leaveNum,
583  SPxId leaveId,
584  SPxBasis::Desc::Status leaveStat,
585  const SVector* //newVec
586 )
587 {
588  SPxBasis::Desc& ds = desc();
589  if (leaveId.isSPxRowId())
590  {
591  MSG_DEBUG( std::cout << "DLEAVE58 rejectLeave() : row " << leaveNum
592  << ": " << ds.rowStatus(leaveNum)
593  << " -> " << leaveStat << std::endl; )
594 
595  if (leaveStat == SPxBasis::Desc::D_ON_BOTH)
596  {
597  if (ds.rowStatus(leaveNum) == SPxBasis::Desc::P_ON_LOWER)
598  theLRbound[leaveNum] = theURbound[leaveNum];
599  else
600  theURbound[leaveNum] = theLRbound[leaveNum];
601  }
602  ds.rowStatus(leaveNum) = leaveStat;
603  }
604  else
605  {
606  MSG_DEBUG( std::cout << "DLEAVE59 rejectLeave() : col " << leaveNum
607  << ": " << ds.colStatus(leaveNum)
608  << " -> " << leaveStat << std::endl; )
609 
610  if (leaveStat == SPxBasis::Desc::D_ON_BOTH)
611  {
612  if (ds.colStatus(leaveNum) == SPxBasis::Desc::P_ON_UPPER)
613  theLCbound[leaveNum] = theUCbound[leaveNum];
614  else
615  theUCbound[leaveNum] = theLCbound[leaveNum];
616  }
617  ds.colStatus(leaveNum) = leaveStat;
618  }
619 }
620 
621 
623 {
624  Real sign = (direction > 0 ? 1.0 : -1.0);
625 
626  primalRay.clear();
628 
629  for( int i = 0; i < coPvec().delta().size(); ++i )
630  primalRay.add(coPvec().delta().index(i), sign * coPvec().delta().value(i));
631 }
632 
634 {
635  Real sign = (direction > 0 ? -1.0 : 1.0);
636 
637  dualFarkas.clear();
639 
640  for( int i = 0; i < coPvec().delta().size(); ++i )
641  dualFarkas.add(coPvec().delta().index(i), sign * coPvec().delta().value(i));
642 }
643 
644 bool SPxSolver::leave(int leaveIdx, bool polish)
645 {
646  assert(leaveIdx < dim() && leaveIdx >= 0);
647  assert(type() == LEAVE);
648  assert(initialized);
649 
650  bool instable = instableLeave;
651  assert(!instable || instableLeaveNum >= 0);
652 
653  /*
654  Before performing the actual basis update, we must determine, how this
655  is to be accomplished.
656  When using steepest edge pricing this solve is already performed by the pricer
657  */
658  if (theCoPvec->delta().isSetup() && theCoPvec->delta().size() == 0)
659  {
660  coSolve(theCoPvec->delta(), unitVecs[leaveIdx]);
661  }
662 #ifdef ENABLE_ADDITIONAL_CHECKS
663  else
664  {
665  SSVector tmp(dim(), epsilon());
666  tmp.clear();
667  coSolve(tmp, unitVecs[leaveIdx]);
668  tmp -= theCoPvec->delta();
669  if (tmp.length() > leavetol()) {
670  // This happens very frequently and does usually not hurt, so print
671  // these warnings only with verbose level INFO2 and higher.
672  MSG_INFO2( (*spxout), (*spxout) << "WLEAVE60 iteration=" << basis().iteration()
673  << ": coPvec.delta error = " << tmp.length()
674  << std::endl; )
675  }
676  }
677 #endif // ENABLE_ADDITIONAL_CHECKS
678 
679  setupPupdate();
680 
681  assert(thePvec->isConsistent());
682  assert(theCoPvec->isConsistent());
683 
684  SPxBasis::Desc::Status leaveStat; // status of leaving var
685  SPxId leaveId; // id of leaving var
686  SPxId none; // invalid id used if leave fails
687  Real leaveMax; // maximium lambda of leaving var
688  Real leavebound; // current fVec value of leaving var
689  int leaveNum; // number of leaveId in bounds
690  Real objChange = 0.0; // amount of change in the objective function
691 
692  getLeaveVals(leaveIdx, leaveStat, leaveId, leaveMax, leavebound, leaveNum, objChange);
693 
694  if (!polish && m_numCycle > m_maxCycle)
695  {
696  if (leaveMax > 0)
697  perturbMaxLeave();
698  else
699  perturbMinLeave();
700  //@ m_numCycle /= 2;
701  // perturbation invalidates the currently stored nonbasic value
703  }
704  //@ testBounds();
705 
706  Real enterVal = leaveMax;
707  boundflips = 0;
708  Real oldShift = theShift;
709  SPxId enterId = theratiotester->selectEnter(enterVal, leaveIdx, polish);
710  if (NE(theShift, oldShift))
711  {
712  MSG_DEBUG( std::cout << "DLEAVE71 trigger recomputation of nonbasic value due to shifts in ratiotest" << std::endl; )
714  }
715 
716  assert(!enterId.isValid() || !isBasic(enterId));
717 
718  instableLeaveNum = -1;
719  instableLeave = false;
720 
721  /*
722  No variable could be selected to enter the basis and even the leaving
723  variable is unbounded.
724  */
725  if (!enterId.isValid())
726  {
727  /* the following line originally was below in "rejecting leave" case;
728  we need it in the unbounded/infeasible case, too, to have the
729  correct basis size */
730  rejectLeave(leaveNum, leaveId, leaveStat);
731  change(-1, none, 0);
732  objChange = 0.0; // the nonbasicValue is not supposed to be updated in this case
733 
734  if (polish)
735  return false;
736 
737  if (NE(enterVal, leaveMax))
738  {
739  MSG_DEBUG( std::cout << "DLEAVE61 rejecting leave A (leaveIdx=" << leaveIdx
740  << ", theCoTest=" << theCoTest[leaveIdx] << ")"
741  << std::endl; )
742 
743  /* In the LEAVE algorithm, when for a selected leaving variable we find only
744  an instable entering variable, then the basis change is not conducted.
745  Instead, we save the leaving variable's index in instableLeaveNum and scale
746  theCoTest[leaveIdx] down by some factor, hoping to find a different leaving
747  variable with a stable entering variable.
748  If this fails, however, and no more leaving variable is found, we have to
749  perform the instable basis change using instableLeaveNum. In this (and only
750  in this) case, the flag instableLeave is set to true.
751 
752  enterVal != leaveMax is the case that selectEnter has found only an instable entering
753  variable. We store this leaving variable for later -- if we are not already in the
754  instable case: then we continue and conclude unboundedness/infeasibility */
755  if (!instable)
756  {
757  instableLeaveNum = leaveIdx;
758 
759  // Note: These changes do not survive a refactorization
760  instableLeaveVal = theCoTest[leaveIdx];
761  theCoTest[leaveIdx] = instableLeaveVal / 10.0;
762 
763  return true;
764  }
765  }
766 
767  if (lastUpdate() > 1)
768  {
769  MSG_INFO3( (*spxout), (*spxout) << "ILEAVE01 factorization triggered in "
770  << "leave() for feasibility test" << std::endl; )
771  try
772  {
773  factorize();
774  }
775  catch( const SPxStatusException& E )
776  {
777  // don't exit immediately but handle the singularity correctly
779  MSG_INFO3( (*spxout), (*spxout) << "Caught exception in factorization: " << E.what() << std::endl; )
780  }
781 
782  /* after a factorization, the leaving column/row might not be infeasible or suboptimal anymore, hence we do
783  * not try to call leave(leaveIdx), but rather return to the main solving loop and call the pricer again
784  */
785  return true;
786  }
787 
788  /* do not exit with status infeasible or unbounded if there is only a very small violation */
789  if (spxAbs(enterVal) < leavetol())
790  {
791  MSG_INFO3( (*spxout), (*spxout) << "ILEAVE11 clean up step to reduce numerical errors" << std::endl; )
792 
793  computeFrhs();
795  computeFtest();
796 
797  return true;
798  }
799  MSG_INFO3( (*spxout), (*spxout) << "ILEAVE02 unboundedness/infeasibility found "
800  << "in leave()" << std::endl; )
801 
802  if (rep() != COLUMN)
803  {
804  computePrimalray4Row(enterVal);
806  }
807  else
808  {
809  computeDualfarkas4Col(enterVal);
811  }
812  return false;
813  }
814  else
815  {
816  /*
817  If an entering variable has been found, a regular basis update is to
818  be performed.
819  */
820  if (enterId != baseId(leaveIdx))
821  {
822  const SVector& newVector = *enterVector(enterId);
823  // update feasibility vectors
824  if( solveVector2 != NULL && solveVector3 != NULL )
825  {
826  assert(solveVector2->isConsistent());
827  assert(solveVector2rhs->isSetup());
828  assert(solveVector3->isConsistent());
829  assert(solveVector3rhs->isSetup());
830  assert(boundflips > 0);
832  *solveVector2,
833  *solveVector3,
834  newVector,
836  *solveVector3rhs);
837 
838  // perform update of basic solution
839  primVec -= (*solveVector3);
840  MSG_DEBUG( std::cout << "ILBFRT02 breakpoints passed / bounds flipped = " << boundflips << std::endl; )
842  }
843  else if( solveVector2 != NULL )
844  {
845  assert(solveVector2->isConsistent());
846  assert(solveVector2rhs->isSetup());
847 
849  *solveVector2,
850  newVector,
851  *solveVector2rhs);
852  }
853  else if( solveVector3 != NULL )
854  {
855  assert(solveVector3->isConsistent());
856  assert(solveVector3rhs->isSetup());
857  assert(boundflips > 0);
859  *solveVector3,
860  newVector,
861  *solveVector3rhs);
862 
863  // perform update of basic solution
864  primVec -= (*solveVector3);
865  MSG_DEBUG( std::cout << "ILBFRT02 breakpoints passed / bounds flipped = " << boundflips << std::endl; )
867  }
868  else
869  SPxBasis::solve4update (theFvec->delta(), newVector);
870 
871 #ifdef ENABLE_ADDITIONAL_CHECKS
872  {
873  SSVector tmp(dim(), epsilon());
874  SPxBasis::solve(tmp, newVector);
875  tmp -= fVec().delta();
876  if (tmp.length() > entertol()) {
877  // This happens very frequently and does usually not hurt, so print
878  // these warnings only with verbose level INFO2 and higher.
879  MSG_INFO2( (*spxout), (*spxout) << "WLEAVE62\t(" << tmp.length() << ")\n"; )
880  }
881  }
882 #endif // ENABLE_ADDITIONAL_CHECKS
883 
884 
885  if (spxAbs(theFvec->delta()[leaveIdx]) < reject_leave_tol)
886  {
887  if (instable)
888  {
889  /* We are in the case that for all leaving variables only instable entering
890  variables were found: Thus, above we already accepted such an instable
891  entering variable. Now even this seems to be impossible, thus we conclude
892  unboundedness/infeasibility. */
893  MSG_INFO3( (*spxout), (*spxout) << "ILEAVE03 unboundedness/infeasibility found "
894  << "in leave()" << std::endl; )
895 
896  rejectLeave(leaveNum, leaveId, leaveStat);
897  change(-1, none, 0);
898  objChange = 0.0; // the nonbasicValue is not supposed to be updated in this case
899 
900  /**@todo if shift() is not zero we must not conclude unboundedness */
901  if (rep() == ROW)
902  {
903  computePrimalray4Row(enterVal);
905  }
906  else
907  {
908  computeDualfarkas4Col(enterVal);
910  }
911 
912  return false;
913  }
914  else
915  {
916  theFvec->delta().clear();
917  rejectLeave(leaveNum, leaveId, leaveStat, &newVector);
918  change(-1, none, 0);
919  objChange = 0.0; // the nonbasicValue is not supposed to be updated in this case
920 
921  MSG_DEBUG( std::cout << "DLEAVE63 rejecting leave B (leaveIdx=" << leaveIdx
922  << ", theCoTest=" << theCoTest[leaveIdx]
923  << ")" << std::endl; )
924 
925  // Note: These changes do not survive a refactorization
926  theCoTest[leaveIdx] *= 0.01;
927 
928  return true;
929  }
930  }
931 
932  // process leaving variable
933  if (leavebound > epsilon() || leavebound < -epsilon())
934  theFrhs->multAdd(-leavebound, baseVec(leaveIdx));
935 
936  // process entering variable
937  Real enterBound;
938  Real newUBbound;
939  Real newLBbound;
940  Real newCoPrhs;
941 
942  try
943  {
944  getLeaveVals2(leaveMax, enterId, enterBound, newUBbound, newLBbound, newCoPrhs, objChange);
945  }
946  catch( const SPxException& F )
947  {
948  rejectLeave(leaveNum, leaveId, leaveStat);
949  change(-1, none, 0);
950  objChange = 0.0; // the nonbasicValue is not supposed to be updated in this case
951  throw F;
952  }
953 
954  theUBbound[leaveIdx] = newUBbound;
955  theLBbound[leaveIdx] = newLBbound;
956  (*theCoPrhs)[leaveIdx] = newCoPrhs;
957 
958  if (enterBound > epsilon() || enterBound < -epsilon())
959  theFrhs->multAdd(enterBound, newVector);
960 
961  // update pricing vectors
962  theCoPvec->value() = enterVal;
963  thePvec->value() = enterVal;
964  if (enterVal > epsilon() || enterVal < -epsilon())
965  doPupdate();
966 
967  // update feasibility vector
968  theFvec->value() = -((*theFvec)[leaveIdx] - leavebound)
969  / theFvec->delta()[leaveIdx];
970  theFvec->update();
971  (*theFvec)[leaveIdx] = enterBound - theFvec->value();
972  updateFtest();
973 
974  // update objective funtion value
975  updateNonbasicValue(objChange);
976 
977  // change basis matrix
978  change(leaveIdx, enterId, &newVector, &(theFvec->delta()));
979  }
980 
981  /*
982  No entering vector has been selected from the basis. However, if the
983  shift amount for |coPvec| is bounded, we are in the case, that the
984  entering variable is moved from one bound to its other, before any of
985  the basis feasibility variables reaches their bound. This may only
986  happen in primal/columnwise case with upper and lower bounds on
987  variables.
988  */
989  else
990  {
991  // @todo update obj function value here!!!
992  assert(rep() == ROW);
993  SPxBasis::Desc& ds = desc();
994 
995  change(leaveIdx, none, 0);
996 
997  if (leaveStat == SPxBasis::Desc::P_ON_UPPER)
998  {
999  if (leaveId.isSPxRowId())
1000  {
1001  ds.rowStatus(leaveNum) = SPxBasis::Desc::P_ON_LOWER;
1002  (*theCoPrhs)[leaveIdx] = theLRbound[leaveNum];
1003  }
1004  else
1005  {
1006  ds.colStatus(leaveNum) = SPxBasis::Desc::P_ON_LOWER;
1007  (*theCoPrhs)[leaveIdx] = theLCbound[leaveNum];
1008  }
1009  theUBbound[leaveIdx] = 0;
1010  theLBbound[leaveIdx] = -infinity;
1011  }
1012  else
1013  {
1014  assert( leaveStat == SPxBasis::Desc::P_ON_LOWER );
1015  if (leaveId.isSPxRowId())
1016  {
1017  ds.rowStatus(leaveNum) = SPxBasis::Desc::P_ON_UPPER;
1018  (*theCoPrhs)[leaveIdx] = theURbound[leaveNum];
1019  }
1020  else
1021  {
1022  ds.colStatus(leaveNum) = SPxBasis::Desc::P_ON_UPPER;
1023  (*theCoPrhs)[leaveIdx] = theUCbound[leaveNum];
1024  }
1025  theUBbound[leaveIdx] = infinity;
1026  theLBbound[leaveIdx] = 0;
1027  }
1028 
1029  // update copricing vector
1030  theCoPvec->value() = enterVal;
1031  thePvec->value() = enterVal;
1032  if (enterVal > epsilon() || enterVal < -epsilon())
1033  doPupdate();
1034 
1035  // update feasibility vectors
1036  theFvec->value() = 0;
1037  assert(theCoTest[leaveIdx] < 0.0);
1038  m_pricingViol += theCoTest[leaveIdx];
1039  theCoTest[leaveIdx] *= -1;
1040  }
1041 
1042  if ((leaveMax > entertol() && enterVal <= entertol()) || (leaveMax < -entertol() && enterVal >= -entertol()))
1043  {
1044  if ((theUBbound[leaveIdx] < infinity || theLBbound[leaveIdx] > -infinity)
1045  && leaveStat != SPxBasis::Desc::P_FREE
1046  && leaveStat != SPxBasis::Desc::D_FREE)
1047  {
1048  m_numCycle++;
1049  leaveCycles++;
1050  }
1051  }
1052  else
1053  m_numCycle /= 2;
1054 
1055 #ifdef ENABLE_ADDITIONAL_CHECKS
1056  {
1057  DVector tmp = fVec();
1058  multBaseWith(tmp);
1059  tmp -= fRhs();
1060  if (tmp.length() > entertol())
1061  {
1062  // This happens very frequently and does usually not hurt, so print
1063  // these warnings only with verbose level INFO2 and higher.
1064  MSG_INFO2( (*spxout), (*spxout) << "WLEAVE64\t" << basis().iteration()
1065  << ": fVec error = " << tmp.length() << std::endl; )
1066  SPxBasis::solve(tmp, fRhs());
1067  tmp -= fVec();
1068  MSG_INFO2( (*spxout), (*spxout) << "WLEAVE65\t(" << tmp.length() << ")\n"; )
1069  }
1070  }
1071 #endif // ENABLE_ADDITIONAL_CHECKS
1072 
1073  return true;
1074  }
1075 }
1076 } // namespace soplex
const VectorBase< Real > & rhs() const
Returns right hand side vector.
Definition: spxlpbase.h:219
void computeFtest()
compute basis feasibility test vector.
Definition: leave.cpp:38
Rational spxAbs(const Rational &r)
Absolute.
Definition: rational.cpp:3909
int iteration() const
returns number of basis changes since last load().
Definition: spxbasis.h:545
Exception class for things that should NEVER happen.This class is derived from the SoPlex exception b...
Definition: exceptions.h:109
bool isSetup() const
Returns setup status.
Definition: ssvectorbase.h:120
virtual void rejectLeave(int leaveNum, SPxId leaveId, SPxBasis::Desc::Status leaveStat, const SVector *newVec=0)
Definition: leave.cpp:581
void coSolve(Vector &x, const Vector &rhs)
Cosolves linear system with basis matrix.
Definition: spxbasis.h:719
primal variable is fixed to both bounds
Definition: spxbasis.h:190
UpdateVector primVec
primal vector
Definition: spxsolver.h:323
int boundflips
number of performed bound flips
Definition: spxsolver.h:370
const VectorBase< Real > & upper() const
Returns upper bound vector.
Definition: spxlpbase.h:456
const Vector & fTest() const
Violations of fVec.
Definition: spxsolver.h:1357
Desc::Status dualColStatus(int i) const
dual Status for the i&#39;th column variable of the loaded LP.
Definition: spxbasis.cpp:69
DIdxSet updateViols
store indices that were changed in the previous iteration and must be checked in hyper pricing ...
Definition: spxsolver.h:406
SPxOut * spxout
message handler
Definition: spxsolver.h:427
bool sparsePricingLeave
These values enable or disable sparse pricing.
Definition: spxsolver.h:417
THREADLOCAL const Real infinity
Definition: spxdefines.cpp:26
bool leave(int i, bool polish=false)
Definition: leave.cpp:644
DVector theCoTest
Definition: spxsolver.h:359
Abstract pricer base class.
Real leavetol() const
feasibility tolerance maintained by ratio test during LEAVE algorithm.
Definition: spxsolver.h:770
SSVector * solveVector3
when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic so...
Definition: spxsolver.h:274
void updateFtest()
update basis feasibility test vector.
Definition: leave.cpp:104
void computePrimalray4Row(Real direction)
Definition: leave.cpp:622
Exception classes for SoPlex.
Status & rowStatus(int i)
Definition: spxbasis.h:239
Abstract ratio test base class.
virtual void perturbMaxLeave(void)
perturb nonbasic bounds.
Definition: spxshift.cpp:483
int m_maxCycle
maximum steps before cycling is detected.
Definition: spxsolver.h:268
DataArray< int > isInfeasible
0: index not violated, 1: index violated, 2: index violated and among candidate list ...
Definition: spxsolver.h:413
bool NE(Real a, Real b, Real eps=Param::epsilon())
returns true iff |a-b| > eps
Definition: spxdefines.h:381
Real length() const
Floating point approximation of euclidian norm (without any approximation guarantee).
Definition: vectorbase.h:397
int number(const SPxRowId &id) const
Returns the row number of the row with identifier id.
Definition: spxlpbase.h:522
void clear()
removes all indices.
Definition: idxset.h:184
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
Vector & multBaseWith(Vector &x) const
Basis-vector product.
Definition: spxbasis.cpp:979
virtual SPxId selectEnter(Real &val, int leaveIdx, bool polish=false)=0
selects variable Id to enter the basis.
Real sparsePricingFactor
enable sparse pricing when viols < factor * dim()
Definition: spxsolver.h:301
SSVector * solveVector2rhs
when 2 systems are to be solved at a time; typically for speepest edge weights
Definition: spxsolver.h:273
Ids for LP columns.Class SPxColId provides DataKeys for the column indices of an SPxLP.
Definition: spxid.h:36
int sign(const Rational &r)
Sign function; returns 1 if r > 0, 0 if r = 0, and -1 if r < 0.
Definition: rational.cpp:3922
virtual void doPupdate(void)
Definition: spxvecs.cpp:526
virtual Real value()
current objective value.
Definition: spxsolver.cpp:887
rowwise representation.
Definition: spxsolver.h:107
Basis is singular.
Definition: spxbasis.h:93
Desc::Status dualRowStatus(int i) const
dual Status for the i&#39;th row variable of the loaded LP.
Definition: spxbasis.cpp:46
virtual const std::string what() const
returns exception message
Definition: exceptions.h:57
dual variable is left free, but unset
Definition: spxbasis.h:191
Wrapper for different output streams and verbosity levels.
void add(const SVectorBase< S > &vec)
Append nonzeros of sv.
Definition: dsvectorbase.h:216
const Vector & fRhs() const
right-hand side vector for fVec
Definition: spxsolver.h:1308
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
UpdateVector & coPvec() const
copricing vector.
Definition: spxsolver.h:1370
int remainingRoundsLeave
number of dense rounds/refactorizations until sparsePricing is enabled again
Definition: spxsolver.h:423
int m_numCycle
actual number of degenerate steps so far.
Definition: spxsolver.h:269
Leaving Simplex.
Definition: spxsolver.h:143
SPxStatus status() const
returns current SPxStatus.
Definition: spxbasis.h:425
SSVector * solveVector3rhs
when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic so...
Definition: spxsolver.h:275
const SVector & baseVec(int i) const
returns the i&#39;th basic vector.
Definition: spxbasis.h:514
bool m_pricingViolCoUpToDate
true, if the stored violation in coDim is up to date
Definition: spxsolver.h:262
double Real
Definition: spxdefines.h:215
DVector * theFrhs
Definition: spxsolver.h:341
#define MSG_DEBUG(x)
Definition: spxdefines.h:129
virtual const SVector * enterVector(const SPxId &p_id)
Get pointer to the id &#39;th vector.
Definition: spxsolver.h:1862
Real m_pricingViol
maximal feasibility violation of current solution
Definition: spxsolver.h:259
Real entertol() const
feasibility tolerance maintained by ratio test during ENTER algorithm.
Definition: spxsolver.h:763
UpdateVector * thePvec
Definition: spxsolver.h:346
void update()
Perform the update.
Definition: updatevector.h:147
int size() const
returns the number of used indices.
Definition: idxset.h:124
#define MSG_INFO2(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO2.
Definition: spxdefines.h:117
#define MSG_ERROR(x)
Prints out message x if the verbosity level is at least SPxOut::ERROR.
Definition: spxdefines.h:111
int size() const
Returns number of elements.
Definition: classarray.h:208
UpdateVector & fVec() const
feasibility vector.
Definition: spxsolver.h:1295
bool isSPxColId() const
is id a column id?
Definition: spxid.h:165
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
virtual void setupPupdate(void)
Definition: spxvecs.cpp:506
void addIdx(int i)
adds index i to the index set
Definition: didxset.h:75
bool isBasic(SPxBasis::Desc::Status stat) const
does stat describe a basic index ?
Definition: spxsolver.h:1235
Real delta() const
guaranteed primal and dual bound violation for optimal solution, returning the maximum of feastol() a...
Definition: spxsolver.h:793
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
void clear()
Clears vector.
Definition: ssvectorbase.h:599
bool updateNonbasicValue(Real objChange)
Definition: spxsolver.cpp:910
Basis descriptor.
Definition: spxbasis.h:104
DVector theURbound
Upper Row Feasibility bound.
Definition: spxsolver.h:328
bool isConsistent() const
consistency check.
Definition: ssvectorbase.h:616
virtual void getLeaveVals2(Real leaveMax, SPxId enterId, Real &enterBound, Real &newUBbound, Real &newLBbound, Real &newCoPrhs, Real &objChange)
Definition: leave.cpp:364
int leaveCycles
the number of degenerate steps during the leaving algorithm
Definition: spxsolver.h:374
int index(int n) const
Returns index of the n &#39;th nonzero element.
Definition: ssvectorbase.h:174
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
#define MSG_INFO3(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO3.
Definition: spxdefines.h:119
virtual void change(int i, SPxId &id, const SVector *enterVec, const SSVector *eta=0)
performs basis update.
Definition: spxbasis.cpp:736
Real m_pricingViolCo
maximal feasibility violation of current solution in coDim
Definition: spxsolver.h:261
Real epsilon() const
values are considered to be 0.
Definition: spxsolver.h:758
void computeDualfarkas4Col(Real direction)
Definition: leave.cpp:633
Debugging, floating point type and parameter definitions.
int totalboundflips
total number of bound flips
Definition: spxsolver.h:371
virtual void getLeaveVals(int i, SPxBasis::Desc::Status &leaveStat, SPxId &leaveId, Real &leaveMax, Real &leavebound, int &leaveNum, Real &objChange)
Definition: leave.cpp:184
SSVector * solveVector2
when 2 systems are to be solved at a time; typically for speepest edge weights
Definition: spxsolver.h:272
DIdxSet infeasibilities
Definition: spxsolver.h:400
DVector theLRbound
Lower Row Feasibility bound.
Definition: spxsolver.h:329
DVector theUCbound
Upper Column Feasibility bound.
Definition: spxsolver.h:330
static const Real reject_leave_tol
Definition: leave.cpp:30
VectorBase< R > & multAdd(const S &x, const VectorBase< T > &vec)
Addition of scaled vector.
Definition: vectorbase.h:410
Exception base class.This class implements a base class for our SoPlex exceptions We provide a what()...
Definition: exceptions.h:32
int size() const
Returns the number of nonzeros.
Definition: ssvectorbase.h:199
Everything should be within this namespace.
const IdxSet & idx() const
nonzero indices of update vector
Definition: updatevector.h:133
void clear()
Remove all indices.
Definition: svectorbase.h:396
UpdateVector * theFvec
Definition: spxsolver.h:342
void solve4update(SSVector &x, const SVector &rhs)
solves linear system with basis matrix.
Definition: spxbasis.h:664
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
std::streamsize precision() const
Definition: spxout.h:139
DVector theLCbound
Lower Column Feasibility bound.
Definition: spxsolver.h:331
Real & value()
update multiplicator , writeable
Definition: updatevector.h:111
void computeFrhs()
compute feasibility vector from scratch.
Definition: spxvecs.cpp:42
virtual void perturbMinLeave(void)
Definition: spxshift.cpp:470
bool isSPxRowId() const
is id a row id?
Definition: spxid.h:160
SPxRatioTester * theratiotester
Definition: spxsolver.h:381
bool isValid() const
returns TRUE iff the id is a valid column or row identifier.
Definition: spxid.h:150
#define DENSEROUNDS
Definition: spxsolver.h:40
dual variable is set to its lower bound
Definition: spxbasis.h:193
DSVector primalRay
stores primal ray in case of unboundedness
Definition: spxsolver.h:362
Type type() const
return current Type.
Definition: spxsolver.h:475
Real theShift
sum of all shifts applied to any bound.
Definition: spxsolver.h:266
Real length() const
Floating point approximation of euclidian norm (without any approximation guarantee).
Definition: ssvectorbase.h:547
bool isConsistent() const
DSVector dualFarkas
stores dual farkas proof in case of infeasibility
Definition: spxsolver.h:363
Array< UnitVector > unitVecs
array of unit vectors
Definition: spxsolver.h:318
dual variable has two bounds
Definition: spxbasis.h:194
Exception class for status exceptions during the computationsThis class is derived from the SoPlex ex...
Definition: exceptions.h:89
Ids for LP rows.Class SPxRowId provides DataKeys for the row indices of an SPxLP. ...
Definition: spxid.h:55
bool initialized
true, if all vectors are setup.
Definition: spxsolver.h:270
void forceRecompNonbasicValue()
Definition: spxsolver.h:633
void solve(Vector &x, const Vector &rhs)
Definition: spxbasis.h:631
SSVector & delta()
update vector , writeable
Definition: updatevector.h:122
bool m_pricingViolUpToDate
true, if the stored violation is up to date
Definition: spxsolver.h:260
int index(int n) const
access n &#39;th index.
Definition: idxset.h:118
UpdateVector * theCoPvec
Definition: spxsolver.h:345
const SPxBasis & basis() const
Return current basis.
Definition: spxsolver.h:1727
Status
Status of a variable.
Definition: spxbasis.h:185
LP has been proven to be primal unbounded.
Definition: spxbasis.h:98
bool hyperPricingLeave
true if hyper sparse pricing is turned on in the leaving Simplex
Definition: spxsolver.h:420
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
Set of indices.Class IdxSet provides a set of indices. At construction it must be given an array of i...
Definition: idxset.h:56
columnwise representation.
Definition: spxsolver.h:108
R value(int n) const
Returns value of the n &#39;th nonzero element.
Definition: ssvectorbase.h:182
virtual void factorize()
Factorize basis matrix.
Definition: spxsolver.cpp:547
void setBasisStatus(SPxBasis::SPxStatus stat)
set the lp solver&#39;s basis status.
Definition: spxsolver.h:2016
void setMax(int newmax=1)
Reset nonzero memory to >= newmax.
Definition: dsvectorbase.h:248
LP has been proven to be primal infeasible.
Definition: spxbasis.h:99