|
| | LpSub (Master *master, const Sub *sub) |
| | The constructor.
|
| |
| virtual | ~LpSub () |
| | The destructor.
|
| |
| virtual double | barXVal (int i) const override |
| | We have to redefine the function barXVal(i) since variables may have been eliminated.
|
| |
| virtual int | getInfeas (int &infeasCon, int &infeasVar, double *bInvRow) const override |
| | Is called if the last linear program has been solved with the dual simplex method and is infeasible.
|
| |
| ArrayBuffer< InfeasCon * > * | infeasCon () |
| | Returns a pointer to the buffer holding the infeasible constraints.
|
| |
| virtual bool | infeasible () const override |
| |
| double | lBound (int i) const |
| | We have to redefine the function lBound(i) since variables may have been eliminated.
|
| |
| virtual void | loadBasis (Array< LPVARSTAT::STATUS > &lpVarStat, Array< SlackStat::STATUS > &slackStat) override |
| | Loads a new basis for the linear program.
|
| |
| virtual LPVARSTAT::STATUS | lpVarStat (int i) const override |
| | Returns the status of the variable in the linear program.
|
| |
| virtual double | reco (int i) const override |
| | We define the reduced costs of eliminated variables as 0.
|
| |
| const Sub * | sub () const |
| |
| int | trueNCol () const |
| | Returns the number of columns which are passed to the LP-solver.
|
| |
| int | trueNnz () const |
| | Returns the number of nonzeros which are currently present in the constraint matrix of the LP-solver.
|
| |
| double | uBound (int i) const |
| | We have to redefine the function uBound(i) since variables may have been eliminated.
|
| |
| virtual double | value () const override |
| | Returns the objective function value of the linear program.
|
| |
| virtual double | xVal (int i) const override |
| | We have to redefine the function xVal(i) since variables may have been eliminated.
|
| |
| | LP (Master *master) |
| | Creates a linear program.
|
| |
| virtual | ~LP () |
| | The destructor.
|
| |
| void | addCols (ArrayBuffer< Column * > &newCols) |
| | Adds columns to the linear program.
|
| |
| void | addRows (ArrayBuffer< Row * > &newRows) |
| | Adds rows to the linear program.
|
| |
| SOLSTAT | barXValStatus () const |
| |
| SOLSTAT | basisStatus () const |
| |
| void | changeRhs (Array< double > &newRhs) |
| | Changes the complete right hand side of the linear program.
|
| |
| void | colRealloc (int newSize) |
| | Performs a reallocation of the column space of the linear program.
|
| |
| int | getSimplexIterationLimit (int &limit) const |
| |
| void | initialize (OptSense sense, int nRow, int maxRow, int nCol, int maxCol, Array< double > &obj, Array< double > &lBound, Array< double > &uBound, Array< Row * > &rows) |
| | Loads the linear program defined by its arguments.
|
| |
| void | initialize (OptSense sense, int nRow, int maxRow, int nCol, int maxCol, Array< double > &obj, Array< double > &lBound, Array< double > &uBound, Array< Row * > &rows, Array< LPVARSTAT::STATUS > &lpVarStat, Array< SlackStat::STATUS > &slackStat) |
| | This version of the function initialize() performs like its previous version, but also initializes the basis with the arguments:
|
| |
| double | lBound (int i) const |
| |
| ogdf::StopwatchCPU * | lpSolverTime () |
| |
| int | maxCol () const |
| |
| int | maxRow () const |
| |
| int | nCol () const |
| |
| int | nnz () const |
| |
| int | nOpt () const |
| |
| int | nRow () const |
| |
| double | obj (int i) const |
| |
| virtual int | pivotSlackVariableIn (ArrayBuffer< int > &rows) |
| | Pivots the slack variables stored in the buffer rows into the basis.
|
| |
| SOLSTAT | recoStatus () const |
| |
| void | remCols (ArrayBuffer< int > &cols) |
| | Removes columns from the linear program.
|
| |
| void | remRows (ArrayBuffer< int > &ind) |
| | Removes rows of the linear program.
|
| |
| double | rhs (int i) const |
| |
| void | row (int i, Row &r) const |
| |
| void | rowRealloc (int newSize) |
| | Performs a reallocation of the row space of the linear program.
|
| |
| OptSense | sense () const |
| |
| void | sense (const OptSense &newSense) |
| |
| int | setSimplexIterationLimit (int limit) |
| | Changes the iteration limit of the Simplex algorithm.
|
| |
| virtual double | slack (int c) const |
| |
| virtual SlackStat::STATUS | slackStat (int i) const |
| |
| SOLSTAT | slackStatus () const |
| |
| double | uBound (int i) const |
| |
| int | writeBasisMatrix (const char *fileName) |
| | Writes the complete basis of an optimal linear program to a file.
|
| |
| SOLSTAT | xValStatus () const |
| |
| virtual double | yVal (int c) const |
| |
| SOLSTAT | yValStatus () const |
| |
| virtual | ~AbacusRoot () |
| | The destructor.
|
| |
|
| virtual void | initialize () |
| | This function will pass the linear program of the associated subproblem to the solver.
|
| |
| virtual void | _addCols (ArrayBuffer< Column * > &newCols)=0 |
| | The pure virtual function _addCols() must be defined by the used LP-solver and should add the columns newCols to the LP.
|
| |
| virtual void | _addRows (ArrayBuffer< Row * > &newRows)=0 |
| | The pure virtual function _addRows() must be defined by the used LP-solver and should add the rows given in the buffer newRows to the LP.
|
| |
| virtual OPTSTAT | _approx ()=0 |
| | The pure virtual function _approx() must be defined by the used LP-solver and should call the approximative method of the used LP-solver.
|
| |
| virtual OPTSTAT | _barrier (bool doCrossover)=0 |
| | The pure virtual function _barrier() must be defined by the used LP-solver and should call the barrier method of the used LP-solver.
|
| |
| virtual double | _barXVal (int i) const =0 |
| |
| virtual void | _changeLBound (int i, double newLb)=0 |
| | The pure virtual function _changeLBound() must be defined by the used LP-solver and should set the lower bound of variable i to newLb.
|
| |
| virtual void | _changeRhs (Array< double > &newRhs)=0 |
| | The pure virtual function _changeRhs() must be defined by the used LP-solver and should set the right hand side of the constraint matrix of the LP to newRhs.
|
| |
| virtual void | _changeUBound (int i, double newUb)=0 |
| | The pure virtual function _changeLBound() must be defined by the used LP-solver and should set the upper bound of variable i to newUb.
|
| |
| virtual void | _colRealloc (int newSize)=0 |
| | The pure virtual function _colRealloc() must be defined by the used LP-solver and should reallocate its memory such that up to newSize columns can be handled.
|
| |
| virtual OPTSTAT | _dualSimplex ()=0 |
| | The pure virtual function _dualSimplex() must be defined by the used LP-solver and should call the dual simplex method of the used LP-solver.
|
| |
| virtual int | _getInfeas (int &infeasRow, int &infeasCol, double *bInvRow) const =0 |
| | The pure virtual function _getInfeas() must be defined by the used LP-solver and can be called if the last linear program has been solved with the dual simplex method and is infeasible.
|
| |
| virtual int | _getSimplexIterationLimit (int &limit) const =0 |
| | The function getSimplexIterationLimit() retrieves the value of the iteration limit of the simplex algorithm.
|
| |
| virtual void | _initialize (OptSense sense, int nRow, int maxRow, int nCol, int maxCol, Array< double > &obj, Array< double > &lBound, Array< double > &uBound, Array< Row * > &rows)=0 |
| | The pure virtual function _initialize() must be defined by the used LP-solver and should initialize the LP-solver with.
|
| |
| virtual double | _lBound (int i) const =0 |
| | The pure virtual function _lBound() must be defined by the used LP-solver and return the lower bound of variable i.
|
| |
| virtual void | _loadBasis (Array< LPVARSTAT::STATUS > &lpVarStat, Array< SlackStat::STATUS > &slackStat)=0 |
| | This pure virtual function should load a basis into the LP-solver.
|
| |
| virtual LPVARSTAT::STATUS | _lpVarStat (int i) const =0 |
| | The pure virtual function _lpVarStat() must be defined by the used LP-solver and should return the status of the variable i in the LP-solution.
|
| |
| virtual int | _maxCol () const =0 |
| | The pure virtual function _maxCol() must be defined by the the used LP-solver and return the maximal number of columns.
|
| |
| virtual int | _maxRow () const =0 |
| | The pure virtual function _maxRow() must be defined by the used LP-solver and return the maximal number of rows.
|
| |
| virtual int | _nCol () const =0 |
| | The pure virtual function _nCol() must be defined by the used LP-solver and return the number of columns.
|
| |
| virtual int | _nnz () const =0 |
| | The pure virtual function _nnz() must be defined by the used LP-solver and return the number of nonzero elements of the constraint matrix not including the right hand side and the bounds of the variables.
|
| |
| virtual int | _nRow () const =0 |
| | The pure virtual function _nRow() must be defined by the used LP-solver and return the number of rows of the problem.
|
| |
| virtual double | _obj (int i) const =0 |
| | The pure virtual function _obj() must be defined by the used LP-solver and return the objective function coefficient of variable i.
|
| |
| virtual int | _pivotSlackVariableIn (ArrayBuffer< int > &rows)=0 |
| | The function pivotSlackVariableIn() pivots the slack variables stored in the buffer rows into the basis.
|
| |
| virtual OPTSTAT | _primalSimplex ()=0 |
| | The pure virtual function _primalSimplex() must be defined by the used LP-solver and should call the primal simplex method of the used LP-solver.
|
| |
| virtual double | _reco (int i) const =0 |
| | The pure virtual function _reco() must be defined by the used LP-solver and should return the reduced cost of variable i.
|
| |
| virtual void | _remCols (ArrayBuffer< int > &vars)=0 |
| | The pure virtual function _remCols() must be defined by the used LP-solver and should remove the columns with numbers given in vars from the LP.
|
| |
| virtual void | _remRows (ArrayBuffer< int > &ind)=0 |
| | The pure virtual function _remRows() must be defined by the used LP-solver and should remove the rows with numbers given in the buffer ind from the LP-solver.
|
| |
| virtual double | _rhs (int i) const =0 |
| | The pure virtual function _rhs() must be defined by the used LP-solver and return the right hand side of constraint i.
|
| |
| virtual void | _row (int i, Row &r) const =0 |
| | The pure virtual function _row() must be defined by the used LP-solver and store the i-th row of the problem in the row r.
|
| |
| virtual void | _rowRealloc (int newSize)=0 |
| | The pure virtual function _rowRealloc() must be defined in the used LP-solver and should reallocate its memory such that up to newSize rows can be handled.
|
| |
| virtual OptSense | _sense () const =0 |
| | The pure virtual function _sense() must be defined by the used LP-solver and return the sense of the optimization.
|
| |
| virtual void | _sense (const OptSense &newSense)=0 |
| |
| virtual int | _setSimplexIterationLimit (int limit)=0 |
| | The function setSimplexIterationLimit() changes the iteration limit of the Simplex algorithm.
|
| |
| virtual double | _slack (int i) const =0 |
| | The pure virtual function _slack() must be defined by the used LP-solver and should return the value of the slack variable i.
|
| |
| virtual SlackStat::STATUS | _slackStat (int i) const =0 |
| | The pure virtual function _slackStat() must be defined by the used LP-solver and should return the status of the slack variable i in the LP-solution.
|
| |
| virtual double | _uBound (int i) const =0 |
| | The pure virtual function _uBound() must be defined by the used LP-solver and return the upper bound of variable i.
|
| |
| virtual double | _value () const =0 |
| | The pure virtual function _value() must be defined by the used LP-solver and should return the optimum value of the linear program after it has been solved.
|
| |
| virtual double | _xVal (int i) const =0 |
| | The pure virtual function _xVal() must be defined by the used LP-solver and should return the value of variable i in the LP-solution.
|
| |
| virtual double | _yVal (int i) const =0 |
| | The pure virtual function _yVal() must be defined by the used LP-solver and should return the value of the dual variable of the constraint i.
|
| |
| void | colRangeCheck (int i) const |
| | Terminates the program if there is no column with index i.
|
| |
| void | colsNnz (int nRow, Array< Row * > &rows, Array< int > &nnz) |
| | Computes the number of nonzero elements in each column of a given set of rows.
|
| |
| void | rowRangeCheck (int r) const |
| | Terminates the program if there is no row with index r.
|
| |
| void | rows2cols (int nRow, Array< Row * > &rows, Array< SparVec * > &cols) |
| | Computes the columnwise representation of the row matrix.
|
| |
|
| | LpSub (const LpSub &rhs) |
| |
| virtual void | addCons (ArrayBuffer< Constraint * > &newCons) |
| | Adds the constraints newCons to the linear program.
|
| |
| virtual void | addVars (ArrayBuffer< Variable * > &vars, ArrayBuffer< FSVarStat * > &fsVarStat, ArrayBuffer< double > &lb, ArrayBuffer< double > &ub) |
| |
| virtual void | changeLBound (int i, double newLb) override |
| | Sets the lower bound of variable i to newLb.
|
| |
| virtual void | changeUBound (int i, double newUb) override |
| | Sets the upper bound of variable i to newUb.
|
| |
| void | colRealloc (int newSize) |
| |
| virtual void | conRealloc (int newSize) |
| | Sets the maximal number of constraints to newSize.
|
| |
| void | constraint2row (ArrayBuffer< Constraint * > &newCons, ArrayBuffer< Row * > &newRows) |
| | Generates the row format of the constraint cons and stores it in rows.
|
| |
| bool | eliminable (int i) const |
| | Returns true if the function can be eliminated.
|
| |
| bool | eliminated (int i) const |
| | Returns true if the variable i is actually eliminated from the LP.
|
| |
| virtual double | elimVal (FSVarStat *stat, double lb, double ub) const |
| | Returns the value a variable is fixed or set to.
|
| |
| virtual double | elimVal (int i) const |
| | Returns the value the variable i to which it is fixed or set to.
|
| |
| void | initialize (OptSense sense, int nRow, int maxRow, int nCol, int maxCol, Array< double > &obj, Array< double > &lBound, Array< double > &uBound, Array< Row * > &rows) |
| |
| void | initialize (OptSense sense, int nRow, int maxRow, int nCol, int maxCol, Array< double > &obj, Array< double > &lBound, Array< double > &uBound, Array< Row * > &rows, Array< LPVARSTAT::STATUS > &lpVarStat, Array< SlackStat::STATUS > &slackStat) |
| |
| int | maxCol () const |
| |
| int | nCol () const |
| |
| int | nnz () const |
| |
| double | obj (int i) const |
| |
| const LpSub & | operator= (const LpSub &rhs) |
| |
| virtual OPTSTAT | optimize (METHOD method) override |
| | Performs the optimization of the linear program with method method.
|
| |
| virtual void | removeCons (ArrayBuffer< int > &ind) |
| | Removes all constraints listed in the buffer ind from the linear program.
|
| |
| virtual void | removeVars (ArrayBuffer< int > &vars) |
| | Removes the variables with names given in vars from the linear program.
|
| |
| void | rowRealloc (int newSize) |
| |
| virtual void | varRealloc (int newSize) |
| | Sets the maximal number of variables to newSize.
|
| |
|
| 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 bool | ascii2bool (const string &str) |
| | Converts the string str to a boolean value.
|
| |
| static bool | endsWith (const string &str, const string &end) |
| | Returns true if str ends with end, false otherwise.
|
| |
| static double | fracPart (double x) |
| | Returns the absolute value of the fractional part of x.
|
| |
| static const char * | onOff (bool value) |
| | Converts a boolean variable to the strings "on" and "off".
|
| |
| SOLSTAT | barXValStatus_ |
| |
| SOLSTAT | basisStatus_ |
| | This member becomes Available if the status of the variables and the slack variables of the optimal solution can be accessed with the functions lpVarStat() and slackStat(), otherwise it has the value Missing.
|
| |
| ogdf::StopwatchCPU | lpSolverTime_ |
| |
| Master * | master_ |
| | A pointer to the corresponding master of the optimization.
|
| |
| int | nOpt_ |
| | The number of optimizations of the linear program.
|
| |
| OPTSTAT | optStat_ |
| | The status of the linear program.
|
| |
| SOLSTAT | recoStatus_ |
| | This member becomes Available if the reduced costs of the optimal solution can be accessed with the function reco(), otherwise it has the value Missing.
|
| |
| SOLSTAT | slackStatus_ |
| | This member becomes Available if the values of the slack variables of the optimal solution can be accessed with the function slack(), otherwise it has the value Missing.
|
| |
| SOLSTAT | xValStatus_ |
| | This member becomes Available if the \(x\)-values of the optimal solution can be accessed with the function xVal(), otherwise it has the value Missing.
|
| |
| SOLSTAT | yValStatus_ |
| | This member becomes Available if the values of the dual variables of the optimal solution can be accessed with the function yVal(), otherwise it has the value Missing/.
|
| |
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.
Inheritance diagram for abacus::LpSub:
