29 bool hasUnboundedRay =
false;
30 bool infeasibilityNotCertified =
false;
31 bool unboundednessNotCertified =
false;
85 #ifdef SOPLEX_WITH_CPX 100 bool primalFeasible =
false;
101 bool dualFeasible =
false;
102 bool infeasible =
false;
103 bool unbounded =
false;
110 primalFeasible, dualFeasible, infeasible, unbounded, stoppedTime, stoppedIter, error);
119 else if( stoppedTime )
124 else if( stoppedIter )
130 else if( unbounded && !unboundednessNotCertified )
136 assert(!hasUnboundedRay || solUnbounded.
hasPrimalRay());
137 assert(!solUnbounded.
hasPrimalRay() || hasUnboundedRay);
146 if( hasUnboundedRay )
155 unboundednessNotCertified = !hasUnboundedRay;
162 else if( stoppedIter )
171 if( hasUnboundedRay )
183 else if( stoppedTime )
188 else if( stoppedIter )
193 else if( infeasible )
199 else if( hasUnboundedRay )
212 else if( infeasible && !infeasibilityNotCertified )
226 infeasibilityNotCertified = !infeasible;
234 else if( stoppedIter )
247 assert(!hasUnboundedRay || solUnbounded.
hasPrimalRay());
248 assert(!solUnbounded.
hasPrimalRay() || hasUnboundedRay);
258 if( hasUnboundedRay )
286 else if( hasUnboundedRay )
298 else if( primalFeasible && dualFeasible )
321 #ifdef SOPLEX_WITH_CPX 354 bool acceptUnbounded,
355 bool acceptInfeasible,
357 bool& primalFeasible,
368 primalFeasible =
false;
369 dualFeasible =
false;
483 sol.
_primal[c] = primalReal[c];
500 sol.
_dual[r] = dualReal[r];
501 if( dualReal[r] != 0.0 )
518 const Rational violationImprovementFactor = 0.9;
519 const Rational errorCorrectionFactor = 1.1;
521 int numFailedRefinements = 0;
531 bool factorSolNewBasis =
true;
532 int lastStallRefinements = 0;
533 int nextRatrecRefinement = 0;
539 MSG_DEBUG( std::cout <<
"Computing primal violations.\n" );
607 if(
_modLhs[r] > sideViolation )
630 if(
_modRhs[r] < -sideViolation )
639 MSG_DEBUG( std::cout <<
"Computing dual violations.\n" );
642 redCostViolation = 0;
652 && sol.
_redCost[c] < -redCostViolation )
654 MSG_DEBUG( std::cout <<
"basisStatusCol = " << basisStatusCol
659 redCostViolation = -sol.
_redCost[c];
663 && sol.
_redCost[c] > redCostViolation )
665 MSG_DEBUG( std::cout <<
"basisStatusCol = " << basisStatusCol
685 && sol.
_dual[r] < -dualViolation )
687 MSG_DEBUG( std::cout <<
"basisStatusRow = " << basisStatusRow
692 dualViolation = -sol.
_dual[r];
696 && sol.
_dual[r] > dualViolation )
698 MSG_DEBUG( std::cout <<
"basisStatusRow = " << basisStatusRow
703 dualViolation = sol.
_dual[r];
713 <<
"Max. reduced cost violation = " <<
rationalToString(redCostViolation) <<
"\n" 717 << std::fixed << std::setprecision(2) << std::setw(10)
718 <<
"Progress table: " 723 << std::setw(10) <<
rationalToString(boundsViolation > sideViolation ? boundsViolation : sideViolation, 2) <<
" & " 724 << std::setw(10) <<
rationalToString(redCostViolation > dualViolation ? redCostViolation : dualViolation, 2) <<
"\n");
729 if( primalFeasible && dualFeasible )
738 MSG_INFO1(
spxout,
spxout <<
"Tolerances reached but minRounds forcing additional refinement rounds.\n" );
747 maxViolation = boundsViolation;
748 if( sideViolation > maxViolation )
749 maxViolation = sideViolation;
750 if( redCostViolation > maxViolation )
751 maxViolation = redCostViolation;
752 if( dualViolation > maxViolation )
753 maxViolation = dualViolation;
754 bestViolation *= violationImprovementFactor;
755 if( maxViolation > bestViolation )
758 numFailedRefinements++;
761 bestViolation = maxViolation;
770 errorCorrection *= errorCorrectionFactor;
771 if( performRatrec && maxViolation > 0 )
775 maxViolation *= errorCorrection;
780 primalFeasible =
true;
785 MSG_DEBUG(
spxout <<
"Next rational reconstruction after refinement " << nextRatrecRefinement <<
".\n" );
789 if( performRatfac && maxViolation > 0 )
795 factorSolNewBasis =
false;
809 primalFeasible =
true;
824 maxScale = primalScale;
827 primalScale = boundsViolation > sideViolation ? boundsViolation : sideViolation;
828 if( primalScale < redCostViolation )
829 primalScale = redCostViolation;
830 assert(primalScale >= 0);
832 if( primalScale > 0 )
835 if( primalScale > maxScale )
836 primalScale = maxScale;
839 primalScale = maxScale;
845 if( primalScale <= 1 )
847 if( primalScale < 1 )
893 assert(primalScale >= 1);
894 if( primalScale == 1 )
938 maxScale = dualScale;
941 dualScale = redCostViolation > dualViolation ? redCostViolation : dualViolation;
942 assert(dualScale >= 0);
947 if( dualScale > maxScale )
948 dualScale = maxScale;
951 dualScale = maxScale;
956 if( dualScale > primalScale )
957 dualScale = primalScale;
987 newRowObj = sol.
_dual[r];
988 newRowObj *= dualScale;
1010 int col = numOrigCols + i;
1032 MSG_DEBUG(
spxout <<
"setting basis in solver " << (_hasBasis ?
"successful" :
"failed") <<
" (3)\n" );
1044 lastStallRefinements++;
1049 factorSolNewBasis =
true;
1050 lastStallRefinements = 0;
1088 MSG_DEBUG( std::cout <<
"Correcting primal solution.\n" );
1091 Rational primalScaleInverse = primalScale;
1092 primalScaleInverse.
invert();
1153 if( primalReal[c] == 1.0 )
1161 else if( primalReal[c] == -1.0 )
1170 else if( primalReal[c] != 0.0 )
1190 #ifdef SOPLEX_WITH_GMP 1194 assert(sol.
_slacks == activity);
1204 MSG_DEBUG( std::cout <<
"Correcting dual solution.\n" );
1214 Rational debugRedCostViolation = 0;
1224 && debugRedCost[c] < -debugRedCostViolation )
1226 MSG_DEBUG( std::cout <<
"basisStatusCol = " << basisStatusCol
1232 debugRedCostViolation = -debugRedCost[c];
1236 && debugRedCost[c] > debugRedCostViolation )
1238 MSG_DEBUG( std::cout <<
"basisStatusCol = " << basisStatusCol
1244 debugRedCostViolation = debugRedCost[c];
1250 Rational debugBasicDualViolation = 0;
1262 && val > debugDualViolation )
1264 MSG_DEBUG( std::cout <<
"basisStatusRow = " << basisStatusRow
1268 <<
", dualReal[r] = " << dualReal[r]
1270 debugDualViolation = val;
1274 && val < -debugDualViolation )
1276 MSG_DEBUG( std::cout <<
"basisStatusRow = " << basisStatusRow
1280 <<
", dualReal[r] = " << dualReal[r]
1282 debugDualViolation = -val;
1287 MSG_DEBUG( std::cout <<
"basisStatusRow = " << basisStatusRow
1291 <<
", dualReal[r] = " << dualReal[r]
1293 debugBasicDualViolation =
spxAbs(val);
1303 <<
" (red. cost, dual, basic).\n" );
1308 Rational dualScaleInverseNeg = dualScale;
1309 dualScaleInverseNeg.
invert();
1310 dualScaleInverseNeg *= -1;
1325 if( dualReal[r] != 0 )
1368 if( numCorrectedPrimals + numCorrectedDuals > 0 )
1370 MSG_INFO2(
spxout,
spxout <<
"Corrected " << numCorrectedPrimals <<
" primal variables and " << numCorrectedDuals <<
" dual values.\n" );
1409 bool& hasUnboundedRay,
1414 bool primalFeasible;
1429 _performOptIRStable(sol,
false,
false, 0, primalFeasible, dualFeasible, infeasible, unbounded, stopped, stoppedIter, error);
1438 hasUnboundedRay =
false;
1442 else if( error || unbounded || infeasible || !primalFeasible || !dualFeasible )
1445 hasUnboundedRay =
false;
1463 hasUnboundedRay = (tau >= 1);
1475 bool& withDualFarkas,
1480 bool primalFeasible;
1484 bool success =
false;
1508 _performOptIRStable(sol,
false,
false, 0, primalFeasible, dualFeasible, infeasible, unbounded, stopped, stoppedIter, error);
1517 withDualFarkas =
false;
1521 else if( error || unbounded || infeasible || !primalFeasible || !dualFeasible )
1524 withDualFarkas =
false;
1541 if( withDualFarkas )
1564 while(!error && !success && !stopped);
1575 MSG_DEBUG( std::cout <<
"Reducing matrix coefficients by lifting.\n" );
1596 MSG_DEBUG( std::cout <<
"in lifting: examining column " << i <<
"\n" );
1601 bool addedLiftingRow =
false;
1602 int liftingColumnIndex = -1;
1605 for(
int k = colVector.
size() - 1; k >= 0; k-- )
1609 if(
spxAbs(value) > maxValue )
1614 if( !addedLiftingRow )
1616 MSG_DEBUG( std::cout <<
" --> adding lifting row\n" );
1618 assert(liftingRowVector.
size() == 0);
1621 liftingRowVector.
add(i, maxValue);
1622 liftingRowVector.
add(liftingColumnIndex, -1);
1633 liftingRowVector.
clear();
1634 addedLiftingRow =
true;
1638 int rowIndex = colVector.
index(k);
1639 assert(rowIndex >= 0);
1643 MSG_DEBUG( std::cout <<
" --> changing matrix\n" );
1651 newValue /= maxValue;
1663 MSG_DEBUG( std::cout <<
"in lifting: examining column " << i <<
"\n" );
1668 bool addedLiftingRow =
false;
1669 int liftingColumnIndex = -1;
1672 for(
int k = colVector.
size() - 1; k >= 0; k-- )
1676 if(
spxAbs(value) < minValue )
1681 if( !addedLiftingRow )
1683 MSG_DEBUG( std::cout <<
" --> adding lifting row\n" );
1685 assert(liftingRowVector.
size() == 0);
1688 liftingRowVector.
add(i, minValue);
1689 liftingRowVector.
add(liftingColumnIndex, -1);
1700 liftingRowVector.
clear();
1701 addedLiftingRow =
true;
1705 int rowIndex = colVector.
index(k);
1706 assert(rowIndex >= 0);
1710 MSG_DEBUG( std::cout <<
" --> changing matrix\n" );
1718 newValue /= minValue;
1812 MSG_INFO1(
spxout,
spxout <<
"Warning: lost basis during project phase because of nonbasic lifting column.\n" );
1822 MSG_INFO1(
spxout,
spxout <<
"Warning: lost basis during project phase because of basic lifting row.\n" );
1847 #ifndef SOPLEX_MANUAL_ALT 1870 #ifndef SOPLEX_MANUAL_ALT 1923 MSG_DEBUG( std::cout <<
"Transforming rows to equation form.\n" );
2016 int col = numOrigCols + i;
2038 int col = numOrigCols + i;
2048 MSG_DEBUG( std::cout <<
"slack column " << col <<
" for row " << row
2087 int col = numOrigCols + i;
2175 obj.
add(numOrigCols, -1);
2263 _basisStatusRows.reSize(numOrigRows);
2278 sol.
_dual /= -alpha;
2294 for(
int i = objRowVector.
size() - 1; i >= 0; i-- )
2440 for(
int i = 0; i < colVector.
size(); i++ )
2442 shiftValue = colVector.
value(i);
2444 int r = colVector.
index(i);
2452 shiftValue2 -= shiftValue;
2498 for(
int i = 0; i < colVector.
size(); i++ )
2500 shiftValue = colVector.
value(i);
2502 int r = colVector.
index(i);
2510 shiftValue2 -= shiftValue;
2670 assert(sol.
_primal[numOrigCols] < 1);
2684 assert(sol.
_primal[numOrigCols] >= 1);
2690 if( sol.
_primal[numOrigCols] != 1 )
2693 for(
int i = 0; i < numOrigCols; i++ )
2741 for(
int c = numOrigCols - 1; c >= 0; c-- )
2746 #ifdef SOPLEX_WITH_GMP 2813 #ifdef SOPLEX_WITH_GMP 2818 assert(sol.
_slacks == activity);
2875 for(
int r = 0; r < numRows; r++ )
2878 ytransb += y[r] * (y[r] > 0 ? lhs[r] : rhs[r]);
2883 ytransA.
reDim(numCols);
2891 bool isTempFinite =
true;
2892 for(
int c = 0; c < numCols && isTempFinite; c++ )
2894 const Rational& minusRedCost = ytransA[c];
2896 if( minusRedCost > 0 )
2902 isTempFinite =
false;
2904 else if( minusRedCost < 0 )
2910 isTempFinite =
false;
2918 if( isTempFinite && temp < ytransb )
2931 for(
int c = 0; c < numCols; c++ )
2935 ytransA.
setValue(c, ytransA[c] - ytransb / lower[c]);
2939 else if( upper[c] < 0 )
2941 ytransA.
setValue(c, ytransA[c] - ytransb / upper[c]);
2952 MSG_INFO1(
spxout,
spxout <<
"Approximate Farkas proof to weak. Could not compute Farkas box. (1)\n" );
2958 const int size = ytransA.
size();
2959 for(
int n = 0; n < size; n++ )
2968 bool success =
false;
2973 assert(ytransb >= 0);
2978 if( n >= ytransA.
size() )
2989 int colIdx = ytransA.
index(n);
2998 ytransb.
subProduct(minusRedCost, lower[colIdx]);
2999 temp += minusRedCost;
3001 assert(ytransb >= 0);
3003 assert(temp == 0 || ytransb / temp > B);
3006 if( temp == 0 && ytransb == 0 )
3008 MSG_INFO1(
spxout,
spxout <<
"Approximate Farkas proof to weak. Could not compute Farkas box. (2)\n" );
3012 else if( temp == 0 )
3014 assert(ytransb > 0);
3031 ytransb.
subProduct(minusRedCost, upper[colIdx]);
3032 temp -= minusRedCost;
3034 assert(ytransb >= 0);
3036 assert(temp == 0 || ytransb / temp > B);
3039 if( temp == 0 && ytransb == 0 )
3041 MSG_INFO1(
spxout,
spxout <<
"Approximate Farkas proof to weak. Could not compute Farkas box. (2)\n" );
3045 else if( temp == 0 )
3047 assert(ytransb > 0);
3060 else if( minusRedCost == 0 )
3070 MSG_INFO1(
spxout,
spxout <<
"Computed Farkas box: provably no feasible solutions with components less than " 3089 #ifndef SOPLEX_MANUAL_ALT 3116 returnedBasis =
false;
3205 returnedBasis =
true;
3227 returnedBasis =
true;
3248 returnedBasis =
true;
3275 returnedBasis =
true;
3294 assert(rationalLP != 0);
3296 rationalLP->~SPxLPRational();
3312 bool fromScratch =
false;
3313 bool solved =
false;
3314 bool solvedFromScratch =
false;
3315 bool initialSolve =
true;
3316 bool increasedMarkowitz =
false;
3317 bool relaxedTolerances =
false;
3318 bool tightenedTolerances =
false;
3319 bool switchedScaler =
false;
3320 bool switchedSimplifier =
false;
3321 bool switchedRatiotester =
false;
3322 bool switchedPricer =
false;
3323 bool turnedoffPre =
false;
3332 if( forceNoSimplifier )
3339 result =
_solveRealForRational(fromScratch, primal, dual, basisStatusRows, basisStatusCols, returnedBasis);
3354 initialSolve =
false;
3362 turnedoffPre =
true;
3369 solvedFromScratch =
true;
3376 if( !increasedMarkowitz )
3381 increasedMarkowitz =
true;
3389 MSG_DEBUG( std::cout << std::endl <<
"Factorization failed." << std::endl );
3393 if( !solvedFromScratch )
3400 solvedFromScratch =
true;
3407 if( !switchedScaler )
3419 solvedFromScratch =
true;
3420 switchedScaler =
true;
3424 if( !switchedSimplifier && !forceNoSimplifier )
3436 solvedFromScratch =
true;
3437 switchedSimplifier =
true;
3443 if( !relaxedTolerances )
3450 solvedFromScratch =
false;
3461 solvedFromScratch =
false;
3467 if( !switchedRatiotester )
3476 switchedRatiotester =
true;
3477 solvedFromScratch =
false;
3481 if( !switchedPricer )
3490 switchedPricer =
true;
3491 solvedFromScratch =
false;
3527 for(
int i = 0; i < matrixdim; i++ )
3574 stoppedTime =
false;
3575 stoppedIter =
false;
3589 MSG_WARNING(
spxout,
spxout <<
"Warning: dimensioning error in rational matrix factorization (recovered).\n" );
3608 bool primalFeasible =
false;
3609 bool dualFeasible =
false;
3615 for(
int i = 0; i < basisStatusRows.
size(); i++ )
3619 basicPrimalRhs[i] = 0;
3620 basicDualRhs[j] = 0;
3630 basicPrimalRhs[i] = 0;
3652 for(
int i = 0; i < basisStatusCols.
size(); i++ )
3687 if( j != matrixdim )
3729 primalViolation = 0;
3730 primalFeasible =
true;
3731 for(
int i = 0; i < basisStatusRows.
size(); i++ )
3735 assert(j < matrixdim);
3738 violation += basicPrimal[j];
3739 if( violation > primalViolation )
3741 primalFeasible =
false;
3742 primalViolation = violation;
3745 violation += basicPrimal[j];
3747 if( violation > primalViolation )
3749 primalFeasible =
false;
3750 primalViolation = violation;
3755 for(
int i = 0; i < basisStatusCols.
size(); i++ )
3759 assert(j < matrixdim);
3764 violation -= basicPrimal[j];
3765 if( violation > primalViolation )
3767 primalFeasible =
false;
3768 primalViolation = violation;
3773 violation = basicPrimal[j];
3775 if( violation > primalViolation )
3777 primalFeasible =
false;
3778 primalViolation = violation;
3785 if( !primalFeasible )
3809 dualFeasible =
true;
3810 for(
int i = 0; i < basisStatusRows.
size(); i++ )
3822 else if( basicDual[i] < 0 )
3827 dualFeasible =
false;
3828 violation = -basicDual[i];
3829 if( violation > dualViolation )
3830 dualViolation = violation;
3833 <<
" and status " << basisStatusRows[i]
3838 else if( basicDual[i] > 0 )
3843 dualFeasible =
false;
3844 if( basicDual[i] > dualViolation )
3845 dualViolation = basicDual[i];
3848 <<
" and status " << basisStatusRows[i]
3856 for(
int i = 0; i < basisStatusCols.
size(); i++ )
3865 #ifdef SOPLEX_WITH_GMP 3879 dualFeasible =
false;
3891 dualFeasible =
false;
3907 optimal = primalFeasible && dualFeasible;
3918 for(
int i = 0; i < basisStatusCols.
size(); i++ )
3922 assert(j < matrixdim);
3924 sol.
_primal[i] = basicPrimal[j];
3950 sol.
_dual = basicDual;
4007 MSG_DEBUG(
spxout <<
"Rational reconstruction of primal solution successful.\n" );
4088 MSG_DEBUG(
spxout <<
"Rational reconstruction of dual vector successful.\n" );
4097 if( (!maximizing && sig > 0) || (maximizing && sig < 0) )
4101 MSG_DEBUG( std::cout <<
"complementary slackness violated by row " << r
4119 else if( (!maximizing && sig < 0) || (maximizing && sig > 0) )
4123 MSG_DEBUG( std::cout <<
"complementary slackness violated by row " << r
4156 if( (!maximizing && sig > 0) || (maximizing && sig < 0) )
4160 MSG_DEBUG( std::cout <<
"complementary slackness violated by column " << c
4178 else if( (!maximizing && sig < 0) || (maximizing && sig > 0) )
4182 MSG_DEBUG( std::cout <<
"complementary slackness violated by column " << c
const VectorBase< R > & rhs() const
Returns right hand side vector.
Rational spxAbs(const Rational &r)
Absolute.
const VectorRational & rhsRational() const
returns right-hand side vector
void _computeBasisInverseRational()
computes rational inverse of basis matrix as defined by _rationalLUSolverBind
textbook ratio test without stabilization
int unbdRefinements
number of refinement steps during undboundedness test
virtual void removeRow(int i)
Removes i 'th row.
Rational _rationalMaxscaleincr
free variable fixed to zero.
DVectorRational _unboundedRhs
bool isSetup() const
Returns setup status.
bool GE(Real a, Real b, Real eps=Param::epsilon())
returns true iff a >= b + eps
void reDim(int newdim, const bool setZero=true)
Resets DVectorBase's dimension to newdim.
Rational & addProduct(const Rational &r, const Rational &s)
add product of two rationals
void _transformEquality()
introduces slack variables to transform inequality constraints into equations for both rational and r...
DVectorBase< R > _dualFarkas
Timer * syncTime
time for synchronization between real and rational LP (included in solving time)
Basis is not known to be dual nor primal feasible.
int feasRefinements
number of refinement steps during infeasibility test
No matrix has yet been loaded.
virtual void unscalePrimal(const SPxLPBase< Real > &lp, Vector &x) const
unscale dense primal solution vector given in x.
int numRowsReal() const
returns number of rows
virtual void changeLower(const Vector &newLower, bool scale=false)
The time limit has been hit.
const VectorBase< R > & upper() const
Returns upper bound vector.
virtual Status getPrimal(Vector &vector) const
get solution vector for primal variables.
upper limit on objective value
THREADLOCAL const Real infinity
void _transformUnbounded()
transforms LP to unboundedness problem by moving the objective function to the constraints, changing right-hand side and bounds to zero, and adding an auxiliary variable for the decrease in the objective function
LPRowBase< Rational > LPRowRational
Result
Result of the simplification.
const SPxRatioTester * ratiotester() const
return loaded SPxRatioTester.
the problem was so much simplified that it vanished
continue iterative refinement with exact basic solution if not optimal?
void setBasis(const VarStatus rows[], const VarStatus cols[])
set the lp solver's basis.
virtual Result simplify(SPxLP &lp, Real eps, Real delta)=0
simplify SPxLP lp with identical primal and dual feasibility tolerance.
type of computational form, i.e., column or row representation
int stallRefinements
number of refinement steps without pivots
T * get_ptr()
get a C pointer to the data.
virtual void removeRowRange(int start, int end, int perm[]=0)
Removes rows from start to end (including both).
dual simplex algorithm, i.e., leaving for column and entering for row representation ...
int size() const
Number of used indices.
int numRowsRational() const
returns number of rows
SPxLPRational * _rationalLP
Status getBasis(VarStatus rows[], VarStatus cols[], const int rowsSize=-1, const int colsSize=-1) const
get current basis, and return solver status.
SPxSolver::Status _solveRealStable(bool acceptUnbounded, bool acceptInfeasible, VectorReal &primal, VectorReal &dual, DataArray< SPxSolver::VarStatus > &basisStatusRows, DataArray< SPxSolver::VarStatus > &basisStatusCols, bool &returnedBasis, const bool forceNoSimplifier=false)
solves real LP with recovery mechanism
primal simplex algorithm, i.e., entering for column and leaving for row representation ...
Real feastol() const
allowed primal feasibility tolerance.
time limit in seconds (INFTY if unlimited)
steepest edge pricer with exact initialization of norms
Rational _rationalFeastol
DVectorBase< R > _primalRay
DVectorBase< R > _redCost
int getFactorCount() const
number of factorizations performed
virtual void clearRowObjs()
primal feasibility tolerance
void getObj(VectorBase< R > &pobj) const
Gets objective vector.
void setType(Type tp)
set LEAVE or ENTER algorithm.
DVectorRational _feasLower
solve() aborted due to iteration limit.
virtual void changeUpper(const Vector &newUpper, bool scale=false)
mode for synchronizing real and rational LP
bool hasDualFarkas() const
is a dual farkas ray available?
void _optimizeRational()
solves rational LP
void setValue(int i, R x)
Sets i 'th element to x.
virtual void unscaleRedCost(const SPxLPBase< Real > &lp, Vector &r) const
unscale dense reduced cost vector given in r.
void _transformFeasibility()
transforms LP to feasibility problem by removing the objective function, shifting variables...
Abstract ratio test base class.Class SPxRatioTester is the virtual base class for computing the ratio...
virtual void unscaleDual(const SPxLPBase< Real > &lp, Vector &pi) const
unscale dense dual solution vector given in pi.
should cycling solutions be accepted during iterative refinement?
void _disableSimplifierAndScaler()
disables simplifier and scaler
DataArray< SPxSolver::VarStatus > _storedBasisStatusCols
void add(const LPColBase< R > &pcol)
Real lowerReal(int i) const
returns lower bound of column i
unsigned int _hasPrimalRay
Implementation of Sparse Linear Solver with Rational precision.
void _performFeasIRStable(SolRational &sol, bool &withDualFarkas, bool &stopped, bool &stoppedIter, bool &error)
performs iterative refinement on the auxiliary problem for testing feasibility
void _storeBasis()
store basis
Rational & subProduct(const Rational &r, const Rational &s)
subtract product of two rationals
Real upperReal(int i) const
returns upper bound of column i
Rational & invert()
inversion
int refinements
number of refinement steps
variable fixed to identical bounds.
virtual void removeCol(int i)
Removes i 'th column.
LP has been proven to be primal infeasible.
R & value(int n)
Reference to value of n 'th nonzero.
SPxSolver::Status _solveRealForRational(bool fromscratch, VectorReal &primal, VectorReal &dual, DataArray< SPxSolver::VarStatus > &basisStatusRows, DataArray< SPxSolver::VarStatus > &basisStatusCols, bool &returnedBasis)
solves real LP during iterative refinement
void _untransformUnbounded(SolRational &sol, bool unbounded)
undoes transformation to unboundedness problem
void dump() const
Prints out status.
Ids for LP columns.Class SPxColId provides DataKeys for the column indices of an SPxLP.
int intParam(const IntParam param) const
returns integer parameter value
void setOpttol(Real d)
set parameter opttol.
minimum number of stalling refinements since last pivot to trigger rational factorization ...
int sign(const Rational &r)
Sign function; returns 1 if r > 0, 0 if r = 0, and -1 if r < 0.
Wrapper for GMP type mpq_class.We wrap mpq_class so that we can replace it by a double type if GMP is...
Real rhsReal(int i) const
returns right-hand side of row i
should a rational factorization be performed after iterative refinement?
const SPxPricer * pricer() const
return loaded SPxPricer.
user sync of real and rational LP
LPColBase< Real > LPColReal
bound flipping ratio test for long steps in the dual simplex
Rational _rationalPosInfty
const VectorRational & lhsRational() const
returns left-hand side vector
int nRows() const
Returns number of rows in LP.
Rational objRational(int i) const
returns objective value of column i
void add(const SVectorBase< S > &vec)
Append nonzeros of sv.
virtual void changeRhs(const Vector &newRhs, bool scale=false)
virtual void start()=0
start timer, resume accounting user, system and real time.
virtual Real stop()=0
stop timer, return accounted user time.
void spx_alloc(T &p, int n=1)
Allocate memory.
simplification could be done
const UnitVectorRational * _unitVectorRational(const int i)
returns pointer to a constant unit vector available until destruction of the SoPlex class ...
virtual Status getDualfarkas(Vector &vector) const
get dual farkas proof of infeasibility.
LP is primal infeasible or unbounded.
Rational reconstruction of solution vector.
void _ensureDSVectorRationalMemory(DSVectorRational &vec, const int newmax) const
extends sparse vector to hold newmax entries if and only if it holds no more free entries ...
DataArray< SPxSolver::VarStatus > _basisStatusCols
DVectorRational _unboundedLower
bool reconstructVector(VectorRational &input, const Rational &denomBoundSquared, const DIdxSet *indexSet)
nothing known about basis status (possibly due to a singular basis in transformed problem) ...
virtual void changeRowObj(const Vector &newObj, bool scale=false)
virtual void writeFile(const char *filename, const NameSet *rowNames=0, const NameSet *colNames=0, const DIdxSet *p_intvars=0) const
Write loaded LP to filename.
SPxStatus status() const
returns current SPxStatus.
DataArray< RangeType > _colTypes
Real getSolveTime() const
time spent in solves
SLUFactorRational _rationalLUSolver
void _solveRealLPAndRecordStatistics()
call floating-point solver and update statistics on iterations etc.
Status status() const
Status of solution process.
void setMarkowitz(Real m)
sets minimum Markowitz threshold.
lower threshold in lifting (nonzero matrix coefficients with smaller absolute value will be reformula...
int & index(int n)
Reference to index of n 'th nonzero.
virtual void changeMaxObj(const VectorBase< R > &newObj, bool scale=false)
Changes objective vector to newObj. scale determines whether the new data should be scaled...
Timer * rationalTime
time for rational LP solving (included in solving time)
bool _isConsistent() const
checks consistency
void _performOptIRStable(SolRational &sol, bool acceptUnbounded, bool acceptInfeasible, int minRounds, bool &primalFeasible, bool &dualFeasible, bool &infeasible, bool &unbounded, bool &stopped, bool &stoppedIter, bool &error)
solves current problem with iterative refinement and recovery mechanism
LP has been solved to optimality.
void setTimeLimit(const Real limit)
set time limit on factorization
#define MSG_INFO2(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO2.
bool _upperFinite(const RangeType &rangeType) const
checks whether RangeType corresponds to finite upper bound
unsigned int _hasDualFarkas
void append(const T &t)
append element t.
LPRowBase< Real > LPRowReal
void _restoreLPReal()
restores objective, bounds, and sides of real LP
DVectorBase< Rational > DVectorRational
void _project(SolRational &sol)
undoes lifting
Class for collecting statistical information.
void clearNum(int n)
Sets n 'th nonzero element to 0 (index n must exist).
solve() aborted due to time limit.
void _performUnboundedIRStable(SolRational &sol, bool &hasUnboundedRay, bool &stopped, bool &stoppedIter, bool &error)
performs iterative refinement on the auxiliary problem for testing unboundedness
void addIdx(int i)
adds index i to the index set
round scaling factors for iterative refinement to powers of two?
const T * get_const_ptr() const
get a const C pointer to the data.
virtual void changeLhs(const Vector &newLhs, bool scale=false)
void _computeInfeasBox(SolRational &sol, bool transformed)
virtual void changeLower(const VectorBase< R > &newLower, bool scale=false)
Changes vector of lower bounds to newLower. scale determines whether the new data should be scaled...
Statistics * _statistics
statistics since last call to solveReal() or solveRational()
virtual void changeRhs(const VectorBase< R > &newRhs, bool scale=false)
Changes right hand side vector for constraints to newRhs. scale determines whether the new data shoul...
LPColSetRational _slackCols
bool isPrimalFeasible() const
is the stored solution primal feasible?
R obj(int i) const
Returns objective value of column i.
void solveRight(VectorRational &x, const VectorRational &b)
Solves .
DVectorRational _feasUpper
const VectorBase< R > & lhs() const
Returns left hand side vector.
void clear()
Clears vector.
virtual void addPrimalActivity(const SVectorBase< R > &primal, VectorBase< R > &activity) const
Updates activity of the rows for a given primal vector; activity does not need to be zero...
int numColsRational() const
returns number of columns
force iterative refinement
Abstract pricer base class.Class SPxPricer is a pure virtual class defining the interface for pricer ...
bool _reconstructSolutionRational(SolRational &sol, DataArray< SPxSolver::VarStatus > &basisStatusRows, DataArray< SPxSolver::VarStatus > &basisStatusCols, const Rational &denomBoundSquared)
attempts rational reconstruction of primal-dual solution
virtual void getBasis(SPxSolver::VarStatus[], SPxSolver::VarStatus[], const int rowsSize=-1, const int colsSize=-1) const =0
get optimal basis.
RangeType _switchRangeType(const RangeType &rangeType) const
switches RANGETYPE_LOWER to RANGETYPE_UPPER and vice versa
variable set to its upper bound.
void setEpsilon(R eps)
Changes the non-zero epsilon, invalidating the setup. */.
Dynamic index set.Class DIdxSet provides dynamic IdxSet in the sense, that no restrictions are posed ...
virtual void changeBounds(const VectorBase< R > &newLower, const VectorBase< R > &newUpper, bool scale=false)
Changes variable bounds to newLower and newUpper. scale determines whether the new data should be sca...
Real realParam(const RealParam param) const
returns real parameter value
Real luSolveTimeRational
time for solving linear systems in rational precision
primal infeasibility was detected
virtual Real time() const =0
DVectorRational _modUpper
SPxLPBase< Rational > SPxLPRational
const SVectorRational & colVectorRational(int i) const
returns vector of column i
const VectorBase< R > & maxRowObj() const
int index(int n) const
Returns index of the n 'th nonzero element.
SPxDefaultRT _ratiotesterTextbook
Status load(const SVectorRational *vec[], int dim)
virtual const Vector & unsimplifiedPrimal()=0
returns a reference to the unsimplified primal solution.
virtual void loadLP(const SPxLP &LP, bool initSlackBasis=true)
copy LP.
variable set to its lower bound.
LPColBase< Rational > LPColRational
Real lhsReal(int i) const
returns left-hand side of row i
Preconfigured SoPlex LP solver.
#define MSG_INFO3(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO3.
void add(int i, const R &v)
Append one nonzero (i,v).
Real markowitz()
returns Markowitz threshold.
virtual void changeUpper(const VectorBase< R > &newUpper, bool scale=false)
Changes vector of upper bounds to newUpper. scale determines whether the new data should be scaled...
void reDim(int newdim)
Resets dimension to newdim.
lower and upper bound finite, but different
int luFactorizationsRational
number of basis matrix factorizations in rational precision
bool isDualFeasible() const
is a dual solution available?
Timer * preprocessingTime
preprocessing time
virtual void changeObj(const VectorBase< R > &newObj, bool scale=false)
Changes objective vector to newObj. scale determines whether the new data should be scaled...
void _storeLPReal()
stores objective, bounds, and sides of real LP
Real getFactorTime() const
time spent in factorizations
Rational _rationalNegInfty
virtual void addDualActivity(const SVectorBase< R > &dual, VectorBase< R > &activity) const
Updates "dual" activity of the columns for a given dual vector, i.e., y^T A; activity does not need t...
VectorBase< R > & multAdd(const S &x, const VectorBase< T > &vec)
Addition of scaled vector.
lower bound equals upper bound
virtual void addCol(const LPColBase< R > &col, bool scale=false)
virtual void scale(SPxLPBase< Real > &lp, bool persistent=true)=0
scale SPxLP.
Timer * reconstructionTime
time for rational reconstructions
int dim() const
Dimension of vector.
int size() const
Returns the number of nonzeros.
Everything should be within this namespace.
working tolerance for feasibility in floating-point solver during iterative refinement ...
bool _lowerFinite(const RangeType &rangeType) const
checks whether RangeType corresponds to finite lower bound
virtual void changeRange(const VectorBase< R > &newLhs, const VectorBase< R > &newRhs, bool scale=false)
Changes left and right hand side vectors. scale determines whether the new data should be scaled...
void clear()
Remove all indices.
DataArray< RangeType > _rowTypes
apply rational reconstruction after each iterative refinement?
solve() aborted due to detection of cycling.
Saving LPs in a form suitable for SoPlex.Class SPxLPBase provides the data structures required for sa...
DSVectorBase< Real > DSVectorReal
primal unboundedness was detected
working tolerance for optimality in floating-point solver during iterative refinement ...
#define MSG_WARNING(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::WARNING.
virtual void unsimplify(const Vector &, const Vector &, const Vector &, const Vector &, const SPxSolver::VarStatus[], const SPxSolver::VarStatus[], bool isOptimal=true)=0
reconstructs an optimal solution for the unsimplified LP.
Real spxNextafter(Real x, Real y)
int iterations
number of iterations/pivots
const VectorBase< R > & maxObj() const
Returns objective vector for maximization problem.
DVectorRational _unboundedLhs
DSVectorRational _primalDualDiff
void setup()
Initializes nonzero indices for elements with absolute values above epsilon and sets all other elemen...
DVectorRational _unboundedUpper
const VectorRational & upperRational() const
returns upper bound vector
column representation Ax - s = 0, lower <= x <= upper, lhs <= s <= rhs
nothing known on loaded problem.
type of algorithm, i.e., primal or dual
const SVectorBase< R > & rowVector(int i) const
Gets row vector of row i.
virtual void addRow(const LPRowBase< R > &row, bool scale=false)
virtual bool isUnsimplified() const
specifies whether an optimal solution has already been unsimplified.
DataArray< SPxSolver::VarStatus > _basisStatusRows
virtual const Vector & unsimplifiedDual()=0
returns a reference to the unsimplified dual solution.
should dual infeasibility be tested in order to try to return a dual solution even if primal infeasib...
void _factorizeColumnRational(SolRational &sol, DataArray< SPxSolver::VarStatus > &basisStatusRows, DataArray< SPxSolver::VarStatus > &basisStatusCols, bool &stoppedTime, bool &stoppedIter, bool &error, bool &optimal)
factorizes rational basis matrix in column representation
Timer * solvingTime
solving time
int size() const
return nr. of elements.
Type type() const
return current Type.
bool boolParam(const BoolParam param) const
returns boolean parameter value
should lifting be used to reduce range of nonzero matrix coefficients?
virtual Status getRedCost(Vector &vector) const
get vector of reduced costs.
DataArray< int > _rationalLUSolverBind
#define MSG_INFO1(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO1.
virtual void removeColRange(int start, int end, int perm[]=0)
Removes columns from start to end (including both).
const SVectorBase< R > & colVector(int i) const
Returns column vector of column i.
int nCols() const
Returns number of columns in LP.
unsigned int _isPrimalFeasible
virtual void changeElement(int i, int j, const R &val, bool scale=false)
Changes LP element (i, j) to val. scale determines whether the new data should be scaled...
lower limit on objective value
DSVectorRational _tauColVector
DVectorRational _modLower
bool _isSolveStopped(bool &stoppedTime, bool &stoppedIter) const
should solving process be stopped?
virtual void changeLhs(const VectorBase< R > &newLhs, bool scale=false)
Changes left hand side vector for constraints to newLhs. scale determines whether the new data should...
void setFeastol(Real d)
set parameter feastol.
Timer * transformTime
time for transforming LPs (included in solving time)
void invalidate()
invalidate solution
void _restoreBasis()
restore basis
equilibrium scaling on rows and columns
bool hasPrimalRay() const
is a primal unbounded ray available?
bool setIntParam(const IntParam param, const int value, const bool init=true)
sets integer parameter value; returns true on success
std::string rationalToString(const Rational &r, const int precision)
convert rational number to string
geometric frequency at which to apply rational reconstruction
Real opttol() const
allowed optimality, i.e., dual feasibility tolerance.
void _enableSimplifierAndScaler()
enables simplifier and scaler according to current parameters
unsigned int _isDualFeasible
virtual void unscaleSlacks(const SPxLPBase< Real > &lp, Vector &s) const
unscale dense slack vector given in s.
bool setBoolParam(const BoolParam param, const bool value, const bool init=true)
sets boolean parameter value; returns true on success
should LP be transformed to equality form before a rational solve?
const SVectorBase< R > & colVector(int i) const
Returns colVector of i 'th LPColBase in LPColSetBase.
virtual void setTerminationValue(Real value=infinity)
set objective limit.
void clear()
Removes all LPColBases from the set.
void solveLeft(VectorRational &x, const VectorRational &b)
Solves .
const SPxBasis & basis() const
Return current basis.
virtual void changeObj(const Vector &newObj, bool scale=false)
scale determines whether the new data needs to be scaled according to the existing LP (persistent sca...
virtual void reLoad()
reload LP.
upper threshold in lifting (nonzero matrix coefficients with larger absolute value will be reformulat...
DataArray< SPxSolver::VarStatus > _storedBasisStatusRows
int numColsReal() const
returns number of columns
void resetCounters()
reset timers and counters
void reSize(int newsize)
reset size to newsize.
Real luFactorizationTimeRational
time for factorizing bases matrices in rational precision
void _lift()
reduces matrix coefficient in absolute value by the lifting procedure of Thiele et al...
const VectorBase< R > & lower() const
Returns (internal and possibly scaled) lower bound vector.
SPxSolver::Status _status
int num() const
Returns the number of LPColBases currently in LPColSetBase.
virtual void computePrimalActivity(const VectorBase< R > &primal, VectorBase< R > &activity, const bool unscaled=true) const
Computes activity of the rows for a given primal vector; activity does not need to be zero...
const Desc & desc() const
int rationalReconstructions
number of rational reconstructions performed
solve() aborted due to objective limit.
void spx_free(T &p)
Release memory.
SPxSimplifier * _simplifier
virtual void addCols(const LPColSetBase< R > &pset, bool scale=false)
void _untransformEquality(SolRational &sol)
undoes transformation to equality form
int pivotRefinements
number of refinement steps until final basis is reached
virtual Status getDual(Vector &vector) const
get current solution vector for dual variables.
Basis is singular, numerical troubles?
R value(int n) const
Returns value of the n 'th nonzero element.
virtual void factorize()
Factorize basis matrix.
upper bound is finite, lower bound is infinite
LP has a usable Basis (maybe LP is changed).
modified Harris ratio test
dual infeasibility was detected
virtual Status getSlacks(Vector &vector) const
get vector of slack variables.
void _untransformFeasibility(SolRational &sol, bool infeasible)
undoes transformation to feasibility problem
LP has been proven to be primal unbounded.
virtual void subDualActivity(const VectorBase< R > &dual, VectorBase< R > &activity) const
Updates "dual" activity of the columns for a given dual vector, i.e., y^T A; activity does not need t...
No Problem has been loaded to the basis.
void setDelta(Real d)
set parameter delta, i.e., set feastol and opttol to same value.
const VectorRational & lowerRational() const
returns lower bound vector
Rational & powRound()
round up to next power of two