SoPlex
|
LP simplifier for removing uneccessary row/columns. More...
#include <spxmainsm.h>
Classes | |
class | AggregationPS |
Postsolves aggregation. More... | |
class | DoubletonEquationPS |
Postsolves doubleton equations combined with a column singleton. More... | |
class | DuplicateColsPS |
Postsolves duplicate columns. More... | |
class | DuplicateRowsPS |
Postsolves duplicate rows. More... | |
struct | ElementCompare |
comparator for class SVectorBase<R>::Element: compare nonzeros according to value More... | |
class | EmptyConstraintPS |
Postsolves empty constraints. More... | |
class | FixBoundsPS |
Postsolves variable bound fixing. More... | |
class | FixVariablePS |
Postsolves variable fixing. More... | |
class | ForceConstraintPS |
Postsolves forcing constraints. More... | |
class | FreeColSingletonPS |
Postsolves free column singletons. More... | |
class | FreeConstraintPS |
Postsolves unconstraint constraints. More... | |
class | FreeZeroObjVariablePS |
Postsolves the case when constraints are removed due to a variable with zero objective that is free in one direction. More... | |
struct | IdxCompare |
comparator for class SVectorBase<R>::Element: compare nonzeros according to index More... | |
class | MultiAggregationPS |
Postsolves multi aggregation. More... | |
class | PostStep |
Base class for postsolving operations. More... | |
class | RowObjPS |
Postsolves row objectives. More... | |
class | RowSingletonPS |
Postsolves row singletons. More... | |
class | TightenBoundsPS |
Postsolves variable bound tightening from pseudo objective propagation. More... | |
class | ZeroObjColSingletonPS |
Postsolves column singletons with zero objective. More... | |
Public Member Functions | |
Constructors / destructors | |
default constructor. | |
SPxMainSM (Timer::TYPE ttype=Timer::USER_TIME) | |
SPxMainSM (const SPxMainSM &old) | |
copy constructor. | |
SPxMainSM & | operator= (const SPxMainSM &rhs) |
assignment operator | |
virtual | ~SPxMainSM () |
destructor. | |
virtual SPxSimplifier< R > * | clone () const |
clone function for polymorphism | |
virtual SPxSimplifier< R >::Result | simplify (SPxLPBase< R > &lp, Real remainingTime, bool keepbounds=false, uint32_t seed=0) |
simplify SPxLPBase<R> lp . | |
virtual void | unsimplify (const VectorBase< R > &x, const VectorBase< R > &y, const VectorBase< R > &s, const VectorBase< R > &r, const typename SPxSolverBase< R >::VarStatus rows[], const typename SPxSolverBase< R >::VarStatus cols[], bool isOptimal=true) |
reconstructs an optimal solution for the unsimplified LP. | |
virtual SPxSimplifier< R >::Result | result () const |
returns result status of the simplification | |
virtual bool | isUnsimplified () const |
specifies whether an optimal solution has already been unsimplified. | |
virtual const VectorBase< R > & | unsimplifiedPrimal () |
returns a reference to the unsimplified primal solution. | |
virtual const VectorBase< R > & | unsimplifiedDual () |
returns a reference to the unsimplified dual solution. | |
virtual const VectorBase< R > & | unsimplifiedSlacks () |
returns a reference to the unsimplified slack values. | |
virtual const VectorBase< R > & | unsimplifiedRedCost () |
returns a reference to the unsimplified reduced costs. | |
virtual SPxSolverBase< R >::VarStatus | getBasisRowStatus (int i) const |
gets basis status for a single row. | |
virtual SPxSolverBase< R >::VarStatus | getBasisColStatus (int j) const |
gets basis status for a single column. | |
virtual void | getBasis (typename SPxSolverBase< R >::VarStatus rows[], typename SPxSolverBase< R >::VarStatus cols[], const int rowsSize=-1, const int colsSize=-1) const |
get optimal basis. | |
![]() | |
void | setOutstream (SPxOut &newOutstream) |
virtual void | setTolerances (std::shared_ptr< Tolerances > newTolerances) |
set the _tolerances member variable | |
const std::shared_ptr< Tolerances > | tolerances () const |
get the _tolerances member variable | |
virtual const char * | getName () const |
get name of simplifier. | |
virtual R | timeUsed () const |
virtual R | getObjoffset () const |
get objective offset. | |
virtual void | addObjoffset (const R val) |
add objective offset. | |
virtual void | setMinReduction (const R minRed) |
set minimal reduction threshold to continue simplification | |
virtual bool | isConsistent () const |
consistency check | |
SPxSimplifier (const char *p_name, Timer::TYPE ttype=Timer::USER_TIME) | |
constructor | |
SPxSimplifier (const SPxSimplifier &old) | |
copy constructor | |
SPxSimplifier & | operator= (const SPxSimplifier &rhs) |
assignment operator | |
virtual | ~SPxSimplifier () |
destructor. | |
Protected Member Functions | |
R | epsZero () const |
R | feastol () const |
R | opttol () const |
Private Types | |
Types | |
Different simplification steps. | |
enum | SimpleStep { EMPTY_ROW = 0 , FREE_ROW = 1 , SINGLETON_ROW = 2 , FORCE_ROW = 3 , EMPTY_COL = 4 , FIX_COL = 5 , FREE_ZOBJ_COL = 6 , ZOBJ_SINGLETON_COL = 7 , DOUBLETON_ROW = 8 , FREE_SINGLETON_COL = 9 , DOMINATED_COL = 10 , WEAKLY_DOMINATED_COL = 11 , DUPLICATE_ROW = 12 , FIX_DUPLICATE_COL = 13 , SUB_DUPLICATE_COL = 14 , AGGREGATION = 15 , MULTI_AGG = 16 } |
Private Member Functions | |
Private helpers | |
handle row objectives | |
void | handleRowObjectives (SPxLPBase< R > &lp) |
void | handleExtremes (SPxLPBase< R > &lp) |
handles extreme values by setting them to zero or R(infinity). | |
void | computeMinMaxResidualActivity (SPxLPBase< R > &lp, int rowNumber, int colNumber, R &minAct, R &maxAct) |
computes the minimum and maximum residual activity for a given row and column. If colNumber is set to -1, then | |
void | computeMinMaxValues (SPxLPBase< R > &lp, R side, R val, R minRes, R maxRes, R &minVal, R &maxVal) |
calculate min/max value for the multi aggregated variables | |
void | trivialHeuristic (SPxLPBase< R > &lp) |
tries to find good lower bound solutions by applying some trivial heuristics | |
bool | checkSolution (SPxLPBase< R > &lp, VectorBase< R > sol) |
checks a solution for feasibility | |
void | propagatePseudoobj (SPxLPBase< R > &lp) |
tightens variable bounds by propagating the pseudo objective function value. | |
SPxSimplifier< R >::Result | removeEmpty (SPxLPBase< R > &lp) |
removed empty rows and empty columns. | |
SPxSimplifier< R >::Result | removeRowSingleton (SPxLPBase< R > &lp, const SVectorBase< R > &row, int &i) |
remove row singletons. | |
SPxSimplifier< R >::Result | aggregateVars (SPxLPBase< R > &lp, const SVectorBase< R > &row, int &i) |
aggregate two variables that appear in an equation. | |
SPxSimplifier< R >::Result | simplifyRows (SPxLPBase< R > &lp, bool &again) |
performs simplification steps on the rows of the LP. | |
SPxSimplifier< R >::Result | simplifyCols (SPxLPBase< R > &lp, bool &again) |
performs simplification steps on the columns of the LP. | |
SPxSimplifier< R >::Result | simplifyDual (SPxLPBase< R > &lp, bool &again) |
performs simplification steps on the LP based on dual concepts. | |
SPxSimplifier< R >::Result | multiaggregation (SPxLPBase< R > &lp, bool &again) |
performs multi-aggregations of variable based upon constraint activitu. | |
SPxSimplifier< R >::Result | duplicateRows (SPxLPBase< R > &lp, bool &again) |
removes duplicate rows. | |
SPxSimplifier< R >::Result | duplicateCols (SPxLPBase< R > &lp, bool &again) |
removes duplicate columns | |
void | fixColumn (SPxLPBase< R > &lp, int i, bool correctIdx=true) |
handles the fixing of a variable. correctIdx is true iff the index mapping has to be updated. | |
void | removeRow (SPxLPBase< R > &lp, int i) |
removes a row in the LP. | |
void | removeCol (SPxLPBase< R > &lp, int j) |
removes a column in the LP. | |
int | rIdx (int i) const |
returns for a given row index of the (reduced) LP the corresponding row index in the unsimplified LP. | |
int | cIdx (int j) const |
returns for a given column index of the (reduced) LP the corresponding column index in the unsimplified LP. | |
Private Attributes | |
Data | |
VectorBase< R > | m_prim |
unsimplified primal solution VectorBase<R>. | |
VectorBase< R > | m_slack |
unsimplified slack VectorBase<R>. | |
VectorBase< R > | m_dual |
unsimplified dual solution VectorBase<R>. | |
VectorBase< R > | m_redCost |
unsimplified reduced cost VectorBase<R>. | |
DataArray< typename SPxSolverBase< R >::VarStatus > | m_cBasisStat |
basis status of columns. | |
DataArray< typename SPxSolverBase< R >::VarStatus > | m_rBasisStat |
basis status of rows. | |
DataArray< int > | m_cIdx |
column index VectorBase<R> in original LP. | |
DataArray< int > | m_rIdx |
row index VectorBase<R> in original LP. | |
Array< std::shared_ptr< PostStep > > | m_hist |
VectorBase<R> of presolve history. | |
Array< DSVectorBase< R > > | m_classSetRows |
stores parallel classes with non-zero colum entry | |
Array< DSVectorBase< R > > | m_classSetCols |
stores parallel classes with non-zero row entry | |
Array< DSVectorBase< R > > | m_dupRows |
arrange duplicate rows using bucket sort w.r.t. their pClass values | |
Array< DSVectorBase< R > > | m_dupCols |
arrange duplicate columns w.r.t. their pClass values | |
bool | m_postsolved |
status of postsolving. | |
DataArray< int > | m_stat |
preprocessing history. | |
SPxLPBase< R >::SPxSense | m_thesense |
optimization sense. | |
bool | m_keepbounds |
keep some bounds (for boundflipping) | |
int | m_addedcols |
columns added by handleRowObjectives() | |
SPxSimplifier< R >::Result | m_result |
result of the simplification. | |
R | m_cutoffbound |
the cutoff bound that is found by heuristics | |
R | m_pseudoobj |
the pseudo objective function value | |
Friends | |
class | FreeConstraintPS |
class | EmptyConstraintPS |
class | RowSingletonPS |
class | ForceConstraintPS |
class | FixVariablePS |
class | FixBoundsPS |
class | FreeZeroObjVariablePS |
class | ZeroObjColSingletonPS |
class | FreeColSingletonPS |
class | DoubletonEquationPS |
class | DuplicateRowsPS |
class | DuplicateColsPS |
class | AggregationPS |
Additional Inherited Members | |
![]() | |
enum | Result { OKAY = 0 , INFEASIBLE = 1 , DUAL_INFEASIBLE = 2 , UNBOUNDED = 3 , VANISHED = 4 } |
Result of the simplification. More... | |
![]() | |
const char * | m_name |
name of the simplifier | |
Timer * | m_timeUsed |
user time used for simplification | |
Timer::TYPE | m_timerType |
int | m_remRows |
number of removed rows | |
int | m_remCols |
number of removed columns | |
int | m_remNzos |
number of removed nonzero coefficients | |
int | m_chgBnds |
number of changed bounds | |
int | m_chgLRhs |
number of change right-hand sides | |
int | m_keptBnds |
number of kept bounds | |
int | m_keptLRhs |
number of kept left- and right-hand sides | |
R | m_objoffset |
objective offset | |
R | m_minReduction |
minimal reduction (sum of removed rows/cols) to continue simplification | |
SPxOut * | spxout |
message handler | |
std::shared_ptr< Tolerances > | _tolerances |
LP simplifier for removing uneccessary row/columns.
This SPxSimplifier is mainly based on the paper "Presolving in linear programming" by E. Andersen and K. Andersen (Mathematical Programming, 1995). It implements all proposed methods and some other preprocessing techniques for removing redundant rows and columns and bounds. Also infeasibility and unboundedness may be detected.
Removed are:
Definition at line 71 of file spxmainsm.h.
|
private |
Definition at line 1309 of file spxmainsm.h.
SPxMainSM | ( | Timer::TYPE | ttype = Timer::USER_TIME | ) |
Definition at line 1469 of file spxmainsm.h.
References soplex::infinity, m_addedcols, m_cutoffbound, m_keepbounds, m_postsolved, m_pseudoobj, m_result, m_stat, m_thesense, SPxSimplifier< R >::OKAY, SPxSimplifier< R >::SPxSimplifier(), and Timer::USER_TIME.
Referenced by clone(), SPxMainSM< R >::FixVariablePS::FixVariablePS(), SPxMainSM< R >::FreeColSingletonPS::FreeColSingletonPS(), SPxMainSM< R >::MultiAggregationPS::MultiAggregationPS(), operator=(), SPxMainSM(), and SPxMainSM< R >::ZeroObjColSingletonPS::ZeroObjColSingletonPS().
copy constructor.
Definition at line 1481 of file spxmainsm.h.
References m_addedcols, m_cBasisStat, m_cIdx, m_cutoffbound, m_dual, m_hist, m_keepbounds, m_postsolved, m_prim, m_pseudoobj, m_rBasisStat, m_redCost, m_result, m_rIdx, m_slack, m_stat, m_thesense, SPxMainSM(), and SPxSimplifier< R >::SPxSimplifier().
|
virtual |
destructor.
Definition at line 1532 of file spxmainsm.h.
|
private |
aggregate two variables that appear in an equation.
|
private |
checks a solution for feasibility
|
private |
returns for a given column index of the (reduced) LP the corresponding column index in the unsimplified LP.
Definition at line 1439 of file spxmainsm.h.
References m_cIdx.
|
virtual |
clone function for polymorphism
Implements SPxSimplifier< R >.
Definition at line 1537 of file spxmainsm.h.
References SPxMainSM(), and SPxSimplifier< R >::SPxSimplifier().
|
private |
computes the minimum and maximum residual activity for a given row and column. If colNumber is set to -1, then
|
private |
calculate min/max value for the multi aggregated variables
|
private |
removes duplicate columns
|
private |
removes duplicate rows.
|
protected |
Definition at line 1448 of file spxmainsm.h.
References SPxSimplifier< R >::tolerances().
|
protected |
Definition at line 1453 of file spxmainsm.h.
References SPxSimplifier< R >::tolerances().
|
private |
handles the fixing of a variable. correctIdx is true iff the index mapping has to be updated.
|
virtual |
get optimal basis.
Implements SPxSimplifier< R >.
Definition at line 1604 of file spxmainsm.h.
References m_cBasisStat, m_postsolved, and m_rBasisStat.
|
virtual |
gets basis status for a single column.
Implements SPxSimplifier< R >.
Definition at line 1598 of file spxmainsm.h.
References m_cBasisStat, and m_postsolved.
|
virtual |
gets basis status for a single row.
Implements SPxSimplifier< R >.
Definition at line 1592 of file spxmainsm.h.
References m_postsolved, and m_rBasisStat.
|
private |
handles extreme values by setting them to zero or R(infinity).
|
private |
|
virtual |
specifies whether an optimal solution has already been unsimplified.
Reimplemented from SPxSimplifier< R >.
Definition at line 1563 of file spxmainsm.h.
References m_postsolved.
|
private |
performs multi-aggregations of variable based upon constraint activitu.
assignment operator
Definition at line 1504 of file spxmainsm.h.
References m_addedcols, m_cBasisStat, m_cIdx, m_cutoffbound, m_dual, m_hist, m_keepbounds, m_postsolved, m_prim, m_pseudoobj, m_rBasisStat, m_redCost, m_result, m_rIdx, m_slack, m_stat, m_thesense, SPxSimplifier< R >::operator=(), and SPxMainSM().
|
protected |
Definition at line 1458 of file spxmainsm.h.
References SPxSimplifier< R >::tolerances().
|
private |
tightens variable bounds by propagating the pseudo objective function value.
|
private |
removes a column in the LP.
Definition at line 1428 of file spxmainsm.h.
References m_cIdx, SPxLPBase< R >::nCols(), and SPxLPBase< R >::removeCol().
|
private |
removed empty rows and empty columns.
|
private |
removes a row in the LP.
Definition at line 1422 of file spxmainsm.h.
References m_rIdx, SPxLPBase< R >::nRows(), and SPxLPBase< R >::removeRow().
|
private |
remove row singletons.
|
virtual |
returns result status of the simplification
Implements SPxSimplifier< R >.
Definition at line 1557 of file spxmainsm.h.
References m_result.
|
private |
returns for a given row index of the (reduced) LP the corresponding row index in the unsimplified LP.
Definition at line 1434 of file spxmainsm.h.
References m_rIdx.
|
virtual |
simplify SPxLPBase<R> lp
.
Implements SPxSimplifier< R >.
|
private |
performs simplification steps on the columns of the LP.
|
private |
performs simplification steps on the LP based on dual concepts.
|
private |
performs simplification steps on the rows of the LP.
|
private |
tries to find good lower bound solutions by applying some trivial heuristics
|
virtual |
returns a reference to the unsimplified dual solution.
Implements SPxSimplifier< R >.
Definition at line 1574 of file spxmainsm.h.
References m_dual, and m_postsolved.
|
virtual |
returns a reference to the unsimplified primal solution.
Implements SPxSimplifier< R >.
Definition at line 1568 of file spxmainsm.h.
References m_postsolved, and m_prim.
|
virtual |
returns a reference to the unsimplified reduced costs.
Implements SPxSimplifier< R >.
Definition at line 1586 of file spxmainsm.h.
References m_postsolved, and m_redCost.
|
virtual |
returns a reference to the unsimplified slack values.
Implements SPxSimplifier< R >.
Definition at line 1580 of file spxmainsm.h.
References m_postsolved, and m_slack.
|
virtual |
reconstructs an optimal solution for the unsimplified LP.
Implements SPxSimplifier< R >.
|
friend |
Definition at line 1302 of file spxmainsm.h.
Referenced by SPxMainSM< R >::AggregationPS::clone().
|
friend |
Definition at line 1299 of file spxmainsm.h.
Referenced by SPxMainSM< R >::DoubletonEquationPS::clone().
|
friend |
Definition at line 1301 of file spxmainsm.h.
Referenced by SPxMainSM< R >::DuplicateColsPS::clone().
|
friend |
Definition at line 1300 of file spxmainsm.h.
Referenced by SPxMainSM< R >::DuplicateRowsPS::clone().
|
friend |
Definition at line 1291 of file spxmainsm.h.
Referenced by SPxMainSM< R >::EmptyConstraintPS::clone().
|
friend |
Definition at line 1295 of file spxmainsm.h.
Referenced by SPxMainSM< R >::FixBoundsPS::clone().
|
friend |
Definition at line 1294 of file spxmainsm.h.
Referenced by SPxMainSM< R >::FixVariablePS::clone().
|
friend |
Definition at line 1293 of file spxmainsm.h.
Referenced by SPxMainSM< R >::ForceConstraintPS::clone().
|
friend |
Definition at line 1298 of file spxmainsm.h.
Referenced by SPxMainSM< R >::FreeColSingletonPS::clone().
|
friend |
Definition at line 1290 of file spxmainsm.h.
Referenced by SPxMainSM< R >::FreeConstraintPS::clone().
|
friend |
Definition at line 1296 of file spxmainsm.h.
Referenced by SPxMainSM< R >::FreeZeroObjVariablePS::clone().
|
friend |
Definition at line 1292 of file spxmainsm.h.
Referenced by SPxMainSM< R >::RowSingletonPS::clone().
|
friend |
Definition at line 1297 of file spxmainsm.h.
Referenced by SPxMainSM< R >::ZeroObjColSingletonPS::clone().
|
private |
columns added by handleRowObjectives()
Definition at line 1356 of file spxmainsm.h.
Referenced by operator=(), SPxMainSM(), and SPxMainSM().
|
private |
basis status of columns.
Definition at line 1339 of file spxmainsm.h.
Referenced by getBasis(), getBasisColStatus(), operator=(), and SPxMainSM().
|
private |
column index VectorBase<R> in original LP.
Definition at line 1341 of file spxmainsm.h.
Referenced by cIdx(), operator=(), removeCol(), and SPxMainSM().
|
private |
stores parallel classes with non-zero row entry
Definition at line 1347 of file spxmainsm.h.
|
private |
stores parallel classes with non-zero colum entry
Definition at line 1345 of file spxmainsm.h.
|
private |
the cutoff bound that is found by heuristics
Definition at line 1358 of file spxmainsm.h.
Referenced by operator=(), SPxMainSM(), and SPxMainSM().
|
private |
unsimplified dual solution VectorBase<R>.
Definition at line 1337 of file spxmainsm.h.
Referenced by operator=(), SPxMainSM(), and unsimplifiedDual().
|
private |
arrange duplicate columns w.r.t. their pClass values
Definition at line 1351 of file spxmainsm.h.
|
private |
arrange duplicate rows using bucket sort w.r.t. their pClass values
Definition at line 1349 of file spxmainsm.h.
VectorBase<R> of presolve history.
Definition at line 1343 of file spxmainsm.h.
Referenced by operator=(), and SPxMainSM().
|
private |
keep some bounds (for boundflipping)
Definition at line 1355 of file spxmainsm.h.
Referenced by operator=(), SPxMainSM(), and SPxMainSM().
|
private |
status of postsolving.
Definition at line 1352 of file spxmainsm.h.
Referenced by getBasis(), getBasisColStatus(), getBasisRowStatus(), isUnsimplified(), operator=(), SPxMainSM(), SPxMainSM(), unsimplifiedDual(), unsimplifiedPrimal(), unsimplifiedRedCost(), and unsimplifiedSlacks().
|
private |
unsimplified primal solution VectorBase<R>.
Definition at line 1335 of file spxmainsm.h.
Referenced by operator=(), SPxMainSM(), and unsimplifiedPrimal().
|
private |
the pseudo objective function value
Definition at line 1359 of file spxmainsm.h.
Referenced by operator=(), SPxMainSM(), and SPxMainSM().
|
private |
basis status of rows.
Definition at line 1340 of file spxmainsm.h.
Referenced by getBasis(), getBasisRowStatus(), operator=(), and SPxMainSM().
|
private |
unsimplified reduced cost VectorBase<R>.
Definition at line 1338 of file spxmainsm.h.
Referenced by operator=(), SPxMainSM(), and unsimplifiedRedCost().
|
private |
result of the simplification.
Definition at line 1357 of file spxmainsm.h.
Referenced by operator=(), result(), SPxMainSM(), and SPxMainSM().
|
private |
row index VectorBase<R> in original LP.
Definition at line 1342 of file spxmainsm.h.
Referenced by operator=(), removeRow(), rIdx(), and SPxMainSM().
|
private |
unsimplified slack VectorBase<R>.
Definition at line 1336 of file spxmainsm.h.
Referenced by operator=(), SPxMainSM(), and unsimplifiedSlacks().
|
private |
preprocessing history.
Definition at line 1353 of file spxmainsm.h.
Referenced by operator=(), SPxMainSM(), and SPxMainSM().
|
private |
optimization sense.
Definition at line 1354 of file spxmainsm.h.
Referenced by operator=(), SPxMainSM(), and SPxMainSM().