27 #define MAX_DEGENCHECK 20 28 #define DEGENCHECK_OFFSET 50 29 #define SLACKCOEFF 1.0 30 #define TIMELIMIT_FRAC 0.5 85 int numDegenCheck = 0;
86 Real degeneracyLevel = 0;
88 bool initSolveFromScratch =
true;
104 initSolveFromScratch =
false;
199 basisStatusCols.
size());
218 spxout <<
"======== Degeneracy Detected ========" << std::endl
220 <<
"======== Commencing decomposition solve ========" << std::endl
229 if( decomp_verbosity < orig_verbosity )
241 bool hasRedBasis =
false;
242 bool redProbError =
false;
243 bool noRedprobIter =
false;
245 int algIterCount = 0;
269 <<
"=========================" << std::endl
270 <<
"Solving: Reduced Problem." << std::endl
271 <<
"=========================" << std::endl
309 spxout <<
"WIMDSM02: reduced problem performed zero iterations. Terminating." << std::endl; );
311 noRedprobIter =
true;
329 if( algIterCount == 0 )
345 <<
"=========================" << std::endl
346 <<
"Solving: Complementary Problem." << std::endl
347 <<
"=========================" << std::endl
384 if( !stop && !explicitviol )
396 compLPPrimalVector, compLPDualVector);
449 #ifdef PERFORM_COMPPROB_CHECK 489 <<
"Max: "<< std::setprecision(20) << maxviol <<
" " 490 <<
"Sum: "<< sumviol << std::endl );
495 <<
"Max: "<< std::setprecision(21) << maxviol <<
" " 496 <<
"Sum: "<< sumviol << std::endl );
506 spxout <<
"======== Decomposition solve completed ========" << std::endl
508 <<
"======== Resolving original problem ========" << std::endl
513 if( (!redProbError && !noRedprobIter) || algIterCount > 0 )
628 int* rowsforremoval = 0;
629 int* colsforremoval = 0;
660 <<
"Solving time: " <<
solveTime() << std::endl );
666 &ncompatind,
true, stop);
668 int* compatboundcons = 0;
669 int ncompatboundcons = 0;
680 <<
"Solving time: " <<
solveTime() << std::endl );
684 spx_alloc(addedrowids, ncompatboundcons);
699 for(
int i = 0; i < ncompatboundcons; i++ )
733 _fixedOrigVars[i] = -2;
765 if( i + 1 < _nPrimalRows &&
779 assert(_nPrimalCols == _nDualRows);
810 int addedrangedrows = 0;
877 MSG_ERROR(
spxout <<
"Caught exception <" << E.
what() <<
"> during simplify and solve.\n" );
882 if( applyPreprocessing )
906 if( applyPreprocessing )
936 if( !applyPreprocessing )
952 assert(
_decompLP == &solver || applyPreprocessing);
953 assert(
_decompLP != &solver || !applyPreprocessing);
980 MSG_ERROR( std::cerr <<
"Caught exception <" << E.
what() <<
"> while solving real LP.\n" );
985 MSG_ERROR( std::cerr <<
"Caught unknown exception while solving real LP.\n" );
1088 MSG_ERROR(
spxout <<
"Caught exception <" << E.
what() <<
"> during unsimplification. Resolving without simplifier and scaler.\n" );
1092 MSG_ERROR(
spxout <<
"Caught unknown exception during unsimplification. Resolving without simplifier and scaler.\n" );
1126 Real reducedProbDual = 0;
1127 Real compProbPrimal = 0;
1135 reducedProbDual = dualVector[solverRowNum];
1142 if(
EQ(reducedProbDual, 0.0, feastol) )
1145 spxout <<
"WIMDSM01: reduced problem dual value is very close to zero." << std::endl; );
1150 if( usecompdual && i < _nPrimalRows - 1 &&
1168 dualRatio = reducedProbDual/compProbPrimal;
1171 if(
LT(dualRatio, maxDualRatio, feastol) )
1172 maxDualRatio = dualRatio;
1185 if( maxDualRatio > 1.0 )
1198 int nviolatedrows = 0;
1203 violatedrows.
reSize(_nPrimalRows);
1205 bool ratioTest =
true;
1211 Real compProbPrimal = 0;
1212 Real compRowRedcost = 0;
1221 compProbPrimal = compPrimalVector[compRowNumber];
1222 compRowRedcost = compProbRedcost[compRowNumber];
1228 compProbPrimal = compDualVector[compRowNumber];
1232 if( usecompdual && i < _nPrimalRows - 1 &&
1237 compProbPrimal += compPrimalVector[compRowNumber];
1238 compRowRedcost += compProbRedcost[compRowNumber];
1245 (varSign ==
SoPlex::IS_POS &&
GT(compProbPrimal*maxDualRatio, 0, feastol)) ||
1246 (varSign ==
SoPlex::IS_NEG &&
LT(compProbPrimal*maxDualRatio, 0, feastol))) )
1254 assert(numIncludedRows <= _realLP->nRows());
1256 violatedrows[nviolatedrows].idx = rownumber;
1257 violatedrows[nviolatedrows].violation =
spxAbs(compProbPrimal*maxDualRatio);
1270 if( !ratioTest || nviolatedrows == 0 )
1279 if( sortsize > 0 && sortsize < nviolatedrows )
1283 for(
int i = 0; i < sortsize; i++ )
1289 newrowidx[nnewrowidx] = violatedrows[i].idx;
1297 for(
int i = 0; i < nnewrowidx; i++ )
1330 Real percenttoadd = 1;
1340 for(
int i = 0; i < nrowstoadd; i++ )
1356 MSG_ERROR(
spxout <<
"Caught exception <" << E.
what() <<
"> while computing compatability.\n" );
1363 for(
int j = 0; j < y.size(); j++ )
1382 if(
LT(norm, bestrownorm) )
1384 bestrow = rowNumber;
1396 newrowidx[nnewrowidx] = rowNumber;
1408 newrowidx[nnewrowidx] = rowNumber;
1414 if( nnewrowidx == 0 )
1416 for(
int i = 0; i < nrowstoadd; i++ )
1424 newrowidx[nnewrowidx] = rowNumber;
1431 if( !allrows && bestrow >= 0 )
1437 newrowidx[nnewrowidx] = bestrow;
1446 for(
int i = 0; i < nnewrowidx; i++ )
1465 Real compProbSlackVal = 0;
1486 Real compProbViol = 0;
1487 Real compSlackCoeff = 0;
1499 compProbViol += compObjValue*compSlackCoeff;
1500 compProbViol *= compSlackCoeff;
1504 Real viol =
_compSolver.
rhs(comprownum) - (compProbActivity[comprownum] + compProbSlackVal);
1506 compProbViol = viol;
1508 viol = (compProbActivity[comprownum] - compProbSlackVal) -
_compSolver.
lhs(comprownum);
1510 compProbViol = viol;
1524 tempViol += compObjValue*compSlackCoeff;
1525 tempViol *= compSlackCoeff;
1529 if( tempViol < compProbViol )
1530 compProbViol = tempViol;
1535 if(
LT(compProbViol, 0, feastol) )
1540 assert(numIncludedRows <= _realLP->nRows());
1542 violatedrows[nviolatedrows].idx = rownumber;
1543 violatedrows[nviolatedrows].violation =
spxAbs(compProbViol);
1556 int* nnonposind,
bool& stop)
1581 colsforremoval[i] = i;
1586 if(
isZero(feasVector[i], feastol) )
1588 nonposind[*nnonposind] = i;
1599 if(
isZero(feasVector[i], feastol) )
1601 nonposind[*nnonposind] = i;
1611 colsforremoval[i] = -1;
1632 int* colsforremoval,
int nnonposind,
int* ncompatind,
bool formRedProb,
bool& stop)
1652 bool* activerows = 0;
1656 activerows[i] =
false;
1662 if( !
isZero(feasVector[i], feastol) )
1667 activerows[bind] =
true;
1683 rowsforremoval[i] = i;
1701 MSG_ERROR(
spxout <<
"Caught exception <" << E.
what() <<
"> while computing compatability.\n" );
1706 for(
int j = 0; j < nnonposind; ++j )
1709 if( !
isZero(y[nonposind[j]], feastol) )
1717 assert(!activerows[i] || compatible);
1725 for(
int j = 0; j < y.size(); j++ )
1726 newRowVector.
add(y.index(j), y.value(j));
1732 if( !
isZero(y[j], feastol) )
1733 newRowVector.
add(j, y[j]);
1740 #ifndef NO_TRANSFORM 1749 if(
EQ(rowtoupdate.
lhs(), rowtoupdate.
rhs()) )
1754 compatind[*ncompatind] = i;
1768 rowsforremoval[i] = -1;
1814 MSG_ERROR(
spxout <<
"Caught exception <" << E.
what() <<
"> while computing compatability.\n" );
1823 if( ycount < y.
size() && i == y.
index(ycount) )
1836 if(
isZero(y[i], feastol) )
1844 #ifndef NO_TRANSFORM 1858 int* ncompatboundcons,
int nnonposind,
bool& stop)
1896 MSG_ERROR(
spxout <<
"Caught exception <" << E.
what() <<
"> while computing compatability.\n" );
1901 for(
int j = 0; j < nnonposind; ++j )
1904 if( !
isZero(y[nonposind[j]]) )
1915 #ifndef NO_TRANSFORM 1918 for(
int j = 0; j < y.
size(); j++ )
1925 if( !
isZero(y[j], feastol) )
1927 newRowVector.
add(j, y[j]);
1932 newRowVector.
add(i, 1.0);
1956 compatboundcons[(*ncompatboundcons)] = i;
1957 (*ncompatboundcons)++;
1959 boundcons.
add(lhs, newRowVector, rhs);
1978 int* nrowsforremoval,
int nnonposind)
1980 *nrowsforremoval = 0;
1982 for(
int i = 0; i < nnonposind; i++ )
1984 if( bind[nonposind[i]] < 0 )
1986 rowsforremoval[*nrowsforremoval] = -1 - bind[nonposind[i]];
1987 (*nrowsforremoval)++;
2045 for(
int i = 0; i < naddedrows; i++ )
2046 rangedRowIds[i] = addedrowid[i];
2054 compSlackCol.
add(-1.0, 0.0, slackColCoeff,
infinity);
2080 int numElimColsAdded = 0;
2081 int currnumrows = prevNumRows;
2090 assert(solverRowNum >= 0 && solverRowNum <
_solver.
nRows());
2109 for(
int j = 0; j < origlprow.
rowVector().size(); j++ )
2113 int colNumber = origlprow.
rowVector().index(j);
2126 coltoaddVec.
add(currnumrows, origlprow.
rowVector().value(j));
2138 for(
int j = 0; j < nnewrows; j++ )
2194 << numElimColsAdded << std::endl );
2211 int* colsforremoval = 0;
2212 int ncolsforremoval = 0;
2213 spx_alloc(colsforremoval, prevPrimalRowIds);
2214 for(
int i = 0; i < prevPrimalRowIds; i++ )
2229 #ifdef KEEP_ALL_ROWS_IN_COMP_PROB 2230 bool incrementI =
false;
2232 if( i + 1 < prevPrimalRowIds
2237 #ifdef KEEP_ALL_ROWS_IN_COMP_PROB // 22.06.2015 2259 assert(solverRowNum >= 0 && solverRowNum <
_solver.
nRows());
2283 #ifdef KEEP_ALL_ROWS_IN_COMP_PROB 2311 #else // 22.06.2015 testing keeping all rows in the complementary problem 2329 #ifdef KEEP_ALL_ROWS_IN_COMP_PROB 2380 int removeCount = 0;
2404 }
while( removeCount < numRemove );
2415 if( slackRowCoeff.size() == 0 )
2433 int* currFixedVars = 0;
2462 int numElimRowsAdded = 0;
2471 assert(solverRowNum >= 0 && solverRowNum <
_solver.
nRows());
2545 << numElimRowsAdded << std::endl );
2563 int* rowsforremoval = 0;
2564 int nrowsforremoval = 0;
2565 spx_alloc(rowsforremoval, prevPrimalRowIds);
2566 for(
int i = 0; i < prevPrimalRowIds; i++ )
2581 assert(solverRowNum >= 0 && solverRowNum <
_solver.
nRows());
2675 int* currFixedVars = 0;
2705 <<
"Checking consistency between the reduced problem and the original problem." << std::endl );
2711 Real objectiveVal = 0;
2721 <<
"Original Problem Objective Value: " << objectiveVal << std::endl );
2738 <<
"Max violation: " << maxviol <<
" Sum violation: " << sumviol << std::endl );
2749 <<
"Max violation: " << maxviol <<
" Sum violation: " << sumviol << std::endl );
2803 int numFixedVar = 0;
2806 currFixedVars[i] = 0;
2828 currFixedVars[i] = 1;
2831 currFixedVars[i] = -1;
2836 MSG_INFO3(
spxout,
spxout <<
"Number of fixed primal variables in the complementary (dual) problem: " 2837 << numFixedVar << std::endl );
2846 int ncolsforremoval = 0;
2847 int* colsforremoval = 0;
2911 int numFixedVars = 0;
2915 int numBoundConsCols = 0;
2916 int* boundConsColsAdded = 0;
2924 boundConsColsAdded[i] = 0;
2931 if( currFixedVars[i] != 0 )
2933 assert(currFixedVars[i] == -1 || currFixedVars[i] == 1);
2937 Real colObjCoeff = 0;
2938 if( currFixedVars[i] == -1 )
2965 boundConsColsAdded[i]++;
2978 boundConsColsAdded[i]++;
2993 int addedcolcount = 0;
3010 spx_alloc(addedbndcolids, numBoundConsCols);
3016 if( boundConsColsAdded[i] > 0 )
3018 for(
int j = 0; j < boundConsColsAdded[i]; j++ )
3025 switch( boundConsColsAdded[i] )
3046 int numFixedVar = 0;
3049 currFixedVars[i] = 0;
3066 MSG_INFO3(
spxout,
spxout <<
"Number of fixed primal variables in the complementary (primal) problem: " 3067 << numFixedVar << std::endl );
3075 int numFixedVars = 0;
3085 if( currFixedVars[colNumber] != 0 )
3087 assert(currFixedVars[colNumber] == -1 || currFixedVars[colNumber] == 1);
3089 if( currFixedVars[colNumber] == -1 )
3240 solverStat = solver.
status();
3247 switch( solverStat )
3349 if(
GT(feasVec[i], 0, feastol) )
3356 if(
LT(feasVec[i], 0, feastol) )
3367 if(
GT(feasVec[i], 0, feastol) )
3374 if(
LT(feasVec[i], 0, feastol) )
3436 spxout <<
"type | time | iters | red iter | alg iter | rows | cols | shift | value\n";
3442 spxout << std::fixed << std::setw(7) << std::setprecision(1) << currentTime <<
" |";
3443 spxout << std::scientific << std::setprecision(2);
3445 spxout << std::scientific << std::setprecision(2);
3447 spxout << std::scientific << std::setprecision(2);
3449 spxout << std::scientific << std::setprecision(2);
3451 spxout << std::scientific << std::setprecision(2);
3453 << solver.
shift() <<
" | " 3487 bool hasLower =
false;
3488 bool hasUpper =
false;
3502 if( hasUpper && hasLower )
3509 if( !hasUpper && !hasLower )
3515 bool hasRhs =
false;
3516 bool hasLhs =
false;
3530 if( hasRhs && hasLhs )
3540 if( !hasRhs && !hasLhs )
3628 bool isViol =
false;
3629 bool isMaxViol =
false;
3633 Real currviol = 0.0;
3643 if( viol > maxviol )
3649 if( currviol < viol )
3653 if(
GT(viol, 0.0, feastol) )
3660 if( viol > maxviol )
3666 if( currviol < viol )
3670 if(
GT(viol, 0.0, feastol) )
3684 _nDecompViolBounds++;
3709 bool isViol =
false;
3710 bool isMaxViol =
false;
3714 Real currviol = 0.0;
3723 if( viol > maxviol )
3729 if( viol > currviol )
3733 if(
GT(viol, 0.0, feastol) )
3740 if( viol > maxviol )
3746 if( viol > currviol )
3750 if(
GT(viol, 0.0, feastol) )
3776 Real maxTime = timeLimit;
3779 if( maxTime < 0 || maxTime >=
infinity )
3783 if ( currentTime >= maxTime )
3786 <<
") reached" << std::endl; )
3809 assert(solverRowNum >= 0 && solverRowNum <
_solver.
nRows());
3844 assert(solverRowNum >= 0 && solverRowNum <
_solver.
nRows());
3853 degenerateRowNums[nDegenerateRows] = rowNumber;
3865 degenerateRowNums[nDegenerateRows] = rowNumber;
3977 nNonBasicRows =
_realLP->
nRows() - basicRow - nDegenerateRows;
3991 int numZeroDual = 0;
4035 << nNonBasicCols <<
" (from " <<
_realLP->
nCols() <<
")" << std::endl
4036 <<
"Number of zero dual columns: " << numZeroDual <<
" (from " <<
_realLP->
nCols() <<
")" << std::endl );
4046 int nNonBasicRows = 0;
4047 int nNonBasicCols = 0;
4048 int nDegenerateRows = 0;
4056 degenerateRowNums.
reSize(numrows);
4057 degenerateRowStatus.
reSize(numrows);
4067 assert(nDegenerateRows + nNonBasicRows + nNonBasicCols >= numcols);
4068 int degenRowsSetNonBasic = 0;
4069 for(
int i = 0; i < nDegenerateRows; i++ )
4071 if( nNonBasicRows + nNonBasicCols + degenRowsSetNonBasic < numcols )
4074 degenRowsSetNonBasic++;
const VectorBase< R > & rhs() const
Returns right hand side vector.
virtual Real objValue()
get objective value of current solution.
virtual void buildDualProblem(SPxLPBase< R > &dualLP, SPxRowId primalRowIds[]=0, SPxColId primalColIds[]=0, SPxRowId dualRowIds[]=0, SPxColId dualColIds[]=0, int *nprimalrows=0, int *nprimalcols=0, int *ndualrows=0, int *ndualcols=0)
Building the dual problem from a given LP.
Real getMaxTime()
the maximum runtime
Rational spxAbs(const Rational &r)
Absolute.
SPxLPBase< Real > SPxLPReal
Starting basis has been found and the simplex can be executed as normal.
int getSolveCount() const
number of solves performed
virtual void changeRow(int i, const LPRow &newRow, bool scale=false)
Exception class for things that should NEVER happen.This class is derived from the SoPlex exception b...
virtual void removeRow(int i)
Removes i 'th row.
virtual Real shift() const
total current shift amount.
int iterations() const
get number of iterations of current solution.
void getRow(int i, LPRowBase< R > &row) const
Gets i 'th row.
free variable fixed to zero.
SPxRowId rId(int n) const
Returns the row identifier for row n.
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.
int callsReducedProb
number of times the reduced problem is solved. This includes the initial solve.
void coSolve(Vector &x, const Vector &rhs)
Cosolves linear system with basis matrix.
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
primal variable is fixed to both bounds
virtual void changeLower(const Vector &newLower, bool scale=false)
const R & objOffset() const
Returns the objective function value offset.
const VectorBase< R > & upper() const
Returns upper bound vector.
const RowViolation * entry
virtual Status getPrimal(Vector &vector) const
get solution vector for primal variables.
upper limit on objective value
void _updateDecompReducedProblem(Real objVal, DVector dualVector, DVector redcostVector, DVector compPrimalVector, DVector compDualVector)
update the reduced problem with additional columns and rows
virtual R minAbsNzo(bool unscaled=true) const
Absolute smallest non-zero element in (possibly scaled) LP.
THREADLOCAL const Real infinity
Result
Result of the simplification.
void setOutstream(SPxOut &newOutstream)
the problem was so much simplified that it vanished
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.
void _findViolatedRows(Real compObjValue, DataArray< RowViolation > &violatedrows, int &nviolatedrows)
builds the update rows with those violated in the complmentary problem
void resetCounters()
reset timers and counters
DataArray< SPxRowId > _decompPrimalRowIDs
DataArray< SPxRowId > _decompElimPrimalRowIDs
void _checkOriginalProblemOptimality(Vector primalVector, bool printViol)
checking the optimality of the original problem.
void _removeComplementaryDualFixedPrimalVars(int *currFixedVars)
removing the dual columns related to the fixed variables
void _setComplementaryPrimalOriginalObjective()
updating the complementary primal problem with the original objective function
T * get_ptr()
get a C pointer to the data.
const VectorBase< R > & lhs() const
Returns the vector of lhs values.
int size() const
Number of used indices.
DataArray< SPxRowId > _decompReducedProbColRowIDs
Status getBasis(VarStatus rows[], VarStatus cols[], const int rowsSize=-1, const int colsSize=-1) const
get current basis, and return solver status.
virtual void setBasisSolver(SLinSolver *slu, const bool destroy=false)
setup linear solver to use. If destroy is true, slusolver will be freed in destructor.
LPRowSet _transformedRows
Real sumDualDegeneracy()
get the sum of dual degeneracy
time limit in seconds (INFTY if unlimited)
Status & rowStatus(int i)
bool isScaled() const
Returns true if and only if the LP is scaled.
virtual void removeCols(int perm[])
Removes multiple columns.
bool LE(Real a, Real b, Real eps=Param::epsilon())
returns true iff a <= b + eps
Real getFactorTime() const
time spent in factorizations
primal feasibility tolerance
bool LT(Real a, Real b, Real eps=Param::epsilon())
returns true iff a < b + eps
const SVectorBase< R > & rowVector() const
Constraint row vector.
bool writeBasisFile(const char *filename, const NameSet *rowNames=0, const NameSet *colNames=0, const bool cpxFormat=false) const
writes basis information to filename; if rowNames and colNames are NULL, default names are used; retu...
int numRedProbCols
number of columns in the reduced problem
solve() aborted due to iteration limit.
R rhs() const
Right-hand side value.
void unSetup()
Makes SSVectorBase not setup.
No Problem has been loaded.
void setSolverStatus(SPxSolver::Status stat)
setting the solver status external from the solve loop.
bool NE(Real a, Real b, Real eps=Param::epsilon())
returns true iff |a-b| > eps
int iterationsInit
number of iterations in the initial LP
virtual void unscaleRedCost(const SPxLPBase< Real > &lp, Vector &r) const
unscale dense reduced cost vector given in r.
int number(const SPxRowId &id) const
Returns the row number of the row with identifier id.
virtual void unscaleDual(const SPxLPBase< Real > &lp, Vector &pi) const
unscale dense dual solution vector given in pi.
void _disableSimplifierAndScaler()
disables simplifier and scaler
void add(const LPColBase< R > &pcol)
bool * _decompReducedProbCols
Timer * simplexTime
simplex time
int luSolvesReal
number of (forward and backward) solves with basis matrix in real precision
void _computeReducedProbObjCoeff(bool &stop)
computes the reduced problem objective coefficients
variable fixed to identical bounds.
int luFactorizationsReal
number of basis matrix factorizations in real precision
int getFactorCount() const
number of factorizations performed
virtual void removeCol(int i)
Removes i 'th column.
LP has been proven to be primal infeasible.
int getOrigVarFixedDirection(int colNum)
determining which bound the primal variables will be fixed to.
Real finalCompObj
the final objective function of the complementary problem
Ids for LP columns.Class SPxColId provides DataKeys for the column indices of an SPxLP.
virtual void changeCol(int i, const LPCol &newCol, bool scale=false)
int intParam(const IntParam param) const
returns integer parameter value
void remove(int n, int m)
Remove nonzeros n thru m.
void setDegenCompOffset(int iterOffset)
sets the offset for the number of iterations before the degeneracy is computed
bool getDecompBoundViolation(Real &maxviol, Real &sumviol)
gets violation of bounds; returns true on success
virtual Real value()
current objective value.
void _getCompatibleBoundCons(LPRowSet &boundcons, int *compatboundcons, int *nonposind, int *ncompatboundcons, int nnonposind, bool &stop)
computes the compatible bound constraints and adds them to the reduced problem
void add(const LPRowBase< R > &row)
virtual void setTerminationTime(Real time=infinity)
set time limit.
DataArray< SPxColId > _decompCompPrimalColIDs
virtual void changeObjOffset(const R &o)
SPxColId cId(int n) const
Returns the column identifier for column n.
virtual void removeRows(int perm[])
Removes multiple rows.
DataArray< SPxColId > _decompReducedProbColIDs
virtual const std::string what() const
returns exception message
dual variable is left free, but unset
Real getDegeneracyLevel(Vector degenvec)
get level of dual degeneracy
int nRows() const
Returns number of rows in LP.
void add(const SVectorBase< S > &vec)
Append nonzeros of sv.
DataArray< SPxRowId > _decompReducedProbRowIDs
void printOriginalProblemStatistics(std::ostream &os)
stores the problem statistics of the original problem
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.
int compProbStatus
status of the complementary problem
int dualDegeneratePivots()
get number of dual degenerate pivots
void spx_alloc(T &p, int n=1)
Allocate memory.
simplification could be done
primal variable is set to its upper bound
void _formDecompReducedProblem(bool &stop)
forms the reduced problem
virtual void changeBounds(const Vector &newLower, const Vector &newUpper, bool scale=false)
LP is primal infeasible or unbounded.
int nNzos() const
Returns number of nonzeros in LP.
void inValidate()
makes the DataKey invalid and clears the info field.
DataArray< SPxRowId > _decompCompPrimalRowIDs
Real luFactorizationTimeReal
time for factorizing bases matrices in real precision
void _updateComplementaryPrimalFixedPrimalVars(int *currFixedVars)
updating the dual columns related to the fixed primal variables.
DataArray< SPxSolver::VarStatus > _basisStatusCols
SPxStatus status() const
returns current SPxStatus.
decompStatus _currentProb
void _getZeroDualMultiplierIndices(Vector feasVector, int *nonposind, int *colsforremoval, int *nnonposind, bool &stop)
identifies the columns of the row-form basis that correspond to rows with zero dual multipliers...
void _evaluateSolutionDecomp(SPxSolver &solver, SLUFactor &sluFactor, SPxSimplifier::Result result)
evaluates the solution of the reduced problem for the DBDS
void _setComplementaryDualOriginalObjective()
updating the complementary dual problem with the original objective function
Status status() const
Status of solution process.
Real sumPrimalDegeneracy()
get the sum of primal degeneracy
bool GT(Real a, Real b, Real eps=Param::epsilon())
returns true iff a > b + eps
SPxSense spxSense() const
Returns the optimization sense.
void _decompSimplifyAndSolve(SPxSolver &solver, SLUFactor &sluFactor, bool fromScratch, bool applyPreprocessing)
simplifies the problem and solves
bool getDecompRowViolation(Real &maxviol, Real &sumviol)
gets violation of constraints; returns true on success
const VectorBase< R > & rhs() const
Returns the vector of rhs values.
Real maxRowViol
the max row violations in the original problem using the red prob sol
SPxColId colId(int i) const
ColId of i 'th column.
virtual Real getObjoffset() const
get objective offset.
R lhs() const
Left-hand side value.
the iteration frequency at which the decomposition solve output is displayed.
void _getCompatibleColumns(Vector feasVector, int *nonposind, int *compatind, int *rowsforremoval, int *colsforremoval, int nnonposind, int *ncompatind, bool formRedProb, bool &stop)
retrieves the compatible columns from the constraint matrix
LP has been solved to optimality.
int getIdx() const
gets the index number (idx) of the DataKey.
#define MSG_INFO2(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO2.
virtual void changeSense(SPxSense sns)
#define MSG_ERROR(x)
Prints out message x if the verbosity level is at least SPxOut::ERROR.
Real sumPrimalDegen
the sum of the rate of primal degeneracy at each iteration
UpdateVector & fVec() const
feasibility vector.
virtual void addRows(const LPRowSetBase< R > &pset, bool scale=false)
Class for collecting statistical information.
bool isSPxColId() const
is id a column id?
dual variable is set to its upper bound
solve() aborted due to commence decomposition simplex
solve() aborted due to time limit.
SPxRowId _compSlackDualRowId
const T * get_const_ptr() const
get a const C pointer to the data.
virtual void changeLhs(const Vector &newLhs, bool scale=false)
bool isBasic(SPxBasis::Desc::Status stat) const
does stat describe a basic index ?
primal variable is left free, but unset
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...
LPRowBase< R >::Type rowType(int i) const
Returns the inequality type of the i'th LPRow.
virtual void setVerbosity(const Verbosity &v)
Statistics * _statistics
statistics since last call to solveReal() or solveRational()
R obj(int i) const
Returns objective value of column i.
Real getCompSlackVarCoeff(int primalRowNum)
gets the coefficient of the slack variable in the primal complementary problem
solve() aborted to exit decomposition simplex
const VectorBase< R > & lhs() const
Returns left hand side vector.
Real spxSqrt(Real a)
returns square root
Verbosity getVerbosity() const
virtual void getBasis(SPxSolver::VarStatus[], SPxSolver::VarStatus[], const int rowsSize=-1, const int colsSize=-1) const =0
get optimal basis.
variable set to its upper bound.
int primalDegeneratePivots()
get number of primal degenerate pivots
Real maxBoundViol
the max bound violation in the original problem using the red prob sol
Real realParam(const RealParam param) const
returns real parameter value
primal infeasibility was detected
DataArray< SPxColId > _decompPrimalColIDs
virtual Real time() const =0
void _decompResolveWithoutPreprocessing(SPxSolver &solver, SLUFactor &sluFactor, SPxSimplifier::Result result)
loads original problem into solver and solves again after it has been solved to optimality with prepr...
int boundFlips() const
get number of bound flips.
int degenPivotsDual
number of dual degenerate pivots
int index(int n) const
Returns index of the n 'th nonzero element.
Status & colStatus(int i)
(In)equality for LPs.Class LPRowBase provides constraints for linear programs in the form where a is...
virtual void loadLP(const SPxLP &LP, bool initSlackBasis=true)
copy LP.
variable set to its lower bound.
Generic QuickSort implementation.
Preconfigured SoPlex LP solver.
#define MSG_INFO3(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO3.
void getOriginalProblemBasisColStatus(int &nNonBasicCols)
function to retrieve the column status for the original problem basis from the reduced and complement...
virtual void changeRow(int n, const LPRowBase< R > &newRow, bool scale=false)
Replaces i 'th row of LP with newRow. scale determines whether the new data should be scaled...
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 _createDecompReducedAndComplementaryProblems()
creating copies of the original problem that will be manipulated to form the reduced and complementar...
apply standard floating-point algorithm
Set of strings.Class NameSet implements a symbol or name table. It allows to store or remove names (i...
DataArray< SPxColId > _decompFixedVarDualIDs
DualSign getOrigProbDualVariableSign(int rowNumber)
returns the expected sign of the dual variables for the original problem
Sequential object-oriented SimPlex.SPxSolver is an LP solver class using the revised Simplex algorith...
bool EQ(Real a, Real b, Real eps=Param::epsilon())
returns true iff |a-b| <= eps
Timer * preprocessingTime
preprocessing time
UpdateVector & pVec() const
pricing vector.
Real luSolveTimeReal
time for solving linear systems in real precision
virtual void changeObj(const VectorBase< R > &newObj, bool scale=false)
Changes objective vector to newObj. scale determines whether the new data should be scaled...
virtual void addCol(const LPColBase< R > &col, bool scale=false)
virtual void scale(SPxLPBase< Real > &lp, bool persistent=true)=0
scale SPxLP.
int dim() const
Dimension of vector.
Implementation of Sparse Linear Solver.This class implements a SLinSolver interface by using the spar...
Starting basis has not been found yet.
Exception base class.This class implements a base class for our SoPlex exceptions We provide a what()...
int size() const
Returns the number of nonzeros.
int * _decompViolatedRows
DataArray< SPxColId > _decompVarBoundDualIDs
DataArray< SPxRowId > _decompDualRowIDs
Everything should be within this namespace.
void _writeOriginalProblemBasis(const char *filename, NameSet *rowNames, NameSet *colNames, bool cpxFormat)
function to build a basis for the original problem as given by the solution to the reduced problem ...
the maximum number of rows that are added in each iteration of the decomposition based simplex ...
void _preprocessAndSolveReal(bool applyPreprocessing)
solves real LP with/without preprocessing
void _deleteAndUpdateRowsComplementaryProblem(SPxRowId rangedRowIds[], int &naddedrows)
removing rows from the complementary problem.
void clear()
Remove all indices.
DVector _decompFeasVector
virtual void printDisplayLine(const bool force=false, const bool forceHead=false)
print display line of flying table
solve() aborted due to detection of cycling.
void _formDecompComplementaryProblem()
forms the complementary problem
Saving LPs in a form suitable for SoPlex.Class SPxLPBase provides the data structures required for sa...
Set of LP columns.Class LPColSetBase implements a set of LPColBase%s. Unless for memory limitations...
primal unboundedness was detected
const SVectorBase< R > & rowVector(int i) const
Returns the rowVector of the i 'th LPRowBase.
should the dual of the complementary problem be used in the decomposition simplex?
#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.
int iterations
number of iterations/pivots
primal variable is set to its lower bound
const VectorBase< R > & maxObj() const
Returns objective vector for maximization problem.
void getOriginalProblemBasisRowStatus(DataArray< int > °enerateRowNums, DataArray< SPxSolver::VarStatus > °enerateRowStatus, int &nDegenerateRows, int &nNonBasicRows)
function to retrieve the original problem row basis status from the reduced and complementary problem...
void setRowVector(const DSVectorBase< R > &p_vec)
access constraint row vector.
#define DEGENCHECK_OFFSET
int boundflips
number of dual bound flips
nothing known on loaded problem.
void printDecompDisplayLine(SPxSolver &solver, const SPxOut::Verbosity origVerb, bool force, bool forceHead)
prints a display line of the flying table for the DBDS
int SPxQuicksortPart(T *keys, COMPARATOR &compare, int start, int end, int size, int start2=0, int end2=0, bool type=true)
Generic implementation of Partial QuickSort.
Verbosity
Verbosity level.
int iterationsRedProb
number of iterations of the reduced problem
void _identifyComplementaryPrimalFixedPrimalVars(int *currFixedVars)
removing the dual columns related to the fixed variables
const SVectorBase< R > & rowVector(int i) const
Gets row vector of row i.
bool * _decompReducedProbRows
void _getRowsForRemovalComplementaryProblem(int *nonposind, int *bind, int *rowsforremoval, int *nrowsforremoval, int nnonposind)
computes the rows to remove from the complementary problem
virtual bool isUnsimplified() const
specifies whether an optimal solution has already been unsimplified.
bool isSPxRowId() const
is id a row id?
DataArray< SPxSolver::VarStatus > _basisStatusRows
Real totalRowViol
the sum of the row violations in the original problem using the red prob sol
int iterationsFromBasis
number of iterations from Basis
void _solveDecompositionDualSimplex()
solves LP using the decomposition based dual simplex
dual variable is set to its lower bound
Timer * solvingTime
solving time
int size() const
return nr. of elements.
SPxBasis _decompTransBasis
Type type() const
return current Type.
bool boolParam(const BoolParam param) const
returns boolean parameter value
the verbosity of the decomposition based simplex
Real getSolveTime() const
time spent in solves
virtual Status getRedCost(Vector &vector) const
get vector of reduced costs.
void _storeSolutionReal(bool verify=true)
stores solution of the real LP; before calling this, the real LP must be loaded in the solver and sol...
#define MSG_INFO1(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO1.
Real solveTime() const
time spent in last call to solve
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
int iterationsPrimal
number of iterations with Primal
int * _decompViolatedBounds
void _updateComplementaryDualSlackColCoeff()
updating the slack column coefficients to adjust for equality constraints
int iterationsCompProb
number of iterations of the complementary problem
virtual void init()
intialize data structures.
Ids for LP rows.Class SPxRowId provides DataKeys for the row indices of an SPxLP. ...
dual feasibility tolerance
bool isZero(Real a, Real eps=Param::epsilon())
returns true iff |a| <= eps
void solve(Vector &x, const Vector &rhs)
const SVector & vector(int i) const
i 'th vector.
void _identifyComplementaryDualFixedPrimalVars(int *currFixedVars)
removing the dual columns related to the fixed variables
void _updateComplementaryDualFixedPrimalVars(int *currFixedVars)
updating the dual columns related to the fixed primal variables.
DualSign getExpectedDualVariableSign(int rowNumber)
returns the expected sign of the dual variables for the reduced problem
bool decompTerminate(Real timeLimit)
function call to terminate the decomposition simplex
bool isRowBasic(int i) const
is the i 'th row vector basic ?
void getOriginalProblemStatistics()
stores the problem statistics of the original problem
void _enableSimplifierAndScaler()
enables simplifier and scaler according to current parameters
int redProbStatus
status of the reduced problem
bool checkBasisDualFeasibility(Vector feasVec)
checks the dual feasibility of the current basis
virtual void unscaleSlacks(const SPxLPBase< Real > &lp, Vector &s) const
unscale dense slack vector given in s.
void setOutstream(SPxOut &newOutstream)
Real sumDualDegen
the sum of the rate of dual degeneracy at each iteration
void setDecompIterationLimit(int iterationLimit)
sets the iteration limit for the decomposition simplex initialisation
virtual void setTerminationValue(Real value=infinity)
set objective limit.
const SPxBasis & basis() const
Return current basis.
the number of iterations before the decomposition simplex initialisation is terminated.
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.
void _updateDecompReducedProblemViol(bool allrows)
update the reduced problem with additional columns and rows based upon the violated original bounds a...
int numColsReal() const
returns number of columns
virtual Status solve()
solve loaded LP.
void reSize(int newsize)
reset size to newsize.
const VectorBase< R > & lower() const
Returns (internal and possibly scaled) lower bound vector.
SPxSolver::Status _status
virtual R maxAbsNzo(bool unscaled=true) const
Absolute biggest non-zero element in (in rational case possibly scaled) LP.
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...
void setDecompStatus(DecompStatus decomp_stat)
turn on or off the improved dual simplex.
SPxRowId rowId(int i) const
RowId of i 'th inequality.
LP column.Class LPColBase provides a datatype for storing the column of an LP a the form similar to ...
const Desc & desc() const
Real totalBoundViol
the sum of the bound violations in the original problem using the red prob sol
Representation rep() const
return the current basis representation.
solve() aborted due to objective limit.
void spx_free(T &p)
Release memory.
SPxSimplifier * _simplifier
void _updateDecompComplementaryPrimalProblem(bool origObj)
update the primal complementary problem with additional columns and rows
DataArray< SPxColId > _decompDualColIDs
virtual void addCols(const LPColSetBase< R > &pset, bool scale=false)
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.
const SVector & unitVector(int i) const
return i 'th unit vector.
should row and bound violations be computed explicitly in the update of reduced problem in the decomp...
int numRedProbRows
number of rows in the reduced problem
int * _decompCompProbColIDsIdx
LP has a usable Basis (maybe LP is changed).
int primalIterations()
return number of iterations done with primal algorithm
dual infeasibility was detected
virtual Status getSlacks(Vector &vector) const
get vector of slack variables.
LP has been proven to be primal unbounded.
int degenPivotsPrimal
number of primal degenerate pivots
No Problem has been loaded to the basis.
void _updateDecompComplementaryDualProblem(bool origObj)
update the dual complementary problem with additional columns and rows