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. 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 SVector::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 SVector::Element: compare nonzeros according to index More...

class	MultiAggregationPS
	Postsolves multi aggregation. More...

class	PostStep
	Base class for postsolving operations.Class PostStep is an abstract base class providing the interface for operations in the postsolving process. 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

	SPxMainSM (Timer::TYPE ttype=Timer::USER_TIME)
	default constructor. More...

	SPxMainSM (const SPxMainSM &old)
	copy constructor. More...

SPxMainSM &	operator= (const SPxMainSM &rhs)
	assignment operator More...

virtual	~SPxMainSM ()
	destructor. More...

virtual SPxSimplifier *	clone () const
	clone function for polymorphism More...


virtual Result	simplify (SPxLP &lp, Real eps, Real delta)
	simplify SPxLP `lp` with identical primal and dual feasibility tolerance. More...

virtual Result	simplify (SPxLP &lp, Real eps, Real ftol, Real otol, bool keepbounds=false)
	simplify SPxLP `lp` with independent primal and dual feasibility tolerance. More...

virtual void	unsimplify (const Vector &x, const Vector &y, const Vector &s, const Vector &r, const SPxSolver::VarStatus rows[], const SPxSolver::VarStatus cols[], bool isOptimal=true)
	reconstructs an optimal solution for the unsimplified LP. More...

virtual Result	result () const
	returns result status of the simplification More...

virtual bool	isUnsimplified () const
	specifies whether an optimal solution has already been unsimplified. More...

virtual const Vector &	unsimplifiedPrimal ()
	returns a reference to the unsimplified primal solution. More...

virtual const Vector &	unsimplifiedDual ()
	returns a reference to the unsimplified dual solution. More...

virtual const Vector &	unsimplifiedSlacks ()
	returns a reference to the unsimplified slack values. More...

virtual const Vector &	unsimplifiedRedCost ()
	returns a reference to the unsimplified reduced costs. More...

virtual SPxSolver::VarStatus	getBasisRowStatus (int i) const
	gets basis status for a single row. More...

virtual SPxSolver::VarStatus	getBasisColStatus (int j) const
	gets basis status for a single column. More...

virtual void	getBasis (SPxSolver::VarStatus rows[], SPxSolver::VarStatus cols[], const int rowsSize=-1, const int colsSize=-1) const
	get optimal basis. More...

Public Member Functions inherited from SPxSimplifier
virtual const char *	getName () const
	get name of simplifier. More...

virtual Real	timeUsed () const

virtual Real	getObjoffset () const
	get objective offset. More...

virtual void	addObjoffset (const Real val)
	add objective offset. More...

virtual void	setMinReduction (const Real minRed)
	set minimal reduction threshold to continue simplification More...

virtual bool	isConsistent () const
	consistency check More...

	SPxSimplifier (const char *p_name, Timer::TYPE ttype=Timer::USER_TIME)
	constructor More...

	SPxSimplifier (const SPxSimplifier &old)
	copy constructor More...

SPxSimplifier &	operator= (const SPxSimplifier &rhs)
	assignment operator More...

virtual	~SPxSimplifier ()
	destructor. More...

Protected Member Functions
Real	epsZero () const

Real	feastol () const

Real	opttol () const

Private Types

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 }
	Different simplification steps. More...

Private Member Functions

void	handleRowObjectives (SPxLP &lp)
	handle row objectives More...

void	handleExtremes (SPxLP &lp)
	handles extreme values by setting them to zero or infinity. More...

void	computeMinMaxResidualActivity (SPxLP &lp, int rowNumber, int colNumber, Real &minAct, Real &maxAct)
	computes the minimum and maximum residual activity for a given row and column. If colNumber is set to -1, then More...

void	computeMinMaxValues (SPxLP &lp, Real side, Real val, Real minRes, Real maxRes, Real &minVal, Real &maxVal)
	calculate min/max value for the multi aggregated variables More...

void	trivialHeuristic (SPxLP &lp)
	tries to find good lower bound solutions by applying some trivial heuristics More...

bool	checkSolution (SPxLP &lp, DVector sol)
	checks a solution for feasibility More...

void	propagatePseudoobj (SPxLP &lp)
	tightens variable bounds by propagating the pseudo objective function value. More...

Result	removeEmpty (SPxLP &lp)
	removed empty rows and empty columns. More...

Result	removeRowSingleton (SPxLP &lp, const SVector &row, int &i)
	remove row singletons. More...

Result	aggregateVars (SPxLP &lp, const SVector &row, int &i)
	aggregate two variables that appear in an equation. More...

Result	simplifyRows (SPxLP &lp, bool &again)
	performs simplification steps on the rows of the LP. More...

Result	simplifyCols (SPxLP &lp, bool &again)
	performs simplification steps on the columns of the LP. More...

Result	simplifyDual (SPxLP &lp, bool &again)
	performs simplification steps on the LP based on dual concepts. More...

Result	multiaggregation (SPxLP &lp, bool &again)
	performs multi-aggregations of variable based upon constraint activitu. More...

Result	duplicateRows (SPxLP &lp, bool &again)
	removes duplicate rows. More...

Result	duplicateCols (SPxLP &lp, bool &again)
	removes duplicate columns More...

void	fixColumn (SPxLP &lp, int i, bool correctIdx=true)
	handles the fixing of a variable. correctIdx is true iff the index mapping has to be updated. More...

void	removeRow (SPxLP &lp, int i)
	removes a row in the LP. More...

void	removeCol (SPxLP &lp, int j)
	removes a column in the LP. More...

int	rIdx (int i) const
	returns for a given row index of the (reduced) LP the corresponding row index in the unsimplified LP. More...

int	cIdx (int j) const
	returns for a given column index of the (reduced) LP the corresponding column index in the unsimplified LP. More...

Private Attributes

DVector	m_prim
	unsimplified primal solution vector. More...

DVector	m_slack
	unsimplified slack vector. More...

DVector	m_dual
	unsimplified dual solution vector. More...

DVector	m_redCost
	unsimplified reduced cost vector. More...

DataArray< SPxSolver::VarStatus >	m_cBasisStat
	basis status of columns. More...

DataArray< SPxSolver::VarStatus >	m_rBasisStat
	basis status of rows. More...

DataArray< int >	m_cIdx
	column index vector in original LP. More...

DataArray< int >	m_rIdx
	row index vector in original LP. More...

DataArray< PostStep * >	m_hist
	vector of presolve history. More...

Array< DSVector >	m_classSetRows
	stores parallel classes with non-zero colum entry More...

Array< DSVector >	m_classSetCols
	stores parallel classes with non-zero row entry More...

Array< DSVector >	m_dupRows
	arrange duplicate rows using bucket sort w.r.t. their pClass values More...

Array< DSVector >	m_dupCols
	arrange duplicate columns w.r.t. their pClass values More...

bool	m_postsolved
	status of postsolving. More...

Real	m_epsilon
	epsilon zero. More...

Real	m_feastol
	primal feasibility tolerance. More...

Real	m_opttol
	dual feasibility tolerance. More...

DataArray< int >	m_stat
	preprocessing history. More...

SPxLP::SPxSense	m_thesense
	optimization sense. More...

bool	m_keepbounds
	keep some bounds (for boundflipping) More...

int	m_addedcols
	columns added by handleRowObjectives() More...

Result	m_result
	result of the simplification. More...

Real	m_cutoffbound
	the cutoff bound that is found by heuristics More...

Real	m_pseudoobj
	the pseudo objective function value More...

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
Public Types inherited from SPxSimplifier
enum	Result { OKAY = 0, INFEASIBLE = 1, DUAL_INFEASIBLE = 2, UNBOUNDED = 3, VANISHED = 4 }
	Result of the simplification. More...

Protected Attributes inherited from SPxSimplifier
const char *	m_name
	name of the simplifier More...

Timer *	m_timeUsed
	user time used for simplification More...

Timer::TYPE	m_timerType

int	m_remRows
	number of removed rows More...

int	m_remCols
	number of removed columns More...

int	m_remNzos
	number of removed nonzero coefficients More...

int	m_chgBnds
	number of changed bounds More...

int	m_chgLRhs
	number of change right-hand sides More...

int	m_keptBnds
	number of kept bounds More...

int	m_keptLRhs
	number of kept left- and right-hand sides More...

Real	m_objoffset
	objective offset More...

Real	m_minReduction
	minimal reduction (sum of removed rows/cols) to continue simplification More...

SPxOut *	spxout
	message handler More...

Detailed Description

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:

empty rows / columns
unconstraint rows
row singletons
forcing rows
zero objective column singletons
(implied) free column singletons
doubleton equations combined with a column singleton
(implicitly) fixed columns
redundant lhs / rhs
redundant variable bounds
variables that are free in one direction
(weakly) dominated columns
duplicate rows / columns

Definition at line 60 of file spxmainsm.h.

Member Enumeration Documentation

◆ SimpleStep

enum SimpleStep

private

Different simplification steps.

Enumerator
EMPTY_ROW
FREE_ROW
SINGLETON_ROW
FORCE_ROW
EMPTY_COL
FIX_COL
FREE_ZOBJ_COL
ZOBJ_SINGLETON_COL
DOUBLETON_ROW
FREE_SINGLETON_COL
DOMINATED_COL
WEAKLY_DOMINATED_COL
DUPLICATE_ROW
FIX_DUPLICATE_COL
SUB_DUPLICATE_COL
AGGREGATION
MULTI_AGG

Definition at line 1260 of file spxmainsm.h.

Constructor & Destructor Documentation

◆ SPxMainSM() [1/2]

SPxMainSM ( Timer::TYPE ttype = Timer::USER_TIME )

default constructor.

Definition at line 1416 of file spxmainsm.h.

Referenced by SPxMainSM::clone().

◆ SPxMainSM() [2/2]

SPxMainSM ( const SPxMainSM & old )

copy constructor.

Definition at line 1431 of file spxmainsm.h.

References DataArray< T >::append(), SPxMainSM::m_hist, and DataArray< T >::reSize().

◆ ~SPxMainSM()

virtual ~SPxMainSM ( )

virtual

destructor.

Definition at line 1511 of file spxmainsm.h.

References DataArray< T >::size(), and soplex::spx_free().

Member Function Documentation

◆ aggregateVars()

SPxSimplifier::Result aggregateVars	(	SPxLP &	lp,
		const SVector &	row,
		int &	i
	)

private

aggregate two variables that appear in an equation.

aggregate variable x_j to x_j = (rhs - aik * x_k) / aij from row i: aij * x_j + aik * x_k = rhs

Definition at line 2182 of file spxmainsm.cpp.

Referenced by SPxMainSM::simplifyRows().

◆ checkSolution()

bool checkSolution	(	SPxLP &	lp,
		DVector	sol
	)

private

checks a solution for feasibility

Definition at line 1918 of file spxmainsm.cpp.

References SPxMainSM::feastol(), soplex::GE(), SVectorBase< R >::index(), soplex::LE(), SPxLPBase< R >::lhs(), SPxLPBase< R >::nRows(), SPxLPBase< R >::rhs(), SPxLPBase< R >::rowVector(), SVectorBase< R >::size(), and SVectorBase< R >::value().

Referenced by SPxMainSM::trivialHeuristic().

◆ cIdx()

int cIdx ( int j ) const

private

returns for a given column index of the (reduced) LP the corresponding column index in the unsimplified LP.

Definition at line 1386 of file spxmainsm.h.

Referenced by SPxMainSM::ForceConstraintPS::execute(), and SPxMainSM::DuplicateColsPS::execute().

◆ clone()

virtual SPxSimplifier* clone ( ) const

virtual

clone function for polymorphism

Implements SPxSimplifier.

Definition at line 1524 of file spxmainsm.h.

References SPxMainSM::SPxMainSM().

◆ computeMinMaxResidualActivity()

void computeMinMaxResidualActivity	(	SPxLP &	lp,
		int	rowNumber,
		int	colNumber,
		Real &	minAct,
		Real &	maxAct
	)

private

computes the minimum and maximum residual activity for a given row and column. If colNumber is set to -1, then

computes the minimum and maximum residual activity for a given variable

Definition at line 1708 of file spxmainsm.cpp.

References soplex::GE(), soplex::GT(), SVectorBase< R >::index(), soplex::infinity, soplex::LE(), SPxLPBase< R >::lower(), soplex::LT(), SPxLPBase< R >::rowVector(), SVectorBase< R >::size(), SPxLPBase< R >::upper(), and SVectorBase< R >::value().

Referenced by SPxMainSM::multiaggregation().

◆ computeMinMaxValues()

void computeMinMaxValues	(	SPxLP &	lp,
		Real	side,
		Real	val,
		Real	minRes,
		Real	maxRes,
		Real &	minVal,
		Real &	maxVal
	)

private

calculate min/max value for the multi aggregated variables

Definition at line 1766 of file spxmainsm.cpp.

References soplex::GE(), soplex::GT(), soplex::infinity, soplex::LE(), and soplex::LT().

Referenced by SPxMainSM::multiaggregation().

◆ duplicateCols()

SPxSimplifier::Result duplicateCols	(	SPxLP &	lp,
		bool &	again
	)

private

removes duplicate columns

Definition at line 4334 of file spxmainsm.cpp.

References ASSERT_WARN, SPxLPBase< R >::changeLower(), SPxLPBase< R >::changeUpper(), SPxLPBase< R >::colVector(), SPxMainSM::DuplicateColsPS, SPxMainSM::epsZero(), soplex::EQrel(), SPxMainSM::feastol(), SPxMainSM::FIX_DUPLICATE_COL, SPxMainSM::FixBoundsPS, SPxMainSM::fixColumn(), soplex::GErel(), SVectorBase< R >::index(), soplex::infinity, soplex::isNotZero(), soplex::isZero(), soplex::LErel(), SPxLPBase< R >::lower(), SPxMainSM::m_cIdx, SPxMainSM::m_classSetCols, SPxMainSM::m_dupCols, SPxMainSM::m_hist, SPxSimplifier::m_minReduction, SPxSimplifier::m_remCols, SPxSimplifier::m_remNzos, SPxMainSM::m_stat, SPxLPBase< R >::maxObj(), MSG_DEBUG, MSG_INFO2, SPxLPBase< R >::nCols(), soplex::NErel(), SPxLPBase< R >::nRows(), SPxSimplifier::OKAY, SPxLPBase< R >::removeCols(), SPxMainSM::removeEmpty(), SPxLPBase< R >::rowVector(), SVectorBase< R >::size(), soplex::spx_alloc(), soplex::spx_free(), SPxSimplifier::spxout, soplex::SPxQuicksort(), SPxMainSM::SUB_DUPLICATE_COL, SPxSimplifier::UNBOUNDED, SPxLPBase< R >::upper(), and SVectorBase< R >::value().

Referenced by SPxMainSM::simplify().

◆ duplicateRows()

SPxSimplifier::Result duplicateRows	(	SPxLP &	lp,
		bool &	again
	)

private

removes duplicate rows.

Definition at line 3980 of file spxmainsm.cpp.

References ASSERT_WARN, SPxLPBase< R >::changeRange(), SPxLPBase< R >::colVector(), SPxMainSM::DUPLICATE_ROW, SPxMainSM::DuplicateRowsPS, SPxMainSM::epsZero(), soplex::EQrel(), SPxMainSM::feastol(), SVectorBase< R >::index(), SPxSimplifier::INFEASIBLE, soplex::infinity, soplex::isNotZero(), SPxLPBase< R >::lhs(), soplex::LTrel(), SPxMainSM::m_classSetRows, SPxMainSM::m_dupRows, SPxMainSM::m_hist, SPxSimplifier::m_minReduction, SPxSimplifier::m_remNzos, SPxSimplifier::m_remRows, SPxMainSM::m_rIdx, SPxMainSM::m_stat, MSG_DEBUG, MSG_INFO2, SPxLPBase< R >::nCols(), soplex::NErel(), SPxLPBase< R >::nRows(), SPxSimplifier::OKAY, SPxMainSM::removeEmpty(), SPxLPBase< R >::removeRows(), SPxMainSM::removeRowSingleton(), SPxLPBase< R >::rhs(), SPxLPBase< R >::rowVector(), SVectorBase< R >::size(), soplex::spx_alloc(), soplex::spx_free(), SPxSimplifier::spxout, soplex::SPxQuicksort(), and SVectorBase< R >::value().

Referenced by SPxMainSM::simplify().

◆ epsZero()

Real epsZero ( ) const

protected

Definition at line 1395 of file spxmainsm.h.

References SPxMainSM::m_epsilon.

Referenced by SPxMainSM::aggregateVars(), SPxMainSM::duplicateCols(), SPxMainSM::duplicateRows(), SPxMainSM::fixColumn(), SPxMainSM::handleExtremes(), SPxMainSM::removeEmpty(), SPxMainSM::removeRowSingleton(), SPxMainSM::simplifyCols(), SPxMainSM::simplifyRows(), and SPxMainSM::unsimplify().

◆ feastol()

Real feastol ( ) const

protected

Definition at line 1400 of file spxmainsm.h.

References SPxMainSM::m_feastol.

Referenced by SPxMainSM::aggregateVars(), SPxMainSM::checkSolution(), SPxMainSM::duplicateCols(), SPxMainSM::duplicateRows(), SPxMainSM::fixColumn(), SPxMainSM::handleExtremes(), SPxMainSM::multiaggregation(), SPxMainSM::removeEmpty(), SPxMainSM::removeRowSingleton(), SPxMainSM::simplifyCols(), SPxMainSM::simplifyDual(), SPxMainSM::simplifyRows(), and SPxMainSM::trivialHeuristic().

◆ fixColumn()

void fixColumn	(	SPxLP &	lp,
		int	i,
		bool	correctIdx = `true`
	)

private

handles the fixing of a variable. correctIdx is true iff the index mapping has to be updated.

Definition at line 4710 of file spxmainsm.cpp.

References SPxLPBase< R >::changeLhs(), SPxLPBase< R >::changeRhs(), SPxLPBase< R >::colVector(), SPxMainSM::epsZero(), soplex::EQrel(), SPxMainSM::feastol(), SPxMainSM::FixVariablePS, SVectorBase< R >::index(), soplex::infinity, soplex::isNotZero(), soplex::isZero(), SPxLPBase< R >::lhs(), SPxLPBase< R >::lower(), SPxMainSM::m_hist, soplex::maxAbs(), MSG_DEBUG, soplex::NE(), SPxLPBase< R >::rhs(), SVectorBase< R >::size(), soplex::spx_alloc(), SPxSimplifier::spxout, SPxLPBase< R >::upper(), and SVectorBase< R >::value().

Referenced by SPxMainSM::duplicateCols(), SPxMainSM::simplifyCols(), and SPxMainSM::simplifyDual().

◆ getBasis()

virtual void getBasis	(	SPxSolver::VarStatus	rows[],
		SPxSolver::VarStatus	cols[],
		const int	rowsSize = `-1`,
		const int	colsSize = `-1`
	)		const

virtual

get optimal basis.

Implements SPxSimplifier.

Definition at line 1593 of file spxmainsm.h.

References DataArray< T >::size().

◆ getBasisColStatus()

virtual SPxSolver::VarStatus getBasisColStatus ( int j ) const

virtual

gets basis status for a single column.

Implements SPxSimplifier.

Definition at line 1587 of file spxmainsm.h.

◆ getBasisRowStatus()

virtual SPxSolver::VarStatus getBasisRowStatus ( int i ) const

virtual

gets basis status for a single row.

Implements SPxSimplifier.

Definition at line 1581 of file spxmainsm.h.

◆ handleExtremes()

void handleExtremes ( SPxLP & lp )

private

handles extreme values by setting them to zero or infinity.

Definition at line 1510 of file spxmainsm.cpp.

Referenced by SPxMainSM::simplify().

◆ handleRowObjectives()

void handleRowObjectives ( SPxLP & lp )

private

handle row objectives

Definition at line 1493 of file spxmainsm.cpp.

References SPxLPBase< R >::addCol(), SPxLPBase< R >::changeRange(), SPxLPBase< R >::changeRowObj(), SPxLPBase< R >::lhs(), SPxMainSM::m_addedcols, SPxMainSM::m_hist, SPxLPBase< R >::maxRowObj(), SPxLPBase< R >::nCols(), SPxLPBase< R >::nRows(), SPxLPBase< R >::rhs(), SPxLPBase< R >::rowObj(), and soplex::spx_alloc().

Referenced by SPxMainSM::simplify().

◆ isUnsimplified()

virtual bool isUnsimplified ( ) const

virtual

specifies whether an optimal solution has already been unsimplified.

Reimplemented from SPxSimplifier.

Definition at line 1552 of file spxmainsm.h.

References SPxMainSM::m_postsolved.

◆ multiaggregation()

SPxSimplifier::Result multiaggregation	(	SPxLP &	lp,
		bool &	again
	)

private

performs multi-aggregations of variable based upon constraint activitu.

Definition at line 3738 of file spxmainsm.cpp.

References ASSERT_WARN, SPxLPBase< R >::changeElement(), SPxLPBase< R >::changeLhs(), SPxLPBase< R >::changeMaxObj(), SPxLPBase< R >::changeRhs(), SPxLPBase< R >::colVector(), SPxMainSM::computeMinMaxResidualActivity(), SPxMainSM::computeMinMaxValues(), soplex::EQ(), SPxMainSM::feastol(), soplex::GT(), SVectorBase< R >::index(), soplex::infinity, soplex::isNotZero(), soplex::LE(), SPxLPBase< R >::lhs(), SPxLPBase< R >::lower(), soplex::LT(), SPxMainSM::m_hist, SPxSimplifier::m_minReduction, SPxSimplifier::m_remCols, SPxSimplifier::m_remNzos, SPxSimplifier::m_remRows, SPxMainSM::m_stat, SPxLPBase< R >::maxObj(), MSG_DEBUG, MSG_INFO2, SPxMainSM::MULTI_AGG, SPxLPBase< R >::nCols(), SPxLPBase< R >::nRows(), SPxSimplifier::OKAY, SVectorBase< R >::pos(), SPxMainSM::removeCol(), SPxMainSM::removeRow(), SPxLPBase< R >::rhs(), SPxLPBase< R >::rowVector(), SVectorBase< R >::size(), soplex::spx_alloc(), SPxSimplifier::spxout, SPxLPBase< R >::upper(), and SVectorBase< R >::value().

Referenced by SPxMainSM::simplify().

◆ operator=()

SPxMainSM& operator= ( const SPxMainSM & rhs )

◆ opttol()

Real opttol ( ) const

protected

Definition at line 1405 of file spxmainsm.h.

References SPxMainSM::m_opttol.

Referenced by SPxMainSM::simplifyDual().

◆ propagatePseudoobj()

void propagatePseudoobj ( SPxLP & lp )

private

tightens variable bounds by propagating the pseudo objective function value.

Definition at line 1938 of file spxmainsm.cpp.

References SPxLPBase< R >::changeLower(), SPxLPBase< R >::changeUpper(), soplex::EQ(), soplex::GT(), soplex::infinity, SPxLPBase< R >::lower(), soplex::LT(), SPxMainSM::m_cutoffbound, SPxMainSM::m_hist, SPxSimplifier::m_objoffset, SPxMainSM::m_pseudoobj, SPxLPBase< R >::maxObj(), SPxLPBase< R >::nCols(), soplex::spx_alloc(), and SPxLPBase< R >::upper().

Referenced by SPxMainSM::simplify().

◆ removeCol()

void removeCol	(	SPxLP &	lp,
		int	j
	)

private

removes a column in the LP.

Definition at line 1375 of file spxmainsm.h.

References SPxLPBase< R >::nCols(), and SPxLPBase< R >::removeCol().

Referenced by SPxMainSM::aggregateVars(), SPxMainSM::multiaggregation(), SPxMainSM::removeEmpty(), SPxMainSM::simplifyCols(), and SPxMainSM::simplifyDual().

◆ removeEmpty()

SPxSimplifier::Result removeEmpty ( SPxLP & lp )

private

removed empty rows and empty columns.

Definition at line 2000 of file spxmainsm.cpp.

References ASSERT_WARN, SPxLPBase< R >::colVector(), SPxMainSM::EMPTY_COL, SPxMainSM::EMPTY_ROW, SPxMainSM::EmptyConstraintPS, SPxMainSM::epsZero(), SPxMainSM::feastol(), SPxMainSM::FixBoundsPS, SPxMainSM::FixVariablePS, soplex::GT(), SPxSimplifier::INFEASIBLE, soplex::infinity, soplex::isZero(), SPxLPBase< R >::lhs(), SPxLPBase< R >::lower(), soplex::LT(), SPxMainSM::m_hist, SPxSimplifier::m_remCols, SPxSimplifier::m_remRows, SPxMainSM::m_stat, SPxLPBase< R >::maxObj(), MSG_DEBUG, MSG_INFO2, SPxLPBase< R >::nCols(), SPxLPBase< R >::nRows(), SPxSimplifier::OKAY, SPxMainSM::removeCol(), SPxMainSM::removeRow(), SPxLPBase< R >::rhs(), SPxLPBase< R >::rowVector(), SVectorBase< R >::size(), soplex::spx_alloc(), SPxSimplifier::spxout, SPxSimplifier::UNBOUNDED, and SPxLPBase< R >::upper().

Referenced by SPxMainSM::duplicateCols(), and SPxMainSM::duplicateRows().

◆ removeRow()

void removeRow	(	SPxLP &	lp,
		int	i
	)

private

removes a row in the LP.

Definition at line 1369 of file spxmainsm.h.

References SPxLPBase< R >::nRows(), and SPxLPBase< R >::removeRow().

Referenced by SPxMainSM::aggregateVars(), SPxMainSM::handleExtremes(), SPxMainSM::multiaggregation(), SPxMainSM::removeEmpty(), SPxMainSM::removeRowSingleton(), SPxMainSM::simplifyCols(), SPxMainSM::simplifyDual(), and SPxMainSM::simplifyRows().

◆ removeRowSingleton()

SPxSimplifier::Result removeRowSingleton	(	SPxLP &	lp,
		const SVector &	row,
		int &	i
	)

private

◆ result()

virtual Result result ( ) const

virtual

returns result status of the simplification

Implements SPxSimplifier.

Definition at line 1546 of file spxmainsm.h.

References SPxMainSM::m_result.

◆ rIdx()

int rIdx ( int i ) const

private

returns for a given row index of the (reduced) LP the corresponding row index in the unsimplified LP.

Definition at line 1381 of file spxmainsm.h.

Referenced by SPxMainSM::FreeZeroObjVariablePS::execute(), and SPxMainSM::DuplicateRowsPS::execute().

◆ simplify() [1/2]

virtual Result simplify	(	SPxLP &	lp,
		Real	eps,
		Real	delta
	)

virtual

simplify SPxLP lp with identical primal and dual feasibility tolerance.

Implements SPxSimplifier.

Definition at line 1534 of file spxmainsm.h.

References SPxMainSM::PostStep::eps(), and SPxMainSM::unsimplify().

◆ simplify() [2/2]

SPxSimplifier::Result simplify	(	SPxLP &	lp,
		Real	eps,
		Real	ftol,
		Real	otol,
		bool	keepbounds = `false`
	)

virtual

simplify SPxLP lp with independent primal and dual feasibility tolerance.

Implements SPxSimplifier.

Definition at line 4788 of file spxmainsm.cpp.

References SPxMainSM::AGGREGATION, SPxMainSM::DOMINATED_COL, SPxMainSM::DOUBLETON_ROW, SPxMainSM::DUPLICATE_ROW, SPxMainSM::duplicateCols(), SPxMainSM::duplicateRows(), SPxMainSM::EMPTY_COL, SPxMainSM::EMPTY_ROW, SPxMainSM::PostStep::eps(), soplex::EQ(), SPxMainSM::FIX_COL, SPxMainSM::FIX_DUPLICATE_COL, SPxMainSM::FORCE_ROW, SPxMainSM::FREE_ROW, SPxMainSM::FREE_SINGLETON_COL, SPxMainSM::FREE_ZOBJ_COL, SPxMainSM::handleExtremes(), SPxMainSM::handleRowObjectives(), soplex::infinity, SPxLPBase< R >::lhs(), SPxLPBase< R >::lower(), SPxMainSM::m_addedcols, SPxMainSM::m_cBasisStat, SPxSimplifier::m_chgBnds, SPxSimplifier::m_chgLRhs, SPxMainSM::m_cIdx, SPxMainSM::m_classSetCols, SPxMainSM::m_classSetRows, SPxMainSM::m_cutoffbound, SPxMainSM::m_dual, SPxMainSM::m_dupCols, SPxMainSM::m_dupRows, SPxMainSM::m_epsilon, SPxMainSM::m_feastol, SPxMainSM::m_hist, SPxMainSM::m_keepbounds, SPxSimplifier::m_keptBnds, SPxSimplifier::m_keptLRhs, SPxSimplifier::m_objoffset, SPxMainSM::m_opttol, SPxMainSM::m_postsolved, SPxMainSM::m_prim, SPxMainSM::m_pseudoobj, SPxMainSM::m_rBasisStat, SPxMainSM::m_redCost, SPxSimplifier::m_remCols, SPxSimplifier::m_remNzos, SPxSimplifier::m_remRows, SPxMainSM::m_result, SPxMainSM::m_rIdx, SPxMainSM::m_slack, SPxMainSM::m_stat, SPxMainSM::m_thesense, SPxSimplifier::m_timeUsed, MSG_INFO1, MSG_INFO2, MSG_INFO3, SPxMainSM::MULTI_AGG, SPxMainSM::multiaggregation(), SPxLPBase< R >::nCols(), SPxLPBase< R >::nNzos(), SPxLPBase< R >::nRows(), SPxSimplifier::OKAY, SPxMainSM::propagatePseudoobj(), DVectorBase< R >::reDim(), Timer::reset(), DataArray< T >::reSize(), SPxLPBase< R >::rhs(), SPxMainSM::simplifyCols(), SPxMainSM::simplifyDual(), SPxMainSM::simplifyRows(), SPxMainSM::SINGLETON_ROW, DataArray< T >::size(), soplex::spx_free(), SPxSimplifier::spxout, SPxLPBase< R >::spxout, SPxLPBase< R >::spxSense(), Timer::start(), Timer::stop(), SPxMainSM::SUB_DUPLICATE_COL, SPxMainSM::trivialHeuristic(), SPxLPBase< R >::upper(), SPxSimplifier::VANISHED, SPxMainSM::WEAKLY_DOMINATED_COL, and SPxMainSM::ZOBJ_SINGLETON_COL.

◆ simplifyCols()

SPxSimplifier::Result simplifyCols	(	SPxLP &	lp,
		bool &	again
	)

private

performs simplification steps on the columns of the LP.

Definition at line 2951 of file spxmainsm.cpp.

References ASSERT_WARN, SPxLPBase< R >::changeBounds(), SPxLPBase< R >::changeLower(), SPxLPBase< R >::changeObj(), SPxLPBase< R >::changeRange(), SPxLPBase< R >::changeUpper(), SPxLPBase< R >::colVector(), SPxMainSM::DOUBLETON_ROW, SPxMainSM::DoubletonEquationPS, SPxMainSM::EMPTY_COL, SPxMainSM::epsZero(), soplex::EQrel(), SPxMainSM::feastol(), SPxMainSM::FIX_COL, SPxMainSM::FixBoundsPS, SPxMainSM::fixColumn(), SPxMainSM::FixVariablePS, SPxMainSM::FREE_ROW, SPxMainSM::FREE_SINGLETON_COL, SPxMainSM::FREE_ZOBJ_COL, SPxMainSM::FreeColSingletonPS, SPxMainSM::FreeConstraintPS, SPxMainSM::FreeZeroObjVariablePS, soplex::GT(), soplex::GTrel(), SVectorBase< R >::index(), SPxSimplifier::INFEASIBLE, soplex::infinity, soplex::isNotZero(), soplex::isZero(), SPxLPBase< R >::lhs(), SPxLPBase< R >::lower(), soplex::LT(), soplex::LTrel(), SPxSimplifier::m_chgBnds, SPxMainSM::m_hist, SPxSimplifier::m_minReduction, SPxSimplifier::m_remCols, SPxSimplifier::m_remNzos, SPxSimplifier::m_remRows, SPxMainSM::m_stat, soplex::maxAbs(), SPxLPBase< R >::maxObj(), MSG_DEBUG, MSG_INFO2, SPxLPBase< R >::nCols(), soplex::NErel(), SPxLPBase< R >::nRows(), SPxLPBase< R >::obj(), SPxSimplifier::OKAY, SPxMainSM::removeCol(), SPxMainSM::removeRow(), SPxLPBase< R >::rhs(), SPxLPBase< R >::rowVector(), SVectorBase< R >::size(), soplex::spx_alloc(), SPxSimplifier::spxout, soplex::SPxQuicksort(), SPxSimplifier::UNBOUNDED, SPxLPBase< R >::upper(), SVectorBase< R >::value(), SPxMainSM::ZeroObjColSingletonPS, and SPxMainSM::ZOBJ_SINGLETON_COL.

Referenced by SPxMainSM::simplify().

◆ simplifyDual()

SPxSimplifier::Result simplifyDual	(	SPxLP &	lp,
		bool &	again
	)

private

performs simplification steps on the LP based on dual concepts.

Definition at line 3480 of file spxmainsm.cpp.

References ASSERT_WARN, SPxLPBase< R >::changeLower(), SPxLPBase< R >::changeUpper(), SPxLPBase< R >::colVector(), SPxMainSM::DOMINATED_COL, SPxSimplifier::DUAL_INFEASIBLE, soplex::EQrel(), SPxMainSM::feastol(), SPxMainSM::FIX_COL, SPxMainSM::FixBoundsPS, SPxMainSM::fixColumn(), SPxMainSM::FREE_ROW, SPxMainSM::FreeConstraintPS, soplex::GTrel(), SVectorBase< R >::index(), soplex::infinity, soplex::isNotZero(), SPxLPBase< R >::lhs(), SPxLPBase< R >::lower(), soplex::LTrel(), SPxMainSM::m_hist, SPxSimplifier::m_minReduction, SPxSimplifier::m_remCols, SPxSimplifier::m_remNzos, SPxSimplifier::m_remRows, SPxMainSM::m_stat, SPxLPBase< R >::maxObj(), MSG_DEBUG, MSG_INFO2, SPxLPBase< R >::nCols(), SPxLPBase< R >::nRows(), SPxSimplifier::OKAY, SPxMainSM::opttol(), SPxMainSM::removeCol(), SPxMainSM::removeRow(), SPxLPBase< R >::rhs(), SPxLPBase< R >::rowVector(), SVectorBase< R >::size(), soplex::spx_alloc(), SPxSimplifier::spxout, SPxSimplifier::UNBOUNDED, SPxLPBase< R >::upper(), SVectorBase< R >::value(), and SPxMainSM::WEAKLY_DOMINATED_COL.

Referenced by SPxMainSM::simplify().

◆ simplifyRows()

SPxSimplifier::Result simplifyRows	(	SPxLP &	lp,
		bool &	again
	)

private

performs simplification steps on the rows of the LP.

Definition at line 2405 of file spxmainsm.cpp.

References SPxMainSM::aggregateVars(), ASSERT_WARN, SPxLPBase< R >::changeLhs(), SPxLPBase< R >::changeLower(), SPxLPBase< R >::changeRhs(), SPxLPBase< R >::changeUpper(), SPxMainSM::EMPTY_ROW, SPxMainSM::EmptyConstraintPS, Param::epsilon(), SPxMainSM::epsZero(), soplex::EQrel(), SPxMainSM::feastol(), SPxMainSM::FORCE_ROW, SPxMainSM::ForceConstraintPS, SPxMainSM::FREE_ROW, SPxMainSM::FreeConstraintPS, soplex::GErel(), soplex::GT(), soplex::GTrel(), SVectorBase< R >::index(), SPxSimplifier::INFEASIBLE, soplex::infinity, soplex::isNotZero(), soplex::isZero(), soplex::LErel(), SPxLPBase< R >::lhs(), SPxLPBase< R >::lower(), soplex::LT(), soplex::LTrel(), SPxSimplifier::m_chgBnds, SPxSimplifier::m_chgLRhs, SPxMainSM::m_epsilon, SPxMainSM::m_hist, SPxMainSM::m_keepbounds, SPxSimplifier::m_keptBnds, SPxSimplifier::m_keptLRhs, SPxSimplifier::m_minReduction, SPxSimplifier::m_remNzos, SPxSimplifier::m_remRows, SPxMainSM::m_stat, soplex::maxAbs(), MSG_DEBUG, MSG_INFO2, MSG_WARNING, soplex::NErel(), SPxLPBase< R >::nRows(), SPxSimplifier::OKAY, SPxMainSM::removeRow(), SPxMainSM::removeRowSingleton(), SPxLPBase< R >::rhs(), SPxLPBase< R >::rowVector(), SVectorBase< R >::size(), soplex::spx_alloc(), soplex::spxAbs(), SPxSimplifier::spxout, SPxLPBase< R >::upper(), and SVectorBase< R >::value().

Referenced by SPxMainSM::simplify().

◆ trivialHeuristic()

void trivialHeuristic ( SPxLP & lp )

private

tries to find good lower bound solutions by applying some trivial heuristics

Definition at line 1799 of file spxmainsm.cpp.

References ASSERT_WARN, SPxMainSM::checkSolution(), SPxLPBase< R >::colVector(), SPxMainSM::feastol(), soplex::GE(), soplex::GT(), SVectorBase< R >::index(), soplex::infinity, soplex::isNotZero(), soplex::LE(), SPxLPBase< R >::lhs(), SPxLPBase< R >::lower(), soplex::LT(), SPxMainSM::m_cutoffbound, SPxSimplifier::m_objoffset, MAXIMUM, SPxLPBase< R >::maxObj(), MINIMUM, SPxLPBase< R >::nCols(), SPxLPBase< R >::rhs(), SVectorBase< R >::size(), SPxLPBase< R >::upper(), and SVectorBase< R >::value().

Referenced by SPxMainSM::simplify().

◆ unsimplifiedDual()

virtual const Vector& unsimplifiedDual ( )

virtual

returns a reference to the unsimplified dual solution.

Implements SPxSimplifier.

Definition at line 1563 of file spxmainsm.h.

References SPxMainSM::m_dual.

◆ unsimplifiedPrimal()

virtual const Vector& unsimplifiedPrimal ( )

virtual

returns a reference to the unsimplified primal solution.

Implements SPxSimplifier.

Definition at line 1557 of file spxmainsm.h.

References SPxMainSM::m_prim.

◆ unsimplifiedRedCost()

virtual const Vector& unsimplifiedRedCost ( )

virtual

returns a reference to the unsimplified reduced costs.

Implements SPxSimplifier.

Definition at line 1575 of file spxmainsm.h.

References SPxMainSM::m_redCost.

◆ unsimplifiedSlacks()

virtual const Vector& unsimplifiedSlacks ( )

virtual

returns a reference to the unsimplified slack values.

Implements SPxSimplifier.

Definition at line 1569 of file spxmainsm.h.

References SPxMainSM::m_slack.

◆ unsimplify()

void unsimplify	(	const Vector &	x,
		const Vector &	y,
		const Vector &	s,
		const Vector &	r,
		const SPxSolver::VarStatus	rows[],
		const SPxSolver::VarStatus	cols[],
		bool	isOptimal = `true`
	)