Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

abacus::LpSub Class Reference

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. More...
 
virtual ~LpSub ()
 The destructor. More...
 
virtual double barXVal (int i) const override
 We have to redefine the function barXVal(i) since variables may have been eliminated. More...
 
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. More...
 
ArrayBuffer< InfeasCon * > * infeasCon ()
 Returns a pointer to the buffer holding the infeasible constraints. More...
 
virtual bool infeasible () const override
 
double lBound (int i) const
 We have to redefine the function lBound(i) since variables may have been eliminated. More...
 
virtual void loadBasis (Array< LPVARSTAT::STATUS > &lpVarStat, Array< SlackStat::STATUS > &slackStat) override
 Loads a new basis for the linear program. More...
 
virtual LPVARSTAT::STATUS lpVarStat (int i) const override
 Returns the status of the variable in the linear program. More...
 
virtual double reco (int i) const override
 We define the reduced costs of eliminated variables as 0. More...
 
const Subsub () const
 
int trueNCol () const
 Returns the number of columns which are passed to the LP-solver. More...
 
int trueNnz () const
 Returns the number of nonzeros which are currently present in the constraint matrix of the LP-solver. More...
 
double uBound (int i) const
 We have to redefine the function uBound(i) since variables may have been eliminated. More...
 
virtual double value () const override
 Returns the objective function value of the linear program. More...
 
virtual double xVal (int i) const override
 We have to redefine the function xVal(i) since variables may have been eliminated. More...
 
- Public Member Functions inherited from abacus::LP
 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...
 
SOLSTAT barXValStatus () const
 
SOLSTAT basisStatus () const
 
void changeRhs (Array< double > &newRhs)
 Changes the complete right hand side of the linear program. More...
 
void colRealloc (int newSize)
 Performs a reallocation of the column space of the linear program. More...
 
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. 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
 
ogdf::StopwatchCPUlpSolverTime ()
 
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. More...
 
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
 
int writeBasisMatrix (const char *fileName)
 Writes the complete basis of an optimal linear program to a file. More...
 
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 initialize ()
 This function will pass the linear program of the associated subproblem to the solver. More...
 
- 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. 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...
 

Private Member Functions

 LpSub (const LpSub &rhs)
 
virtual void addCons (ArrayBuffer< Constraint * > &newCons)
 Adds the constraints newCons to the linear program. More...
 
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. More...
 
virtual void changeUBound (int i, double newUb) override
 Sets the upper bound of variable i to newUb. More...
 
void colRealloc (int newSize)
 
virtual void conRealloc (int newSize)
 Sets the maximal number of constraints to newSize. More...
 
void constraint2row (ArrayBuffer< Constraint * > &newCons, ArrayBuffer< Row * > &newRows)
 Generates the row format of the constraint cons and stores it in rows. More...
 
bool eliminable (int i) const
 Returns true if the function can be eliminated. More...
 
bool eliminated (int i) const
 Returns true if the variable i is actually eliminated from the LP. More...
 
virtual double elimVal (FSVarStat *stat, double lb, double ub) const
 Returns the value a variable is fixed or set to. More...
 
virtual double elimVal (int i) const
 Returns the value the variable i to which it is fixed or set to. 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)
 
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 LpSuboperator= (const LpSub &rhs)
 
virtual OPTSTAT optimize (METHOD method) override
 Performs the optimization of the linear program with method method. More...
 
virtual void removeCons (ArrayBuffer< int > &ind)
 Removes all constraints listed in the buffer ind from the linear program. More...
 
virtual void removeVars (ArrayBuffer< int > &vars)
 Removes the variables with names given in vars from the linear program. More...
 
void rowRealloc (int newSize)
 
virtual void varRealloc (int newSize)
 Sets the maximal number of variables to newSize. More...
 

Private Attributes

ArrayBuffer< InfeasCon * > infeasCons_
 Buffer storing the infeasible constraints found be the constructor. More...
 
Array< int > lp2orig_
 Original number of a (non-eliminated) variable. More...
 
int nOrigVar_
 The number of original variables of the linear program. More...
 
Array< int > orig2lp_
 After the elimination of variables the internal variables are again numbered consecutively starting with 0. More...
 
const Subsub_
 A pointer to the corresponding subproblem. More...
 
double valueAdd_
 The constant which has been added to the objective function value due to the elimination of variables. More...
 

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

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
masterA pointer to the corresponding master of the optimization.
subThe 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
varsThe new variables which are added to the linear program.
fsVarStatThe status of fixing/setting of the new variables.
lbThe lower bounds of the new variables.
ubThe 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
statA pointer to the status of the variable.
lbThe lower bound of the variable.
ubThe 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
infeasConIf nonnegative, this is the number of the infeasible slack variable.
infeasVarIf nonnegative, this is the number of the infeasible structural variable. Note, either infeasCon or infeasVar is nonnegative.
bInvRowAn 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
iThe 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
lpVarStatAn array storing the status of the columns.
slackStatAn 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 Function 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: