Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

abacus::Sub Class Referenceabstract

The subproblem. More...

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

+ Inheritance diagram for abacus::Sub:

Public Types

enum  PHASE { Done, Cutting, Branching, Fathoming }
 The optimization of the subproblem can be in one of the following phases. More...
 
enum  STATUS { Unprocessed, ActiveSub, Dormant, Processed, Fathomed }
 A subproblem can have different statuses. More...
 

Public Member Functions

 Sub (Master *master, double conRes, double varRes, double nnzRes, bool relativeRes=true, ArrayBuffer< PoolSlot< Constraint, Variable > * > *constraints=nullptr, ArrayBuffer< PoolSlot< Variable, Constraint > * > *variables=nullptr)
 Creates the root node of the enumeration tree. More...
 
 Sub (Master *master, Sub *father, BranchRule *branchRule)
 Creates a non-root node of the enumeration tree. More...
 
virtual ~Sub ()
 The destructor only deletes the sons of the node. More...
 
Active< Constraint, Variable > * actCon () const
 Returns a pointer to the currently active constraints. More...
 
Active< Variable, Constraint > * actVar () const
 Returns a pointer to the currently active variables. More...
 
virtual int addBranchingConstraint (PoolSlot< Constraint, Variable > *slot)
 Adds a branching constraint to the constraint buffer. More...
 
int addConBufferSpace () const
 Can be used to determine the maximal number of the constraints which still can be added to the constraint buffer. More...
 
int addVarBufferSpace () const
 Can be used to determine the maximal number of the variables which still can be added to the variable buffer. More...
 
bool ancestor (const Sub *sub) const
 Returns true if this subproblem is an ancestor of the subproblem sub, false otherwise. More...
 
BranchRulebranchRule () const
 Returns a pointer to the branching rule of the subproblem. More...
 
Constraintconstraint (int i) const
 Returns a pointer to the i-th active constraint. More...
 
double dualBound () const
 Returns a bound which is "better" than the optimal solution of the subproblem w.r.t. the sense of the optimization. More...
 
void dualBound (double x)
 Sets the dual bound of the subproblem. More...
 
const Subfather () const
 Returns a pointer to the father of the subproblem in the branch-and-bound tree. More...
 
bool forceExactSolver () const
 Returns whether using the exact solver is forced. More...
 
FSVarStatfsVarStat (int i) const
 Returns a pointer to the status of fixing/setting of the i-th variable. More...
 
int id () const
 Returns the identity number of the subproblem. More...
 
void ignoreInTailingOff ()
 Can be used to control better the tailing-off effect. More...
 
double lBound (int i) const
 Can be used to access the lower of an active variable of the subproblem. More...
 
void lBound (int i, double l)
 Sets the local lower bound of variable i to l. More...
 
int level () const
 Returns the level of the subproblem in the branch-and-bound tree. More...
 
double lowerBound () const
 Returns a lower bound on the optimal solution of the subproblem. More...
 
LpSublp () const
 Returns a pointer to the linear program of the subproblem. More...
 
LPVARSTATlpVarStat (int i) const
 Returns a pointer to the status of the variable i in the last solved linear program. More...
 
Mastermaster ()
 Returns the master of the optimization. More...
 
const Mastermaster () const
 Returns the const master of the optimization. More...
 
int maxCon () const
 Returns the maximum number of constraints which can be handled without reallocation. More...
 
void maxIterations (int max)
 Sets the maximal number of iterations in the cutting plane phase. More...
 
int maxVar () const
 Returns the maximum number of variables which can be handled without reallocation. More...
 
int nCon () const
 Returns the number of active constraints. More...
 
int nDormantRounds () const
 
double nnzReserve () const
 Returns the additional space for nonzero elements of the constraint matrix when it is passed to the LP-solver. More...
 
int nVar () const
 Returns the number of active variables. More...
 
bool objAllInteger () const
 Tests if all active variables and objective function coefficients are integer. More...
 
bool relativeReserve () const
 
virtual void removeCon (int i)
 Adds a single constraint to the set of constraints which are removed from the active set at the beginning of the next iteration. More...
 
virtual void removeCons (ArrayBuffer< int > &remove)
 Adds constraints to the buffer of the removed constraints. More...
 
void removeVar (int i)
 Remove variable i from the set of active variables. More...
 
void removeVars (ArrayBuffer< int > &remove)
 Removes the variables in remove from the set of active variables. More...
 
SlackStatslackStat (int i) const
 Returns a pointer to the status of the slack variable i in the last solved linear program. More...
 
STATUS status () const
 Returns the status of the subproblem optimization. More...
 
double uBound (int i) const
 Can be used to access the upper of an active variable of the subproblem. More...
 
void uBound (int i, double u)
 Sets the local upper bound of variable i to u. More...
 
double upperBound () const
 Returns an upper bound on the optimal solution of the subproblem. More...
 
Variablevariable (int i) const
 Returns a pointer to the i-th active variable. More...
 
double xVal (int i) const
 Returns the value of the i-th variable in the last solved linear program. More...
 
double yVal (int i) const
 Returns the value of the i-th dual variable in the last solved linear program. More...
 
- Public Member Functions inherited from abacus::AbacusRoot
virtual ~AbacusRoot ()
 The destructor. More...
 

Protected Member Functions

virtual void activate ()
 Can be used as an entrance point for problem specific activations. More...
 
virtual int addCons (ArrayBuffer< Constraint * > &constraints, Pool< Constraint, Variable > *pool=nullptr, ArrayBuffer< bool > *keepInPool=nullptr, ArrayBuffer< double > *rank=nullptr)
 Tries to add new constraints to the constraint buffer and a pool. More...
 
virtual int addCons (ArrayBuffer< PoolSlot< Constraint, Variable > * > &newCons)
 Adds constraints to the active constraints and the linear program. More...
 
virtual int addVars (ArrayBuffer< PoolSlot< Variable, Constraint > * > &newVars)
 Adds both the variables in newVars to the set of active variables and to the linear program of the subproblem. More...
 
virtual int addVars (ArrayBuffer< Variable * > &variables, Pool< Variable, Constraint > *pool=nullptr, ArrayBuffer< bool > *keepInPool=nullptr, ArrayBuffer< double > *rank=nullptr)
 Tries to add new variables to the variable buffer and a pool. More...
 
virtual void basicConEliminate (ArrayBuffer< int > &remove)
 Retrieves all dynamic constraints having basic slack variable. More...
 
bool betterDual (double x) const
 Returns true if x is better than the best known dual bound of the subproblem, false otherwise. More...
 
bool boundCrash () const
 Returns true if the dual bound is worse than the best known primal bound, false otherwise. More...
 
virtual PHASE branching ()
 Performs branching. More...
 
virtual int branchingOnVariable (ArrayBuffer< BranchRule * > &rules)
 Generates branching rules for two new subproblems by selecting a branching variable with the function selectBranchingVariable(). More...
 
virtual LP::METHOD chooseLpMethod (int nVarRemoved, int nConRemoved, int nVarAdded, int nConAdded)
 Controls the method used to solve a linear programming relaxation. More...
 
int closeHalf (ArrayBuffer< int > &branchVar, VarType::TYPE branchVarType)
 Searches searches several possible branching variable of type branchVarType, with fraction as close to \(0.5\) as possible. More...
 
int closeHalf (int &branchVar, VarType::TYPE branchVarType)
 Searches a branching variable of type branchVarType, with fraction as close to \(0.5\) as possible. More...
 
int closeHalfExpensive (ArrayBuffer< int > &variables, VarType::TYPE branchVarType)
 Selects several candidates for branching variables of type branchVarType. More...
 
int closeHalfExpensive (int &branchVar, VarType::TYPE branchVarType)
 Selects a single branching variable of type branchVarType, with fractional part close to \(0.5\) and high absolute objective function coefficient. More...
 
virtual int compareBranchingSampleRanks (Array< double > &rank1, Array< double > &rank2)
 Compares the ranks of two branching samples. More...
 
virtual void conEliminate (ArrayBuffer< int > &remove)
 Can be used as an entry point for application specific elimination of constraints. More...
 
virtual void conRealloc (int newSize)
 Reallocates memory that at most newSize constraints can be handled in the subproblem. More...
 
virtual int constraintPoolSeparation (int ranking=0, Pool< Constraint, Variable > *pool=nullptr, double minViolation=0.001)
 Tries to generate inactive constraints from a pool. More...
 
virtual PHASE cutting ()
 Iteratively solves the LP-relaxation, generates constraints and/or variables. More...
 
virtual void deactivate ()
 Can be used as entrance point for problem specific deactivations after the subproblem optimization. More...
 
virtual double dualRound (double x)
 
virtual bool exceptionBranch ()
 Can be used to specify a problem specific criteria for enforcing a branching step. More...
 
virtual bool exceptionFathom ()
 Can be used to specify a problem specific fathoming criterium that is checked before the separation or pricing. More...
 
virtual void fathom (bool reoptimize)
 Fathoms a node and recursively tries to fathom its father. More...
 
virtual PHASE fathoming ()
 Fathoms the node, and if certain conditions are satisfied, also its ancestor. More...
 
virtual void fathomTheSubTree ()
 Fathoms all nodes in the subtree rooted at this subproblem. More...
 
virtual bool feasible ()=0
 Must check the feasibility of a solution of the LP-relaxation. More...
 
int findNonFixedSet (ArrayBuffer< int > &branchVar, VarType::TYPE branchVarType)
 Selects the first variables that are neither fixed nor set. More...
 
int findNonFixedSet (int &branchVar, VarType::TYPE branchVarType)
 Selects the first variable that is neither fixed nor set. More...
 
virtual int fix (int i, FSVarStat *newStat, bool &newValue)
 Fixes a variable. More...
 
virtual int fixAndSet (bool &newValues)
 Tries to fix and set variables both by logical implications and reduced cost criteria. More...
 
virtual bool fixAndSetTime ()
 Controls if variables should be fixed or set when all variables price out correctly. More...
 
virtual void fixByLogImp (ArrayBuffer< int > &variables, ArrayBuffer< FSVarStat * > &status)
 Should collect the numbers of the variables to be fixed in variable and the respective statuses in status. More...
 
virtual int fixByRedCost (bool &newValues, bool saveCand)
 Tries to fix variables according to the reduced cost criterion. More...
 
virtual int fixing (bool &newValues, bool saveCand=false)
 Tries to fix variables by reduced cost criteria and logical implications. More...
 
virtual int generateBranchRules (ArrayBuffer< BranchRule * > &rules)
 Tries to find rules for splitting the current subproblem in further subproblems. More...
 
virtual LpSubgenerateLp ()
 Instantiates an LP for the solution of the LP-relaxation in this subproblem. More...
 
virtual SubgenerateSon (BranchRule *rule)=0
 Returns a pointer to an object of a problem specific subproblem, which is generated from the current subproblem by branching rule rule. More...
 
virtual bool goodCol (Column &col, Array< double > &row, double x, double lb, double ub)
 
virtual double guarantee () const
 May not be called if the lower bound is 0 and upper bound not equal to 0. More...
 
virtual bool guaranteed () const
 
virtual int improve (double &primalValue)
 Can be redefined in order to implement primal heuristics for finding feasible solutions. More...
 
bool infeasible ()
 Returns true if the subproblem does not contain a feasible solution, false otherwise. More...
 
virtual void initializeCons (int maxCon)
 Initializes the active constraint set. More...
 
virtual int initializeLp ()
 Initializes the linear program. More...
 
virtual void initializeVars (int maxVar)
 Initializes the active variable set. More...
 
virtual int initMakeFeas (ArrayBuffer< InfeasCon * > &infeasCon, ArrayBuffer< Variable * > &newVars, Pool< Variable, Constraint > **pool)
 The default implementation of the virtual initMakeFeas() does nothing. More...
 
bool integerFeasible ()
 Can be used to check if the solution of the LP-relaxation is primally feasible if integrality is suficinet. More...
 
double lpRankBranchingRule (BranchRule *branchRule, int iterLimit=-1)
 Computes the rank of a branching rule by modifying the linear programming relaxation of the subproblem according to the branching rule and solving it. More...
 
virtual int makeFeasible ()
 The default implementation of makeFeasible()does nothing. More...
 
virtual void nonBindingConEliminate (ArrayBuffer< int > &remove)
 Retrieves the dynamic constraints with slack exceeding the value given by the parameter ConElimEps. More...
 
virtual int optimize ()
 Performs the optimization of the subproblem. More...
 
virtual bool pausing ()
 Sometimes it is appropriate to put a subproblem back into the list of open subproblems. More...
 
virtual int prepareBranching (bool &lastIteration)
 Is called before a branching step to remove constraints. More...
 
virtual int pricing ()
 Should generate inactive variables which do not price out correctly. More...
 
virtual bool primalSeparation ()
 Controls if during the cutting plane phase a (primal) separation step or a pricing step (dual separation) should be performed. More...
 
virtual double rankBranchingRule (BranchRule *branchRule)
 Computes the rank of a branching rule. More...
 
virtual void rankBranchingSample (ArrayBuffer< BranchRule * > &sample, Array< double > &rank)
 Computes for each branching rule of a branching sample a rank with the function rankBranchingRule(). More...
 
void redCostVarEliminate (ArrayBuffer< int > &remove)
 Retrieves all variables with "wrong" reduced costs. More...
 
virtual bool removeNonLiftableCons ()
 
virtual void reoptimize ()
 Repeats the optimization of an already optimized subproblem. More...
 
virtual int selectBestBranchingSample (int nSamples, ArrayBuffer< BranchRule * > **samples)
 Evaluates branching samples. More...
 
virtual int selectBranchingVariable (int &variable)
 Chooses a branching variable. More...
 
virtual int selectBranchingVariableCandidates (ArrayBuffer< int > &candidates)
 Selects candidates for branching variables. More...
 
virtual void selectCons ()
 Is called before constraint are selected from the constraint buffer. More...
 
virtual void selectVars ()
 Is called before variables are selected from the variable buffer. More...
 
virtual int separate ()
 Must be redefined in derived classes for the generation of cutting planes. More...
 
virtual int set (int i, FSVarStat *newStat, bool &newValue)
 Sets a variable. More...
 
virtual int set (int i, FSVarStat::STATUS newStat, bool &newValue)
 Sets a variable. More...
 
virtual int set (int i, FSVarStat::STATUS newStat, double value, bool &newValue)
 Sets a variable. More...
 
virtual void setByLogImp (ArrayBuffer< int > &variable, ArrayBuffer< FSVarStat * > &status)
 The default implementation of setByLogImp() does nothing. More...
 
virtual int setByRedCost ()
 Tries to set variables according to the reduced cost criterion. More...
 
virtual int setting (bool &newValues)
 Tries to set variables by reduced cost criteria and logical implications like fixing(). More...
 
virtual bool solveApproxNow ()
 The default implementation always returns false. More...
 
virtual int solveLp ()
 Solves the LP-relaxation of the subproblem. More...
 
virtual bool tailingOff ()
 Called when a tailing off effect according to the parameters TailOffPercent and TailOffNLps is observed. More...
 
virtual void varEliminate (ArrayBuffer< int > &remove)
 Entry point for application specific variable elimination. More...
 
virtual int variablePoolSeparation (int ranking=0, Pool< Variable, Constraint > *pool=nullptr, double minViolation=0.001)
 Tries to generate inactive variables from a pool. More...
 
virtual void varRealloc (int newSize)
 Reallocates memory that at most newSize variables can be handled in the subproblem. More...
 

Protected Attributes

Active< Constraint, Variable > * actCon_
 The active constraints of the subproblem. More...
 
Active< Variable, Constraint > * actVar_
 The active variables of the subproblem. More...
 
CutBuffer< Constraint, Variable > * addConBuffer_
 The buffer of the newly generated constraints. More...
 
CutBuffer< Variable, Constraint > * addVarBuffer_
 The buffer of the newly generated variables. More...
 
bool allBranchOnSetVars_
 If true, then the branching rule of the subproblem and of all ancestor on the path to the root node are branching on a binary variable. More...
 
double * bInvRow_
 A row of the basis inverse associated with the infeasible variable infeasVar_ or slack variable infeasCon_. More...
 
BranchRulebranchRule_
 The branching rule for the subproblem. More...
 
double dualBound_
 The dual bound of the subproblem. More...
 
Subfather_
 A pointer to the father in the branch-and-cut tree. More...
 
Array< FSVarStat * > * fsVarStat_
 A pointer to an array storing the status of fixing and setting of the active variables. More...
 
bool genNonLiftCons_
 If true, then the management of non-liftable constraints is performed. More...
 
int infeasCon_
 The number of an infeasible constraint. More...
 
int infeasVar_
 The number of an infeasible variable. More...
 
int lastIterConAdd_
 The last iteration in which constraints have been added. More...
 
int lastIterVarAdd_
 The last iteration in which variables have been added. More...
 
Array< double > * lBound_
 A pointer to an array with the local lower bound of the active variables. More...
 
LpSublp_
 A pointer to the corresponding linear program. More...
 
LP::METHOD lpMethod_
 The solution method for the next linear program. More...
 
Array< LPVARSTAT * > * lpVarStat_
 A pointer to an array storing the status of each active variable in the linear program. More...
 
Mastermaster_
 A pointer to the corresponding master of the optimization. More...
 
int nIter_
 The number of iterations in the cutting plane phase. More...
 
ArrayBuffer< int > * removeConBuffer_
 The buffer of the constraints which are removed at the beginning of the next iteration. More...
 
ArrayBuffer< int > * removeVarBuffer_
 The buffer of the variables which are removed at the beginning of the next iteration. More...
 
Array< SlackStat * > * slackStat_
 A pointer to an array storing the statuses of the slack variables of the last solved linear program. More...
 
TailOfftailOff_
 A pointer to the tailing off manager. More...
 
Array< double > * uBound_
 A pointer to an array with the local upper bounds of the active variables. More...
 
double * xVal_
 The last LP-solution. More...
 
double * yVal_
 The dual variables of the last linear program. More...
 

Private Member Functions

 Sub (const Sub &rhs)
 
virtual PHASE _activate ()
 Allocates and initializes memory of the subproblem at the beginning of the optimization. More...
 
bool _atLowerBound (int i)
 Returns true iff the current value of variable i in the primal lp is equal to its lower bound. More...
 
bool _atUpperBound (int i)
 Returns true iff the current value of variable i in the primal lp is equal to its upper bound. More...
 
virtual int _conEliminate ()
 Returns the number of eliminated constraints. More...
 
virtual void _deactivate ()
 Deallocates the memory which is not required after the optimization of the subproblem. More...
 
virtual int _fixByLogImp (bool &newValues)
 Returns 1, if a contradiction has been found, 0 otherwise. More...
 
virtual int _improve (double &primalValue)
 Tries to find a better feasible solution. More...
 
virtual int _initMakeFeas ()
 Tries to add variables to restore infeasibilities detected at initialization time. More...
 
virtual int _makeFeasible ()
 Is called if the LP is infeasible and adds inactive variables, which can make the LP feasible again, to the set of active variables. More...
 
virtual int _pricing (bool &newValues, bool doFixSet=true)
 If doFixSet is true, then we try to fix and set variables, if all inactive variables price out correctly. More...
 
virtual int _removeCons (ArrayBuffer< int > &remove)
 Removes the constraints with numbers remove from the set of active constraints. More...
 
virtual int _removeVars (ArrayBuffer< int > &remove)
 Removes the variables with numbers remove from the set of active variables. More...
 
virtual void _selectCons (ArrayBuffer< PoolSlot< Constraint, Variable > * > &newCons)
 Selects the master_->maxConAdd() best constraints from the buffered constraints and stores them in newCons. More...
 
virtual void _selectVars (ArrayBuffer< PoolSlot< Variable, Constraint > * > &newVars)
 Selects the master_->maxVarAdd() best variables from the buffered variables. More...
 
virtual int _separate ()
 Returns the number of generated cutting planes. More...
 
virtual int _setByLogImp (bool &newValues)
 Tries to set variables according to logical implications of already set and fixed variables. More...
 
virtual int _varEliminate ()
 Returns the number of eliminated variables. More...
 
virtual void activateVars (ArrayBuffer< PoolSlot< Variable, Constraint > * > &newVars)
 Adds the variables stored in the pool slots of newVars to the set of active variables, but not to the linear program. More...
 
virtual void addVarsToLp (ArrayBuffer< PoolSlot< Variable, Constraint > * > &newVars, ArrayBuffer< FSVarStat * > *localStatus=nullptr)
 Adds the variables stored in the pool slots of newVars to the linear program. localStatus can specify a local status of fixing and setting. More...
 
virtual double fixSetNewBound (int i)
 Returns the value which the upper and lower bounds of a variable should take after it is fixed or set. More...
 
virtual void getBase ()
 Updates the status of the variables and the slack variables. More...
 
virtual void infeasibleSub ()
 Should be called if a subproblem turns out to be infeasible. More...
 
virtual void newDormantRound ()
 Increments the counter for the number of rounds the subproblem is dormant. More...
 
const Suboperator= (const Sub &rhs)
 
virtual void updateBoundInLp (int i)
 Adapts the bound of a fixed or set variable i also in the linear program. More...
 

Private Attributes

bool activated_
 The variable is true if the function activate() has been called from the function _activate(). More...
 
double conReserve_
 The additional space for constraints. More...
 
bool forceExactSolver_
 Indicates whether to force the use of an exact solver to prepare branching etc. More...
 
int id_
 The number of the subproblem. More...
 
bool ignoreInTailingOff_
 If this flag is set to true then the next LP-solution is ignored in the tailing-off control. More...
 
LP::METHOD lastLP_
 The method that was used to solve the last LP. More...
 
int level_
 The level of the subproblem in the enumeration tree. More...
 
ogdf::StopwatchCPU localTimer_
 
int maxIterations_
 The maximum number of iterations in the cutting plane phase. More...
 
int nDormantRounds_
 The number of subproblem optimizations the subproblem has already the status Dormant. More...
 
double nnzReserve_
 The additional space for nonzeros. More...
 
int nOpt_
 The number of optimizations of the subproblem. More...
 
bool relativeReserve_
 If this member is true then the space reserve of the following three members varReserve_, conReserve_, and nnzReserve_ is relative to the initial numbers of constraints, variables, and nonzeros, respectively. More...
 
ArrayBuffer< Sub * > * sons_
 The sons of the node in the branch-and-cut tree. More...
 
STATUS status_
 The status of the subproblem. More...
 
double varReserve_
 The additional space for variables. More...
 

Friends

class BoundBranchRule
 
class LpSolution< Constraint, Variable >
 
class LpSolution< Variable, Constraint >
 
class Master
 
class OpenSub
 

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

The subproblem.

This class implements an abstract base class for a subproblem of the enumeration, i.e., a node of the branch-and-bound tree. The core of this class is the solution of the linear programming relaxation. If a derived class provides methods for the generation of cutting planes and/or variables, then the subproblem is processed by a cutting plane and/or column generation algorithm. Essential is that every subproblem has its own sets of active constraints and variables, which provides a very high flexibility.

Definition at line 68 of file sub.h.

Member Enumeration Documentation

◆ PHASE

The optimization of the subproblem can be in one of the following phases.

Enumerator
Done 

The optimization is done.

Cutting 

The iterative solution of the LP-relaxation and the generation of cutting planes and/or variables is currently performed.

Branching 

We try to generate further subproblems as sons of this subproblem.

Fathoming 

The subproblem is currently being fathomed.

Definition at line 89 of file sub.h.

◆ STATUS

A subproblem can have different statuses.

Enumerator
Unprocessed 

The status after generation, but before optimization of the subproblem.

ActiveSub 

The subproblem is currently processed.

Dormant 

The subproblem is partially processed and waiting in the set of open subproblems for further optimization.

Processed 

The subproblem is completely processed but could not be fathomed.

Fathomed 

The subproblem is fathomed.

Definition at line 79 of file sub.h.

Constructor & Destructor Documentation

◆ Sub() [1/3]

abacus::Sub::Sub ( Master master,
double  conRes,
double  varRes,
double  nnzRes,
bool  relativeRes = true,
ArrayBuffer< PoolSlot< Constraint, Variable > * > *  constraints = nullptr,
ArrayBuffer< PoolSlot< Variable, Constraint > * > *  variables = nullptr 
)

Creates the root node of the enumeration tree.

Parameters
masterA pointer to the corresponding master of the optimization.
conResThe additional memory allocated for constraints.
varResThe additional memory allocated for variables.
nnzResThe additional memory allocated for nonzero elements of the constraint matrix.
relativeResIf this argument is true, then reserve space for variables, constraints, and nonzeros given by the previous three arguments, is given in percent of the original numbers. Otherwise, the numbers are interpreted as absolute values (casted to integer). The default value is true.
constraintsThe pool slots of the initial constraints. If the value is 0, then the constraints of the default constraint pool are taken. The default value is 0.
variablesThe pool slots of the initial variables. If the value is 0, then the variables of the default variable pool are taken. The default value is 0.

◆ Sub() [2/3]

abacus::Sub::Sub ( Master master,
Sub father,
BranchRule branchRule 
)

Creates a non-root node of the enumeration tree.

Parameters
masterA pointer to the corresponding master of the optimization.
fatherA pointer to the father in the enumeration tree.
branchRuleThe rule defining the subspace of the solution space associated with this subproblem.

◆ ~Sub()

virtual abacus::Sub::~Sub ( )
virtual

The destructor only deletes the sons of the node.

The deletion of allocated memory is already performed when the node is fathomed. We recursively call the destructors of all subproblems contained in the enumeration tree below this subproblem itself.

If a subproblem has no sons and its status is either Unprocessed or Dormant, then it is still contained in the set of open subproblems, where it is removed from.

Reimplemented in ogdf::MinSteinerTreeDirectedCut< T >::Sub.

◆ Sub() [3/3]

abacus::Sub::Sub ( const Sub rhs)
private

Member Function Documentation

◆ _activate()

virtual PHASE abacus::Sub::_activate ( )
privatevirtual

Allocates and initializes memory of the subproblem at the beginning of the optimization.

The function returns the next phase of the optimization. This is either Cutting or Fathoming if the subproblem immediately turns out to be infeasible.

Since many objects of the class Sub can exist at the same time, yet in a sequential algorithm only one problem is active, a lot of memory can be saved if some memory is dynamically allocated when the subproblem becomes active and other information is stored in a compressed format for dormant problems.

These allocations and decompressions are performed by the function _activate(), the respective deallocations and compression of data is executed by the function _deactivate().

Currently for all subproblems which have not been processed already (except for the root) we initialize the active constraints and variables with the respective data from the father node adapted by the branching information since so we can make sure that all fixed and set variables are active. A more flexible strategy might be desirable but also dangerous.

The virtual function activate() can perform problem specific activations. It is called before variables are fixed by logical implications, because, e.g., for problems on graphs, the graph associated with the subproblem might have to be activated.

Moreover, the function _activate() is redundant in the sense that it is called only once and could be substituted by a function. However, having a future generalization to non linear-programming based branch-and-bound in mind, we keep this function.

◆ _atLowerBound()

bool abacus::Sub::_atLowerBound ( int  i)
private

Returns true iff the current value of variable i in the primal lp is equal to its lower bound.

◆ _atUpperBound()

bool abacus::Sub::_atUpperBound ( int  i)
private

Returns true iff the current value of variable i in the primal lp is equal to its upper bound.

◆ _conEliminate()

virtual int abacus::Sub::_conEliminate ( )
privatevirtual

Returns the number of eliminated constraints.

Only dynamic constraints are eliminated from the LP.

It might be worth to implement problem specific versions of this function.

◆ _deactivate()

virtual void abacus::Sub::_deactivate ( )
privatevirtual

Deallocates the memory which is not required after the optimization of the subproblem.

The virtual dummy function deactivate() can perform problem specific deactivations.

As the function _activate(), the function _deactivate() is redundant in the sense that it is called only once and could be substituted by a function. However, having a future generalization to non linear-programming based branch-and-bound in mind, we keep this function.

◆ _fixByLogImp()

virtual int abacus::Sub::_fixByLogImp ( bool &  newValues)
privatevirtual

Returns 1, if a contradiction has been found, 0 otherwise.

The parameter newValues is set to true if a variable is fixed to value different from its value in the last solved linear program.

◆ _improve()

virtual int abacus::Sub::_improve ( double &  primalValue)
privatevirtual

Tries to find a better feasible solution.

If a better solution is found its value is stored in primalValue and we return 1, otherwise we return 0.

If the upper bound has been initialized with the optimum solution or with the optimum solution plus/minus one these primal heuristics are skipped.

The primal bound, if improved, is either updated in the function cutting(), from which _improved() is called, are can be updated in the function improve() of an application in a derived class.

◆ _initMakeFeas()

virtual int abacus::Sub::_initMakeFeas ( )
privatevirtual

Tries to add variables to restore infeasibilities detected at initialization time.

It returns 0 if variables could be activated which might restore feasibility, otherwise it returns 1.

The function should analyse the constraints stored in LpSub::infeasCons_ and try to add inactive variables which could restore the infeasibility.

The new variables are only added to the set of active variables but not to the linear program since no linear program exists when this function is called.

◆ _makeFeasible()

virtual int abacus::Sub::_makeFeasible ( )
privatevirtual

Is called if the LP is infeasible and adds inactive variables, which can make the LP feasible again, to the set of active variables.

The function returns 0 if feasibility might have been restored and 1 if it is guaranteed that the linear program is infeasible on the complete variable set.

◆ _pricing()

virtual int abacus::Sub::_pricing ( bool &  newValues,
bool  doFixSet = true 
)
privatevirtual

If doFixSet is true, then we try to fix and set variables, if all inactive variables price out correctly.

In this case newValues becomes true of a variable is set or fixed to a value different from its value in the last linear program.

In a pricing step the reduced costs of inactive variables are computed and variables with positive (negative) reduced costs in a maximization (minimization) problem are activated.

The function _pricing() returns the 1 if no global optimality can be guaranteed, since variables have negative reduced costs, it returns 2 if before a pricing step can be performed, non-liftable constraints have to be removed, and 0 if the LP-solution is global dual feasible.

Also if there are no inactive variables, this function is called since it will also try to fix and set variables.

true is the default value of doFixSet. No variables should be fixed or set if _pricing() is called from _makeFeasible().

◆ _removeCons()

virtual int abacus::Sub::_removeCons ( ArrayBuffer< int > &  remove)
privatevirtual

Removes the constraints with numbers remove from the set of active constraints.

◆ _removeVars()

virtual int abacus::Sub::_removeVars ( ArrayBuffer< int > &  remove)
privatevirtual

Removes the variables with numbers remove from the set of active variables.

◆ _selectCons()

virtual void abacus::Sub::_selectCons ( ArrayBuffer< PoolSlot< Constraint, Variable > * > &  newCons)
privatevirtual

Selects the master_->maxConAdd() best constraints from the buffered constraints and stores them in newCons.

◆ _selectVars()

virtual void abacus::Sub::_selectVars ( ArrayBuffer< PoolSlot< Variable, Constraint > * > &  newVars)
privatevirtual

Selects the master_->maxVarAdd() best variables from the buffered variables.

Parameters
newVarsHolds the selected variables after the call.

◆ _separate()

virtual int abacus::Sub::_separate ( )
privatevirtual

Returns the number of generated cutting planes.

◆ _setByLogImp()

virtual int abacus::Sub::_setByLogImp ( bool &  newValues)
privatevirtual

Tries to set variables according to logical implications of already set and fixed variables.

Since logical implications are problem specific the virtual function setByLogImp() is called to find variables which can be set. If a variable is set to a new value, i.e., a value different from the one in the last solved LP, newValues is set to true. If such a setting implies a contradiction, _setByLogImp() returns 1, otherwise it returns 0.

◆ _varEliminate()

virtual int abacus::Sub::_varEliminate ( )
privatevirtual

Returns the number of eliminated variables.

Only dynamic variables can be eliminated.

◆ actCon()

Active<Constraint, Variable>* abacus::Sub::actCon ( ) const
inline

Returns a pointer to the currently active constraints.

Definition at line 213 of file sub.h.

◆ activate()

virtual void abacus::Sub::activate ( )
inlineprotectedvirtual

Can be used as an entrance point for problem specific activations.

The default implementation does nothing.

Definition at line 555 of file sub.h.

◆ activateVars()

virtual void abacus::Sub::activateVars ( ArrayBuffer< PoolSlot< Variable, Constraint > * > &  newVars)
privatevirtual

Adds the variables stored in the pool slots of newVars to the set of active variables, but not to the linear program.

If the new number of variables exceeds the maximal number of variables an automatic reallocation is performed.

◆ actVar()

Active<Variable, Constraint>* abacus::Sub::actVar ( ) const
inline

Returns a pointer to the currently active variables.

Definition at line 216 of file sub.h.

◆ addBranchingConstraint()

int abacus::Sub::addBranchingConstraint ( PoolSlot< Constraint, Variable > *  slot)
inlinevirtual

Adds a branching constraint to the constraint buffer.

This constraint is automatically added at the beginning of the cutting plane algorithm. It should be used in definitions of the pure virtual function BRANCHRULE::extract().

Returns
0 If the constraint could be added, 1 otherwise.
Parameters
slotA pointer to the pool slot containing the branching constraint.

Definition at line 1823 of file sub.h.

◆ addConBufferSpace()

int abacus::Sub::addConBufferSpace ( ) const
inline

Can be used to determine the maximal number of the constraints which still can be added to the constraint buffer.

A separation algorithm should stop as soon as the number of generated constraints reaches this number because further work is useless.

Returns
The number of constraints which still can be inserted into the constraint buffer.

Definition at line 1828 of file sub.h.

◆ addCons() [1/2]

virtual int abacus::Sub::addCons ( ArrayBuffer< Constraint * > &  constraints,
Pool< Constraint, Variable > *  pool = nullptr,
ArrayBuffer< bool > *  keepInPool = nullptr,
ArrayBuffer< double > *  rank = nullptr 
)
protectedvirtual

Tries to add new constraints to the constraint buffer and a pool.

The memory management of added constraints is passed to ABACUS by calling this function.

Parameters
constraintsThe new constraints.
poolThe pool in which the new constraints are inserted. If the value of this argument is 0, then the cut pool of the master is selected. Its default value is 0.
keepInPoolIf (*keepInPool)[i] is true, then the constraint stays in the pool even if it is not activated. The default value is a 0-pointer.
rankIf this pointer to a buffer is nonzero, this buffer should store a rank for each constraint. The greater the rank, the better the variable. The default value of rank is 0.
Returns
The number of added constraints.

◆ addCons() [2/2]

virtual int abacus::Sub::addCons ( ArrayBuffer< PoolSlot< Constraint, Variable > * > &  newCons)
protectedvirtual

Adds constraints to the active constraints and the linear program.

Parameters
newConsA buffer storing the pool slots of the new constraints.
Returns
The number of added constraints.

◆ addVarBufferSpace()

int abacus::Sub::addVarBufferSpace ( ) const
inline

Can be used to determine the maximal number of the variables which still can be added to the variable buffer.

A pricing algorithm should stop as soon as the number of generated variables reaches this number because further work is useless.

Returns
The number of variables which still can be inserted into the variable buffer.

Definition at line 1833 of file sub.h.

◆ addVars() [1/2]

virtual int abacus::Sub::addVars ( ArrayBuffer< PoolSlot< Variable, Constraint > * > &  newVars)
protectedvirtual

Adds both the variables in newVars to the set of active variables and to the linear program of the subproblem.

If the new number of variables exceeds the maximal number of variables an automatic reallocation is performed.

We require this feature in derived classes if variables of newVars can be discarded if they are already active.

Parameters
newVarsA buffer storing the pool slots of the new variables.
Returns
The number of added variables.

◆ addVars() [2/2]

virtual int abacus::Sub::addVars ( ArrayBuffer< Variable * > &  variables,
Pool< Variable, Constraint > *  pool = nullptr,
ArrayBuffer< bool > *  keepInPool = nullptr,
ArrayBuffer< double > *  rank = nullptr 
)
protectedvirtual

Tries to add new variables to the variable buffer and a pool.

The memory management of added variables is passed to ABACUS by calling this function.

Parameters
variablesThe new variables.
poolThe pool in which the new variables are inserted. If the value of this argument is 0, then the default variable pool is taken. The default value is 0.
keepInPoolIf (*keepInPool)[i] is true, then the variable stays in the pool even if it is not activated. The default value is a 0-pointer.
rankIf this pointer to a buffer is nonzero, this buffer should store a rank for each variable. The greater the rank, the better the variable. The default value of rank is 0.
Returns
The number of added variables.

◆ addVarsToLp()

virtual void abacus::Sub::addVarsToLp ( ArrayBuffer< PoolSlot< Variable, Constraint > * > &  newVars,
ArrayBuffer< FSVarStat * > *  localStatus = nullptr 
)
privatevirtual

Adds the variables stored in the pool slots of newVars to the linear program. localStatus can specify a local status of fixing and setting.

If the local FSVarStat of the added variables differs from their global status, then this local status can be stated in localStatus. Per default the value of localStatus is 0.

◆ ancestor()

bool abacus::Sub::ancestor ( const Sub sub) const

Returns true if this subproblem is an ancestor of the subproblem sub, false otherwise.

We define that a subproblem is also an ancestor of its own.

Parameters
subA pointer to a subproblem.

◆ basicConEliminate()

virtual void abacus::Sub::basicConEliminate ( ArrayBuffer< int > &  remove)
protectedvirtual

Retrieves all dynamic constraints having basic slack variable.

Parameters
removeStores the nonbinding constraints.

◆ betterDual()

bool abacus::Sub::betterDual ( double  x) const
inlineprotected

Returns true if x is better than the best known dual bound of the subproblem, false otherwise.

Definition at line 1889 of file sub.h.

◆ boundCrash()

bool abacus::Sub::boundCrash ( ) const
inlineprotected

Returns true if the dual bound is worse than the best known primal bound, false otherwise.

Definition at line 1897 of file sub.h.

◆ branching()

virtual PHASE abacus::Sub::branching ( )
protectedvirtual

Performs branching.

Is called if the global lower bound of a branch-and-cut node is still strictly less than the local upper bound, but either no violated cutting planes or variables are found, or we abort the cutting phase for some other strategic reason (e.g., observation of a tailing off effect, or branch pausing).

Usually, two new subproblems are generated. However, our implementation of branching() is more sophisticated that allows different branching. Moreover, we also check if this node is only paused. If this is the case the node is put back into the list of open branch-and-cut nodes without generating sons of this node.

Finally if none of the previous conditions is satisfied we generate new subproblems.

Returns
Done If sons of the subproblem could be generated,
Fathoming otherwise.

◆ branchingOnVariable()

virtual int abacus::Sub::branchingOnVariable ( ArrayBuffer< BranchRule * > &  rules)
protectedvirtual

Generates branching rules for two new subproblems by selecting a branching variable with the function selectBranchingVariable().

If a new branching variable selection strategy should be used the function selectBranchingVariable() should be redefined.

Parameters
rulesIf branching rules are found, then they are stored in this buffer. The length of this buffer is the number of active variables of the subproblem. If more branching rules are generated a reallocation has to be performed.
Returns
0 If branching rules could be found, 1 otherwise

◆ branchRule()

BranchRule* abacus::Sub::branchRule ( ) const
inline

Returns a pointer to the branching rule of the subproblem.

Definition at line 355 of file sub.h.

◆ chooseLpMethod()

virtual LP::METHOD abacus::Sub::chooseLpMethod ( int  nVarRemoved,
int  nConRemoved,
int  nVarAdded,
int  nConAdded 
)
protectedvirtual

Controls the method used to solve a linear programming relaxation.

The default implementation chooses the barrier method for the first linear program of the root node and for all other linear programs it tries to choose a method such that phase 1 of the simplex method is not required.

Parameters
nVarRemovedThe number of removed variables.
nConRemovedThe number of removed constraints.
nVarAddedThe number of added variables.
nConAddedThe number of added constraint.
Returns
The method the next linear programming relaxation is solved with.

◆ closeHalf() [1/2]

int abacus::Sub::closeHalf ( ArrayBuffer< int > &  branchVar,
VarType::TYPE  branchVarType 
)
protected

Searches searches several possible branching variable of type branchVarType, with fraction as close to \(0.5\) as possible.

Parameters
branchVarStores the possible branching variables.
branchVarTypeThe type of the branching variable can berestricted either to VarType::Binary or VarType::Integer.
Returns
0 If at least one branching variable is found, 1 otherwise.

◆ closeHalf() [2/2]

int abacus::Sub::closeHalf ( int &  branchVar,
VarType::TYPE  branchVarType 
)
protected

Searches a branching variable of type branchVarType, with fraction as close to \(0.5\) as possible.

Parameters
branchVarHolds the branching variable if one is found.
branchVarTypeThe type of the branching variable can be restricted either to VarType::Binary or VarType::Integer.
Returns
0 If a branching variable is found, 1 otherwise.

◆ closeHalfExpensive() [1/2]

int abacus::Sub::closeHalfExpensive ( ArrayBuffer< int > &  variables,
VarType::TYPE  branchVarType 
)
protected

Selects several candidates for branching variables of type branchVarType.

◆ closeHalfExpensive() [2/2]

int abacus::Sub::closeHalfExpensive ( int &  branchVar,
VarType::TYPE  branchVarType 
)
protected

Selects a single branching variable of type branchVarType, with fractional part close to \(0.5\) and high absolute objective function coefficient.

This is the default strategy from the TSP project.

Parameters
branchVarHolds the number of the branching variable if one is found.
branchVarTypeThe type of the branching variable can be restricted either to VarType::Binary or VarType::Integer.
Returns
0 If a branching variable is found, 1 otherwise.

◆ compareBranchingSampleRanks()

virtual int abacus::Sub::compareBranchingSampleRanks ( Array< double > &  rank1,
Array< double > &  rank2 
)
protectedvirtual

Compares the ranks of two branching samples.

For maximimization problem that rank is better for which the maximal rank of a rule is minimal, while for minimization problem the rank is better for which the minimal rank of a rule is maximal. If this value equals for both ranks we continue with the secand greatest value, etc.

Returns
1 If rank1 is better.
0 If both ranks are equal.
-1 If rank2 is better.

◆ conEliminate()

virtual void abacus::Sub::conEliminate ( ArrayBuffer< int > &  remove)
protectedvirtual

Can be used as an entry point for application specific elimination of constraints.

The default implementation of this function calls either the function nonBindingConEliminate() or the function basicConEliminate() depending on the constraint elimination mode of the master that is initialized via the parameter file.

Parameters
removeThe constraints that should be eliminated must be inserted in this buffer.

◆ conRealloc()

virtual void abacus::Sub::conRealloc ( int  newSize)
protectedvirtual

Reallocates memory that at most newSize constraints can be handled in the subproblem.

Parameters
newSizeThe new maximal number of constraints of the subproblem.

◆ constraint()

Constraint * abacus::Sub::constraint ( int  i) const
inline

Returns a pointer to the i-th active constraint.

Parameters
iThe constraint being accessed.

Definition at line 1858 of file sub.h.

◆ constraintPoolSeparation()

virtual int abacus::Sub::constraintPoolSeparation ( int  ranking = 0,
Pool< Constraint, Variable > *  pool = nullptr,
double  minViolation = 0.001 
)
protectedvirtual

Tries to generate inactive constraints from a pool.

Parameters
rankingThis parameter indicates how the ranks of violated constraints should be computed (0: no ranking; 1: violation is rank, 2: absolute value of violation is rank, 3: rank determined by ConVar::rank()). The default value is 0.
poolThe pool the constraints are generated from. If pool is 0, then the default constraint pool is used. The default value of pool is 0.
minViolationA violated constraint/variable is only added if the absolute value of its violation is at least minAbsViolation. The default value is 0.001.
Returns
The number of generated constraints.

◆ cutting()

virtual PHASE abacus::Sub::cutting ( )
protectedvirtual

Iteratively solves the LP-relaxation, generates constraints and/or variables.

Also generating variables can be regarded as "cutting", namely as generating cuts for the dual problem. A reader even studying these lines has been very brave! Therefore, the first reader of these lines is invited to a beer from the author.

Returns
Fathoming If one of the conditions for fathoming the subproblem is satisfied.
Branching If the subproblem should be splitted in further subproblems.

◆ deactivate()

virtual void abacus::Sub::deactivate ( )
inlineprotectedvirtual

Can be used as entrance point for problem specific deactivations after the subproblem optimization.

The default version of this function does nothing. This function is only called if the function activate() for the subproblem has been executed. This function is called from _deactivate().

Definition at line 563 of file sub.h.

◆ dualBound() [1/2]

double abacus::Sub::dualBound ( ) const
inline

Returns a bound which is "better" than the optimal solution of the subproblem w.r.t. the sense of the optimization.

I.e., it returns an upper for a maximization problem or a lower bound for a minimization problem, respectively.

Definition at line 181 of file sub.h.

◆ dualBound() [2/2]

void abacus::Sub::dualBound ( double  x)

Sets the dual bound of the subproblem.

If the subproblem is the root node of the enumeration tree and the new value is better than its dual bound, also the global dual bound is updated. It is an error if the dual bound gets worse.

In normal applications it is not required to call this function explicitly. This is already done by ABACUS during the subproblem optimization.

Parameters
xThe new value of the dual bound.

◆ dualRound()

virtual double abacus::Sub::dualRound ( double  x)
protectedvirtual
Parameters
xThe value that should be rounded if possible.
Returns
If all objective function values of feasible solutions are integer the function dualRound() returns x rounded up to the next integer if this is a minimization problem, or x rounded down to the next integer if this is a maximization problem, respectively. Otherwise, the return value is x.

◆ exceptionBranch()

virtual bool abacus::Sub::exceptionBranch ( )
inlineprotectedvirtual

Can be used to specify a problem specific criteria for enforcing a branching step.

This criterium is checked before the separation or pricing. The default implementation always returns false.

Returns
true If the subproblem should be fathomed, false otherwise.

Definition at line 1424 of file sub.h.

◆ exceptionFathom()

virtual bool abacus::Sub::exceptionFathom ( )
inlineprotectedvirtual

Can be used to specify a problem specific fathoming criterium that is checked before the separation or pricing.

The default implementation always returns false.

Returns
true If the subproblem should be fathomed, false otherwise.

Definition at line 1415 of file sub.h.

◆ father()

const Sub* abacus::Sub::father ( ) const
inline

Returns a pointer to the father of the subproblem in the branch-and-bound tree.

Definition at line 198 of file sub.h.

◆ fathom()

virtual void abacus::Sub::fathom ( bool  reoptimize)
protectedvirtual

Fathoms a node and recursively tries to fathom its father.

If the root of the remaining branch-and-cut tree is fathomed we are done since the optimization problem has been solved.

Otherwise, we count the number of unfathomed sons of the father of the subproblem being fathomed. If all sons of the father are fathomed it is recursively fathomed, too. If the father is the root of the remaining branch-and-cut tree and only one of its sons is unfathomed, then this unfathomed son becomes the new root of the remaining branch-and-cut tree.

We could stop the recursive fathoming already at the root of the remaining branch-and-cut tree. But, we proceed until the root of the complete tree was visited to be really correct.

Note
Use the function ExceptionFathom() for specifying problem specific fathoming criteria.
Parameters
reoptimizeIf reoptimize is true, then we perform a reoptimization in the new root. This is controlled via a parameter since it might not be desirable when we find a new root during the fathoming of a complete subtree with the function fathomTheSubTree().

◆ fathoming()

virtual PHASE abacus::Sub::fathoming ( )
protectedvirtual

Fathoms the node, and if certain conditions are satisfied, also its ancestor.

The third central phase of the optimization of a subproblem is the Fathoming of a subproblem. A subproblem is fathomed if it can be guaranteed that this subproblem cannot contain a better solution than the best known one. This is the case if the global upper bound does not exceed the local lower bound (maximization problem assumed) or the subproblem cannot contain a feasible solution either if there is a fixing/setting contradiction or the LP-relaxation turns out to be infeasible.

Note
Use the function ExceptionFathom() for specifying problem specific fathoming criteria.

The called function fathom() fathoms the subproblem itself and recursively also tries to fathom its father in the enumeration tree. The argument of fathom() is true as a possibly detected new root should be reoptimized in order to receive better criteria for fixing variables by reduced costs.

In the parallel version, only the subproblem itself is fathomed. No processed unfathomed nodes are kept in memory (father_=0).

Returns
The function always returns Done.

◆ fathomTheSubTree()

virtual void abacus::Sub::fathomTheSubTree ( )
protectedvirtual

Fathoms all nodes in the subtree rooted at this subproblem.

Dormant and Unprocessed nodes are also removed from the set of open subproblems.

If the subproblem is already Fathomed we do not have to proceed in this branch. Otherwise, we fathom the node and continue with all its sons. The actual fathoming starts at the unfathomed leaves of the subtree and recursively goes up through the tree.

◆ feasible()

virtual bool abacus::Sub::feasible ( )
protectedpure virtual

Must check the feasibility of a solution of the LP-relaxation.

If the function returns true and the value of the primal bound is worse than the value of this feasible solution, the value of the primal bound is updated automatically.

Returns
true If the LP-solution is feasible, false otherwise.

Implemented in ogdf::MinSteinerTreeDirectedCut< T >::Sub, ogdf::cluster_planarity::MaxCPlanarSub, and ogdf::cluster_planarity::CPlanaritySub.

◆ findNonFixedSet() [1/2]

int abacus::Sub::findNonFixedSet ( ArrayBuffer< int > &  branchVar,
VarType::TYPE  branchVarType 
)
protected

Selects the first variables that are neither fixed nor set.

Parameters
branchVarHolds the number of the possible branching variables if one is found.
branchVarTypeThe type of the branching variable can be restricted either to VarType::Binary or VarType::Integer.
Returns
0 If at least one variable neither fixed nor set is found, 1 otherwise.

◆ findNonFixedSet() [2/2]

int abacus::Sub::findNonFixedSet ( int &  branchVar,
VarType::TYPE  branchVarType 
)
protected

Selects the first variable that is neither fixed nor set.

Returns
0 If a variable neither fixed nor set is found, 1 otherwise.
Parameters
branchVarHolds the number of the branching variable if one is found.
branchVarTypeThe type of the branching have (VarType::Binary or VarType::Integer).

◆ fix()

virtual int abacus::Sub::fix ( int  i,
FSVarStat newStat,
bool &  newValue 
)
protectedvirtual

Fixes a variable.

If the variable which is currently fixed is already set then we must not change its bounds in the LP since it might be eliminated.

Parameters
iThe number of the variable being fixed.
newStatA pointer to an object storing the new status of the variable.
newValueIf the variable is fixed to a value different from the one of the last LP-solution, the argument newValue is set to true. Otherwise, it is set to false.
Returns
1 If a contradiction is found, 0 otherwise.

◆ fixAndSet()

virtual int abacus::Sub::fixAndSet ( bool &  newValues)
protectedvirtual

Tries to fix and set variables both by logical implications and reduced cost criteria.

Actually, variables fixed or set to 0 could be eliminated. However, this could lead to a loss of important structural information for fixing and setting further variables later, for the computation of feasible solutions, for the separation and for detecting contradictions. Therefore, we do not eliminate these variables per default.

Returns
1 If a contradiction is found, 0 otherwise.
Parameters
newValuesIf a variables is set or fixed to a value different from the last LP-solution, newValues is set to true, otherwise it is set to false.

◆ fixAndSetTime()

virtual bool abacus::Sub::fixAndSetTime ( )
inlineprotectedvirtual

Controls if variables should be fixed or set when all variables price out correctly.

The default implementation always returns true.

Returns
true If variables should be fixed and set, false otherwise.

Definition at line 1138 of file sub.h.

◆ fixByLogImp()

virtual void abacus::Sub::fixByLogImp ( ArrayBuffer< int > &  variables,
ArrayBuffer< FSVarStat * > &  status 
)
inlineprotectedvirtual

Should collect the numbers of the variables to be fixed in variable and the respective statuses in status.

Definition at line 1056 of file sub.h.

◆ fixByRedCost()

virtual int abacus::Sub::fixByRedCost ( bool &  newValues,
bool  saveCand 
)
protectedvirtual

Tries to fix variables according to the reduced cost criterion.

Parameters
newValuesIf variables are fixed to different values as in the last solved linear program, then newValues becomes true.
saveCandIf saveCand is true, then a new list of candidates for later calls is compiled. This is only possible when the root of the remaining branch-and-bound is processed.
Returns
1 If a contradiction is found, 0 otherwise.

◆ fixing()

virtual int abacus::Sub::fixing ( bool &  newValues,
bool  saveCand = false 
)
protectedvirtual

Tries to fix variables by reduced cost criteria and logical implications.

Parameters
newValuesThe parameter newValues becomes true if variables are fixed to other values as in the current LP-solution.
saveCandIf the parameter saveCand is true a new candidate list of variables for fixing is generated. The default value of saveCand is false. Candidates should not be saved if fixing is performed after the addition of variables.
Returns
1 If a contradiction is found, 0 otherwise.

◆ fixSetNewBound()

virtual double abacus::Sub::fixSetNewBound ( int  i)
privatevirtual

Returns the value which the upper and lower bounds of a variable should take after it is fixed or set.

◆ forceExactSolver()

bool abacus::Sub::forceExactSolver ( ) const
inline

Returns whether using the exact solver is forced.

Definition at line 147 of file sub.h.

◆ fsVarStat()

FSVarStat* abacus::Sub::fsVarStat ( int  i) const
inline

Returns a pointer to the status of fixing/setting of the i-th variable.

In a branch-and-cut-and-price algorithm we also would have to refer to the global variable status. While this subproblem is processed another subproblem could change the global status.

Note
This is the local status of fixing/setting that might differ from the global status of fixing/setting of the variable (variable(i)->fsVarStat()).
Parameters
iThe number of the variable.
Returns
A pointer to the status of fixing/setting of the i-th variable.

Definition at line 291 of file sub.h.

◆ generateBranchRules()

virtual int abacus::Sub::generateBranchRules ( ArrayBuffer< BranchRule * > &  rules)
inlineprotectedvirtual

Tries to find rules for splitting the current subproblem in further subproblems.

Per default we generate rules for branching on variables (branchingOnVariable()). But by redefining this function in a derived class any other branching strategy can be implemented.

Returns
0 If branching rules could be found, 1 otherwise.
Parameters
rulesIf branching rules are found, then they are stored in this buffer.

Definition at line 575 of file sub.h.

◆ generateLp()

virtual LpSub* abacus::Sub::generateLp ( )
protectedvirtual

Instantiates an LP for the solution of the LP-relaxation in this subproblem.

This function is redefined in a derived class for a specific LP-solver interface

This function is defined in the file lpif.cpp.

Returns
A pointer to an object of type LpSub.

◆ generateSon()

virtual Sub* abacus::Sub::generateSon ( BranchRule rule)
protectedpure virtual

Returns a pointer to an object of a problem specific subproblem, which is generated from the current subproblem by branching rule rule.

Parameters
ruleThe branching rule with which the subproblem is generated.

Implemented in ogdf::MinSteinerTreeDirectedCut< T >::Sub, ogdf::cluster_planarity::CPlanaritySub, and ogdf::cluster_planarity::MaxCPlanarSub.

◆ getBase()

virtual void abacus::Sub::getBase ( )
privatevirtual

Updates the status of the variables and the slack variables.

◆ goodCol()

virtual bool abacus::Sub::goodCol ( Column col,
Array< double > &  row,
double  x,
double  lb,
double  ub 
)
protectedvirtual
Parameters
colThe column of the variable.
rowThe row of the basis inverse associated with the infeasible variable.
xThe LP-value of the infeasible variable.
lbThe lower bound of the infeasible variable.
ubThe upper bound of the infeasible variable.
Returns
true If the column col might restore feasibiblity if the variable with value x turns out to be infeasible, false otherwise.

◆ guarantee()

virtual double abacus::Sub::guarantee ( ) const
protectedvirtual

May not be called if the lower bound is 0 and upper bound not equal to 0.

The guarantee that can be given for the subproblem.

◆ guaranteed()

virtual bool abacus::Sub::guaranteed ( ) const
protectedvirtual
Returns
true If the lower and the upper bound of the subproblem satisfies the guarantee requirements, false otherwise.

◆ id()

int abacus::Sub::id ( ) const
inline

Returns the identity number of the subproblem.

Definition at line 153 of file sub.h.

◆ ignoreInTailingOff()

void abacus::Sub::ignoreInTailingOff ( )

Can be used to control better the tailing-off effect.

If this function is called, the next LP-solution is ignored in the tailing-off control. Calling ignoreInTailingOff() can e.g. be considered in the following situation: If only constraints that are required for the integer programming formulation of the optimization problem are added then the next LP-value could be ignored in the tailing-off control. Only "real" cutting planes should be considered in the tailing-off control (this is only an example strategy that might not be practical in many situations, but sometimes turned out to be efficient).

◆ improve()

virtual int abacus::Sub::improve ( double &  primalValue)
protectedvirtual

Can be redefined in order to implement primal heuristics for finding feasible solutions.

The default implementation does nothing.

Returns
0 If no better solution could be found, 1 otherwise.
Parameters
primalValueShould hold the value of the feasible solution, if a better one is found.

Reimplemented in ogdf::cluster_planarity::MaxCPlanarSub, and ogdf::cluster_planarity::CPlanaritySub.

◆ infeasible()

bool abacus::Sub::infeasible ( )
protected

Returns true if the subproblem does not contain a feasible solution, false otherwise.

◆ infeasibleSub()

virtual void abacus::Sub::infeasibleSub ( )
privatevirtual

Should be called if a subproblem turns out to be infeasible.

It sets the dual bound of the subproblem correctly.

◆ initializeCons()

virtual void abacus::Sub::initializeCons ( int  maxCon)
protectedvirtual

Initializes the active constraint set.

Parameters
maxConThe maximal number of constraints of the subproblem.

◆ initializeLp()

virtual int abacus::Sub::initializeLp ( )
protectedvirtual

Initializes the linear program.

Since not all variables might be active we first have to try making the LP feasible again by the addition of variables. If this fails, i.e., _initMakeFeas() has a nonzero return value, we return 1 in order to indicate that the corresponding subproblem can be fathomed. Otherwise, we continue with the initialization of the LP.

Returns
0 If the linear program could be initialized successfully.
1 If the linear program turns out to be infeasible.

◆ initializeVars()

virtual void abacus::Sub::initializeVars ( int  maxVar)
protectedvirtual

Initializes the active variable set.

Parameters
maxVarThe maximal number of variables of the subproblem.

◆ initMakeFeas()

virtual int abacus::Sub::initMakeFeas ( ArrayBuffer< InfeasCon * > &  infeasCon,
ArrayBuffer< Variable * > &  newVars,
Pool< Variable, Constraint > **  pool 
)
inlineprotectedvirtual

The default implementation of the virtual initMakeFeas() does nothing.

A reimplementation of this function should generate inactive variables until at least one variable v which satisfies the function InfeasCon::goodVar(v) for each infeasible constraint is found.

Parameters
infeasConThe infeasible constraints.
newVarsThe variables that might restore feasibility should be added here.
poolA pointer to the pool to which the new variables should be added. If this is a 0-pointer the variables are added to the default variable pool. The default value is 0.
Returns
0 if the feasibility might have been restored, 1 otherwise.

Definition at line 797 of file sub.h.

◆ integerFeasible()

bool abacus::Sub::integerFeasible ( )
protected

Can be used to check if the solution of the LP-relaxation is primally feasible if integrality is suficinet.

Checks if all binary and integer variables have an integral value. This function can be called from the function feasible() in derived classes.

Returns
true If the LP-value of all binary and integer variables is integral, false otherwise.

◆ lBound() [1/2]

double abacus::Sub::lBound ( int  i) const
inline

Can be used to access the lower of an active variable of the subproblem.

Warning
This is the lower bound of the variable within the current subproblem which can differ from its global lower bound.
Parameters
iThe number of the variable.
Returns
The lower bound of the i-th variable.

Definition at line 245 of file sub.h.

◆ lBound() [2/2]

void abacus::Sub::lBound ( int  i,
double  l 
)
inline

Sets the local lower bound of variable i to l.

It does not change the global lower bound of the variable. The bound of a fixed or set variable should not be changed.

Parameters
iThe number of the variable.
lThe new value of the lower bound.

Definition at line 1907 of file sub.h.

◆ level()

int abacus::Sub::level ( ) const
inline

Returns the level of the subproblem in the branch-and-bound tree.

Definition at line 150 of file sub.h.

◆ lowerBound()

double abacus::Sub::lowerBound ( ) const
inline

Returns a lower bound on the optimal solution of the subproblem.

Definition at line 1873 of file sub.h.

◆ lp()

LpSub* abacus::Sub::lp ( ) const
inline

Returns a pointer to the linear program of the subproblem.

Definition at line 201 of file sub.h.

◆ lpRankBranchingRule()

double abacus::Sub::lpRankBranchingRule ( BranchRule branchRule,
int  iterLimit = -1 
)
protected

Computes the rank of a branching rule by modifying the linear programming relaxation of the subproblem according to the branching rule and solving it.

This modifiction is undone after the solution of the linear program.

It is useless, but no error, to call this function for branching rules for which the virtual dummy functions extract(LpSub*) and unExtract(LpSub*) of the base class BranchRule are not redefined.

Parameters
branchRuleA pointer to a branching rule.
iterLimitThe maximal number of iterations that should be performed by the simplex method. If this number is negative there is no iteration limit (besides internal limits of the LP-solver). The default value is -1.
Returns
The value of the linear programming relaxation of the subproblem modified by the branching rule.

◆ lpVarStat()

LPVARSTAT* abacus::Sub::lpVarStat ( int  i) const
inline

Returns a pointer to the status of the variable i in the last solved linear program.

Parameters
iThe number of the variable.

Definition at line 297 of file sub.h.

◆ makeFeasible()

virtual int abacus::Sub::makeFeasible ( )
inlineprotectedvirtual

The default implementation of makeFeasible()does nothing.

If there is an infeasible structural variable then it is stored in infeasVar_, otherwise infeasVar_ is -1. If there is an infeasible slack variable, it is stored in infeasCon_, otherwise it is -1. At most one of the two members infeasVar_ and infeasCon_ can be nonnegative. A reimplementation in a derived class should generate variables to restore feasibility or confirm that the subproblem is infeasible.

The strategy for the generation of inactive variables is completely problem and user specific. For testing if a variable might restore again the feasibility the functions Variable::useful() and Sub::goodCol() might be helpful.

Returns
0 If feasibility can be restored, 1 otherwise.

Reimplemented in ogdf::cluster_planarity::MaxCPlanarSub, and ogdf::cluster_planarity::CPlanaritySub.

Definition at line 822 of file sub.h.

◆ master() [1/2]

Master* abacus::Sub::master ( )
inline

Returns the master of the optimization.

Definition at line 320 of file sub.h.

◆ master() [2/2]

const Master* abacus::Sub::master ( ) const
inline

Returns the const master of the optimization.

Definition at line 323 of file sub.h.

◆ maxCon()

int abacus::Sub::maxCon ( ) const
inline

Returns the maximum number of constraints which can be handled without reallocation.

Definition at line 1853 of file sub.h.

◆ maxIterations()

void abacus::Sub::maxIterations ( int  max)

Sets the maximal number of iterations in the cutting plane phase.

Setting this value to 1 implies that no cuts are generated in the optimization process of the subproblem.

Parameters
maxThe maximal number of iterations.

◆ maxVar()

int abacus::Sub::maxVar ( ) const
inline

Returns the maximum number of variables which can be handled without reallocation.

Definition at line 1848 of file sub.h.

◆ nCon()

int abacus::Sub::nCon ( ) const
inline

Returns the number of active constraints.

Definition at line 1843 of file sub.h.

◆ nDormantRounds()

int abacus::Sub::nDormantRounds ( ) const
inline
Returns
The number of subproblem optimization the subproblem is already dormant.

Definition at line 408 of file sub.h.

◆ newDormantRound()

virtual void abacus::Sub::newDormantRound ( )
inlineprivatevirtual

Increments the counter for the number of rounds the subproblem is dormant.

This function is called, when the set of open subproblems is scanned for the selection of the next subproblem.

Definition at line 1611 of file sub.h.

◆ nnzReserve()

double abacus::Sub::nnzReserve ( ) const
inline

Returns the additional space for nonzero elements of the constraint matrix when it is passed to the LP-solver.

Definition at line 346 of file sub.h.

◆ nonBindingConEliminate()

virtual void abacus::Sub::nonBindingConEliminate ( ArrayBuffer< int > &  remove)
protectedvirtual

Retrieves the dynamic constraints with slack exceeding the value given by the parameter ConElimEps.

Parameters
removeStores the nonbinding constraints.

◆ nVar()

int abacus::Sub::nVar ( ) const
inline

Returns the number of active variables.

Definition at line 1838 of file sub.h.

◆ objAllInteger()

bool abacus::Sub::objAllInteger ( ) const

Tests if all active variables and objective function coefficients are integer.

If all variables are Binary or Integer and all objective function coefficients are integral, then all objective function values of feasible solutions are integral. The function objAllInteger() tests this condition for the current set of active variables.

Note
The result of this function can only be used to set the global parameter if actVar contains all variables of the problem formulation.
Returns
true If this condition is satisfied by the currently active variable set, false otherwise.

◆ operator=()

const Sub& abacus::Sub::operator= ( const Sub rhs)
private

◆ optimize()

virtual int abacus::Sub::optimize ( )
protectedvirtual

Performs the optimization of the subproblem.

After activating the subproblem, i.e., allocating and initializing memory, and initializing the LP, the optimization process constitutes of the three phases Cutting, Branching, and Fathoming, which are alternately processed. The function fathoming() always returns Done. However, we think that the code is better readable instead of taking it out of the while loop. The optimization stops if the PHASE Done is reached. Note, Done does not necessarily mean that the subproblem is solved to optimality!

After the node is processed we deallocate memory, which is not required for further computations or of which the corresponding data can be easily reconstructed. This is performed in _deactivate().

Returns
0 If the optimization has been performed without error, 1 otherwise.

Reimplemented in ogdf::cluster_planarity::MaxCPlanarSub, and ogdf::cluster_planarity::CPlanaritySub.

◆ pausing()

virtual bool abacus::Sub::pausing ( )
inlineprotectedvirtual

Sometimes it is appropriate to put a subproblem back into the list of open subproblems.

This is called pausing. In the default implementation the virtual function pausing() always returns false.

It could be useful to enforce pausing a node if a tailing off effect is observed during its first optimization.

Returns
true The function pausing() should return true if this condition is satisfied, false otherwise.

Definition at line 968 of file sub.h.

◆ prepareBranching()

virtual int abacus::Sub::prepareBranching ( bool &  lastIteration)
protectedvirtual

Is called before a branching step to remove constraints.

Returns
1 If constraints have been removed, 0 otherwise.
Parameters
lastIterationThis argument is always set to true in the function call.

◆ pricing()

virtual int abacus::Sub::pricing ( )
inlineprotectedvirtual

Should generate inactive variables which do not price out correctly.

The default implementation does nothing and returns 0.

Returns
The number of new variables.

Reimplemented in ogdf::cluster_planarity::MaxCPlanarSub, and ogdf::cluster_planarity::CPlanaritySub.

Definition at line 934 of file sub.h.

◆ primalSeparation()

virtual bool abacus::Sub::primalSeparation ( )
protectedvirtual

Controls if during the cutting plane phase a (primal) separation step or a pricing step (dual separation) should be performed.

Per default a pure cutting plane algorithm performs always a primal separation step, a pure column generation algorithm never performs a primal separation, and a hybrid algorithm generates usually cutting planes but from time to time also inactive variables are priced out depending on the pricingFrequency().

Returns
true Then cutting planes are generated in this iteration.
false Then columns are generated in this iteration.

◆ rankBranchingRule()

double abacus::Sub::rankBranchingRule ( BranchRule branchRule)
inlineprotectedvirtual

Computes the rank of a branching rule.

This default implementation computes the rank with the function lpRankBranchingRule(). By redefining this virtual function the rank for a branching rule can be computed differently.

Parameters
branchRuleA pointer to a branching rule.
Returns
The rank of the branching rule.

Definition at line 1868 of file sub.h.

◆ rankBranchingSample()

virtual void abacus::Sub::rankBranchingSample ( ArrayBuffer< BranchRule * > &  sample,
Array< double > &  rank 
)
protectedvirtual

Computes for each branching rule of a branching sample a rank with the function rankBranchingRule().

Parameters
sampleA branching sample.
rankAn array storing the rank for each branching rule in the sample after the function call.

◆ redCostVarEliminate()

void abacus::Sub::redCostVarEliminate ( ArrayBuffer< int > &  remove)
protected

Retrieves all variables with "wrong" reduced costs.

Parameters
removeThe variables with "wrong" reduced cost are stored in this buffer.

◆ relativeReserve()

bool abacus::Sub::relativeReserve ( ) const
inline
Returns
true If the reserve space for variables, constraints, and nonzeros is given in percent of the original space, and false if its given as absolute value.

Definition at line 352 of file sub.h.

◆ removeCon()

void abacus::Sub::removeCon ( int  i)
inlinevirtual

Adds a single constraint to the set of constraints which are removed from the active set at the beginning of the next iteration.

Parameters
iThe number of the constraint being removed.

Definition at line 1902 of file sub.h.

◆ removeCons()

virtual void abacus::Sub::removeCons ( ArrayBuffer< int > &  remove)
virtual

Adds constraints to the buffer of the removed constraints.

These will be removed at the beginning of the next iteration of the cutting plane algorithm.

Parameters
removeThe constraints which should be removed.

◆ removeNonLiftableCons()

virtual bool abacus::Sub::removeNonLiftableCons ( )
protectedvirtual
Returns
true If all active constraints can be lifted.
false otherwise. In this case the non-liftable constraints are removed and genNonLiftCons_ is set to false to avoid the generation of non-liftable constraints in the next cutting plane iterations.

◆ removeVar()

void abacus::Sub::removeVar ( int  i)
inline

Remove variable i from the set of active variables.

Like in the function removeVars() the variable is buffered and removed at the beginning of the next iteration.

Parameters
iThe variable which should be removed.

Definition at line 343 of file sub.h.

◆ removeVars()

void abacus::Sub::removeVars ( ArrayBuffer< int > &  remove)

Removes the variables in remove from the set of active variables.

The variables are not removed when this function is called, but are buffered and removed at the beginning of the next iteration.

Parameters
removeThe variables which should be removed.

◆ reoptimize()

virtual void abacus::Sub::reoptimize ( )
protectedvirtual

Repeats the optimization of an already optimized subproblem.

This function is used to determine the reduced costs for fixing variables of a new root of the remaining branch-and-bound tree.

As the subproblem has been processed already earlier it is sufficient to perform the cutting plane algorithm. If the subproblem is fathomed the complete subtree rooted at this subproblem can be fathomed, too. Since this function is usually only called for the root of the remaining branch-and-bound tree, we are done in this case.

It is not guaranteed that all constraints and variables of this subproblem can be regenerated in _activate(). Therefore, the result of a call to reoptimize() can differ from the result obtained by the cutting plane algorithm in optimize().

◆ selectBestBranchingSample()

virtual int abacus::Sub::selectBestBranchingSample ( int  nSamples,
ArrayBuffer< BranchRule * > **  samples 
)
protectedvirtual

Evaluates branching samples.

We denote a branching sample the set of rules defining all sons of a subproblem in the enumeration tree). For each sample the ranks are determined with the function rankBranchingSample(). The ranks of the various samples are compared with the function compareBranchingSample().

Parameters
nSamplesThe number of branching samples.
samplesAn array of pointer to buffers storing the branching rules of each sample.
Returns
The number of the best branching sample, or -1 in case of an internal error.

◆ selectBranchingVariable()

virtual int abacus::Sub::selectBranchingVariable ( int &  variable)
protectedvirtual

Chooses a branching variable.

The function selectBranchingVariableCandidates() is asked to generate depending in the parameter NBranchingVariableCandidates of the file .abacus candidates for branching variables. If only one candidate is generated, this one becomes the branching variable. Otherwise, the pairs of branching rules are generated for all candidates and the "best" branching variables is determined with the function selectBestBranchingSample().

Parameters
variableHolds the branching variable if one is found.
Returns
0 If a branching variable is found, 1 otherwise.

Reimplemented in ogdf::cluster_planarity::MaxCPlanarSub, and ogdf::cluster_planarity::CPlanaritySub.

◆ selectBranchingVariableCandidates()

virtual int abacus::Sub::selectBranchingVariableCandidates ( ArrayBuffer< int > &  candidates)
protectedvirtual

Selects candidates for branching variables.

Candidates are selected depending on the branching variable strategy given by the parameter BranchingStrategy in the file .abacus candidates that for branching variables.

Currently two branching variable selection strategies are implemented. The first one (CloseHalf) first searches the binary variables with fractional part closest to \(0.5\). If there is no fractional binary variable it repeats this process with the integer variables.

The second strategy (CloseHalfExpensive) first tries to find binary variables with fraction close to \(0.5\) and high absolute objective function coefficient. If this fails, it tries to find an integer variable with fractional part close to \(0.5\) and high absolute objective function coefficient.

If neither a binary nor an integer variable with fractional value is found then for both strategies we try to find non-fixed and non-set binary variables. If this fails we repeat this process with the integer variables.

Other branching variable selection strategies can be implemented by redefining this virtual function in a derived class.

Parameters
candidatesThe candidates for branching variables are stored in this buffer. We try to find as many variables as fit into the buffer.
Returns
0 If a candidate is found, 1 otherwise.

Reimplemented in ogdf::cluster_planarity::MaxCPlanarSub, and ogdf::cluster_planarity::CPlanaritySub.

◆ selectCons()

virtual void abacus::Sub::selectCons ( )
inlineprotectedvirtual

Is called before constraint are selected from the constraint buffer.

It can be redefined in a derived class e.g., to remove multiply inserted constraints from the buffer.

Definition at line 1031 of file sub.h.

◆ selectVars()

virtual void abacus::Sub::selectVars ( )
inlineprotectedvirtual

Is called before variables are selected from the variable buffer.

It can be redefined in a derived class e.g., to remove multiply inserted variables from the buffer.

Definition at line 1024 of file sub.h.

◆ separate()

virtual int abacus::Sub::separate ( )
protectedvirtual

Must be redefined in derived classes for the generation of cutting planes.

The default implementation does nothing.

Returns
The number of generated cutting planes.

Reimplemented in ogdf::MinSteinerTreeDirectedCut< T >::Sub, ogdf::cluster_planarity::MaxCPlanarSub, and ogdf::cluster_planarity::CPlanaritySub.

◆ set() [1/3]

virtual int abacus::Sub::set ( int  i,
FSVarStat newStat,
bool &  newValue 
)
protectedvirtual

Sets a variable.

Parameters
iThe number of the variable being set.
newStatA pointer to the object storing the new status of the the variable.
newValueIf the variable is set to a value different from the one of the last LP-solution, newValue is set to true. Otherwise, it is set to false.
Returns
1 If a contradiction is found, 0 otherwise.

◆ set() [2/3]

virtual int abacus::Sub::set ( int  i,
FSVarStat::STATUS  newStat,
bool &  newValue 
)
protectedvirtual

Sets a variable.

Parameters
iThe number of the variable being set.
newStatThe new status of the variable.
newValueIf the variable is set to a value different from the one of the last LP-solution, newValue is set to true. Otherwise, it is set to false.
Returns
1 If a contradiction is found, 0 otherwise.

◆ set() [3/3]

virtual int abacus::Sub::set ( int  i,
FSVarStat::STATUS  newStat,
double  value,
bool &  newValue 
)
protectedvirtual

Sets a variable.

Parameters
iThe number of the variable being set.
newStatThe new status of the variable.
valueThe value the variable is set to.
newValueIf the variable is set to a value different from the one of the last LP-solution, newValue is set to true. Otherwise, it is set to false.
Returns
1 If a contradiction is found, 0 otherwise.

◆ setByLogImp()

virtual void abacus::Sub::setByLogImp ( ArrayBuffer< int > &  variable,
ArrayBuffer< FSVarStat * > &  status 
)
inlineprotectedvirtual

The default implementation of setByLogImp() does nothing.

In derived classes this function can be reimplemented.

Parameters
variableThe variables which should be set have to be inserted in this buffer.
statusThe status of the set variables.

Definition at line 845 of file sub.h.

◆ setByRedCost()

virtual int abacus::Sub::setByRedCost ( )
protectedvirtual

Tries to set variables according to the reduced cost criterion.

Returns
1 If a contradiction is found, 0 otherwise.

◆ setting()

virtual int abacus::Sub::setting ( bool &  newValues)
protectedvirtual

Tries to set variables by reduced cost criteria and logical implications like fixing().

But instead of global conditions only locally valid conditions have to be satisfied.

Parameters
newValuesThe parameter newValues becomes true if variables are fixed to other values as in the current LP-solution (setByRedCost() cannot set variables to new values).
Returns
1 If a contradiction has been found, 0 otherwise.

◆ slackStat()

SlackStat* abacus::Sub::slackStat ( int  i) const
inline

Returns a pointer to the status of the slack variable i in the last solved linear program.

Parameters
iThe number of the slack variable.

Definition at line 228 of file sub.h.

◆ solveApproxNow()

virtual bool abacus::Sub::solveApproxNow ( )
inlineprotectedvirtual

The default implementation always returns false.

Returns
True, if the approximative solver should be used to solve the next linear program, false otherwise.

Definition at line 1432 of file sub.h.

◆ solveLp()

virtual int abacus::Sub::solveLp ( )
protectedvirtual

Solves the LP-relaxation of the subproblem.

As soon as the LP-relaxation becomes infeasible in a static branch and cut algorithm the respective subproblem can be fathomed. Otherwise, we memorize the value of the LP-solution to control the tailing off effect.

We assume that the LP is never primal unbounded.

Returns
0 The linear program has an optimimal solution.
1 If the linear program is infeasible.
2 If the linear program is infeasible for the current variable set, but non-liftable constraints have to be removed before a pricing step can be performed.

Reimplemented in ogdf::cluster_planarity::MaxCPlanarSub, and ogdf::cluster_planarity::CPlanaritySub.

◆ status()

STATUS abacus::Sub::status ( ) const
inline

Returns the status of the subproblem optimization.

Definition at line 156 of file sub.h.

◆ tailingOff()

virtual bool abacus::Sub::tailingOff ( )
inlineprotectedvirtual

Called when a tailing off effect according to the parameters TailOffPercent and TailOffNLps is observed.

This function can be redefined in derived classes in order to perform actions to resolve the tailing off (e.g., switching on an enhanced separation strategy).

Returns
true If a branching step should be enforced. But before branching a pricing operation is perfored. The branching step is only performed if no variables are added. Otherwise, the cutting plane algorithm is continued.
false If the cutting plane algorithm should be continued.

Definition at line 1014 of file sub.h.

◆ uBound() [1/2]

double abacus::Sub::uBound ( int  i) const
inline

Can be used to access the upper of an active variable of the subproblem.

Warning
This is the upper bound of the variable within the current subproblem which can differ from its global upper bound.
Parameters
iThe number of the variable.
Returns
The upper bound of the i-th variable.

Definition at line 266 of file sub.h.

◆ uBound() [2/2]

void abacus::Sub::uBound ( int  i,
double  u 
)
inline

Sets the local upper bound of variable i to u.

This does not change the global lower bound of the variable. The bound of a fixed or set variable should not be changed.

Parameters
iThe number of the variable.
uThe new value of the upper bound.

Definition at line 1914 of file sub.h.

◆ updateBoundInLp()

virtual void abacus::Sub::updateBoundInLp ( int  i)
privatevirtual

Adapts the bound of a fixed or set variable i also in the linear program.

This can be only done if a linear program is available and the variable is not eliminated.

◆ upperBound()

double abacus::Sub::upperBound ( ) const
inline

Returns an upper bound on the optimal solution of the subproblem.

Definition at line 1881 of file sub.h.

◆ varEliminate()

virtual void abacus::Sub::varEliminate ( ArrayBuffer< int > &  remove)
protectedvirtual

Entry point for application specific variable elimination.

The default implementation selects the variables with the function redCostVarEliminate().

Parameters
removeThe variables that should be removed have to be stored in this buffer.

◆ variable()

Variable * abacus::Sub::variable ( int  i) const
inline

Returns a pointer to the i-th active variable.

Parameters
iThe number of the variable being accessed.

Definition at line 1863 of file sub.h.

◆ variablePoolSeparation()

virtual int abacus::Sub::variablePoolSeparation ( int  ranking = 0,
Pool< Variable, Constraint > *  pool = nullptr,
double  minViolation = 0.001 
)
protectedvirtual

Tries to generate inactive variables from a pool.

Parameters
rankingThis parameter indicates how the ranks of geneated variables should be computed (0: no ranking; 1: violation is rank, 2: absolute value of violation is rank 3: rank determined by ConVar::rank()). The default value is 0.
poolThe pool the variables are generated from. If pool is 0, then the default variable pool is used. The default value of pool is 0.
minViolationA violated constraint/variable is only added if the absolute value of its violation is at least minAbsViolation. The default value is 0.001.
Returns
The number of generated variables.

◆ varRealloc()

virtual void abacus::Sub::varRealloc ( int  newSize)
protectedvirtual

Reallocates memory that at most newSize variables can be handled in the subproblem.

Parameters
newSizeThe new maximal number of variables in the subproblem.

◆ xVal()

double abacus::Sub::xVal ( int  i) const
inline

Returns the value of the i-th variable in the last solved linear program.

Parameters
iThe number of the variable under consideration.

Definition at line 303 of file sub.h.

◆ yVal()

double abacus::Sub::yVal ( int  i) const
inline

Returns the value of the i-th dual variable in the last solved linear program.

Parameters
iThe number of the variable under consideration.

Definition at line 309 of file sub.h.

Friends And Related Function Documentation

◆ BoundBranchRule

friend class BoundBranchRule
friend

Definition at line 71 of file sub.h.

◆ LpSolution< Constraint, Variable >

friend class LpSolution< Constraint, Variable >
friend

Definition at line 73 of file sub.h.

◆ LpSolution< Variable, Constraint >

friend class LpSolution< Variable, Constraint >
friend

Definition at line 74 of file sub.h.

◆ Master

friend class Master
friend

Definition at line 70 of file sub.h.

◆ OpenSub

friend class OpenSub
friend

Definition at line 72 of file sub.h.

Member Data Documentation

◆ actCon_

Active<Constraint, Variable>* abacus::Sub::actCon_
protected

The active constraints of the subproblem.

Definition at line 1439 of file sub.h.

◆ activated_

bool abacus::Sub::activated_
private

The variable is true if the function activate() has been called from the function _activate().

This memorization is required such that a deactivate() is only called when activate() has been called.

Definition at line 1790 of file sub.h.

◆ actVar_

Active<Variable, Constraint>* abacus::Sub::actVar_
protected

The active variables of the subproblem.

Definition at line 1442 of file sub.h.

◆ addConBuffer_

CutBuffer<Constraint, Variable>* abacus::Sub::addConBuffer_
protected

The buffer of the newly generated constraints.

Definition at line 1503 of file sub.h.

◆ addVarBuffer_

CutBuffer<Variable, Constraint>* abacus::Sub::addVarBuffer_
protected

The buffer of the newly generated variables.

Definition at line 1500 of file sub.h.

◆ allBranchOnSetVars_

bool abacus::Sub::allBranchOnSetVars_
protected

If true, then the branching rule of the subproblem and of all ancestor on the path to the root node are branching on a binary variable.

Definition at line 1494 of file sub.h.

◆ bInvRow_

double* abacus::Sub::bInvRow_
protected

A row of the basis inverse associated with the infeasible variable infeasVar_ or slack variable infeasCon_.

Definition at line 1518 of file sub.h.

◆ branchRule_

BranchRule* abacus::Sub::branchRule_
protected

The branching rule for the subproblem.

Definition at line 1488 of file sub.h.

◆ conReserve_

double abacus::Sub::conReserve_
private

The additional space for constraints.

Definition at line 1777 of file sub.h.

◆ dualBound_

double abacus::Sub::dualBound_
protected

The dual bound of the subproblem.

Definition at line 1476 of file sub.h.

◆ father_

Sub* abacus::Sub::father_
protected

A pointer to the father in the branch-and-cut tree.

Definition at line 1445 of file sub.h.

◆ forceExactSolver_

bool abacus::Sub::forceExactSolver_
private

Indicates whether to force the use of an exact solver to prepare branching etc.

Definition at line 1805 of file sub.h.

◆ fsVarStat_

Array<FSVarStat*>* abacus::Sub::fsVarStat_
protected

A pointer to an array storing the status of fixing and setting of the active variables.

Although fixed and set variables are already kept at their value by the adaption of the lower and upper bounds, we store this information, since, e.g., a fixed or set variable should not be removed, but a variable with an upper bound equal to the lower bound can be removed.

Definition at line 1458 of file sub.h.

◆ genNonLiftCons_

bool abacus::Sub::genNonLiftCons_
protected

If true, then the management of non-liftable constraints is performed.

Definition at line 1527 of file sub.h.

◆ id_

int abacus::Sub::id_
private

The number of the subproblem.

Definition at line 1749 of file sub.h.

◆ ignoreInTailingOff_

bool abacus::Sub::ignoreInTailingOff_
private

If this flag is set to true then the next LP-solution is ignored in the tailing-off control.

The default value of the variable is false. It can be set to true by the function ignoreInTailingOff().

Definition at line 1797 of file sub.h.

◆ infeasCon_

int abacus::Sub::infeasCon_
protected

The number of an infeasible constraint.

Definition at line 1521 of file sub.h.

◆ infeasVar_

int abacus::Sub::infeasVar_
protected

The number of an infeasible variable.

Definition at line 1524 of file sub.h.

◆ lastIterConAdd_

int abacus::Sub::lastIterConAdd_
protected

The last iteration in which constraints have been added.

Definition at line 1482 of file sub.h.

◆ lastIterVarAdd_

int abacus::Sub::lastIterVarAdd_
protected

The last iteration in which variables have been added.

Definition at line 1485 of file sub.h.

◆ lastLP_

LP::METHOD abacus::Sub::lastLP_
private

The method that was used to solve the last LP.

Definition at line 1800 of file sub.h.

◆ lBound_

Array<double>* abacus::Sub::lBound_
protected

A pointer to an array with the local lower bound of the active variables.

Definition at line 1464 of file sub.h.

◆ level_

int abacus::Sub::level_
private

The level of the subproblem in the enumeration tree.

Definition at line 1746 of file sub.h.

◆ localTimer_

ogdf::StopwatchCPU abacus::Sub::localTimer_
private

Definition at line 1802 of file sub.h.

◆ lp_

LpSub* abacus::Sub::lp_
protected

A pointer to the corresponding linear program.

Definition at line 1448 of file sub.h.

◆ lpMethod_

LP::METHOD abacus::Sub::lpMethod_
protected

The solution method for the next linear program.

Definition at line 1497 of file sub.h.

◆ lpVarStat_

Array<LPVARSTAT*>* abacus::Sub::lpVarStat_
protected

A pointer to an array storing the status of each active variable in the linear program.

Definition at line 1461 of file sub.h.

◆ master_

Master* abacus::Sub::master_
protected

A pointer to the corresponding master of the optimization.

Definition at line 1436 of file sub.h.

◆ maxIterations_

int abacus::Sub::maxIterations_
private

The maximum number of iterations in the cutting plane phase.

Definition at line 1758 of file sub.h.

◆ nDormantRounds_

int abacus::Sub::nDormantRounds_
private

The number of subproblem optimizations the subproblem has already the status Dormant.

Definition at line 1783 of file sub.h.

◆ nIter_

int abacus::Sub::nIter_
protected

The number of iterations in the cutting plane phase.

Definition at line 1479 of file sub.h.

◆ nnzReserve_

double abacus::Sub::nnzReserve_
private

The additional space for nonzeros.

Definition at line 1780 of file sub.h.

◆ nOpt_

int abacus::Sub::nOpt_
private

The number of optimizations of the subproblem.

Definition at line 1761 of file sub.h.

◆ relativeReserve_

bool abacus::Sub::relativeReserve_
private

If this member is true then the space reserve of the following three members varReserve_, conReserve_, and nnzReserve_ is relative to the initial numbers of constraints, variables, and nonzeros, respectively.

Otherwise, the values are casted to integers and regarded as absolute values.

Definition at line 1771 of file sub.h.

◆ removeConBuffer_

ArrayBuffer<int>* abacus::Sub::removeConBuffer_
protected

The buffer of the constraints which are removed at the beginning of the next iteration.

Definition at line 1509 of file sub.h.

◆ removeVarBuffer_

ArrayBuffer<int>* abacus::Sub::removeVarBuffer_
protected

The buffer of the variables which are removed at the beginning of the next iteration.

Definition at line 1506 of file sub.h.

◆ slackStat_

Array<SlackStat*>* abacus::Sub::slackStat_
protected

A pointer to an array storing the statuses of the slack variables of the last solved linear program.

Definition at line 1470 of file sub.h.

◆ sons_

ArrayBuffer<Sub*>* abacus::Sub::sons_
private

The sons of the node in the branch-and-cut tree.

Definition at line 1755 of file sub.h.

◆ status_

STATUS abacus::Sub::status_
private

The status of the subproblem.

Definition at line 1752 of file sub.h.

◆ tailOff_

TailOff* abacus::Sub::tailOff_
protected

A pointer to the tailing off manager.

Definition at line 1473 of file sub.h.

◆ uBound_

Array<double>* abacus::Sub::uBound_
protected

A pointer to an array with the local upper bounds of the active variables.

Definition at line 1467 of file sub.h.

◆ varReserve_

double abacus::Sub::varReserve_
private

The additional space for variables.

Definition at line 1774 of file sub.h.

◆ xVal_

double* abacus::Sub::xVal_
protected

The last LP-solution.

Definition at line 1512 of file sub.h.

◆ yVal_

double* abacus::Sub::yVal_
protected

The dual variables of the last linear program.

Definition at line 1515 of file sub.h.


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