The linear program of a subproblem. More...

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

Inheritance diagram for abacus::LpSub:

Public Member Functions
	LpSub (Master master, const Sub sub)
	The constructor.

virtual	~LpSub ()
	The destructor.

virtual double	barXVal (int i) const override
	We have to redefine the function barXVal(i) since variables may have been eliminated.

virtual int	getInfeas (int &infeasCon, int &infeasVar, double *bInvRow) const override
	Is called if the last linear program has been solved with the dual simplex method and is infeasible.

ArrayBuffer< InfeasCon * > *	infeasCon ()
	Returns a pointer to the buffer holding the infeasible constraints.

virtual bool	infeasible () const override

double	lBound (int i) const
	We have to redefine the function lBound(i) since variables may have been eliminated.

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

virtual LPVARSTAT::STATUS	lpVarStat (int i) const override
	Returns the status of the variable in the linear program.

virtual double	reco (int i) const override
	We define the reduced costs of eliminated variables as 0.

const Sub *	sub () const

int	trueNCol () const
	Returns the number of columns which are passed to the LP-solver.

int	trueNnz () const
	Returns the number of nonzeros which are currently present in the constraint matrix of the LP-solver.

double	uBound (int i) const
	We have to redefine the function uBound(i) since variables may have been eliminated.

virtual double	value () const override
	Returns the objective function value of the linear program.

virtual double	xVal (int i) const override
	We have to redefine the function xVal(i) since variables may have been eliminated.

Public Member Functions inherited from abacus::LP
	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.

SOLSTAT	barXValStatus () const

SOLSTAT	basisStatus () const

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

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

int	getSimplexIterationLimit (int &limit) 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

ogdf::StopwatchCPU *	lpSolverTime ()

int	maxCol () const

int	maxRow () const

int	nCol () const

int	nnz () const

int	nOpt () const

int	nRow () const

double	obj (int i) const

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

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

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

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	initialize ()
	This function will pass the linear program of the associated subproblem to the solver.

Protected Member Functions inherited from abacus::LP
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.

Private Member Functions
	LpSub (const LpSub &rhs)

virtual void	addCons (ArrayBuffer< Constraint * > &newCons)
	Adds the constraints newCons to the linear program.

virtual void	addVars (ArrayBuffer< Variable * > &vars, ArrayBuffer< FSVarStat * > &fsVarStat, ArrayBuffer< double > &lb, ArrayBuffer< double > &ub)

virtual void	changeLBound (int i, double newLb) override
	Sets the lower bound of variable i to newLb.

virtual void	changeUBound (int i, double newUb) override
	Sets the upper bound of variable i to newUb.

void	colRealloc (int newSize)

virtual void	conRealloc (int newSize)
	Sets the maximal number of constraints to newSize.

void	constraint2row (ArrayBuffer< Constraint * > &newCons, ArrayBuffer< Row * > &newRows)
	Generates the row format of the constraint cons and stores it in rows.

bool	eliminable (int i) const
	Returns true if the function can be eliminated.

bool	eliminated (int i) const
	Returns true if the variable i is actually eliminated from the LP.

virtual double	elimVal (FSVarStat *stat, double lb, double ub) const
	Returns the value a variable is fixed or set to.

virtual double	elimVal (int i) const
	Returns the value the variable i to which it is fixed or set to.

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

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)

int	maxCol () const

int	nCol () const

int	nnz () const

double	obj (int i) const

const LpSub &	operator= (const LpSub &rhs)

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

virtual void	removeCons (ArrayBuffer< int > &ind)
	Removes all constraints listed in the buffer ind from the linear program.

virtual void	removeVars (ArrayBuffer< int > &vars)
	Removes the variables with names given in vars from the linear program.

void	rowRealloc (int newSize)

virtual void	varRealloc (int newSize)
	Sets the maximal number of variables to newSize.

Private Attributes
ArrayBuffer< InfeasCon * >	infeasCons_
	Buffer storing the infeasible constraints found be the constructor.

Array< int >	lp2orig_
	Original number of a (non-eliminated) variable.

int	nOrigVar_
	The number of original variables of the linear program.

Array< int >	orig2lp_
	After the elimination of variables the internal variables are again numbered consecutively starting with 0.

const Sub *	sub_
	A pointer to the corresponding subproblem.

double	valueAdd_
	The constant which has been added to the objective function value due to the elimination of variables.

Friends
class	BoundBranchRule

class	ConBranchRule

class	COPBRANCHRULE

class	SetBranchRule

class	Sub

class	ValBranchRule

Additional Inherited Members
Public Types inherited from abacus::LP
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...

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".

Protected Attributes inherited from abacus::LP
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/.

Detailed Description

The linear program of a subproblem.

This class is derived from the class LP to implement the linear programming relaxations of a subproblem. We require this class as the Constraint/Variable format of the constraints/variables has to be transformed to the Row/Column format required by the class LP. Moreover the class LpSub is also a preprocessor for the linear programs. Currently we only provide the elimination of (nonbasic) fixed and set variables. Future extensions should be considered.

The class LpSub is still an abstract class independent of the used LP-solver. The class for solving LP-relaxation with the LP-solvers supported by the Open Solver Interface (OSI) is the class LpSubOsi.

Definition at line 61 of file lpsub.h.

Constructor & Destructor Documentation

◆ LpSub() [1/2]

abacus::LpSub::LpSub	(	Master *	master,
		const Sub *	sub
	)

inline

The constructor.

Parameters

master	A pointer to the corresponding master of the optimization.
sub	The subproblem of which the LP-relaxation is solved.

Definition at line 368 of file lpsub.h.

◆ ~LpSub()

virtual abacus::LpSub::~LpSub ( )

virtual

The destructor.

deletes the components of infeasCons_ since they might have been allocated in the constructor and Sub::initializeLp() deletes after having tried to add variables restoring feasibility immediately LpSub. Afterwards the constructor of LpSub is called again.

◆ LpSub() [2/2]

abacus::LpSub::LpSub ( const LpSub & rhs )

private

Member Function Documentation

◆ addCons()

virtual void abacus::LpSub::addCons ( ArrayBuffer< Constraint * > & newCons )

privatevirtual

Adds the constraints newCons to the linear program.

◆ addVars()

virtual void abacus::LpSub::addVars	(	ArrayBuffer< Variable * > &	vars,
		ArrayBuffer< FSVarStat * > &	fsVarStat,
		ArrayBuffer< double > &	lb,
		ArrayBuffer< double > &	ub
	)

privatevirtual

Parameters

vars	The new variables which are added to the linear program.
fsVarStat	The status of fixing/setting of the new variables.
lb	The lower bounds of the new variables.
ub	The upper bounds of the new variables.

◆ barXVal()

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

overridevirtual

We have to redefine the function barXVal(i) since variables may have been eliminated.

Returns: The x-value of variable i after the solution of the linear program before crossing over to a basic solution.

Reimplemented from abacus::LP.

◆ changeLBound()

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

overrideprivatevirtual

Sets the lower bound of variable i to newLb.

It is not allowed to change the lower bound of an eliminated variable. This will cause a run-time error.

Reimplemented from abacus::LP.

◆ changeUBound()

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

overrideprivatevirtual

Sets the upper bound of variable i to newUb.

It is not allowed to change the upper bound of an eliminated variable. This will cause a run-time error.

Reimplemented from abacus::LP.

◆ colRealloc()

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

private

◆ conRealloc()

virtual void abacus::LpSub::conRealloc ( int newSize )

privatevirtual

Sets the maximal number of constraints to newSize.

◆ constraint2row()

void abacus::LpSub::constraint2row	(	ArrayBuffer< Constraint * > &	newCons,
		ArrayBuffer< Row * > &	newRows
	)

private

Generates the row format of the constraint cons and stores it in rows.

◆ eliminable()

bool abacus::LpSub::eliminable ( int i ) const

private

Returns true if the function can be eliminated.

This function may be only applied to variables which are fixed or set! It is sufficient for turning off any variable elimination to return always false by this function.

◆ eliminated()

bool abacus::LpSub::eliminated ( int i ) const

inlineprivate

Returns true if the variable i is actually eliminated from the LP.

This function can give different results than the function eliminate(i) since the condition to eliminate a variable might have become true after the LP has been set up.

Definition at line 281 of file lpsub.h.

◆ elimVal() [1/2]

virtual double abacus::LpSub::elimVal	(	FSVarStat *	stat,
		double	lb,
		double	ub
	)		const

privatevirtual

Returns the value a variable is fixed or set to.

Parameters

stat	A pointer to the status of the variable.
lb	The lower bound of the variable.
ub	The upper bound of the variable.

◆ elimVal() [2/2]

virtual double abacus::LpSub::elimVal ( int i ) const

privatevirtual

Returns the value the variable i to which it is fixed or set to.

The value of an eliminated variable is defined by the bound to which it is fixed or set. There is no reason to distinguish between sub_ and master_ in the switch statement, since both values should be equal.

◆ getInfeas()

virtual int abacus::LpSub::getInfeas	(	int &	infeasCon,
		int &	infeasVar,
		double *	bInvRow
	)		const

overridevirtual

Is called if the last linear program has been solved with the dual simplex method and is infeasible.

In this case it computes the infeasible basic variable or constraint and the corresponding row of the basis inverse.

Returns: 0 If no error occurs, 1 otherwise.

Parameters

infeasCon	If nonnegative, this is the number of the infeasible slack variable.
infeasVar	If nonnegative, this is the number of the infeasible structural variable. Note, either infeasCon or infeasVar is nonnegative.
bInvRow	An array containing the corresponding row of the basis inverse.

Reimplemented from abacus::LP.

◆ infeasCon()

ArrayBuffer< InfeasCon * > * abacus::LpSub::infeasCon ( )

inline

Returns a pointer to the buffer holding the infeasible constraints.

Definition at line 179 of file lpsub.h.

◆ infeasible()

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

inlineoverridevirtual

Returns: true If the LP turned out to be infeasible either if the base class LP detected an infeasibility during the solution of the linear program or infeasible constraints have been memorized during the construction of the LP or during the addition of constraints,; false otherwise.

Reimplemented from abacus::LP.

Definition at line 174 of file lpsub.h.

◆ initialize() [1/3]

virtual void abacus::LpSub::initialize ( )

protectedvirtual

This function will pass the linear program of the associated subproblem to the solver.

The function initialize() has to be called in the constructor of the class derived from this class and from a class implementing an LP-solver.

◆ initialize() [2/3]

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

private

◆ initialize() [3/3]

void abacus::LpSub::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
	)

private

◆ lBound()

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

We have to redefine the function lBound(i) since variables may have been eliminated.

Parameters

i	The number of a variable.

Returns: The lower bound of variable i. If a variable is eliminated, we return the value the eliminated variable is fixed or set to.

◆ loadBasis()

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

overridevirtual

Loads a new basis for the linear program.

The function redefines a virtual function of the base class LP. Eliminated variables have to be considered when the basis is loaded.

Parameters

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

Reimplemented from abacus::LP.

◆ lpVarStat()

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

overridevirtual

Returns the status of the variable in the linear program.

If the variable i is eliminated, then LPVARSTAT::Eliminated is returned.

Reimplemented from abacus::LP.

◆ maxCol()

int abacus::LpSub::maxCol ( ) const

private

◆ nCol()

int abacus::LpSub::nCol ( ) const

private

◆ nnz()

int abacus::LpSub::nnz ( ) const

private

◆ obj()

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

private

◆ operator=()

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

private

◆ optimize()

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

overrideprivatevirtual

Performs the optimization of the linear program with method method.

This function redefines a virtual function of the base class LP.

We have to reimplement optimize() since there might be infeasible constraints. If a linear program turns out to be infeasible but has not been solved with the dual simplex method we solve it again to find a dual feasible basis which can be used to determine inactive variables restoring feasibility. Before the optimization can be performed the infeasible constraints must be removed with the function _initMakeFeas(), then the LP should be deleted and reconstructed. This is done by the function solveLp() in the cutting plane algorithm of the class Sub.

Reimplemented from abacus::LP.

◆ reco()

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

overridevirtual

We define the reduced costs of eliminated variables as 0.

Returns: The reduced cost of variable i.

Reimplemented from abacus::LP.

◆ removeCons()

virtual void abacus::LpSub::removeCons ( ArrayBuffer< int > & ind )

inlineprivatevirtual

Removes all constraints listed in the buffer ind from the linear program.

Definition at line 221 of file lpsub.h.

◆ removeVars()

virtual void abacus::LpSub::removeVars ( ArrayBuffer< int > & vars )

privatevirtual

Removes the variables with names given in vars from the linear program.

◆ rowRealloc()

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

private

◆ sub()

const Sub * abacus::LpSub::sub ( ) const

inline

Definition at line 88 of file lpsub.h.

◆ trueNCol()

int abacus::LpSub::trueNCol ( ) const

inline

Returns the number of columns which are passed to the LP-solver.

I.e., the number of active variables of the subproblem minus the number of eliminated variables.

Definition at line 95 of file lpsub.h.

◆ trueNnz()

int abacus::LpSub::trueNnz ( ) const

inline

Returns the number of nonzeros which are currently present in the constraint matrix of the LP-solver.

Definition at line 98 of file lpsub.h.

◆ uBound()

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

We have to redefine the function uBound(i) since variables may have been eliminated.

◆ value()

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

inlineoverridevirtual

Returns the objective function value of the linear program.

Since variables might be eliminated we have to add to the solution value of the LP-solver the objective function part of the eliminated variables, to get the right value of value().

Reimplemented from abacus::LP.

Definition at line 124 of file lpsub.h.

◆ varRealloc()

virtual void abacus::LpSub::varRealloc ( int newSize )

privatevirtual

Sets the maximal number of variables to newSize.

◆ xVal()

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

overridevirtual

We have to redefine the function xVal(i) since variables may have been eliminated.

Returns: The x-value of variable i after the solution of the linear program.

Reimplemented from abacus::LP.

Friends And Related Symbol Documentation

◆ BoundBranchRule

friend class BoundBranchRule

friend

Definition at line 65 of file lpsub.h.

◆ ConBranchRule

friend class ConBranchRule

friend

Definition at line 67 of file lpsub.h.

◆ COPBRANCHRULE

friend class COPBRANCHRULE

friend

Definition at line 68 of file lpsub.h.

◆ SetBranchRule

friend class SetBranchRule

friend

Definition at line 64 of file lpsub.h.

◆ Sub

friend class Sub

friend

Definition at line 63 of file lpsub.h.

◆ ValBranchRule

friend class ValBranchRule

friend

Definition at line 66 of file lpsub.h.

Member Data Documentation

◆ infeasCons_

ArrayBuffer<InfeasCon*> abacus::LpSub::infeasCons_

private

Buffer storing the infeasible constraints found be the constructor.

Definition at line 350 of file lpsub.h.

◆ lp2orig_

Array<int> abacus::LpSub::lp2orig_

private

Original number of a (non-eliminated) variable.

Definition at line 347 of file lpsub.h.

◆ nOrigVar_

int abacus::LpSub::nOrigVar_

private

The number of original variables of the linear program.

Definition at line 356 of file lpsub.h.

◆ orig2lp_

Array<int> abacus::LpSub::orig2lp_

private

After the elimination of variables the internal variables are again numbered consecutively starting with 0.

orig2lp_[i] is the internal number of the variable i. This is -1 if the variable is eliminated.

Definition at line 344 of file lpsub.h.

◆ sub_

const Sub* abacus::LpSub::sub_

private

A pointer to the corresponding subproblem.

Definition at line 336 of file lpsub.h.

◆ valueAdd_

double abacus::LpSub::valueAdd_

private

The constant which has been added to the objective function value due to the elimination of variables.

Definition at line 353 of file lpsub.h.

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

include/ogdf/lib/abacus/lpsub.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Friends

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ LpSub() [1/2]

◆ ~LpSub()

◆ LpSub() [2/2]

Member Function Documentation

◆ addCons()

◆ addVars()

◆ barXVal()

◆ changeLBound()

◆ changeUBound()

◆ colRealloc()

◆ conRealloc()

◆ constraint2row()

◆ eliminable()

◆ eliminated()

◆ elimVal() [1/2]

◆ elimVal() [2/2]

◆ getInfeas()

◆ infeasCon()

◆ infeasible()

◆ initialize() [1/3]

◆ initialize() [2/3]

◆ initialize() [3/3]

◆ lBound()

◆ loadBasis()

◆ lpVarStat()

◆ maxCol()

◆ nCol()

◆ nnz()

◆ obj()

◆ operator=()

◆ optimize()

◆ reco()

◆ removeCons()

◆ removeVars()

◆ rowRealloc()

◆ sub()

◆ trueNCol()

◆ trueNnz()

◆ uBound()

◆ value()

◆ varRealloc()

◆ xVal()

Friends And Related Symbol Documentation

◆ BoundBranchRule

◆ ConBranchRule

◆ COPBRANCHRULE

◆ SetBranchRule

◆ Sub

◆ ValBranchRule

Member Data Documentation

◆ infeasCons_

◆ lp2orig_

◆ nOrigVar_

◆ orig2lp_

◆ sub_

◆ valueAdd_

Open
Graph Drawing
Framework