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

#include <lpsub.h>

Inheritance diagram for ABA_LPSUB:

ABA_LP ABA_ABACUSROOT ABA_LPSUBOSI List of all members.

Public Member Functions

 ABA_LPSUB (ABA_MASTER *master, const ABA_SUB *sub)
virtual ~ABA_LPSUB ()
 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.
const ABA_SUB * sub () const
int trueNCol () const
int trueNnz () const
double lBound (int i) const
 We have to redefine the function lBound(i) since variables may have been eliminated.
double uBound (int i) const
 We have to redefine the function uBound(i) since variables may have been eliminated.
virtual double value () const
 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().
virtual double xVal (int i)
 We have to redefine the function xVal(i) since variables may have been eliminated.
virtual double barXVal (int i)
 We have to redefine the function barXVal(i) since variables may have been eliminated.
virtual double reco (int i)
virtual ABA_LPVARSTAT::STATUS lpVarStat (int i)
virtual int getInfeas (int &infeasCon, int &infeasVar, double *bInvRow)
 Is called if the last linear program has been solved with the dual simplex method and is infeasible.
virtual bool infeasible () const
ABA_BUFFER< ABA_INFEASCON * > * infeasCon ()
virtual void loadBasis (ABA_ARRAY< ABA_LPVARSTAT::STATUS > &lpVarStat, ABA_ARRAY< ABA_SLACKSTAT::STATUS > &slackStat)

Protected Member Functions

virtual void initialize ()
 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.

Private Member Functions

virtual OPTSTAT optimize (METHOD method)
virtual void removeCons (ABA_BUFFER< int > &ind)
virtual void removeVars (ABA_BUFFER< int > &vars)
virtual void addCons (ABA_BUFFER< ABA_CONSTRAINT * > &newCons)
virtual void addVars (ABA_BUFFER< ABA_VARIABLE * > &vars, ABA_BUFFER< ABA_FSVARSTAT * > &fsVarStat, ABA_BUFFER< double > &lb, ABA_BUFFER< double > &ub)
virtual void changeLBound (int i, double newLb)
virtual void changeUBound (int i, double newUb)
virtual void varRealloc (int newSize)
virtual void conRealloc (int newSize)
void constraint2row (ABA_BUFFER< ABA_CONSTRAINT * > &newCons, ABA_BUFFER< ABA_ROW * > &newRows)
bool eliminable (int i) const
bool eliminated (int i) const
 Returns true if the variable i is actually eliminated from the LP.
virtual double elimVal (int i) const
virtual double elimVal (ABA_FSVARSTAT *stat, double lb, double ub) const
void 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)
void 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)
 This version of the function initialize() performs like its previous version, but also initializes the basis with the arguments:.
int nCol () const
int maxCol () const
int nnz () const
double obj (int i) const
void rowRealloc (int newSize)
void colRealloc (int newSize)
 ABA_LPSUB (const ABA_LPSUB &rhs)
const ABA_LPSUB & operator= (const ABA_LPSUB &rhs)

Private Attributes

const ABA_SUB * sub_
ABA_ARRAY< int > orig2lp_
 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.
ABA_ARRAY< int > lp2orig_
ABA_BUFFER< ABA_INFEASCON * > infeasCons_
double valueAdd_
 The constant which has been added to the objective function value due to the elimination of variables.
int nOrigVar_

Friends

class ABA_SUB
class ABA_SETBRANCHRULE
class ABA_BOUNDBRANCHRULE
class ABA_VALBRANCHRULE
class ABA_CONBRANCHRULE
class COPBRANCHRULE

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.

Constructor & Destructor Documentation

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.

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.

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

Member Function Documentation

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

Definition at line 357 of file lpsub.h.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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

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

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

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

Adds the constraints newCons to the linear program.

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.

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.

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.

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

Sets the maximal number of variables to newSize.

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

Sets the maximal number of constraints to newSize.

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.

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.

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.

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.

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.

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.

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.

int ABA_LPSUB::nCol (  )  const [private]

Reimplemented from ABA_LP.

int ABA_LPSUB::maxCol (  )  const [private]

Reimplemented from ABA_LP.

int ABA_LPSUB::nnz (  )  const [private]

Reimplemented from ABA_LP.

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

Reimplemented from ABA_LP.

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.

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.

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

Friends And Related Function Documentation

friend class ABA_SUB [friend]

Definition at line 58 of file lpsub.h.

friend class ABA_SETBRANCHRULE [friend]

Definition at line 59 of file lpsub.h.

friend class ABA_BOUNDBRANCHRULE [friend]

Definition at line 60 of file lpsub.h.

friend class ABA_VALBRANCHRULE [friend]

Definition at line 61 of file lpsub.h.

friend class ABA_CONBRANCHRULE [friend]

Definition at line 62 of file lpsub.h.

friend class COPBRANCHRULE [friend]

Definition at line 63 of file lpsub.h.

Member Data Documentation

const ABA_SUB* ABA_LPSUB::sub_ [private]

A pointer to the corresponding subproblem.

Definition at line 327 of file lpsub.h.

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.

ABA_ARRAY<int> ABA_LPSUB::lp2orig_ [private]

Orignial number of a (non-eliminated) variable.

Definition at line 338 of file lpsub.h.

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.

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.

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:
Generated on Tue Aug 14 18:09:57 2007 for ABACUS by  doxygen 1.5.1