Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

abacus::Variable Class Reference

Forms the virtual base class for all possible variables given in pool format. More...

#include <ogdf/lib/abacus/variable.h>

+ Inheritance diagram for abacus::Variable:

Public Member Functions

 Variable (Master *master, const Sub *sub, bool dynamic, bool local, double obj, double lBound, double uBound, VarType::TYPE type)
 Initializes a variable. More...
 
virtual ~Variable ()
 
bool binary () const
 Returns true If the type of the variable is Binary, false otherwise. More...
 
virtual double coeff (const Constraint *con) const
 Computes the coefficient of the variable in the constraint con. More...
 
bool discrete () const
 Returns true if the type of the variable is Integer or Binary, false otherwise. More...
 
FSVarStatfsVarStat ()
 
const FSVarStatfsVarStat () const
 
virtual int genColumn (Active< Constraint, Variable > *actCon, Column &col) const
 Computes the column col of the variable associated with the active constraints *actCon. More...
 
bool integer () const
 Returns true If the type of the variable is Integer, false otherwise. More...
 
double lBound () const
 Returns the lower bound of the variable. More...
 
void lBound (double newBound)
 Sets the lower bound of the variable to newBound. More...
 
virtual double obj () const
 Returns the objective function coefficient. More...
 
void printCol (std::ostream &out, Active< Constraint, Variable > *constraints) const
 Writes the column of the variable corresponding to the constraints to output stream out. More...
 
virtual double redCost (Active< Constraint, Variable > *actCon, double *y) const
 Computes the reduced cost of the variable corresponding the constraint set actCon and the dual variables y. More...
 
double uBound () const
 Returns the upper bound of the variable. More...
 
void uBound (double newBound)
 Sets the upper bound of the variable to newBound. More...
 
virtual bool useful (Active< Constraint, Variable > *actCon, double *y, double lpVal) const
 Returns whether an (inactive) discrete variable is useful. More...
 
virtual bool valid (const Sub *sub) const
 Returns true if the variable is valid, false otherwise. More...
 
VarType::TYPE varType () const
 Returns the type of the variable. More...
 
virtual bool violated (Active< Constraint, Variable > *constraints, double *y, double *slack=nullptr) const
 Checks, if a variable does not price out correctly. More...
 
virtual bool violated (double rc) const
 Checks, if a variable does not price out correctly. More...
 
- Public Member Functions inherited from abacus::ConVar
 ConVar (Master *master, const Sub *sub, bool dynamic, bool local)
 Creates an instance of type ConVar. More...
 
virtual ~ConVar ()
 
bool active () const
 Checks if the constraint/variable is active in at least one active subproblem. More...
 
virtual bool dynamic () const
 Return true if the constraint/variable is dynamic. More...
 
bool global () const
 Returns true if the constraint/variable is globally valid, false otherwise. More...
 
bool local () const
 Returns true if the constraint/variable is only locally valid, false otherwise. More...
 
bool expanded () const
 Returns true if the expanded format of a constraint/variable is available, false otherwise. More...
 
virtual void expand () const
 Expands a constraint/variable. More...
 
virtual void compress () const
 Compresses a constraint/variable. More...
 
virtual bool deletable () const
 Returns true if the constraint/variable can be destructed. More...
 
virtual void print (std::ostream &out) const
 Writes the constraint/variable to the output stream out. More...
 
const Subsub () const
 Returns a const pointer to the subproblem associated with the constraint/variable. More...
 
void sub (Sub *sub)
 Associates a new subproblem with the constraint/variable. More...
 
virtual unsigned hashKey () const
 Should provide a key for the constraint/variable that can be used to insert it into a hash table. More...
 
virtual const char * name () const
 Should return the name of the constraint/variable. More...
 
virtual bool equal (const ConVar *cv) const
 Should compare if the constraint/variable is identical (in a mathematical sense) with the constraint/variable cv. More...
 
virtual double rank () const
 The function should return a rank associated with the constraint/variable. More...
 
- Public Member Functions inherited from abacus::AbacusRoot
virtual ~AbacusRoot ()
 The destructor. More...
 

Protected Attributes

FSVarStat fsVarStat_
 The global status of fixing and setting of the variable. More...
 
double lBound_
 The lower bound of the variable. More...
 
double obj_
 The objective function coefficient of the variable. More...
 
VarType type_
 The type of the variable. More...
 
double uBound_
 The upper bound of the variable. More...
 
- Protected Attributes inherited from abacus::ConVar
Mastermaster_
 A pointer to the corresponding master of the optimization. More...
 
const Subsub_
 A pointer to the subproblem associated with the constraint/variable. More...
 
bool expanded_
 true, if expanded version of constraint/variables available. More...
 
int nReferences_
 The number of references to the pool slot the constraint is stored in. More...
 
bool dynamic_
 If this member is true then the constraint/variable can be also removed from the active formulation after it is added the first time. More...
 
int nActive_
 The number of active subproblems of which the constraint/variable belongs to the set of active constraints/variables. More...
 
int nLocks_
 The number of locks which have been set on the constraint/variable. More...
 
bool local_
 true if the constraint/variable is only locally valid 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

Forms the virtual base class for all possible variables given in pool format.

Variables are one of the central items in a linear-programming based branch-and-bound algorithm. This class forms the virtual base class for all possible variables given in pool format and is derived from the common base class ConVar of all constraints and variables.

Definition at line 59 of file variable.h.

Constructor & Destructor Documentation

◆ Variable()

abacus::Variable::Variable ( Master master,
const Sub sub,
bool  dynamic,
bool  local,
double  obj,
double  lBound,
double  uBound,
VarType::TYPE  type 
)
inline

Initializes a variable.

Parameters
masterA pointer to the corresponding master of the optimization.
subA pointer to the subproblem associated with the variable. This can also be the 0-pointer.
dynamicIf this argument is true, then the variable can also be removed again from the set of active variables after it is added once.
localIf this argument is true, then the variable is only locally valid, otherwise it is globally valid. As a locally valid variable is always associated with a subproblem, the argument sub must not be 0 if local is true.
objThe objective function coefficient.
lBoundThe lower bound of the variable.
uBoundThe upper bound of the variable.
typeThe type of the variable.

Definition at line 78 of file variable.h.

◆ ~Variable()

virtual abacus::Variable::~Variable ( )
inlinevirtual

Definition at line 92 of file variable.h.

Member Function Documentation

◆ binary()

bool abacus::Variable::binary ( ) const
inline

Returns true If the type of the variable is Binary, false otherwise.

Definition at line 104 of file variable.h.

◆ coeff()

virtual double abacus::Variable::coeff ( const Constraint con) const
inlinevirtual

Computes the coefficient of the variable in the constraint con.

Per default the coefficient of a variable iscomputed indirectly via the coefficient of a constraint. Problem specific redefinitions might be required.

Parameters
conThe constraint of which the coefficient should be computed.
Returns
The coefficient of the variable in the constraint con.

Reimplemented in abacus::ColVar.

Definition at line 188 of file variable.h.

◆ discrete()

bool abacus::Variable::discrete ( ) const
inline

Returns true if the type of the variable is Integer or Binary, false otherwise.

Definition at line 100 of file variable.h.

◆ fsVarStat() [1/2]

FSVarStat* abacus::Variable::fsVarStat ( )
inline
Note
This is the global status of fixing/setting that might differ from the local status of fixing/setting a variable returned by the function Sub::fsVarStat().
Returns
A pointer to the global status of fixing and setting of the variable.

Definition at line 144 of file variable.h.

◆ fsVarStat() [2/2]

const FSVarStat* abacus::Variable::fsVarStat ( ) const
inline
Note
This is the global status of fixing/setting that might differ from the local status of fixing/setting a variable returned by the function Sub::fsVarStat().
Returns
A const pointer to the global status of fixing and setting of the variable.

Definition at line 153 of file variable.h.

◆ genColumn()

virtual int abacus::Variable::genColumn ( Active< Constraint, Variable > *  actCon,
Column col 
) const
virtual

Computes the column col of the variable associated with the active constraints *actCon.

Note
The upper and lower bound of the column are initialized with the global upper and lower bound of the variable. Therefore, an adaption with the local bounds might be required.
Parameters
actConThe constraints for which the column of the variable should be computed.
colStores the column when the function terminates.
Returns
The number of nonzero entries in col.

◆ integer()

bool abacus::Variable::integer ( ) const
inline

Returns true If the type of the variable is Integer, false otherwise.

Definition at line 108 of file variable.h.

◆ lBound() [1/2]

double abacus::Variable::lBound ( ) const
inline

Returns the lower bound of the variable.

Definition at line 127 of file variable.h.

◆ lBound() [2/2]

void abacus::Variable::lBound ( double  newBound)
inline

Sets the lower bound of the variable to newBound.

Parameters
newBoundThe new value of the lower bound.

Definition at line 134 of file variable.h.

◆ obj()

virtual double abacus::Variable::obj ( ) const
inlinevirtual

Returns the objective function coefficient.

Definition at line 112 of file variable.h.

◆ printCol()

void abacus::Variable::printCol ( std::ostream &  out,
Active< Constraint, Variable > *  constraints 
) const

Writes the column of the variable corresponding to the constraints to output stream out.

Parameters
outThe output stream.
constraintsThe constraints for which the column should be written.

◆ redCost()

virtual double abacus::Variable::redCost ( Active< Constraint, Variable > *  actCon,
double *  y 
) const
virtual

Computes the reduced cost of the variable corresponding the constraint set actCon and the dual variables y.

Given the dual variables \(y\), then the reduced cost of a variable with objective function coefficient \(c_e\), column \(a_{.e}\) are defined as \(c_e - y^{\mathrm{T}} a_{.e}\).

Parameters
actConThe constraints associated with the dual variables y.
yThe dual variables of the constraint.
Returns
The reduced cost of the variable.

◆ uBound() [1/2]

double abacus::Variable::uBound ( ) const
inline

Returns the upper bound of the variable.

Definition at line 116 of file variable.h.

◆ uBound() [2/2]

void abacus::Variable::uBound ( double  newBound)
inline

Sets the upper bound of the variable to newBound.

Parameters
newBoundThe new value of the upper bound.

Definition at line 123 of file variable.h.

◆ useful()

virtual bool abacus::Variable::useful ( Active< Constraint, Variable > *  actCon,
double *  y,
double  lpVal 
) const
virtual

Returns whether an (inactive) discrete variable is useful.

An (inactive) discrete variable is considered as useful() if its activation might not produce only solutions worse than the best known feasible solution.

This is the same criterion for fixing inactive variables by reduced cost criteria.

Parameters
actConThe active constraints.
yThe dual variables of these constraints.
lpValThe value of the linear program.
Returns
true If the variable is considered as useful, false otherwise.

◆ valid()

bool abacus::Variable::valid ( const Sub sub) const
inlinevirtual

Returns true if the variable is valid, false otherwise.

Returns
true If the variable is globally valid, or the subproblem sub is an ancestor in the enumeration tree of the subproblem associated with the variable.
false otherwise.
Parameters
subThe subproblem for which validity of the variable is checked.

Definition at line 270 of file variable.h.

◆ varType()

VarType::TYPE abacus::Variable::varType ( ) const
inline

Returns the type of the variable.

Definition at line 96 of file variable.h.

◆ violated() [1/2]

virtual bool abacus::Variable::violated ( Active< Constraint, Variable > *  constraints,
double *  y,
double *  slack = nullptr 
) const
virtual

Checks, if a variable does not price out correctly.

I.e., if the reduced cost of the variable associated with the constraint set constraints and the dual variables y are positive for a maximization problem and negative for a minimization problem, respectively.

Parameters
constraintsThe constraints associated with the dual variables y.
yThe dual variables of the constraint.
slackIf r is not the 0-pointer, it will store the reduced cost after the function call. Per default r is 0.
Returns
true if the variable does not price out correctly, false otherwise.

◆ violated() [2/2]

virtual bool abacus::Variable::violated ( double  rc) const
virtual

Checks, if a variable does not price out correctly.

I.e., if the reduced cost rc is positive fora maximization problem and negative for a minimization problem, respectively.

Parameters
rcThe reduced cost of the variable.
Returns
true If the variable does not price out correctly, false otherwise.

Member Data Documentation

◆ fsVarStat_

FSVarStat abacus::Variable::fsVarStat_
protected

The global status of fixing and setting of the variable.

Definition at line 263 of file variable.h.

◆ lBound_

double abacus::Variable::lBound_
protected

The lower bound of the variable.

Definition at line 265 of file variable.h.

◆ obj_

double abacus::Variable::obj_
protected

The objective function coefficient of the variable.

Definition at line 264 of file variable.h.

◆ type_

VarType abacus::Variable::type_
protected

The type of the variable.

Definition at line 267 of file variable.h.

◆ uBound_

double abacus::Variable::uBound_
protected

The upper bound of the variable.

Definition at line 266 of file variable.h.


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