[next] [prev] [prev-tail] [tail] [up]

6.20 ABA_LPSUB Class Reference

class is derived from the class LP to implement the linear programming relaxations of a subproblem. We require this class as the ABA_CONSTRAINT/ABA_VARIABLE format of the constraints/variables has to be transformed to the ABA_ROW/ABA_COLUMN format required by the class LP.

#include <lpsub.h>

Inheritance diagram for ABA_LPSUB::

PIC

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Friends

6.20.1 Detailed Description

class is derived from the class LP to implement the linear programming relaxations of a subproblem. We require this class as the ABA_CONSTRAINT/ABA_VARIABLE format of the constraints/variables has to be transformed to the ABA_ROW/ABA_COLUMN format required by the class LP.

Definition at line 57 of file lpsub.h.

6.20.2 Constructor & Destructor Documentation

6.20.2.1 ABA_LPSUB::ABA_LPSUB (ABA_MASTER * master, const ABA_SUB * sub)

The constructor.

Parameters:

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

6.20.2.2 virtual ABA_LPSUB::~ABA_LPSUB () [virtual]

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

6.20.2.3 ABA_LPSUB::ABA_LPSUB (const ABA_LPSUB & rhs) [private]

6.20.3 Member Function Documentation

6.20.3.1 const ABA_SUB * ABA_LPSUB::sub () const [inline]

Definition at line 357 of file lpsub.h.

6.20.3.2 int ABA_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 368 of file lpsub.h.

6.20.3.3 int ABA_LPSUB::trueNnz () const [inline]

Returns:

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

Definition at line 373 of file lpsub.h.

6.20.3.4 double ABA_LPSUB::lBound (int i) const

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

Returns:

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

Parameters:

i
The number of a variable.

Reimplemented from ABA_LP.

6.20.3.5 double ABA_LPSUB::uBound (int i) const

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

Returns:

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

Parameters:

i
The number of a variable.*

Reimplemented from ABA_LP.

6.20.3.6 double ABA_LPSUB::value () const [inline, virtual]

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

Returns:

The objective function value of the linear program.

Reimplemented from ABA_LP.

Definition at line 378 of file lpsub.h.

6.20.3.7 virtual double ABA_LPSUB::xVal (int i) [virtual]

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

6.20.3.8 virtual double ABA_LPSUB::barXVal (int i) [virtual]

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

6.20.3.9 virtual double ABA_LPSUB::reco (int i) [virtual]

We define the reduced costs of eliminated variables as 0.

Returns:

The reduced cost of variable i.

Reimplemented from ABA_LP.

6.20.3.10 virtual ABA_LPVARSTAT::STATUS ABA_LPSUB::lpVarStat (int i) [virtual]

Returns:

The status of the variable in the linear program. If the variable i is eliminated, then ABA_LPVARSTAT::Eliminated is returned.

Reimplemented from ABA_LP.

6.20.3.11 virtual int ABA_LPSUB::getInfeas (int & infeasCon, int & infeasVar, double * bInvRow) [virtual]

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

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

Returns:

0 If no error occurs,

1 otherwise.

Parameters:

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

Reimplemented from ABA_LP.

6.20.3.12 virtual bool ABA_LPSUB::infeasible () const [virtual]

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

6.20.3.13 ABA_BUFFER< ABA_INFEASCON * > * ABA_LPSUB::infeasCon () [inline]

return A pointer to the buffer holding the infeasible constraints.

Definition at line 383 of file lpsub.h.

6.20.3.14 virtual void ABA_LPSUB::loadBasis (ABA_ARRAY< ABA_LPVARSTAT::STATUS > & lpVarStat, ABA_ARRAY< ABA_SLACKSTAT::STATUS > & slackStat) [virtual]

Loads a new basis for the linear program.

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

Parameters:

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

Reimplemented from ABA_LP.

6.20.3.15 virtual void ABA_LPSUB::initialize () [protected, virtual]

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.

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

6.20.3.16 virtual OPTSTAT ABA_LPSUB::optimize (METHOD method) [private, virtual]

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

Reimplemented from ABA_LP.

6.20.3.17 virtual void ABA_LPSUB::removeCons (ABA_BUFFER< int > & ind) [private, virtual]

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

6.20.3.18 virtual void ABA_LPSUB::removeVars (ABA_BUFFER< int > & vars) [private, virtual]

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

6.20.3.19 virtual void ABA_LPSUB::addCons (ABA_BUFFER< ABA_CONSTRAINT * > & newCons) [private, virtual]

Adds the constraints newCons to the linear program.

6.20.3.20 virtual void ABA_LPSUB::addVars (ABA_BUFFER< ABA_VARIABLE * > & vars, ABA_BUFFER< ABA_FSVARSTAT * > & fsVarStat, ABA_BUFFER< double > & lb, ABA_BUFFER< double > & ub) [private, virtual]

Parameters:

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

6.20.3.21 virtual void ABA_LPSUB::changeLBound (int i, double newLb) [private, virtual]

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

6.20.3.22 virtual void ABA_LPSUB::changeUBound (int i, double newUb) [private, virtual]

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

6.20.3.23 virtual void ABA_LPSUB::varRealloc (int newSize) [private, virtual]

Sets the maximal number of variables to newSize.

6.20.3.24 virtual void ABA_LPSUB::conRealloc (int newSize) [private, virtual]

Sets the maximal number of constraints to newSize.

6.20.3.25 void ABA_LPSUB::constraint2row (ABA_BUFFER< ABA_CONSTRAINT * > & newCons, ABA_BUFFER< ABA_ROW * > & newRows) [private]

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

6.20.3.26 bool ABA_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.

6.20.3.27 bool ABA_LPSUB::eliminated (int i) const [inline, private]

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 362 of file lpsub.h.

6.20.3.28 virtual double ABA_LPSUB::elimVal (int i) const [private, virtual]

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.

6.20.3.29 virtual double ABA_LPSUB::elimVal (ABA_FSVARSTAT * stat, double lb, double ub) const [private, virtual]

Returns the value a variable is fixed or set to.

Parameters:

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

6.20.3.30 void ABA_LPSUB::initialize (ABA_OPTSENSE sense, int nRow, int maxRow, int nCol, int maxCol, ABA_ARRAY< double > & obj, ABA_ARRAY< double > & lBound, ABA_ARRAY< double > & uBound, ABA_ARRAY< ABA_ROW * > & rows) [private]

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 , the solution of the linear programming relaxations in the subproblems, the problem data is preprocessed before it is loaded. Only after the preprocessing in the constructor of the derived class, we can call initialize().

Of course, it would be possible to provide an extra constructor with automatic initialization if required.

Parameters:

sense
The sense of the objective function.
nCol
The number of columns (variables).
maxCol
The maximal number of columns.
nRow
The number of rows.
maxRow
The maximal number of rows.
obj
An array with the objective function coefficients.
lb
An array with the lower bounds of the columns.
ub
An array with the upper bounds of the columns.
rows
An array storing the rows of the problem.

Reimplemented from ABA_LP.

6.20.3.31 void ABA_LPSUB::initialize (ABA_OPTSENSE sense, int nRow, int maxRow, int nCol, int maxCol, ABA_ARRAY< double > & obj, ABA_ARRAY< double > & lBound, ABA_ARRAY< double > & uBound, ABA_ARRAY< ABA_ROW * > & rows, ABA_ARRAY< ABA_LPVARSTAT::STATUS > & lpVarStat, ABA_ARRAY< ABA_SLACKSTAT::STATUS > & slackStat) [private]

This version of the function initialize() performs like its previous version, but also initializes the basis with the arguments:.

Parameters:

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

Reimplemented from ABA_LP.

6.20.3.32 int ABA_LPSUB::nCol () const [private]

Reimplemented from ABA_LP.

6.20.3.33 int ABA_LPSUB::maxCol () const [private]

Reimplemented from ABA_LP.

6.20.3.34 int ABA_LPSUB::nnz () const [private]

Reimplemented from ABA_LP.

6.20.3.35 double ABA_LPSUB::obj (int i) const [private]

Reimplemented from ABA_LP.

6.20.3.36 void ABA_LPSUB::rowRealloc (int newSize) [private]

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

Parameters:

newSize
The new maximal number of rows of the linear program.

Reimplemented from ABA_LP.

6.20.3.37 void ABA_LPSUB::colRealloc (int newSize) [private]

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

Parameters:

newSize
The new maximal number of columns of the linear program.

Reimplemented from ABA_LP.

6.20.3.38 const ABA_LPSUB& ABA_LPSUB::operator= (const ABA_LPSUB & rhs) [private]

6.20.4 Friends And Related Function Documentation

6.20.4.1 friend class ABA_SUB [friend]

Definition at line 58 of file lpsub.h.

6.20.4.2 friend class ABA_SETBRANCHRULE [friend]

Definition at line 59 of file lpsub.h.

6.20.4.3 friend class ABA_BOUNDBRANCHRULE [friend]

Definition at line 60 of file lpsub.h.

6.20.4.4 friend class ABA_VALBRANCHRULE [friend]

Definition at line 61 of file lpsub.h.

6.20.4.5 friend class ABA_CONBRANCHRULE [friend]

Definition at line 62 of file lpsub.h.

6.20.4.6 friend class COPBRANCHRULE [friend]

Definition at line 63 of file lpsub.h.

6.20.5 Member Data Documentation

6.20.5.1 const ABA_SUB*ABA_LPSUB::sub_ [private]

A pointer to the corresponding subproblem.

Definition at line 327 of file lpsub.h.

6.20.5.2 ABA_ARRAY<int> ABA_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 334 of file lpsub.h.

6.20.5.3 ABA_ARRAY<int> ABA_LPSUB::lp2orig_ [private]

Orignial number of a (non-eliminated) variable.

Definition at line 338 of file lpsub.h.

6.20.5.4 ABA_BUFFER<ABA_INFEASCON*> ABA_LPSUB::infeasCons_ [private]

Buffer storing the infeasible constraints found be the constructor.

Definition at line 342 of file lpsub.h.

6.20.5.5 double ABA_LPSUB::valueAdd_ [private]

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

Definition at line 347 of file lpsub.h.

6.20.5.6 int ABA_LPSUB::nOrigVar_ [private]

The number of original variables of the linear program.

Definition at line 351 of file lpsub.h.

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

[next] [prev] [prev-tail] [front] [up]