# OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

abacus::LP Class Referenceabstract

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

virtual ~LP ()
The destructor. More...

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

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

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

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

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

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

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

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

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: More...

double lBound (int i) const

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

ogdf::StopwatchCPUlpSolverTime ()

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

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

virtual double reco (int i) const

SOLSTAT recoStatus () const

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

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

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

OptSense sense () const

void sense (const OptSense &newSense)

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

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

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

## 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. More...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

virtual void _sense (const OptSense &newSense)=0

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

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

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

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

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

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

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

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

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

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

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

## 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. More...

ogdf::StopwatchCPU lpSolverTime_

Mastermaster_
A pointer to the corresponding master of the optimization. More...

int nOpt_
The number of optimizations of the linear program. More...

OPTSTAT optStat_
The status of the linear program. More...

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

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

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

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/. More...

## Private Member Functions

LP (const LP &rhs)

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

const LPoperator= (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. More...

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

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

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

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

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

## ◆ 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.

## ◆ 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

 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.

 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.

 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.

 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.

 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.

 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.

## ◆ 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.

## ◆ 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