30 bool hasUnboundedRay =
false;
31 bool infeasibilityNotCertified =
false;
32 bool unboundednessNotCertified =
false;
86 #ifdef SOPLEX_WITH_CPX 101 bool primalFeasible =
false;
102 bool dualFeasible =
false;
103 bool infeasible =
false;
104 bool unbounded =
false;
111 primalFeasible, dualFeasible, infeasible, unbounded, stoppedTime, stoppedIter, error);
120 else if( stoppedTime )
125 else if( stoppedIter )
131 else if( unbounded && !unboundednessNotCertified )
137 assert(!hasUnboundedRay || solUnbounded.
hasPrimalRay());
138 assert(!solUnbounded.
hasPrimalRay() || hasUnboundedRay);
147 if( hasUnboundedRay )
156 unboundednessNotCertified = !hasUnboundedRay;
163 else if( stoppedIter )
172 if( hasUnboundedRay )
184 else if( stoppedTime )
189 else if( stoppedIter )
194 else if( infeasible )
200 else if( hasUnboundedRay )
213 else if( infeasible && !infeasibilityNotCertified )
227 infeasibilityNotCertified = !infeasible;
235 else if( stoppedIter )
248 assert(!hasUnboundedRay || solUnbounded.
hasPrimalRay());
249 assert(!solUnbounded.
hasPrimalRay() || hasUnboundedRay);
259 if( hasUnboundedRay )
287 else if( hasUnboundedRay )
299 else if( primalFeasible && dualFeasible )
322 #ifdef SOPLEX_WITH_CPX 355 bool acceptUnbounded,
356 bool acceptInfeasible,
358 bool& primalFeasible,
369 primalFeasible =
false;
370 dualFeasible =
false;
484 sol.
_primal[c] = primalReal[c];
501 sol.
_dual[r] = dualReal[r];
502 if( dualReal[r] != 0.0 )
519 const Rational violationImprovementFactor = 0.9;
520 const Rational errorCorrectionFactor = 1.1;
522 int numFailedRefinements = 0;
532 bool factorSolNewBasis =
true;
533 int lastStallRefinements = 0;
534 int nextRatrecRefinement = 0;
540 MSG_DEBUG( std::cout <<
"Computing primal violations.\n" );
608 if(
_modLhs[r] > sideViolation )
631 if(
_modRhs[r] < -sideViolation )
640 MSG_DEBUG( std::cout <<
"Computing dual violations.\n" );
643 redCostViolation = 0;
653 && sol.
_redCost[c] < -redCostViolation )
655 MSG_DEBUG( std::cout <<
"basisStatusCol = " << basisStatusCol
660 redCostViolation = -sol.
_redCost[c];
664 && sol.
_redCost[c] > redCostViolation )
666 MSG_DEBUG( std::cout <<
"basisStatusCol = " << basisStatusCol
686 && sol.
_dual[r] < -dualViolation )
688 MSG_DEBUG( std::cout <<
"basisStatusRow = " << basisStatusRow
693 dualViolation = -sol.
_dual[r];
697 && sol.
_dual[r] > dualViolation )
699 MSG_DEBUG( std::cout <<
"basisStatusRow = " << basisStatusRow
704 dualViolation = sol.
_dual[r];
714 <<
"Max. reduced cost violation = " <<
rationalToString(redCostViolation) <<
"\n" 718 << std::fixed << std::setprecision(2) << std::setw(10)
719 <<
"Progress table: " 724 << std::setw(10) <<
rationalToString(boundsViolation > sideViolation ? boundsViolation : sideViolation, 2) <<
" & " 725 << std::setw(10) <<
rationalToString(redCostViolation > dualViolation ? redCostViolation : dualViolation, 2) <<
"\n");
730 if( primalFeasible && dualFeasible )
739 MSG_INFO1(
spxout,
spxout <<
"Tolerances reached but minRounds forcing additional refinement rounds.\n" );
748 maxViolation = boundsViolation;
749 if( sideViolation > maxViolation )
750 maxViolation = sideViolation;
751 if( redCostViolation > maxViolation )
752 maxViolation = redCostViolation;
753 if( dualViolation > maxViolation )
754 maxViolation = dualViolation;
755 bestViolation *= violationImprovementFactor;
756 if( maxViolation > bestViolation )
759 numFailedRefinements++;
762 bestViolation = maxViolation;
771 errorCorrection *= errorCorrectionFactor;
772 if( performRatrec && maxViolation > 0 )
776 maxViolation *= errorCorrection;
781 primalFeasible =
true;
786 MSG_DEBUG(
spxout <<
"Next rational reconstruction after refinement " << nextRatrecRefinement <<
".\n" );
790 if( performRatfac && maxViolation > 0 )
796 factorSolNewBasis =
false;
810 primalFeasible =
true;
825 maxScale = primalScale;
828 primalScale = boundsViolation > sideViolation ? boundsViolation : sideViolation;
829 if( primalScale < redCostViolation )
830 primalScale = redCostViolation;
831 assert(primalScale >= 0);
833 if( primalScale > 0 )
836 if( primalScale > maxScale )
837 primalScale = maxScale;
840 primalScale = maxScale;
846 if( primalScale <= 1 )
848 if( primalScale < 1 )
894 assert(primalScale >= 1);
895 if( primalScale == 1 )
939 maxScale = dualScale;
942 dualScale = redCostViolation > dualViolation ? redCostViolation : dualViolation;
943 assert(dualScale >= 0);
948 if( dualScale > maxScale )
949 dualScale = maxScale;
952 dualScale = maxScale;
957 if( dualScale > primalScale )
958 dualScale = primalScale;
988 newRowObj = sol.
_dual[r];
989 newRowObj *= dualScale;
1011 int col = numOrigCols + i;
1033 MSG_DEBUG(
spxout <<
"setting basis in solver " << (_hasBasis ?
"successful" :
"failed") <<
" (3)\n" );
1045 lastStallRefinements++;
1050 factorSolNewBasis =
true;
1051 lastStallRefinements = 0;
1089 MSG_DEBUG( std::cout <<
"Correcting primal solution.\n" );
1092 Rational primalScaleInverse = primalScale;
1093 primalScaleInverse.
invert();
1154 if( primalReal[c] == 1.0 )
1162 else if( primalReal[c] == -1.0 )
1171 else if( primalReal[c] != 0.0 )
1191 #ifdef SOPLEX_WITH_GMP 1195 assert(sol.
_slacks == activity);
1205 MSG_DEBUG( std::cout <<
"Correcting dual solution.\n" );
1215 Rational debugRedCostViolation = 0;
1225 && debugRedCost[c] < -debugRedCostViolation )
1227 MSG_DEBUG( std::cout <<
"basisStatusCol = " << basisStatusCol
1233 debugRedCostViolation = -debugRedCost[c];
1237 && debugRedCost[c] > debugRedCostViolation )
1239 MSG_DEBUG( std::cout <<
"basisStatusCol = " << basisStatusCol
1245 debugRedCostViolation = debugRedCost[c];
1251 Rational debugBasicDualViolation = 0;
1263 && val > debugDualViolation )
1265 MSG_DEBUG( std::cout <<
"basisStatusRow = " << basisStatusRow
1269 <<
", dualReal[r] = " << dualReal[r]
1271 debugDualViolation = val;
1275 && val < -debugDualViolation )
1277 MSG_DEBUG( std::cout <<
"basisStatusRow = " << basisStatusRow
1281 <<
", dualReal[r] = " << dualReal[r]
1283 debugDualViolation = -val;
1288 MSG_DEBUG( std::cout <<
"basisStatusRow = " << basisStatusRow
1292 <<
", dualReal[r] = " << dualReal[r]
1294 debugBasicDualViolation =
spxAbs(val);
1304 <<
" (red. cost, dual, basic).\n" );
1309 Rational dualScaleInverseNeg = dualScale;
1310 dualScaleInverseNeg.
invert();
1311 dualScaleInverseNeg *= -1;
1326 if( dualReal[r] != 0 )
1369 if( numCorrectedPrimals + numCorrectedDuals > 0 )
1371 MSG_INFO2(
spxout,
spxout <<
"Corrected " << numCorrectedPrimals <<
" primal variables and " << numCorrectedDuals <<
" dual values.\n" );
1410 bool& hasUnboundedRay,
1415 bool primalFeasible;
1430 _performOptIRStable(sol,
false,
false, 0, primalFeasible, dualFeasible, infeasible, unbounded, stopped, stoppedIter, error);
1439 hasUnboundedRay =
false;
1443 else if( error || unbounded || infeasible || !primalFeasible || !dualFeasible )
1446 hasUnboundedRay =
false;
1464 hasUnboundedRay = (tau >= 1);
1476 bool& withDualFarkas,
1481 bool primalFeasible;
1485 bool success =
false;
1509 _performOptIRStable(sol,
false,
false, 0, primalFeasible, dualFeasible, infeasible, unbounded, stopped, stoppedIter, error);
1518 withDualFarkas =
false;
1522 else if( error || unbounded || infeasible || !primalFeasible || !dualFeasible )
1525 withDualFarkas =
false;
1542 if( withDualFarkas )
1565 while(!error && !success && !stopped);
1576 MSG_DEBUG( std::cout <<
"Reducing matrix coefficients by lifting.\n" );
1597 MSG_DEBUG( std::cout <<
"in lifting: examining column " << i <<
"\n" );
1602 bool addedLiftingRow =
false;
1603 int liftingColumnIndex = -1;
1606 for(
int k = colVector.
size() - 1; k >= 0; k-- )
1610 if(
spxAbs(value) > maxValue )
1615 if( !addedLiftingRow )
1617 MSG_DEBUG( std::cout <<
" --> adding lifting row\n" );
1619 assert(liftingRowVector.
size() == 0);
1622 liftingRowVector.
add(i, maxValue);
1623 liftingRowVector.
add(liftingColumnIndex, -1);
1634 liftingRowVector.
clear();
1635 addedLiftingRow =
true;
1639 int rowIndex = colVector.
index(k);
1640 assert(rowIndex >= 0);
1644 MSG_DEBUG( std::cout <<
" --> changing matrix\n" );
1652 newValue /= maxValue;
1664 MSG_DEBUG( std::cout <<
"in lifting: examining column " << i <<
"\n" );
1669 bool addedLiftingRow =
false;
1670 int liftingColumnIndex = -1;
1673 for(
int k = colVector.
size() - 1; k >= 0; k-- )
1677 if(
spxAbs(value) < minValue )
1682 if( !addedLiftingRow )
1684 MSG_DEBUG( std::cout <<
" --> adding lifting row\n" );
1686 assert(liftingRowVector.
size() == 0);
1689 liftingRowVector.
add(i, minValue);
1690 liftingRowVector.
add(liftingColumnIndex, -1);
1701 liftingRowVector.
clear();
1702 addedLiftingRow =
true;
1706 int rowIndex = colVector.
index(k);
1707 assert(rowIndex >= 0);
1711 MSG_DEBUG( std::cout <<
" --> changing matrix\n" );
1719 newValue /= minValue;
1813 MSG_INFO1(
spxout,
spxout <<
"Warning: lost basis during project phase because of nonbasic lifting column.\n" );
1823 MSG_INFO1(
spxout,
spxout <<
"Warning: lost basis during project phase because of basic lifting row.\n" );
1848 #ifndef SOPLEX_MANUAL_ALT 1871 #ifndef SOPLEX_MANUAL_ALT 1924 MSG_DEBUG( std::cout <<
"Transforming rows to equation form.\n" );
2017 int col = numOrigCols + i;
2039 int col = numOrigCols + i;
2049 MSG_DEBUG( std::cout <<
"slack column " << col <<
" for row " << row
2088 int col = numOrigCols + i;
2176 obj.
add(numOrigCols, -1);
2264 _basisStatusRows.reSize(numOrigRows);
2279 sol.
_dual /= -alpha;
2295 for(
int i = objRowVector.
size() - 1; i >= 0; i-- )
2441 for(
int i = 0; i < colVector.
size(); i++ )
2443 shiftValue = colVector.
value(i);
2445 int r = colVector.
index(i);
2453 shiftValue2 -= shiftValue;
2499 for(
int i = 0; i < colVector.
size(); i++ )
2501 shiftValue = colVector.
value(i);
2503 int r = colVector.
index(i);
2511 shiftValue2 -= shiftValue;
2671 assert(sol.
_primal[numOrigCols] < 1);
2685 assert(sol.
_primal[numOrigCols] >= 1);
2691 if( sol.
_primal[numOrigCols] != 1 )
2694 for(
int i = 0; i < numOrigCols; i++ )
2742 for(
int c = numOrigCols - 1; c >= 0; c-- )
2747 #ifdef SOPLEX_WITH_GMP 2814 #ifdef SOPLEX_WITH_GMP 2819 assert(sol.
_slacks == activity);
2876 for(
int r = 0; r < numRows; r++ )
2879 ytransb += y[r] * (y[r] > 0 ? lhs[r] : rhs[r]);
2884 ytransA.
reDim(numCols);
2892 bool isTempFinite =
true;
2893 for(
int c = 0; c < numCols && isTempFinite; c++ )
2895 const Rational& minusRedCost = ytransA[c];
2897 if( minusRedCost > 0 )
2903 isTempFinite =
false;
2905 else if( minusRedCost < 0 )
2911 isTempFinite =
false;
2919 if( isTempFinite && temp < ytransb )
2932 for(
int c = 0; c < numCols; c++ )
2936 ytransA.
setValue(c, ytransA[c] - ytransb / lower[c]);
2940 else if( upper[c] < 0 )
2942 ytransA.
setValue(c, ytransA[c] - ytransb / upper[c]);
2953 MSG_INFO1(
spxout,
spxout <<
"Approximate Farkas proof to weak. Could not compute Farkas box. (1)\n" );
2959 const int size = ytransA.
size();
2960 for(
int n = 0; n < size; n++ )
2969 bool success =
false;
2974 assert(ytransb >= 0);
2979 if( n >= ytransA.
size() )
2990 int colIdx = ytransA.
index(n);
2999 ytransb.
subProduct(minusRedCost, lower[colIdx]);
3000 temp += minusRedCost;
3002 assert(ytransb >= 0);
3004 assert(temp == 0 || ytransb / temp > B);
3007 if( temp == 0 && ytransb == 0 )
3009 MSG_INFO1(
spxout,
spxout <<
"Approximate Farkas proof to weak. Could not compute Farkas box. (2)\n" );
3013 else if( temp == 0 )
3015 assert(ytransb > 0);
3032 ytransb.
subProduct(minusRedCost, upper[colIdx]);
3033 temp -= minusRedCost;
3035 assert(ytransb >= 0);
3037 assert(temp == 0 || ytransb / temp > B);
3040 if( temp == 0 && ytransb == 0 )
3042 MSG_INFO1(
spxout,
spxout <<
"Approximate Farkas proof to weak. Could not compute Farkas box. (2)\n" );
3046 else if( temp == 0 )
3048 assert(ytransb > 0);
3061 else if( minusRedCost == 0 )
3071 MSG_INFO1(
spxout,
spxout <<
"Computed Farkas box: provably no feasible solutions with components less than " 3090 #ifndef SOPLEX_MANUAL_ALT 3117 returnedBasis =
false;
3206 returnedBasis =
true;
3228 returnedBasis =
true;
3249 returnedBasis =
true;
3276 returnedBasis =
true;
3295 assert(rationalLP != 0);
3297 rationalLP->~SPxLPRational();
3313 bool fromScratch =
false;
3314 bool solved =
false;
3315 bool solvedFromScratch =
false;
3316 bool initialSolve =
true;
3317 bool increasedMarkowitz =
false;
3318 bool relaxedTolerances =
false;
3319 bool tightenedTolerances =
false;
3320 bool switchedScaler =
false;
3321 bool switchedSimplifier =
false;
3322 bool switchedRatiotester =
false;
3323 bool switchedPricer =
false;
3324 bool turnedoffPre =
false;
3333 if( forceNoSimplifier )
3340 result =
_solveRealForRational(fromScratch, primal, dual, basisStatusRows, basisStatusCols, returnedBasis);
3355 initialSolve =
false;
3363 turnedoffPre =
true;
3370 solvedFromScratch =
true;
3377 if( !increasedMarkowitz )
3382 increasedMarkowitz =
true;
3390 MSG_DEBUG( std::cout << std::endl <<
"Factorization failed." << std::endl );
3394 if( !solvedFromScratch )
3401 solvedFromScratch =
true;
3408 if( !switchedScaler )
3420 solvedFromScratch =
true;
3421 switchedScaler =
true;
3425 if( !switchedSimplifier && !forceNoSimplifier )
3437 solvedFromScratch =
true;
3438 switchedSimplifier =
true;
3444 if( !relaxedTolerances )
3451 solvedFromScratch =
false;
3462 solvedFromScratch =
false;
3468 if( !switchedRatiotester )
3477 switchedRatiotester =
true;
3478 solvedFromScratch =
false;
3482 if( !switchedPricer )
3491 switchedPricer =
true;
3492 solvedFromScratch =
false;
3528 for(
int i = 0; i < matrixdim; i++ )
3575 stoppedTime =
false;
3576 stoppedIter =
false;
3590 MSG_WARNING(
spxout,
spxout <<
"Warning: dimensioning error in rational matrix factorization (recovered).\n" );
3609 bool primalFeasible =
false;
3610 bool dualFeasible =
false;
3616 for(
int i = 0; i < basisStatusRows.
size(); i++ )
3620 basicPrimalRhs[i] = 0;
3621 basicDualRhs[j] = 0;
3631 basicPrimalRhs[i] = 0;
3653 for(
int i = 0; i < basisStatusCols.
size(); i++ )
3688 if( j != matrixdim )
3730 primalViolation = 0;
3731 primalFeasible =
true;
3732 for(
int i = 0; i < basisStatusRows.
size(); i++ )
3736 assert(j < matrixdim);
3739 violation += basicPrimal[j];
3740 if( violation > primalViolation )
3742 primalFeasible =
false;
3743 primalViolation = violation;
3746 violation += basicPrimal[j];
3748 if( violation > primalViolation )
3750 primalFeasible =
false;
3751 primalViolation = violation;
3756 for(
int i = 0; i < basisStatusCols.
size(); i++ )
3760 assert(j < matrixdim);
3765 violation -= basicPrimal[j];
3766 if( violation > primalViolation )
3768 primalFeasible =
false;
3769 primalViolation = violation;
3774 violation = basicPrimal[j];
3776 if( violation > primalViolation )
3778 primalFeasible =
false;
3779 primalViolation = violation;
3786 if( !primalFeasible )
3810 dualFeasible =
true;
3811 for(
int i = 0; i < basisStatusRows.
size(); i++ )
3823 else if( basicDual[i] < 0 )
3828 dualFeasible =
false;
3829 violation = -basicDual[i];
3830 if( violation > dualViolation )
3831 dualViolation = violation;
3834 <<
" and status " << basisStatusRows[i]
3839 else if( basicDual[i] > 0 )
3844 dualFeasible =
false;
3845 if( basicDual[i] > dualViolation )
3846 dualViolation = basicDual[i];
3849 <<
" and status " << basisStatusRows[i]
3857 for(
int i = 0; i < basisStatusCols.
size(); i++ )
3866 #ifdef SOPLEX_WITH_GMP 3880 dualFeasible =
false;
3892 dualFeasible =
false;
3908 optimal = primalFeasible && dualFeasible;
3919 for(
int i = 0; i < basisStatusCols.
size(); i++ )
3923 assert(j < matrixdim);
3925 sol.
_primal[i] = basicPrimal[j];
3951 sol.
_dual = basicDual;
4008 MSG_DEBUG(
spxout <<
"Rational reconstruction of primal solution successful.\n" );
4089 MSG_DEBUG(
spxout <<
"Rational reconstruction of dual vector successful.\n" );
4098 if( (!maximizing && sig > 0) || (maximizing && sig < 0) )
4102 MSG_DEBUG( std::cout <<
"complementary slackness violated by row " << r
4120 else if( (!maximizing && sig < 0) || (maximizing && sig > 0) )
4124 MSG_DEBUG( std::cout <<
"complementary slackness violated by row " << r
4157 if( (!maximizing && sig > 0) || (maximizing && sig < 0) )
4161 MSG_DEBUG( std::cout <<
"complementary slackness violated by column " << c
4179 else if( (!maximizing && sig < 0) || (maximizing && sig > 0) )
4183 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
textbook ratio test without stabilization
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
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
Real feastol() const
allowed primal feasibility tolerance.
time limit in seconds (INFTY if unlimited)
Rational _rationalFeastol
DVectorBase< R > _primalRay
modified Harris ratio test
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.
bound flipping ratio test for long steps in the dual simplex
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.
LPColBase< Real > LPColReal
Rational _rationalPosInfty
const VectorRational & lhsRational() const
returns left-hand side vector
steepest edge pricer with exact initialization of norms
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
dual simplex algorithm, i.e., leaving for column and entering for row representation ...
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
user sync of real and rational LP
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
equilibrium scaling on rows and columns
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.
column representation Ax - s = 0, lower <= x <= upper, lhs <= s <= rhs
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
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
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
primal simplex algorithm, i.e., entering for column and leaving for row representation ...
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...
force iterative refinement
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 _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