Linear programs. More...

#include <ogdf/lib/abacus/lp.h>

Inheritance diagram for abacus::LP:

Public Types
enum	METHOD { Primal , Dual , BarrierAndCrossover , BarrierNoCrossover , Approximate }
	The solution method for the linear program. More...

enum	OPTSTAT { Optimal , Unoptimized , Error , Feasible , Infeasible , Unbounded , LimitReached }
	The optimization status of the linear program. More...

enum	SOLSTAT { Available , Missing }
	Describes if parts of the solution like x-values, reduced costs, etc. are available. More...

Public Member Functions
	LP (Master *master)
	Creates a linear program.

virtual	~LP ()
	The destructor.

void	addCols (ArrayBuffer< Column * > &newCols)
	Adds columns to the linear program.

void	addRows (ArrayBuffer< Row * > &newRows)
	Adds rows to the linear program.

virtual double	barXVal (int i) const

SOLSTAT	barXValStatus () const

SOLSTAT	basisStatus () const

virtual void	changeLBound (int i, double newLb)
	Changes the lower bound of a single column.

void	changeRhs (Array< double > &newRhs)
	Changes the complete right hand side of the linear program.

virtual void	changeUBound (int i, double newUb)
	Changes the upper bound of a single column.

void	colRealloc (int newSize)
	Performs a reallocation of the column space of the linear program.

virtual int	getInfeas (int &infeasRow, int &infeasCol, double *bInvRow) const
	Can be called if the last linear program has been solved with the dual simplex method and is infeasible and all inactive variables price out correctly.

int	getSimplexIterationLimit (int &limit) const

virtual bool	infeasible () const

void	initialize (OptSense sense, int nRow, int maxRow, int nCol, int maxCol, Array< double > &obj, Array< double > &lBound, Array< double > &uBound, Array< Row * > &rows)
	Loads the linear program defined by its arguments.

void	initialize (OptSense sense, int nRow, int maxRow, int nCol, int maxCol, Array< double > &obj, Array< double > &lBound, Array< double > &uBound, Array< Row * > &rows, Array< LPVARSTAT::STATUS > &lpVarStat, Array< SlackStat::STATUS > &slackStat)
	This version of the function initialize() performs like its previous version, but also initializes the basis with the arguments:

double	lBound (int i) const

virtual void	loadBasis (Array< LPVARSTAT::STATUS > &lpVarStat, Array< SlackStat::STATUS > &slackStat)
	Loads a new basis for the linear program.

ogdf::StopwatchCPU *	lpSolverTime ()

virtual LPVARSTAT::STATUS	lpVarStat (int i) const

int	maxCol () const

int	maxRow () const

int	nCol () const

int	nnz () const

int	nOpt () const

int	nRow () const

double	obj (int i) const

virtual OPTSTAT	optimize (METHOD method)
	Performs the optimization of the linear program.

virtual int	pivotSlackVariableIn (ArrayBuffer< int > &rows)
	Pivots the slack variables stored in the buffer rows into the basis.

virtual double	reco (int i) const

SOLSTAT	recoStatus () const

void	remCols (ArrayBuffer< int > &cols)
	Removes columns from the linear program.

void	remRows (ArrayBuffer< int > &ind)
	Removes rows of the linear program.

double	rhs (int i) const

void	row (int i, Row &r) const

void	rowRealloc (int newSize)
	Performs a reallocation of the row space of the linear program.

OptSense	sense () const

void	sense (const OptSense &newSense)

int	setSimplexIterationLimit (int limit)
	Changes the iteration limit of the Simplex algorithm.

virtual double	slack (int c) const

virtual SlackStat::STATUS	slackStat (int i) const

SOLSTAT	slackStatus () const

double	uBound (int i) const

virtual double	value () const

int	writeBasisMatrix (const char *fileName)
	Writes the complete basis of an optimal linear program to a file.

virtual double	xVal (int i) const

SOLSTAT	xValStatus () const

virtual double	yVal (int c) const

SOLSTAT	yValStatus () const

Public Member Functions inherited from abacus::AbacusRoot
virtual	~AbacusRoot ()
	The destructor.

Protected Member Functions
virtual void	_addCols (ArrayBuffer< Column * > &newCols)=0
	The pure virtual function _addCols() must be defined by the used LP-solver and should add the columns newCols to the LP.

virtual void	_addRows (ArrayBuffer< Row * > &newRows)=0
	The pure virtual function _addRows() must be defined by the used LP-solver and should add the rows given in the buffer newRows to the LP.

virtual OPTSTAT	_approx ()=0
	The pure virtual function _approx() must be defined by the used LP-solver and should call the approximative method of the used LP-solver.

virtual OPTSTAT	_barrier (bool doCrossover)=0
	The pure virtual function _barrier() must be defined by the used LP-solver and should call the barrier method of the used LP-solver.

virtual double	_barXVal (int i) const =0

virtual void	_changeLBound (int i, double newLb)=0
	The pure virtual function _changeLBound() must be defined by the used LP-solver and should set the lower bound of variable i to newLb.

virtual void	_changeRhs (Array< double > &newRhs)=0
	The pure virtual function _changeRhs() must be defined by the used LP-solver and should set the right hand side of the constraint matrix of the LP to newRhs.

virtual void	_changeUBound (int i, double newUb)=0
	The pure virtual function _changeLBound() must be defined by the used LP-solver and should set the upper bound of variable i to newUb.

virtual void	_colRealloc (int newSize)=0
	The pure virtual function _colRealloc() must be defined by the used LP-solver and should reallocate its memory such that up to newSize columns can be handled.

virtual OPTSTAT	_dualSimplex ()=0
	The pure virtual function _dualSimplex() must be defined by the used LP-solver and should call the dual simplex method of the used LP-solver.

virtual int	_getInfeas (int &infeasRow, int &infeasCol, double *bInvRow) const =0
	The pure virtual function _getInfeas() must be defined by the used LP-solver and can be called if the last linear program has been solved with the dual simplex method and is infeasible.

virtual int	_getSimplexIterationLimit (int &limit) const =0
	The function getSimplexIterationLimit() retrieves the value of the iteration limit of the simplex algorithm.

virtual void	_initialize (OptSense sense, int nRow, int maxRow, int nCol, int maxCol, Array< double > &obj, Array< double > &lBound, Array< double > &uBound, Array< Row * > &rows)=0
	The pure virtual function _initialize() must be defined by the used LP-solver and should initialize the LP-solver with.

virtual double	_lBound (int i) const =0
	The pure virtual function _lBound() must be defined by the used LP-solver and return the lower bound of variable i.

virtual void	_loadBasis (Array< LPVARSTAT::STATUS > &lpVarStat, Array< SlackStat::STATUS > &slackStat)=0
	This pure virtual function should load a basis into the LP-solver.

virtual LPVARSTAT::STATUS	_lpVarStat (int i) const =0
	The pure virtual function _lpVarStat() must be defined by the used LP-solver and should return the status of the variable i in the LP-solution.

virtual int	_maxCol () const =0
	The pure virtual function _maxCol() must be defined by the the used LP-solver and return the maximal number of columns.

virtual int	_maxRow () const =0
	The pure virtual function _maxRow() must be defined by the used LP-solver and return the maximal number of rows.

virtual int	_nCol () const =0
	The pure virtual function _nCol() must be defined by the used LP-solver and return the number of columns.

virtual int	_nnz () const =0
	The pure virtual function _nnz() must be defined by the used LP-solver and return the number of nonzero elements of the constraint matrix not including the right hand side and the bounds of the variables.

virtual int	_nRow () const =0
	The pure virtual function _nRow() must be defined by the used LP-solver and return the number of rows of the problem.

virtual double	_obj (int i) const =0
	The pure virtual function _obj() must be defined by the used LP-solver and return the objective function coefficient of variable i.

virtual int	_pivotSlackVariableIn (ArrayBuffer< int > &rows)=0
	The function pivotSlackVariableIn() pivots the slack variables stored in the buffer rows into the basis.

virtual OPTSTAT	_primalSimplex ()=0
	The pure virtual function _primalSimplex() must be defined by the used LP-solver and should call the primal simplex method of the used LP-solver.

virtual double	_reco (int i) const =0
	The pure virtual function _reco() must be defined by the used LP-solver and should return the reduced cost of variable i.

virtual void	_remCols (ArrayBuffer< int > &vars)=0
	The pure virtual function _remCols() must be defined by the used LP-solver and should remove the columns with numbers given in vars from the LP.

virtual void	_remRows (ArrayBuffer< int > &ind)=0
	The pure virtual function _remRows() must be defined by the used LP-solver and should remove the rows with numbers given in the buffer ind from the LP-solver.

virtual double	_rhs (int i) const =0
	The pure virtual function _rhs() must be defined by the used LP-solver and return the right hand side of constraint i.

virtual void	_row (int i, Row &r) const =0
	The pure virtual function _row() must be defined by the used LP-solver and store the i-th row of the problem in the row r.

virtual void	_rowRealloc (int newSize)=0
	The pure virtual function _rowRealloc() must be defined in the used LP-solver and should reallocate its memory such that up to newSize rows can be handled.

virtual OptSense	_sense () const =0
	The pure virtual function _sense() must be defined by the used LP-solver and return the sense of the optimization.

virtual void	_sense (const OptSense &newSense)=0

virtual int	_setSimplexIterationLimit (int limit)=0
	The function setSimplexIterationLimit() changes the iteration limit of the Simplex algorithm.

virtual double	_slack (int i) const =0
	The pure virtual function _slack() must be defined by the used LP-solver and should return the value of the slack variable i.

virtual SlackStat::STATUS	_slackStat (int i) const =0
	The pure virtual function _slackStat() must be defined by the used LP-solver and should return the status of the slack variable i in the LP-solution.

virtual double	_uBound (int i) const =0
	The pure virtual function _uBound() must be defined by the used LP-solver and return the upper bound of variable i.

virtual double	_value () const =0
	The pure virtual function _value() must be defined by the used LP-solver and should return the optimum value of the linear program after it has been solved.

virtual double	_xVal (int i) const =0
	The pure virtual function _xVal() must be defined by the used LP-solver and should return the value of variable i in the LP-solution.

virtual double	_yVal (int i) const =0
	The pure virtual function _yVal() must be defined by the used LP-solver and should return the value of the dual variable of the constraint i.

void	colRangeCheck (int i) const
	Terminates the program if there is no column with index i.

void	colsNnz (int nRow, Array< Row * > &rows, Array< int > &nnz)
	Computes the number of nonzero elements in each column of a given set of rows.

void	rowRangeCheck (int r) const
	Terminates the program if there is no row with index r.

void	rows2cols (int nRow, Array< Row * > &rows, Array< SparVec * > &cols)
	Computes the columnwise representation of the row matrix.

Protected Attributes
SOLSTAT	barXValStatus_

SOLSTAT	basisStatus_
	This member becomes Available if the status of the variables and the slack variables of the optimal solution can be accessed with the functions lpVarStat() and slackStat(), otherwise it has the value Missing.

ogdf::StopwatchCPU	lpSolverTime_

Master *	master_
	A pointer to the corresponding master of the optimization.

int	nOpt_
	The number of optimizations of the linear program.

OPTSTAT	optStat_
	The status of the linear program.

SOLSTAT	recoStatus_
	This member becomes Available if the reduced costs of the optimal solution can be accessed with the function reco(), otherwise it has the value Missing.

SOLSTAT	slackStatus_
	This member becomes Available if the values of the slack variables of the optimal solution can be accessed with the function slack(), otherwise it has the value Missing.

SOLSTAT	xValStatus_
	This member becomes Available if the \(x\)-values of the optimal solution can be accessed with the function xVal(), otherwise it has the value Missing.

SOLSTAT	yValStatus_
	This member becomes Available if the values of the dual variables of the optimal solution can be accessed with the function yVal(), otherwise it has the value Missing/.

Private Member Functions
	LP (const LP &rhs)

void	initPostOpt ()
	Resets the optimization status and the availability statuses of the solution.

const LP &	operator= (const LP &rhs)

Friends
std::ostream &	operator<< (std::ostream &out, const LP &rhs)
	The output operator writes the objective function, followed by the constraints, the bounds on the columns and the solution values (if available) to an output stream.

Additional Inherited Members
Static Public Member Functions inherited from abacus::AbacusRoot
static bool	ascii2bool (const string &str)
	Converts the string str to a boolean value.

static bool	endsWith (const string &str, const string &end)
	Returns true if str ends with end, false otherwise.

static double	fracPart (double x)
	Returns the absolute value of the fractional part of x.

static const char *	onOff (bool value)
	Converts a boolean variable to the strings "on" and "off".

Detailed Description

Linear programs.

The following section provides a generic interface class to linear programs, from which we will derive further classes both for the solution of LP-relaxations (LpSub) with a linear-programming based branch-and-bound algorithm and for interfaces to LP-solvers (OsiIF).

The framework should be very flexible in the use of different LP-solvers. Therefore, we implement in the class LP a very general interface to the linear program. All functions of the framework communicate with the linear program only by the public functions of the class LP.

The public functions call pure virtual functions starting with the prefix _, which have to be implemented in the derived class for each specific LP-solver.

Linear programs cannot only be used for solving the LP-relaxation within the branch-and-cut algorithm. There are also techniques in integer programming where linear programming is used for generating cutting planes and for applying heuristics. Therefore, we design the class LP that it can be used very generally.

Definition at line 70 of file lp.h.

Member Enumeration Documentation

◆ METHOD

enum abacus::LP::METHOD

The solution method for the linear program.

Enumerator
Primal	The primal simplex method.
Dual	The dual simplex method.
BarrierAndCrossover	The barrier method followed by a crossover to a basis.
BarrierNoCrossover	The barrier method without crossover.
Approximate	An approximative solver.

Definition at line 93 of file lp.h.

◆ OPTSTAT

enum abacus::LP::OPTSTAT

The optimization status of the linear program.

Enumerator
Optimal	The optimal solution has been computed.
Unoptimized	Unoptimized Optimization is still required, this is also the case for reoptimization.
Error	An error has happened during optimization.
Feasible	A primal feasible solution for the linear program, but not the optimal solution has been found.
Infeasible	The linear program is primal infeasible.
Unbounded	The linear program is unbounded.
LimitReached	The iteration limit was reached while optimizing.

Definition at line 74 of file lp.h.

◆ SOLSTAT

enum abacus::LP::SOLSTAT

Describes if parts of the solution like x-values, reduced costs, etc. are available.

Enumerator
Available	The part of the solution is available.
Missing	Missing The part of the solution is missing.

Definition at line 87 of file lp.h.

Constructor & Destructor Documentation

◆ LP() [1/2]

abacus::LP::LP ( Master * master )

inline

Creates a linear program.

Parameters

master A pointer to the corresponding master of the optimization.

Definition at line 105 of file lp.h.

◆ ~LP()

virtual abacus::LP::~LP ( )

inlinevirtual

The destructor.

Definition at line 118 of file lp.h.

◆ LP() [2/2]

abacus::LP::LP ( const LP & rhs )

private

Member Function Documentation

◆ _addCols()

virtual void abacus::LP::_addCols ( ArrayBuffer< Column * > & newCols )

protectedpure virtual

The pure virtual function _addCols() must be defined by the used LP-solver and should add the columns newCols to the LP.

Implemented in abacus::OsiIF.

◆ _addRows()

virtual void abacus::LP::_addRows ( ArrayBuffer< Row * > & newRows )

protectedpure virtual

The pure virtual function _addRows() must be defined by the used LP-solver and should add the rows given in the buffer newRows to the LP.

Implemented in abacus::OsiIF.

◆ _approx()

virtual OPTSTAT abacus::LP::_approx ( )

protectedpure virtual

The pure virtual function _approx() must be defined by the used LP-solver and should call the approximative method of the used LP-solver.

Implemented in abacus::OsiIF.

◆ _barrier()

virtual OPTSTAT abacus::LP::_barrier ( bool doCrossover )

protectedpure virtual

The pure virtual function _barrier() must be defined by the used LP-solver and should call the barrier method of the used LP-solver.

Implemented in abacus::OsiIF.

◆ _barXVal()

virtual double abacus::LP::_barXVal ( int i ) const

protectedpure virtual

Implemented in abacus::OsiIF.

◆ _changeLBound()

virtual void abacus::LP::_changeLBound	(	int	i,
		double	newLb
	)

protectedpure virtual

The pure virtual function _changeLBound() must be defined by the used LP-solver and should set the lower bound of variable i to newLb.

Implemented in abacus::OsiIF.

◆ _changeRhs()

virtual void abacus::LP::_changeRhs ( Array< double > & newRhs )

protectedpure virtual

The pure virtual function _changeRhs() must be defined by the used LP-solver and should set the right hand side of the constraint matrix of the LP to newRhs.

Implemented in abacus::OsiIF.

◆ _changeUBound()

virtual void abacus::LP::_changeUBound	(	int	i,
		double	newUb
	)

protectedpure virtual

The pure virtual function _changeLBound() must be defined by the used LP-solver and should set the upper bound of variable i to newUb.

Implemented in abacus::OsiIF.

◆ _colRealloc()

virtual void abacus::LP::_colRealloc ( int newSize )

protectedpure virtual

The pure virtual function _colRealloc() must be defined by the used LP-solver and should reallocate its memory such that up to newSize columns can be handled.

Implemented in abacus::OsiIF.

◆ _dualSimplex()

virtual OPTSTAT abacus::LP::_dualSimplex ( )

protectedpure virtual

The pure virtual function _dualSimplex() must be defined by the used LP-solver and should call the dual simplex method of the used LP-solver.

Implemented in abacus::OsiIF.

◆ _getInfeas()

virtual int abacus::LP::_getInfeas	(	int &	infeasRow,
		int &	infeasCol,
		double *	bInvRow
	)		const

protectedpure virtual

The pure virtual function _getInfeas() must be defined by the used LP-solver and can be called if the last linear program has been solved with the dual simplex method and is infeasible.

In this case it should compute the infeasible basic variable or constraint and the corresponding row bInvRow of the basis inverse. Either infeasRow or infeasCol is nonnegative. The nonnegative argument is an infeasible row or column, respectively.

Returns: 0 if it is successful; 1 otherwise.

Implemented in abacus::OsiIF.

◆ _getSimplexIterationLimit()

virtual int abacus::LP::_getSimplexIterationLimit ( int & limit ) const

protectedpure virtual

The function getSimplexIterationLimit() retrieves the value of the iteration limit of the simplex algorithm.

Returns: 0 If the iteration limit could be get,; 1 otherwise.

Parameters

limit Stores the value of the iteration limit if the function returns 0.

Implemented in abacus::OsiIF.

◆ _initialize()

virtual void abacus::LP::_initialize	(	OptSense	sense,
		int	nRow,
		int	maxRow,
		int	nCol,
		int	maxCol,
		Array< double > &	obj,
		Array< double > &	lBound,
		Array< double > &	uBound,
		Array< Row * > &	rows
	)

protectedpure virtual

The pure virtual function _initialize() must be defined by the used LP-solver and should initialize the LP-solver with.

Parameters

sense	The sense of the optimization.
nRow	The number of rows.
maxRow	The maximal number of rows.
nCol	The number of columns.
maxCol	The maximal number of columns.
obj	An array with the objective functions coefficients.
lBound	An array with the lower bounds of the variables.
uBound	An array with the upper bounds of the variables.
rows	An array storing the constraint matrix in row format.

Implemented in abacus::OsiIF.

◆ _lBound()

virtual double abacus::LP::_lBound ( int i ) const

protectedpure virtual

The pure virtual function _lBound() must be defined by the used LP-solver and return the lower bound of variable i.

Implemented in abacus::OsiIF.

◆ _loadBasis()

virtual void abacus::LP::_loadBasis	(	Array< LPVARSTAT::STATUS > &	lpVarStat,
		Array< SlackStat::STATUS > &	slackStat
	)

protectedpure virtual

This pure virtual function should load a basis into the LP-solver.

Parameters

lpVarStat	An array storing the status of the variables.
slackStat	An array storing the status of the slack variables.

Implemented in abacus::OsiIF.

◆ _lpVarStat()

virtual LPVARSTAT::STATUS abacus::LP::_lpVarStat ( int i ) const

protectedpure virtual

The pure virtual function _lpVarStat() must be defined by the used LP-solver and should return the status of the variable i in the LP-solution.

Implemented in abacus::OsiIF.

◆ _maxCol()

virtual int abacus::LP::_maxCol ( ) const

protectedpure virtual

The pure virtual function _maxCol() must be defined by the the used LP-solver and return the maximal number of columns.

Implemented in abacus::OsiIF.

◆ _maxRow()

virtual int abacus::LP::_maxRow ( ) const

protectedpure virtual

The pure virtual function _maxRow() must be defined by the used LP-solver and return the maximal number of rows.

Implemented in abacus::OsiIF.

◆ _nCol()

virtual int abacus::LP::_nCol ( ) const

protectedpure virtual

The pure virtual function _nCol() must be defined by the used LP-solver and return the number of columns.

Implemented in abacus::OsiIF.

◆ _nnz()

virtual int abacus::LP::_nnz ( ) const

protectedpure virtual

The pure virtual function _nnz() must be defined by the used LP-solver and return the number of nonzero elements of the constraint matrix not including the right hand side and the bounds of the variables.

Implemented in abacus::OsiIF.

◆ _nRow()

virtual int abacus::LP::_nRow ( ) const

protectedpure virtual

The pure virtual function _nRow() must be defined by the used LP-solver and return the number of rows of the problem.

Implemented in abacus::OsiIF.

◆ _obj()

virtual double abacus::LP::_obj ( int i ) const

protectedpure virtual

The pure virtual function _obj() must be defined by the used LP-solver and return the objective function coefficient of variable i.

Implemented in abacus::OsiIF.

◆ _pivotSlackVariableIn()

virtual int abacus::LP::_pivotSlackVariableIn ( ArrayBuffer< int > & rows )

protectedpure virtual

The function pivotSlackVariableIn() pivots the slack variables stored in the buffer rows into the basis.

Returns: 0 All variables could be pivoted in,; 1 otherwise.

Parameters

rows	The numbers of the slack variables that should be pivoted in.

Implemented in abacus::OsiIF.

◆ _primalSimplex()

virtual OPTSTAT abacus::LP::_primalSimplex ( )

protectedpure virtual

The pure virtual function _primalSimplex() must be defined by the used LP-solver and should call the primal simplex method of the used LP-solver.

Implemented in abacus::OsiIF.

◆ _reco()

virtual double abacus::LP::_reco ( int i ) const

protectedpure virtual

The pure virtual function _reco() must be defined by the used LP-solver and should return the reduced cost of variable i.

Implemented in abacus::OsiIF.

◆ _remCols()

virtual void abacus::LP::_remCols ( ArrayBuffer< int > & vars )

protectedpure virtual

The pure virtual function _remCols() must be defined by the used LP-solver and should remove the columns with numbers given in vars from the LP.

Implemented in abacus::OsiIF.

◆ _remRows()

virtual void abacus::LP::_remRows ( ArrayBuffer< int > & ind )

protectedpure virtual

The pure virtual function _remRows() must be defined by the used LP-solver and should remove the rows with numbers given in the buffer ind from the LP-solver.

Implemented in abacus::OsiIF.

◆ _rhs()

virtual double abacus::LP::_rhs ( int i ) const

protectedpure virtual

The pure virtual function _rhs() must be defined by the used LP-solver and return the right hand side of constraint i.

Implemented in abacus::OsiIF.

◆ _row()

virtual void abacus::LP::_row	(	int	i,
		Row &	r
	)		const

protectedpure virtual

The pure virtual function _row() must be defined by the used LP-solver and store the i-th row of the problem in the row r.

Implemented in abacus::OsiIF.

◆ _rowRealloc()

virtual void abacus::LP::_rowRealloc ( int newSize )

protectedpure virtual

The pure virtual function _rowRealloc() must be defined in the used LP-solver and should reallocate its memory such that up to newSize rows can be handled.

Implemented in abacus::OsiIF.

◆ _sense() [1/2]

virtual OptSense abacus::LP::_sense ( ) const

protectedpure virtual

The pure virtual function _sense() must be defined by the used LP-solver and return the sense of the optimization.

Implemented in abacus::OsiIF.

◆ _sense() [2/2]

virtual void abacus::LP::_sense ( const OptSense & newSense )

protectedpure virtual

Implemented in abacus::OsiIF.

◆ _setSimplexIterationLimit()

virtual int abacus::LP::_setSimplexIterationLimit ( int limit )

protectedpure virtual

The function setSimplexIterationLimit() changes the iteration limit of the Simplex algorithm.

Returns: 0 If the iteration limit could be set,; 1 otherwise.

Parameters

limit The new value of the iteration limit.

Implemented in abacus::OsiIF.

◆ _slack()

virtual double abacus::LP::_slack ( int i ) const

protectedpure virtual

The pure virtual function _slack() must be defined by the used LP-solver and should return the value of the slack variable i.

Implemented in abacus::OsiIF.

◆ _slackStat()

virtual SlackStat::STATUS abacus::LP::_slackStat ( int i ) const

protectedpure virtual

The pure virtual function _slackStat() must be defined by the used LP-solver and should return the status of the slack variable i in the LP-solution.

Implemented in abacus::OsiIF.

◆ _uBound()

virtual double abacus::LP::_uBound ( int i ) const

protectedpure virtual

The pure virtual function _uBound() must be defined by the used LP-solver and return the upper bound of variable i.

Implemented in abacus::OsiIF.

◆ _value()

virtual double abacus::LP::_value ( ) const

protectedpure virtual

The pure virtual function _value() must be defined by the used LP-solver and should return the optimum value of the linear program after it has been solved.

Implemented in abacus::OsiIF.

◆ _xVal()

virtual double abacus::LP::_xVal ( int i ) const

protectedpure virtual

The pure virtual function _xVal() must be defined by the used LP-solver and should return the value of variable i in the LP-solution.

Implemented in abacus::OsiIF.

◆ _yVal()

virtual double abacus::LP::_yVal ( int i ) const

protectedpure virtual

The pure virtual function _yVal() must be defined by the used LP-solver and should return the value of the dual variable of the constraint i.

Implemented in abacus::OsiIF.

◆ addCols()

void abacus::LP::addCols ( ArrayBuffer< Column * > & newCols )

Adds columns to the linear program.

If the new number of columns exceeds the maximal number of columns a reallocation is performed.

Parameters

newCols The new columns that are added.

◆ addRows()

void abacus::LP::addRows ( ArrayBuffer< Row * > & newRows )

Adds rows to the linear program.

If the new number of rows exceeds the maximal number of rows a reallocation is performed.

Parameters

newRows The rows that should be added to the linear program.

◆ barXVal()

virtual double abacus::LP::barXVal ( int i ) const

inlinevirtual

Reimplemented in abacus::LpSub.

Definition at line 273 of file lp.h.

◆ barXValStatus()

SOLSTAT abacus::LP::barXValStatus ( ) const

inline

Definition at line 303 of file lp.h.

◆ basisStatus()

SOLSTAT abacus::LP::basisStatus ( ) const

inline

Definition at line 311 of file lp.h.

◆ changeLBound()

virtual void abacus::LP::changeLBound	(	int	i,
		double	newLb
	)

virtual

Changes the lower bound of a single column.

Parameters

i	The column.
newLb	The new lower bound of the column.

Reimplemented in abacus::LpSub.

◆ changeRhs()

void abacus::LP::changeRhs ( Array< double > & newRhs )

inline

Changes the complete right hand side of the linear program.

Parameters

newRhs The new right hand side of the rows.

Definition at line 412 of file lp.h.

◆ changeUBound()

virtual void abacus::LP::changeUBound	(	int	i,
		double	newUb
	)

virtual

Changes the upper bound of a single column.

Parameters

i	The column.
newUb	The new upper bound of the column.

Reimplemented in abacus::LpSub.

◆ colRangeCheck()

void abacus::LP::colRangeCheck ( int i ) const

protected

Terminates the program if there is no column with index i.

Parameters

i	The number of a column.

◆ colRealloc()

void abacus::LP::colRealloc ( int newSize )

inline

Performs a reallocation of the column space of the linear program.

Parameters

newSize The new maximal number of columns of the linear program.

Definition at line 453 of file lp.h.

◆ colsNnz()

void abacus::LP::colsNnz	(	int	nRow,
		Array< Row * > &	rows,
		Array< int > &	nnz
	)

protected

Computes the number of nonzero elements in each column of a given set of rows.

Parameters

nRow	The number of rows.
rows	The array storing the rows.
nnz	An array of length at least the number of columns of the linear program which will hold the number of nonzero elements of each column.

◆ getInfeas()

virtual int abacus::LP::getInfeas	(	int &	infeasRow,
		int &	infeasCol,
		double *	bInvRow
	)		const

inlinevirtual

Can be called if the last linear program has been solved with the dual simplex method and is infeasible and all inactive variables price out correctly.

Then, the basis is dual feasible, but primal infeasible, i.e., some variables or slack variables violate their bounds. In this case the function getInfeas() determines an infeasible variable or slack variable.

If getInfeas() is successful, then either infeasRow or infeasVar is \(-1\) and the other argument holds the nonnegative number of the infeasible variable.

Returns: 0 On success,; 1 otherwise.

Parameters

infeasRow	Holds after the execution the number of an infeasible slack variable, or \(-1\).
infeasCol	Holds after the execution the number of an infeasible column, or \(-1\).
bInvRow	Holds after the execution the row of the basis inverse corresponding to the infeasible column or slack variable, which is always a basic variable.

Reimplemented in abacus::LpSub.

Definition at line 346 of file lp.h.

◆ getSimplexIterationLimit()

int abacus::LP::getSimplexIterationLimit ( int & limit ) const

inline

Returns: 0 If the iteration limit could be get,; 1 otherwise.

Parameters

limit Stores the iteration limit if the return value is 0.

Definition at line 485 of file lp.h.

◆ infeasible()

virtual bool abacus::LP::infeasible ( ) const

inlinevirtual

Reimplemented in abacus::LpSub.

Definition at line 315 of file lp.h.

◆ initialize() [1/2]

void abacus::LP::initialize	(	OptSense	sense,
		int	nRow,
		int	maxRow,
		int	nCol,
		int	maxCol,
		Array< double > &	obj,
		Array< double > &	lBound,
		Array< double > &	uBound,
		Array< Row * > &	rows
	)

inline

Loads the linear program defined by its arguments.

We do not perform the initialization via arguments of a constructor, since for the most frequent application of linear programs within ABACUS, the solution of the linear programming relaxations in the subproblems, the problem data is preprocessed before it is loaded. Only after the preprocessing in the constructor of the derived class, we can call initialize().

Of course, it would be possible to provide an extra constructor with automatic initialization if required.

Parameters

sense	The sense of the objective function.
nRow	The number of rows.
maxRow	The maximal number of rows.
nCol	The number of columns (variables).
maxCol	The maximal number of columns.
obj	An array with the objective function coefficients.
lBound	An array with the lower bounds of the columns.
uBound	An array with the upper bounds of the columns.
rows	An array storing the rows of the problem.

Definition at line 160 of file lp.h.

◆ initialize() [2/2]

void abacus::LP::initialize	(	OptSense	sense,
		int	nRow,
		int	maxRow,
		int	nCol,
		int	maxCol,
		Array< double > &	obj,
		Array< double > &	lBound,
		Array< double > &	uBound,
		Array< Row * > &	rows,
		Array< LPVARSTAT::STATUS > &	lpVarStat,
		Array< SlackStat::STATUS > &	slackStat
	)

inline

This version of the function initialize() performs like its previous version, but also initializes the basis with the arguments:

Parameters

sense	The sense of the objective function.
nRow	The number of rows.
maxRow	The maximal number of rows.
nCol	The number of columns (variables).
maxCol	The maximal number of columns.
obj	An array with the objective function coefficients.
lBound	An array with the lower bounds of the columns.
uBound	An array with the upper bounds of the columns.
rows	An array storing the rows of the problem.
lpVarStat	An array storing the status of the columns.
slackStat	An array storing the status of the slack variables.

Definition at line 189 of file lp.h.

◆ initPostOpt()

void abacus::LP::initPostOpt ( )

inlineprivate

Resets the optimization status and the availability statuses of the solution.

The function initPostOpt() must be called after each modification of the linear program. It resets the optimization status and the availability status of the solution.

Definition at line 841 of file lp.h.

◆ lBound()

double abacus::LP::lBound ( int i ) const

inline

Definition at line 236 of file lp.h.

◆ loadBasis()

virtual void abacus::LP::loadBasis	(	Array< LPVARSTAT::STATUS > &	lpVarStat,
		Array< SlackStat::STATUS > &	slackStat
	)

inlinevirtual

Loads a new basis for the linear program.

Parameters

lpVarStat	An array storing the status of the columns.
slackStat	An array storing the status of the slack variables.

Reimplemented in abacus::LpSub.

Definition at line 209 of file lp.h.

◆ lpSolverTime()

ogdf::StopwatchCPU * abacus::LP::lpSolverTime ( )

inline

Definition at line 489 of file lp.h.

◆ lpVarStat()

virtual LPVARSTAT::STATUS abacus::LP::lpVarStat ( int i ) const

inlinevirtual

Reimplemented in abacus::LpSub.

Definition at line 350 of file lp.h.

◆ maxCol()

int abacus::LP::maxCol ( ) const

inline

Definition at line 225 of file lp.h.

◆ maxRow()

int abacus::LP::maxRow ( ) const

inline

Definition at line 221 of file lp.h.

◆ nCol()

int abacus::LP::nCol ( ) const

inline

Definition at line 223 of file lp.h.

◆ nnz()

int abacus::LP::nnz ( ) const

inline

Definition at line 227 of file lp.h.

◆ nOpt()

int abacus::LP::nOpt ( ) const

inline

Definition at line 313 of file lp.h.

◆ nRow()

int abacus::LP::nRow ( ) const

inline

Definition at line 219 of file lp.h.

◆ obj()

double abacus::LP::obj ( int i ) const

inline

Definition at line 229 of file lp.h.

◆ operator=()

const LP & abacus::LP::operator= ( const LP & rhs )

private

◆ optimize()

virtual OPTSTAT abacus::LP::optimize ( METHOD method )

virtual

Performs the optimization of the linear program.

Returns: The status of the optimization.

Parameters

method The method with which the optimization is performed.

Reimplemented in abacus::LpSub.

◆ pivotSlackVariableIn()

virtual int abacus::LP::pivotSlackVariableIn ( ArrayBuffer< int > & rows )

virtual

Pivots the slack variables stored in the buffer rows into the basis.

Returns: 0 All variables could be pivoted in,; 1 otherwise.

Parameters

rows	The numbers of the slack variables that should be pivoted in.

◆ reco()

virtual double abacus::LP::reco ( int i ) const

inlinevirtual

Reimplemented in abacus::LpSub.

Definition at line 280 of file lp.h.

◆ recoStatus()

SOLSTAT abacus::LP::recoStatus ( ) const

inline

Definition at line 307 of file lp.h.

◆ remCols()

void abacus::LP::remCols ( ArrayBuffer< int > & cols )

inline

Removes columns from the linear program.

Parameters

cols	The numbers of the columns that should be removed.

Definition at line 394 of file lp.h.

◆ remRows()

void abacus::LP::remRows ( ArrayBuffer< int > & ind )

inline

Removes rows of the linear program.

Parameters

ind	The numbers of the rows that should be removed.

Definition at line 376 of file lp.h.

◆ rhs()

double abacus::LP::rhs ( int i ) const

inline

Definition at line 257 of file lp.h.

◆ row()

void abacus::LP::row	(	int	i,
		Row &	r
	)		const

inline

Definition at line 250 of file lp.h.

◆ rowRangeCheck()

void abacus::LP::rowRangeCheck ( int r ) const

protected

Terminates the program if there is no row with index r.

Parameters

r	The number of a row of the linear program.

◆ rowRealloc()

void abacus::LP::rowRealloc ( int newSize )

inline

Performs a reallocation of the row space of the linear program.

Parameters

newSize The new maximal number of rows of the linear program.

Definition at line 445 of file lp.h.

◆ rows2cols()

void abacus::LP::rows2cols	(	int	nRow,
		Array< Row * > &	rows,
		Array< SparVec * > &	cols
	)

protected

Computes the columnwise representation of the row matrix.

Parameters

nRow	The number of rows.
rows	The array storing the rows.
cols	An array holding pointers to sparse vectors which will contain the columnwise representation of the constraint matrix defined by rows. The length of this array must be at least the number of columns. The elements of the array must not be 0-pointers. Sparse vectors of sufficient length should be allocated before the function is called. The size of these sparse vectors can be determined with the function colsNnz().

◆ sense() [1/2]

OptSense abacus::LP::sense ( ) const

inline

Definition at line 215 of file lp.h.

◆ sense() [2/2]

void abacus::LP::sense ( const OptSense & newSense )

inline

Definition at line 217 of file lp.h.

◆ setSimplexIterationLimit()

int abacus::LP::setSimplexIterationLimit ( int limit )

inline

Changes the iteration limit of the Simplex algorithm.

Returns: 0 If the iteration limit could be set,; 1 otherwise.

Parameters

limit The new value of the iteration limit.

Definition at line 475 of file lp.h.

◆ slack()

virtual double abacus::LP::slack ( int c ) const

inlinevirtual

Definition at line 294 of file lp.h.

◆ slackStat()

virtual SlackStat::STATUS abacus::LP::slackStat ( int i ) const

inlinevirtual

Definition at line 357 of file lp.h.

◆ slackStatus()

SOLSTAT abacus::LP::slackStatus ( ) const

inline

Definition at line 309 of file lp.h.

◆ uBound()

double abacus::LP::uBound ( int i ) const

inline

Definition at line 243 of file lp.h.

◆ value()

virtual double abacus::LP::value ( ) const

inlinevirtual

Reimplemented in abacus::LpSub.

Definition at line 264 of file lp.h.

◆ writeBasisMatrix()

int abacus::LP::writeBasisMatrix ( const char * fileName )

Writes the complete basis of an optimal linear program to a file.

Returns: 0 If a basis is available and could be written,; 1 otherwise.

Parameters

fileName The name of the file the basis is written to.

◆ xVal()

virtual double abacus::LP::xVal ( int i ) const

inlinevirtual

Reimplemented in abacus::LpSub.

Definition at line 266 of file lp.h.

◆ xValStatus()

SOLSTAT abacus::LP::xValStatus ( ) const

inline

Definition at line 301 of file lp.h.

◆ yVal()

virtual double abacus::LP::yVal ( int c ) const

inlinevirtual

Definition at line 287 of file lp.h.

◆ yValStatus()

SOLSTAT abacus::LP::yValStatus ( ) const

inline

Definition at line 305 of file lp.h.

Friends And Related Symbol Documentation

◆ operator<<

std::ostream & operator<<	(	std::ostream &	out,
		const LP &	rhs
	)

friend

The output operator writes the objective function, followed by the constraints, the bounds on the columns and the solution values (if available) to an output stream.

Every ten output columns we perform a line break for better readability. This has also the advantage that LP-solvers with an input function requiring a limited length of a line (e.g., Cplex 255 characters) have a higher chance to read a file generated by this output operator.

Returns: A reference to the output stream.

Parameters

out	The output stream.
rhs	The linear program being output.

Member Data Documentation

◆ barXValStatus_

SOLSTAT abacus::LP::barXValStatus_

protected

Definition at line 797 of file lp.h.

◆ basisStatus_

SOLSTAT abacus::LP::basisStatus_

protected

This member becomes Available if the status of the variables and the slack variables of the optimal solution can be accessed with the functions lpVarStat() and slackStat(), otherwise it has the value Missing.

Definition at line 825 of file lp.h.

◆ lpSolverTime_

ogdf::StopwatchCPU abacus::LP::lpSolverTime_

protected

Definition at line 830 of file lp.h.

◆ master_

Master* abacus::LP::master_

protected

A pointer to the corresponding master of the optimization.

Definition at line 786 of file lp.h.

◆ nOpt_

int abacus::LP::nOpt_

protected

The number of optimizations of the linear program.

Definition at line 829 of file lp.h.

◆ optStat_

OPTSTAT abacus::LP::optStat_

protected

The status of the linear program.

Definition at line 790 of file lp.h.

◆ recoStatus_

SOLSTAT abacus::LP::recoStatus_

protected

This member becomes Available if the reduced costs of the optimal solution can be accessed with the function reco(), otherwise it has the value Missing.

Definition at line 810 of file lp.h.

◆ slackStatus_

SOLSTAT abacus::LP::slackStatus_

protected

This member becomes Available if the values of the slack variables of the optimal solution can be accessed with the function slack(), otherwise it has the value Missing.

Definition at line 817 of file lp.h.

◆ xValStatus_

SOLSTAT abacus::LP::xValStatus_

protected

This member becomes Available if the \(x\)-values of the optimal solution can be accessed with the function xVal(), otherwise it has the value Missing.

Definition at line 796 of file lp.h.

◆ yValStatus_

SOLSTAT abacus::LP::yValStatus_

protected

This member becomes Available if the values of the dual variables of the optimal solution can be accessed with the function yVal(), otherwise it has the value Missing/.

Definition at line 804 of file lp.h.

The documentation for this class was generated from the following file:

include/ogdf/lib/abacus/lp.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Friends

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

◆ METHOD

◆ OPTSTAT

◆ SOLSTAT

Constructor & Destructor Documentation

◆ LP() [1/2]

◆ ~LP()

◆ LP() [2/2]

Member Function Documentation

◆ _addCols()

◆ _addRows()

◆ _approx()

◆ _barrier()

◆ _barXVal()

◆ _changeLBound()

◆ _changeRhs()

◆ _changeUBound()

◆ _colRealloc()

◆ _dualSimplex()

◆ _getInfeas()

◆ _getSimplexIterationLimit()

◆ _initialize()

◆ _lBound()

◆ _loadBasis()

◆ _lpVarStat()

◆ _maxCol()

◆ _maxRow()

◆ _nCol()

◆ _nnz()

◆ _nRow()

◆ _obj()

◆ _pivotSlackVariableIn()

◆ _primalSimplex()

◆ _reco()

◆ _remCols()

◆ _remRows()

◆ _rhs()

◆ _row()

◆ _rowRealloc()

◆ _sense() [1/2]

◆ _sense() [2/2]

◆ _setSimplexIterationLimit()

◆ _slack()

◆ _slackStat()

◆ _uBound()

◆ _value()

◆ _xVal()

◆ _yVal()

◆ addCols()

◆ addRows()

◆ barXVal()

◆ barXValStatus()

◆ basisStatus()

◆ changeLBound()

◆ changeRhs()

◆ changeUBound()

◆ colRangeCheck()

◆ colRealloc()

◆ colsNnz()

◆ getInfeas()

◆ getSimplexIterationLimit()

◆ infeasible()

◆ initialize() [1/2]

◆ initialize() [2/2]

◆ initPostOpt()

◆ lBound()

◆ loadBasis()

◆ lpSolverTime()

◆ lpVarStat()

◆ maxCol()

◆ maxRow()

Open
Graph Drawing
Framework