28 #define MAX_DEGENCHECK 20 29 #define DEGENCHECK_OFFSET 50 30 #define SLACKCOEFF 1.0 31 #define TIMELIMIT_FRAC 0.5 86 int numDegenCheck = 0;
87 Real degeneracyLevel = 0;
89 bool initSolveFromScratch =
true;
105 initSolveFromScratch =
false;
200 basisStatusCols.
size());
219 spxout <<
"======== Degeneracy Detected ========" << std::endl
221 <<
"======== Commencing decomposition solve ========" << std::endl
230 if( decomp_verbosity < orig_verbosity )
242 bool hasRedBasis =
false;
243 bool redProbError =
false;
244 bool noRedprobIter =
false;
246 int algIterCount = 0;
270 <<
"=========================" << std::endl
271 <<
"Solving: Reduced Problem." << std::endl
272 <<
"=========================" << std::endl
310 spxout <<
"WIMDSM02: reduced problem performed zero iterations. Terminating." << std::endl; );
312 noRedprobIter =
true;
330 if( algIterCount == 0 )
346 <<
"=========================" << std::endl
347 <<
"Solving: Complementary Problem." << std::endl
348 <<
"=========================" << std::endl
385 if( !stop && !explicitviol )
397 compLPPrimalVector, compLPDualVector);
450 #ifdef PERFORM_COMPPROB_CHECK 490 <<
"Max: "<< std::setprecision(20) << maxviol <<
" " 491 <<
"Sum: "<< sumviol << std::endl );
496 <<
"Max: "<< std::setprecision(21) << maxviol <<
" " 497 <<
"Sum: "<< sumviol << std::endl );
507 spxout <<
"======== Decomposition solve completed ========" << std::endl
509 <<
"======== Resolving original problem ========" << std::endl
514 if( (!redProbError && !noRedprobIter) || algIterCount > 0 )
629 int* rowsforremoval = 0;
630 int* colsforremoval = 0;
661 <<
"Solving time: " <<
solveTime() << std::endl );
667 &ncompatind,
true, stop);
669 int* compatboundcons = 0;
670 int ncompatboundcons = 0;
681 <<
"Solving time: " <<
solveTime() << std::endl );
685 spx_alloc(addedrowids, ncompatboundcons);
700 for(
int i = 0; i < ncompatboundcons; i++ )
734 _fixedOrigVars[i] = -2;
766 if( i + 1 < _nPrimalRows &&
780 assert(_nPrimalCols == _nDualRows);
811 int addedrangedrows = 0;
878 MSG_ERROR(
spxout <<
"Caught exception <" << E.
what() <<
"> during simplify and solve.\n" );
883 if( applyPreprocessing )
907 if( applyPreprocessing )
937 if( !applyPreprocessing )
953 assert(
_decompLP == &solver || applyPreprocessing);
954 assert(
_decompLP != &solver || !applyPreprocessing);
981 MSG_ERROR( std::cerr <<
"Caught exception <" << E.
what() <<
"> while solving real LP.\n" );
986 MSG_ERROR( std::cerr <<
"Caught unknown exception while solving real LP.\n" );
1089 MSG_ERROR(
spxout <<
"Caught exception <" << E.
what() <<
"> during unsimplification. Resolving without simplifier and scaler.\n" );
1093 MSG_ERROR(
spxout <<
"Caught unknown exception during unsimplification. Resolving without simplifier and scaler.\n" );
1127 Real reducedProbDual = 0;
1128 Real compProbPrimal = 0;
1136 reducedProbDual = dualVector[solverRowNum];
1143 if(
EQ(reducedProbDual, 0.0, feastol) )
1146 spxout <<
"WIMDSM01: reduced problem dual value is very close to zero." << std::endl; );
1151 if( usecompdual && i < _nPrimalRows - 1 &&
1169 dualRatio = reducedProbDual/compProbPrimal;
1172 if(
LT(dualRatio, maxDualRatio, feastol) )
1173 maxDualRatio = dualRatio;
1186 if( maxDualRatio > 1.0 )
1199 int nviolatedrows = 0;
1204 violatedrows.
reSize(_nPrimalRows);
1206 bool ratioTest =
true;
1212 Real compProbPrimal = 0;
1213 Real compRowRedcost = 0;
1222 compProbPrimal = compPrimalVector[compRowNumber];
1223 compRowRedcost = compProbRedcost[compRowNumber];
1229 compProbPrimal = compDualVector[compRowNumber];
1233 if( usecompdual && i < _nPrimalRows - 1 &&
1238 compProbPrimal += compPrimalVector[compRowNumber];
1239 compRowRedcost += compProbRedcost[compRowNumber];
1246 (varSign ==
SoPlex::IS_POS &&
GT(compProbPrimal*maxDualRatio, 0, feastol)) ||
1247 (varSign ==
SoPlex::IS_NEG &&
LT(compProbPrimal*maxDualRatio, 0, feastol))) )
1255 assert(numIncludedRows <= _realLP->nRows());
1257 violatedrows[nviolatedrows].idx = rownumber;
1258 violatedrows[nviolatedrows].violation =
spxAbs(compProbPrimal*maxDualRatio);
1271 if( !ratioTest || nviolatedrows == 0 )
1280 if( sortsize > 0 && sortsize < nviolatedrows )
1284 for(
int i = 0; i < sortsize; i++ )
1290 newrowidx[nnewrowidx] = violatedrows[i].idx;
1298 for(
int i = 0; i < nnewrowidx; i++ )
1331 Real percenttoadd = 1;
1341 for(
int i = 0; i < nrowstoadd; i++ )
1357 MSG_ERROR(
spxout <<
"Caught exception <" << E.
what() <<
"> while computing compatability.\n" );
1364 for(
int j = 0; j < y.size(); j++ )
1383 if(
LT(norm, bestrownorm) )
1385 bestrow = rowNumber;
1397 newrowidx[nnewrowidx] = rowNumber;
1409 newrowidx[nnewrowidx] = rowNumber;
1415 if( nnewrowidx == 0 )
1417 for(
int i = 0; i < nrowstoadd; i++ )
1425 newrowidx[nnewrowidx] = rowNumber;
1432 if( !allrows && bestrow >= 0 )
1438 newrowidx[nnewrowidx] = bestrow;
1447 for(
int i = 0; i < nnewrowidx; i++ )
1466 Real compProbSlackVal = 0;
1487 Real compProbViol = 0;
1488 Real compSlackCoeff = 0;
1500 compProbViol += compObjValue*compSlackCoeff;
1501 compProbViol *= compSlackCoeff;
1505 Real viol =
_compSolver.
rhs(comprownum) - (compProbActivity[comprownum] + compProbSlackVal);
1507 compProbViol = viol;
1509 viol = (compProbActivity[comprownum] - compProbSlackVal) -
_compSolver.
lhs(comprownum);
1511 compProbViol = viol;
1525 tempViol += compObjValue*compSlackCoeff;
1526 tempViol *= compSlackCoeff;
1530 if( tempViol < compProbViol )
1531 compProbViol = tempViol;
1536 if(
LT(compProbViol, 0, feastol) )
1541 assert(numIncludedRows <= _realLP->nRows());
1543 violatedrows[nviolatedrows].idx = rownumber;
1544 violatedrows[nviolatedrows].violation =
spxAbs(compProbViol);
1557 int* nnonposind,
bool& stop)
1582 colsforremoval[i] = i;
1587 if(
isZero(feasVector[i], feastol) )
1589 nonposind[*nnonposind] = i;
1600 if(
isZero(feasVector[i], feastol) )
1602 nonposind[*nnonposind] = i;
1612 colsforremoval[i] = -1;
1633 int* colsforremoval,
int nnonposind,
int* ncompatind,
bool formRedProb,
bool& stop)
1653 bool* activerows = 0;
1657 activerows[i] =
false;
1663 if( !
isZero(feasVector[i], feastol) )
1668 activerows[bind] =
true;
1684 rowsforremoval[i] = i;
1702 MSG_ERROR(
spxout <<
"Caught exception <" << E.
what() <<
"> while computing compatability.\n" );
1707 for(
int j = 0; j < nnonposind; ++j )
1710 if( !
isZero(y[nonposind[j]], feastol) )
1718 assert(!activerows[i] || compatible);
1726 for(
int j = 0; j < y.size(); j++ )
1727 newRowVector.
add(y.index(j), y.value(j));
1733 if( !
isZero(y[j], feastol) )
1734 newRowVector.
add(j, y[j]);
1741 #ifndef NO_TRANSFORM 1750 if(
EQ(rowtoupdate.
lhs(), rowtoupdate.
rhs()) )
1755 compatind[*ncompatind] = i;
1769 rowsforremoval[i] = -1;
1815 MSG_ERROR(
spxout <<
"Caught exception <" << E.
what() <<
"> while computing compatability.\n" );
1824 if( ycount < y.
size() && i == y.
index(ycount) )
1837 if(
isZero(y[i], feastol) )
1845 #ifndef NO_TRANSFORM 1859 int* ncompatboundcons,
int nnonposind,
bool& stop)
1897 MSG_ERROR(
spxout <<
"Caught exception <" << E.
what() <<
"> while computing compatability.\n" );
1902 for(
int j = 0; j < nnonposind; ++j )
1905 if( !
isZero(y[nonposind[j]]) )
1916 #ifndef NO_TRANSFORM 1919 for(
int j = 0; j < y.
size(); j++ )
1926 if( !
isZero(y[j], feastol) )
1928 newRowVector.
add(j, y[j]);
1933 newRowVector.
add(i, 1.0);
1957 compatboundcons[(*ncompatboundcons)] = i;
1958 (*ncompatboundcons)++;
1960 boundcons.
add(lhs, newRowVector, rhs);
1979 int* nrowsforremoval,
int nnonposind)
1981 *nrowsforremoval = 0;
1983 for(
int i = 0; i < nnonposind; i++ )
1985 if( bind[nonposind[i]] < 0 )
1987 rowsforremoval[*nrowsforremoval] = -1 - bind[nonposind[i]];
1988 (*nrowsforremoval)++;
2046 for(
int i = 0; i < naddedrows; i++ )
2047 rangedRowIds[i] = addedrowid[i];
2055 compSlackCol.
add(-1.0, 0.0, slackColCoeff,
infinity);
2081 int numElimColsAdded = 0;
2082 int currnumrows = prevNumRows;
2091 assert(solverRowNum >= 0 && solverRowNum <
_solver.
nRows());
2110 for(
int j = 0; j < origlprow.
rowVector().size(); j++ )
2114 int colNumber = origlprow.
rowVector().index(j);
2127 coltoaddVec.
add(currnumrows, origlprow.
rowVector().value(j));
2139 for(
int j = 0; j < nnewrows; j++ )
2195 << numElimColsAdded << std::endl );
2212 int* colsforremoval = 0;
2213 int ncolsforremoval = 0;
2214 spx_alloc(colsforremoval, prevPrimalRowIds);
2215 for(
int i = 0; i < prevPrimalRowIds; i++ )
2230 #ifdef KEEP_ALL_ROWS_IN_COMP_PROB 2231 bool incrementI =
false;
2233 if( i + 1 < prevPrimalRowIds
2238 #ifdef KEEP_ALL_ROWS_IN_COMP_PROB // 22.06.2015 2260 assert(solverRowNum >= 0 && solverRowNum <
_solver.
nRows());
2284 #ifdef KEEP_ALL_ROWS_IN_COMP_PROB 2312 #else // 22.06.2015 testing keeping all rows in the complementary problem 2330 #ifdef KEEP_ALL_ROWS_IN_COMP_PROB 2381 int removeCount = 0;
2405 }
while( removeCount < numRemove );
2416 if( slackRowCoeff.size() == 0 )
2434 int* currFixedVars = 0;
2463 int numElimRowsAdded = 0;
2472 assert(solverRowNum >= 0 && solverRowNum <
_solver.
nRows());
2546 << numElimRowsAdded << std::endl );
2564 int* rowsforremoval = 0;
2565 int nrowsforremoval = 0;
2566 spx_alloc(rowsforremoval, prevPrimalRowIds);
2567 for(
int i = 0; i < prevPrimalRowIds; i++ )
2582 assert(solverRowNum >= 0 && solverRowNum <
_solver.
nRows());
2676 int* currFixedVars = 0;
2706 <<
"Checking consistency between the reduced problem and the original problem." << std::endl );
2712 Real objectiveVal = 0;
2722 <<
"Original Problem Objective Value: " << objectiveVal << std::endl );
2739 <<
"Max violation: " << maxviol <<
" Sum violation: " << sumviol << std::endl );
2750 <<
"Max violation: " << maxviol <<
" Sum violation: " << sumviol << std::endl );
2804 int numFixedVar = 0;
2807 currFixedVars[i] = 0;
2829 currFixedVars[i] = 1;
2832 currFixedVars[i] = -1;
2837 MSG_INFO3(
spxout,
spxout <<
"Number of fixed primal variables in the complementary (dual) problem: " 2838 << numFixedVar << std::endl );
2847 int ncolsforremoval = 0;
2848 int* colsforremoval = 0;
2912 int numFixedVars = 0;
2916 int numBoundConsCols = 0;
2917 int* boundConsColsAdded = 0;
2925 boundConsColsAdded[i] = 0;
2932 if( currFixedVars[i] != 0 )
2934 assert(currFixedVars[i] == -1 || currFixedVars[i] == 1);
2938 Real colObjCoeff = 0;
2939 if( currFixedVars[i] == -1 )
2966 boundConsColsAdded[i]++;
2979 boundConsColsAdded[i]++;
2994 int addedcolcount = 0;
3011 spx_alloc(addedbndcolids, numBoundConsCols);
3017 if( boundConsColsAdded[i] > 0 )
3019 for(
int j = 0; j < boundConsColsAdded[i]; j++ )
3026 switch( boundConsColsAdded[i] )
3047 int numFixedVar = 0;
3050 currFixedVars[i] = 0;
3067 MSG_INFO3(
spxout,
spxout <<
"Number of fixed primal variables in the complementary (primal) problem: " 3068 << numFixedVar << std::endl );
3076 int numFixedVars = 0;
3086 if( currFixedVars[colNumber] != 0 )
3088 assert(currFixedVars[colNumber] == -1 || currFixedVars[colNumber] == 1);
3090 if( currFixedVars[colNumber] == -1 )
3241 solverStat = solver.
status();
3248 switch( solverStat )
3350 if(
GT(feasVec[i], 0, feastol) )
3357 if(
LT(feasVec[i], 0, feastol) )
3368 if(
GT(feasVec[i], 0, feastol) )
3375 if(
LT(feasVec[i], 0, feastol) )
3437 spxout <<
"type | time | iters | red iter | alg iter | rows | cols | shift | value\n";
3443 spxout << std::fixed << std::setw(7) << std::setprecision(1) << currentTime <<
" |";
3444 spxout << std::scientific << std::setprecision(2);
3446 spxout << std::scientific << std::setprecision(2);
3448 spxout << std::scientific << std::setprecision(2);
3450 spxout << std::scientific << std::setprecision(2);
3452 spxout << std::scientific << std::setprecision(2);
3454 << solver.
shift() <<
" | " 3488 bool hasLower =
false;
3489 bool hasUpper =
false;
3503 if( hasUpper && hasLower )
3506 if( !hasUpper && !hasLower )
3512 bool hasRhs =
false;
3513 bool hasLhs =
false;
3527 if( hasRhs && hasLhs )
3530 if( !hasRhs && !hasLhs )
3617 bool isViol =
false;
3618 bool isMaxViol =
false;
3622 Real currviol = 0.0;
3632 if( viol > maxviol )
3638 if( currviol < viol )
3642 if(
GT(viol, 0.0, feastol) )
3649 if( viol > maxviol )
3655 if( currviol < viol )
3659 if(
GT(viol, 0.0, feastol) )
3673 _nDecompViolBounds++;
3698 bool isViol =
false;
3699 bool isMaxViol =
false;
3703 Real currviol = 0.0;
3712 if( viol > maxviol )
3718 if( viol > currviol )
3722 if(
GT(viol, 0.0, feastol) )
3729 if( viol > maxviol )
3735 if( viol > currviol )
3739 if(
GT(viol, 0.0, feastol) )
3765 Real maxTime = timeLimit;
3768 if( maxTime < 0 || maxTime >=
infinity )
3772 if ( currentTime >= maxTime )
3775 <<
") reached" << std::endl; )
3798 assert(solverRowNum >= 0 && solverRowNum <
_solver.
nRows());
3833 assert(solverRowNum >= 0 && solverRowNum <
_solver.
nRows());
3842 degenerateRowNums[nDegenerateRows] = rowNumber;
3854 degenerateRowNums[nDegenerateRows] = rowNumber;
3966 nNonBasicRows =
_realLP->
nRows() - basicRow - nDegenerateRows;
3980 int numZeroDual = 0;
4024 << nNonBasicCols <<
" (from " <<
_realLP->
nCols() <<
")" << std::endl
4025 <<
"Number of zero dual columns: " << numZeroDual <<
" (from " <<
_realLP->
nCols() <<
")" << std::endl );
4035 int nNonBasicRows = 0;
4036 int nNonBasicCols = 0;
4037 int nDegenerateRows = 0;
4045 degenerateRowNums.
reSize(numrows);
4046 degenerateRowStatus.
reSize(numrows);
4056 assert(nDegenerateRows + nNonBasicRows + nNonBasicCols >= numcols);
4057 int degenRowsSetNonBasic = 0;
4058 for(
int i = 0; i < nDegenerateRows; i++ )
4060 if( nNonBasicRows + nNonBasicCols + degenRowsSetNonBasic < numcols )
4063 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
apply standard floating-point algorithm
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...
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