Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

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

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

Member Enumeration Documentation

◆ 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

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

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
masterA 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
limitStores 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
senseThe sense of the optimization.
nRowThe number of rows.
maxRowThe maximal number of rows.
nColThe number of columns.
maxColThe maximal number of columns.
objAn array with the objective functions coefficients.
lBoundAn array with the lower bounds of the variables.
uBoundAn array with the upper bounds of the variables.
rowsAn 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
lpVarStatAn array storing the status of the variables.
slackStatAn 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
rowsThe 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
limitThe 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
newColsThe 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
newRowsThe 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
iThe column.
newLbThe 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
newRhsThe 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
iThe column.
newUbThe 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
iThe number of a column.

◆ colRealloc()

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

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

Parameters
newSizeThe 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
nRowThe number of rows.
rowsThe array storing the rows.
nnzAn 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
infeasRowHolds after the execution the number of an infeasible slack variable, or \(-1\).
infeasColHolds after the execution the number of an infeasible column, or \(-1\).
bInvRowHolds 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
limitStores 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
senseThe sense of the objective function.
nRowThe number of rows.
maxRowThe maximal number of rows.
nColThe number of columns (variables).
maxColThe maximal number of columns.
objAn array with the objective function coefficients.
lBoundAn array with the lower bounds of the columns.
uBoundAn array with the upper bounds of the columns.
rowsAn 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
senseThe sense of the objective function.
nRowThe number of rows.
maxRowThe maximal number of rows.
nColThe number of columns (variables).
maxColThe maximal number of columns.
objAn array with the objective function coefficients.
lBoundAn array with the lower bounds of the columns.
uBoundAn array with the upper bounds of the columns.
rowsAn array storing the rows of the problem.
lpVarStatAn array storing the status of the columns.
slackStatAn 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
lpVarStatAn array storing the status of the columns.
slackStatAn 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
methodThe 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
rowsThe 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
colsThe 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
indThe 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
rThe 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
newSizeThe 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
nRowThe number of rows.
rowsThe array storing the rows.
colsAn 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
limitThe 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
fileNameThe 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 Function 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
outThe output stream.
rhsThe 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: