29 bool hasUnboundedRay =
false;
30 bool infeasibilityNotCertified =
false;
31 bool unboundednessNotCertified =
false;
87 #ifdef SOPLEX_WITH_CPX 103 bool primalFeasible =
false;
104 bool dualFeasible =
false;
105 bool infeasible =
false;
106 bool unbounded =
false;
113 primalFeasible, dualFeasible, infeasible, unbounded, stoppedTime, stoppedIter, error);
133 else if(unbounded && !unboundednessNotCertified)
139 assert(!hasUnboundedRay || solUnbounded.
hasPrimalRay());
140 assert(!solUnbounded.
hasPrimalRay() || hasUnboundedRay);
158 unboundednessNotCertified = !hasUnboundedRay;
202 else if(hasUnboundedRay)
215 else if(infeasible && !infeasibilityNotCertified)
229 infeasibilityNotCertified = !infeasible;
250 assert(!hasUnboundedRay || solUnbounded.
hasPrimalRay());
251 assert(!solUnbounded.
hasPrimalRay() || hasUnboundedRay);
289 else if(hasUnboundedRay)
301 else if(primalFeasible && dualFeasible)
325 #ifdef SOPLEX_WITH_CPX 373 bool acceptUnbounded,
374 bool acceptInfeasible,
376 bool& primalFeasible,
387 primalFeasible =
false;
388 dualFeasible =
false;
510 sol.
_primal[c] = primalReal[c];
529 sol.
_dual[r] = dualReal[r];
531 if(dualReal[r] != 0.0)
549 const Rational violationImprovementFactor = 0.9;
550 const Rational errorCorrectionFactor = 1.1;
552 int numFailedRefinements = 0;
563 bool factorSolNewBasis =
true;
564 int lastStallRefinements = 0;
565 int nextRatrecRefinement = 0;
572 MSG_DEBUG(std::cout <<
"Computing primal violations.\n");
673 if(
_modRhs[r] < -sideViolation)
682 MSG_DEBUG(std::cout <<
"Computing dual violations.\n");
685 redCostViolation = 0;
697 && sol.
_redCost[c] < -redCostViolation)
699 MSG_DEBUG(std::cout <<
"basisStatusCol = " << basisStatusCol
704 redCostViolation = -sol.
_redCost[c];
709 && sol.
_redCost[c] > redCostViolation)
711 MSG_DEBUG(std::cout <<
"basisStatusCol = " << basisStatusCol
733 && sol.
_dual[r] < -dualViolation)
735 MSG_DEBUG(std::cout <<
"basisStatusRow = " << basisStatusRow
740 dualViolation = -sol.
_dual[r];
745 && sol.
_dual[r] > dualViolation)
747 MSG_DEBUG(std::cout <<
"basisStatusRow = " << basisStatusRow
752 dualViolation = sol.
_dual[r];
762 <<
"Max. reduced cost violation = " <<
rationalToString(redCostViolation) <<
"\n" 766 << std::fixed << std::setprecision(2) << std::setw(10)
767 <<
"Progress table: " 772 << std::setw(10) <<
rationalToString(boundsViolation > sideViolation ? boundsViolation :
773 sideViolation, 2) <<
" & " 774 << std::setw(10) <<
rationalToString(redCostViolation > dualViolation ? redCostViolation :
775 dualViolation, 2) <<
"\n");
781 if(primalFeasible && dualFeasible)
791 "Tolerances reached but minRounds forcing additional refinement rounds.\n");
800 maxViolation = boundsViolation;
802 if(sideViolation > maxViolation)
803 maxViolation = sideViolation;
805 if(redCostViolation > maxViolation)
806 maxViolation = redCostViolation;
808 if(dualViolation > maxViolation)
809 maxViolation = dualViolation;
811 bestViolation *= violationImprovementFactor;
813 if(maxViolation > bestViolation)
816 numFailedRefinements++;
819 bestViolation = maxViolation;
828 errorCorrection *= errorCorrectionFactor;
830 if(performRatrec && maxViolation > 0)
834 maxViolation *= errorCorrection;
840 primalFeasible =
true;
846 MSG_DEBUG(
spxout <<
"Next rational reconstruction after refinement " << nextRatrecRefinement <<
851 if(performRatfac && maxViolation > 0)
858 factorSolNewBasis =
false;
872 primalFeasible =
true;
887 maxScale = primalScale;
890 primalScale = boundsViolation > sideViolation ? boundsViolation : sideViolation;
892 if(primalScale < redCostViolation)
893 primalScale = redCostViolation;
895 assert(primalScale >= 0);
901 if(primalScale > maxScale)
902 primalScale = maxScale;
905 primalScale = maxScale;
964 assert(primalScale >= 1);
1014 maxScale = dualScale;
1017 dualScale = redCostViolation > dualViolation ? redCostViolation : dualViolation;
1018 assert(dualScale >= 0);
1024 if(dualScale > maxScale)
1025 dualScale = maxScale;
1028 dualScale = maxScale;
1033 if(dualScale > primalScale)
1034 dualScale = primalScale;
1066 newRowObj = sol.
_dual[r];
1067 newRowObj *= dualScale;
1091 int col = numOrigCols + i;
1115 MSG_DEBUG(
spxout <<
"setting basis in solver " << (_hasBasis ?
"successful" :
"failed") <<
1130 lastStallRefinements++;
1135 factorSolNewBasis =
true;
1136 lastStallRefinements = 0;
1179 MSG_DEBUG(std::cout <<
"Correcting primal solution.\n");
1182 Rational primalScaleInverse = primalScale;
1183 primalScaleInverse.
invert();
1246 if(primalReal[c] == 1.0)
1254 else if(primalReal[c] == -1.0)
1263 else if(primalReal[c] != 0.0)
1283 #ifdef SOPLEX_WITH_GMP 1287 assert(sol.
_slacks == activity);
1298 MSG_DEBUG(std::cout <<
"Correcting dual solution.\n");
1308 Rational debugRedCostViolation = 0;
1320 && debugRedCost[c] < -debugRedCostViolation)
1322 MSG_DEBUG(std::cout <<
"basisStatusCol = " << basisStatusCol
1328 debugRedCostViolation = -debugRedCost[c];
1333 && debugRedCost[c] > debugRedCostViolation)
1335 MSG_DEBUG(std::cout <<
"basisStatusCol = " << basisStatusCol
1341 debugRedCostViolation = debugRedCost[c];
1347 Rational debugBasicDualViolation = 0;
1361 && val > debugDualViolation)
1363 MSG_DEBUG(std::cout <<
"basisStatusRow = " << basisStatusRow
1367 <<
", dualReal[r] = " << dualReal[r]
1369 debugDualViolation = val;
1374 && val < -debugDualViolation)
1376 MSG_DEBUG(std::cout <<
"basisStatusRow = " << basisStatusRow
1380 <<
", dualReal[r] = " << dualReal[r]
1382 debugDualViolation = -val;
1387 MSG_DEBUG(std::cout <<
"basisStatusRow = " << basisStatusRow
1391 <<
", dualReal[r] = " << dualReal[r]
1393 debugBasicDualViolation =
spxAbs(val);
1398 || debugBasicDualViolation > 1e-9)
1404 <<
" (red. cost, dual, basic).\n");
1409 Rational dualScaleInverseNeg = dualScale;
1410 dualScaleInverseNeg.
invert();
1411 dualScaleInverseNeg *= -1;
1427 if(dualReal[r] != 0)
1471 if(numCorrectedPrimals + numCorrectedDuals > 0)
1474 numCorrectedDuals <<
" dual values.\n");
1516 bool& hasUnboundedRay,
1521 bool primalFeasible;
1536 _performOptIRStable(sol,
false,
false, 0, primalFeasible, dualFeasible, infeasible, unbounded,
1537 stopped, stoppedIter, error);
1546 hasUnboundedRay =
false;
1550 else if(error || unbounded || infeasible || !primalFeasible || !dualFeasible)
1553 hasUnboundedRay =
false;
1571 hasUnboundedRay = (tau >= 1);
1583 bool& withDualFarkas,
1588 bool primalFeasible;
1592 bool success =
false;
1616 _performOptIRStable(sol,
false,
false, 0, primalFeasible, dualFeasible, infeasible, unbounded,
1617 stopped, stoppedIter, error);
1626 withDualFarkas =
false;
1630 else if(error || unbounded || infeasible || !primalFeasible || !dualFeasible)
1633 withDualFarkas =
false;
1674 while(!error && !success && !stopped);
1685 MSG_DEBUG(std::cout <<
"Reducing matrix coefficients by lifting.\n");
1706 MSG_DEBUG(std::cout <<
"in lifting: examining column " << i <<
"\n");
1711 bool addedLiftingRow =
false;
1712 int liftingColumnIndex = -1;
1715 for(
int k = colVector.
size() - 1; k >= 0; k--)
1719 if(
spxAbs(value) > maxValue)
1722 value) <<
" in row " << colVector.
index(k) <<
"\n");
1725 if(!addedLiftingRow)
1727 MSG_DEBUG(std::cout <<
" --> adding lifting row\n");
1729 assert(liftingRowVector.
size() == 0);
1732 liftingRowVector.
add(i, maxValue);
1733 liftingRowVector.
add(liftingColumnIndex, -1);
1744 liftingRowVector.
clear();
1745 addedLiftingRow =
true;
1749 int rowIndex = colVector.
index(k);
1750 assert(rowIndex >= 0);
1754 MSG_DEBUG(std::cout <<
" --> changing matrix\n");
1762 newValue /= maxValue;
1774 MSG_DEBUG(std::cout <<
"in lifting: examining column " << i <<
"\n");
1779 bool addedLiftingRow =
false;
1780 int liftingColumnIndex = -1;
1783 for(
int k = colVector.
size() - 1; k >= 0; k--)
1787 if(
spxAbs(value) < minValue)
1790 value) <<
" in row " << colVector.
index(k) <<
"\n");
1793 if(!addedLiftingRow)
1795 MSG_DEBUG(std::cout <<
" --> adding lifting row\n");
1797 assert(liftingRowVector.
size() == 0);
1800 liftingRowVector.
add(i, minValue);
1801 liftingRowVector.
add(liftingColumnIndex, -1);
1812 liftingRowVector.
clear();
1813 addedLiftingRow =
true;
1817 int rowIndex = colVector.
index(k);
1818 assert(rowIndex >= 0);
1822 MSG_DEBUG(std::cout <<
" --> changing matrix\n");
1830 newValue /= minValue;
1925 "Warning: lost basis during project phase because of nonbasic lifting column.\n");
1936 "Warning: lost basis during project phase because of basic lifting row.\n");
1961 #ifndef SOPLEX_MANUAL_ALT 1986 #ifndef SOPLEX_MANUAL_ALT 2040 MSG_DEBUG(std::cout <<
"Transforming rows to equation form.\n");
2117 " slack columns to transform rows to equality form.\n");
2140 int col = numOrigCols + i;
2162 int col = numOrigCols + i;
2172 MSG_DEBUG(std::cout <<
"slack column " << col <<
" for row " << row
2214 int col = numOrigCols + i;
2310 obj.
add(numOrigCols, -1);
2401 _basisStatusRows.reSize(numOrigRows);
2416 sol.
_dual /= -alpha;
2434 for(
int i = objRowVector.
size() - 1; i >= 0; i--)
2591 for(
int i = 0; i < colVector.
size(); i++)
2593 shiftValue = colVector.
value(i);
2595 int r = colVector.
index(i);
2603 shiftValue2 -= shiftValue;
2650 for(
int i = 0; i < colVector.
size(); i++)
2652 shiftValue = colVector.
value(i);
2654 int r = colVector.
index(i);
2662 shiftValue2 -= shiftValue;
2831 assert(sol.
_primal[numOrigCols] < 1);
2845 assert(sol.
_primal[numOrigCols] >= 1);
2851 if(sol.
_primal[numOrigCols] != 1)
2855 for(
int i = 0; i < numOrigCols; i++)
2907 for(
int c = numOrigCols - 1; c >= 0; c--)
2913 #ifdef SOPLEX_WITH_GMP 2985 #ifdef SOPLEX_WITH_GMP 2991 assert(sol.
_slacks == activity);
3049 for(
int r = 0; r < numRows; r++)
3052 ytransb += y[r] * (y[r] > 0 ? lhs[r] : rhs[r]);
3057 ytransA.
reDim(numCols);
3065 bool isTempFinite =
true;
3067 for(
int c = 0; c < numCols && isTempFinite; c++)
3069 const Rational& minusRedCost = ytransA[c];
3071 if(minusRedCost > 0)
3078 isTempFinite =
false;
3080 else if(minusRedCost < 0)
3087 isTempFinite =
false;
3092 temp) :
"infinite") <<
"\n");
3096 if(isTempFinite && temp < ytransb)
3109 for(
int c = 0; c < numCols; c++)
3113 ytransA.
setValue(c, ytransA[c] - ytransb / lower[c]);
3117 else if(upper[c] < 0)
3119 ytransA.
setValue(c, ytransA[c] - ytransb / upper[c]);
3131 "Approximate Farkas proof to weak. Could not compute Farkas box. (1)\n");
3137 const int size = ytransA.
size();
3139 for(
int n = 0; n < size; n++)
3148 bool success =
false;
3153 assert(ytransb >= 0);
3158 if(n >= ytransA.
size())
3169 int colIdx = ytransA.
index(n);
3179 ytransb.
subProduct(minusRedCost, lower[colIdx]);
3180 temp += minusRedCost;
3182 assert(ytransb >= 0);
3184 assert(temp == 0 || ytransb / temp > B);
3187 if(temp == 0 && ytransb == 0)
3190 "Approximate Farkas proof to weak. Could not compute Farkas box. (2)\n");
3196 assert(ytransb > 0);
3213 ytransb.
subProduct(minusRedCost, upper[colIdx]);
3214 temp -= minusRedCost;
3216 assert(ytransb >= 0);
3218 assert(temp == 0 || ytransb / temp > B);
3221 if(temp == 0 && ytransb == 0)
3224 "Approximate Farkas proof to weak. Could not compute Farkas box. (2)\n");
3230 assert(ytransb > 0);
3243 else if(minusRedCost == 0)
3254 "Computed Farkas box: provably no feasible solutions with components less than " 3275 #ifndef SOPLEX_MANUAL_ALT 3305 returnedBasis =
false;
3391 basisStatusCols.
size());
3402 basisStatusCols.
size());
3403 returnedBasis =
true;
3425 basisStatusCols.
size());
3426 returnedBasis =
true;
3448 basisStatusCols.
size());
3449 returnedBasis =
true;
3480 basisStatusCols.
size());
3481 returnedBasis =
true;
3500 assert(rationalLP != 0);
3502 rationalLP->~SPxLPRational();
3518 const bool forceNoSimplifier)
3522 bool fromScratch =
false;
3523 bool solved =
false;
3524 bool solvedFromScratch =
false;
3525 bool initialSolve =
true;
3526 bool increasedMarkowitz =
false;
3527 bool relaxedTolerances =
false;
3528 bool tightenedTolerances =
false;
3529 bool switchedScaler =
false;
3530 bool switchedSimplifier =
false;
3531 bool switchedRatiotester =
false;
3532 bool switchedPricer =
false;
3533 bool turnedoffPre =
false;
3542 if(forceNoSimplifier)
3565 initialSolve =
false;
3574 turnedoffPre =
true;
3581 solvedFromScratch =
true;
3588 if(!increasedMarkowitz)
3593 increasedMarkowitz =
true;
3602 MSG_DEBUG(std::cout << std::endl <<
"Factorization failed." << std::endl);
3606 if(!solvedFromScratch)
3613 solvedFromScratch =
true;
3632 solvedFromScratch =
true;
3633 switchedScaler =
true;
3637 if(!switchedSimplifier && !forceNoSimplifier)
3649 solvedFromScratch =
true;
3650 switchedSimplifier =
true;
3656 if(!relaxedTolerances)
3663 solvedFromScratch =
false;
3674 solvedFromScratch =
false;
3680 if(!switchedRatiotester)
3691 switchedRatiotester =
true;
3692 solvedFromScratch =
false;
3707 switchedPricer =
true;
3708 solvedFromScratch =
false;
3744 for(
int i = 0; i < matrixdim; i++)
3790 bool& error,
bool& optimal)
3795 stoppedTime =
false;
3796 stoppedIter =
false;
3813 "Warning: dimensioning error in rational matrix factorization (recovered).\n");
3833 bool primalFeasible =
false;
3834 bool dualFeasible =
false;
3841 for(
int i = 0; i < basisStatusRows.
size(); i++)
3845 basicPrimalRhs[i] = 0;
3846 basicDualRhs[j] = 0;
3858 basicPrimalRhs[i] = 0;
3881 for(
int i = 0; i < basisStatusCols.
size(); i++)
3962 primalViolation = 0;
3963 primalFeasible =
true;
3965 for(
int i = 0; i < basisStatusRows.
size(); i++)
3969 assert(j < matrixdim);
3972 violation += basicPrimal[j];
3974 if(violation > primalViolation)
3976 primalFeasible =
false;
3977 primalViolation = violation;
3981 violation += basicPrimal[j];
3984 if(violation > primalViolation)
3986 primalFeasible =
false;
3987 primalViolation = violation;
3994 for(
int i = 0; i < basisStatusCols.
size(); i++)
3998 assert(j < matrixdim);
4004 violation -= basicPrimal[j];
4006 if(violation > primalViolation)
4008 primalFeasible =
false;
4009 primalViolation = violation;
4015 violation = basicPrimal[j];
4018 if(violation > primalViolation)
4020 primalFeasible =
false;
4021 primalViolation = violation;
4054 dualFeasible =
true;
4056 for(
int i = 0; i < basisStatusRows.
size(); i++)
4069 else if(basicDual[i] < 0)
4075 dualFeasible =
false;
4076 violation = -basicDual[i];
4078 if(violation > dualViolation)
4079 dualViolation = violation;
4083 <<
" and status " << basisStatusRows[i]
4089 else if(basicDual[i] > 0)
4095 dualFeasible =
false;
4097 if(basicDual[i] > dualViolation)
4098 dualViolation = basicDual[i];
4102 <<
" and status " << basisStatusRows[i]
4111 for(
int i = 0; i < basisStatusCols.
size(); i++)
4120 #ifdef SOPLEX_WITH_GMP 4138 dualFeasible =
false;
4154 dualFeasible =
false;
4171 optimal = primalFeasible && dualFeasible;
4186 for(
int i = 0; i < basisStatusCols.
size(); i++)
4190 assert(j < matrixdim);
4192 sol.
_primal[i] = basicPrimal[j];
4219 sol.
_dual = basicDual;
4281 MSG_DEBUG(
spxout <<
"Rational reconstruction of primal solution successful.\n");
4368 MSG_DEBUG(
spxout <<
"Rational reconstruction of dual vector successful.\n");
4378 if((!maximizing && sig > 0) || (maximizing && sig < 0))
4382 MSG_DEBUG(std::cout <<
"complementary slackness violated by row " << r
4400 else if((!maximizing && sig < 0) || (maximizing && sig > 0))
4404 MSG_DEBUG(std::cout <<
"complementary slackness violated by row " << r
4437 if((!maximizing && sig > 0) || (maximizing && sig < 0))
4441 MSG_DEBUG(std::cout <<
"complementary slackness violated by column " << c
4459 else if((!maximizing && sig < 0) || (maximizing && sig > 0))
4463 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
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
steepest edge pricer with exact initialization of norms
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).
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
Basis is optimal, i.e. dual and primal feasible.
Real feastol() const
allowed primal feasibility tolerance.
time limit in seconds (INFTY if unlimited)
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
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.
LPColBase< Real > LPColReal
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 ...
column representation Ax - s = 0, lower <= x <= upper, lhs <= s <= rhs
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.
DataArray< RangeType > _colTypes
Real getSolveTime() const
time spent in solves
SLUFactorRational _rationalLUSolver
void _solveRealLPAndRecordStatistics()
call floating-point solver and update statistics on iterations etc.
user sync of real and rational LP
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
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.
dual simplex algorithm, i.e., leaving for column and entering for row representation ...
force iterative refinement
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...
textbook ratio test without stabilization
void clear()
Remove all indices.
DataArray< RangeType > _rowTypes
apply rational reconstruction after each iterative refinement?
solve() aborted due to detection of cycling.
bound flipping ratio test for long steps in the dual simplex
Saving LPs in a form suitable for SoPlex.Class SPxLPBase provides the data structures required for sa...
DSVectorBase< Real > DSVectorReal
equilibrium scaling on rows and columns
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
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.
primal simplex algorithm, i.e., entering for column and leaving for row representation ...
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
modified Harris ratio test
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
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
LP has been proven to be primal unbounded.
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).
dual infeasibility was detected
virtual Status getSlacks(Vector &vector) const
get vector of slack variables.
void setBasisStatus(SPxBasis::SPxStatus stat)
set the lp solver's basis status.
void _untransformFeasibility(SolRational &sol, bool infeasible)
undoes transformation to feasibility problem
LP has been proven to be primal unbounded.
LP has been proven to be primal infeasible.
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