The subproblem. More...
#include <ogdf/lib/abacus/sub.h>
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 nonroot 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...  
BranchRule *  branchRule () const 
Returns a pointer to the branching rule of the subproblem. More...  
Constraint *  constraint (int i) const 
Returns a pointer to the ith 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 Sub *  father () const 
Returns a pointer to the father of the subproblem in the branchandbound tree. More...  
bool  forceExactSolver () const 
Returns whether using the exact solver is forced. More...  
FSVarStat *  fsVarStat (int i) const 
Returns a pointer to the status of fixing/setting of the ith variable. More...  
int  id () const 
Returns the identity number of the subproblem. More...  
void  ignoreInTailingOff () 
Can be used to control better the tailingoff 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 branchandbound tree. More...  
double  lowerBound () const 
Returns a lower bound on the optimal solution of the subproblem. More...  
LpSub *  lp () const 
Returns a pointer to the linear program of the subproblem. More...  
LPVARSTAT *  lpVarStat (int i) const 
Returns a pointer to the status of the variable i in the last solved linear program. More...  
Master *  master () 
Returns the master of the optimization. More...  
const Master *  master () 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 LPsolver. 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...  
SlackStat *  slackStat (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...  
Variable *  variable (int i) const 
Returns a pointer to the ith active variable. More...  
double  xVal (int i) const 
Returns the value of the ith variable in the last solved linear program. More...  
double  yVal (int i) const 
Returns the value of the ith 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 LPrelaxation, 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 LPrelaxation. 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 LpSub *  generateLp () 
Instantiates an LP for the solution of the LPrelaxation in this subproblem. More...  
virtual Sub *  generateSon (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 LPrelaxation 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 LPrelaxation 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...  
BranchRule *  branchRule_ 
The branching rule for the subproblem. More...  
double  dualBound_ 
The dual bound of the subproblem. More...  
Sub *  father_ 
A pointer to the father in the branchandcut 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 nonliftable 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...  
LpSub *  lp_ 
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...  
Master *  master_ 
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...  
TailOff *  tailOff_ 
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 LPsolution. 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 Sub &  operator= (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 LPsolution is ignored in the tailingoff 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 branchandcut 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...  
The subproblem.
This class implements an abstract base class for a subproblem of the enumeration, i.e., a node of the branchandbound 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.
enum abacus::Sub::PHASE 
The optimization of the subproblem can be in one of the following phases.
enum abacus::Sub::STATUS 
A subproblem can have different statuses.
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.
master  A pointer to the corresponding master of the optimization. 
conRes  The additional memory allocated for constraints. 
varRes  The additional memory allocated for variables. 
nnzRes  The additional memory allocated for nonzero elements of the constraint matrix. 
relativeRes  If 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. 
constraints  The 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. 
variables  The 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. 
abacus::Sub::Sub  (  Master *  master, 
Sub *  father,  
BranchRule *  branchRule  
) 
Creates a nonroot node of the enumeration tree.
master  A pointer to the corresponding master of the optimization. 
father  A pointer to the father in the enumeration tree. 
branchRule  The rule defining the subspace of the solution space associated with this subproblem. 

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.

private 

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 linearprogramming based branchandbound in mind, we keep this function.

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

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

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.

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 linearprogramming based branchandbound in mind, we keep this function.

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.

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.

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.

privatevirtual 

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, nonliftable constraints have to be removed, and 0 if the LPsolution 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().

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

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

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

privatevirtual 
Selects the master_>maxVarAdd() best variables from the buffered variables.
newVars  Holds the selected variables after the call. 

privatevirtual 
Returns the number of generated cutting planes.

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.

privatevirtual 
Returns the number of eliminated variables.
Only dynamic variables can be eliminated.

inline 

inlineprotectedvirtual 

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.

inline 

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().
slot  A pointer to the pool slot containing the branching constraint. 

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.

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.
constraints  The new constraints. 
pool  The 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. 
keepInPool  If (*keepInPool)[i] is true, then the constraint stays in the pool even if it is not activated. The default value is a 0pointer. 
rank  If 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. 

protectedvirtual 
Adds constraints to the active constraints and the linear program.
newCons  A buffer storing the pool slots of the new constraints. 

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.

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.
newVars  A buffer storing the pool slots of the new variables. 

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.
variables  The new variables. 
pool  The 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. 
keepInPool  If (*keepInPool)[i] is true, then the variable stays in the pool even if it is not activated. The default value is a 0pointer. 
rank  If 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. 

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.
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.
sub  A pointer to a subproblem. 

protectedvirtual 
Retrieves all dynamic constraints having basic slack variable.
remove  Stores the nonbinding constraints. 

inlineprotected 

inlineprotected 

protectedvirtual 
Performs branching.
Is called if the global lower bound of a branchandcut 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 branchandcut nodes without generating sons of this node.
Finally if none of the previous conditions is satisfied we generate new subproblems.

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.
rules  If 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. 

inline 

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.
nVarRemoved  The number of removed variables. 
nConRemoved  The number of removed constraints. 
nVarAdded  The number of added variables. 
nConAdded  The number of added constraint. 

protected 
Searches searches several possible branching variable of type branchVarType, with fraction as close to \(0.5\) as possible.
branchVar  Stores the possible branching variables. 
branchVarType  The type of the branching variable can berestricted either to VarType::Binary or VarType::Integer. 

protected 
Searches a branching variable of type branchVarType, with fraction as close to \(0.5\) as possible.
branchVar  Holds the branching variable if one is found. 
branchVarType  The type of the branching variable can be restricted either to VarType::Binary or VarType::Integer. 

protected 
Selects several candidates for branching variables of 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.
branchVar  Holds the number of the branching variable if one is found. 
branchVarType  The type of the branching variable can be restricted either to VarType::Binary or VarType::Integer. 

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.

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.
remove  The constraints that should be eliminated must be inserted in this buffer. 

protectedvirtual 
Reallocates memory that at most newSize constraints can be handled in the subproblem.
newSize  The new maximal number of constraints of the subproblem. 

inline 

protectedvirtual 
Tries to generate inactive constraints from a pool.
ranking  This 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. 
pool  The pool the constraints are generated from. If pool is 0, then the default constraint pool is used. The default value of pool is 0. 
minViolation  A violated constraint/variable is only added if the absolute value of its violation is at least minAbsViolation. The default value is 0.001. 

protectedvirtual 
Iteratively solves the LPrelaxation, 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.

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

inline 
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.
x  The new value of the dual bound. 

protectedvirtual 
x  The value that should be rounded if possible. 

inlineprotectedvirtual 

inlineprotectedvirtual 

inline 

protectedvirtual 
Fathoms a node and recursively tries to fathom its father.
If the root of the remaining branchandcut 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 branchandcut tree and only one of its sons is unfathomed, then this unfathomed son becomes the new root of the remaining branchandcut tree.
We could stop the recursive fathoming already at the root of the remaining branchandcut tree. But, we proceed until the root of the complete tree was visited to be really correct.
reoptimize  If 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(). 

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 LPrelaxation turns out to be infeasible.
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).

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.

protectedpure virtual 
Must check the feasibility of a solution of the LPrelaxation.
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.
Implemented in ogdf::MinSteinerTreeDirectedCut< T >::Sub, ogdf::cluster_planarity::MaxCPlanarSub, and ogdf::cluster_planarity::CPlanaritySub.

protected 
Selects the first variables that are neither fixed nor set.
branchVar  Holds the number of the possible branching variables if one is found. 
branchVarType  The type of the branching variable can be restricted either to VarType::Binary or VarType::Integer. 

protected 
Selects the first variable that is neither fixed nor set.
branchVar  Holds the number of the branching variable if one is found. 
branchVarType  The type of the branching have (VarType::Binary or VarType::Integer). 

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.
i  The number of the variable being fixed. 
newStat  A pointer to an object storing the new status of the variable. 
newValue  If the variable is fixed to a value different from the one of the last LPsolution, the argument newValue is set to true. Otherwise, it is set to false. 

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.
newValues  If a variables is set or fixed to a value different from the last LPsolution, newValues is set to true, otherwise it is set to false. 

inlineprotectedvirtual 

inlineprotectedvirtual 

protectedvirtual 
Tries to fix variables according to the reduced cost criterion.
newValues  If variables are fixed to different values as in the last solved linear program, then newValues becomes true. 
saveCand  If saveCand is true, then a new list of candidates for later calls is compiled. This is only possible when the root of the remaining branchandbound is processed. 

protectedvirtual 
Tries to fix variables by reduced cost criteria and logical implications.
newValues  The parameter newValues becomes true if variables are fixed to other values as in the current LPsolution. 
saveCand  If 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. 

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

inline 

inline 
Returns a pointer to the status of fixing/setting of the ith variable.
In a branchandcutandprice algorithm we also would have to refer to the global variable status. While this subproblem is processed another subproblem could change the global status.
i  The number of the variable. 

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.
rules  If branching rules are found, then they are stored in this buffer. 

protectedvirtual 

protectedpure virtual 
Returns a pointer to an object of a problem specific subproblem, which is generated from the current subproblem by branching rule rule.
rule  The branching rule with which the subproblem is generated. 
Implemented in ogdf::MinSteinerTreeDirectedCut< T >::Sub, ogdf::cluster_planarity::CPlanaritySub, and ogdf::cluster_planarity::MaxCPlanarSub.

privatevirtual 
Updates the status of the variables and the slack variables.

protectedvirtual 
col  The column of the variable. 
row  The row of the basis inverse associated with the infeasible variable. 
x  The LPvalue of the infeasible variable. 
lb  The lower bound of the infeasible variable. 
ub  The upper bound of the infeasible variable. 

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.

protectedvirtual 

inline 
void abacus::Sub::ignoreInTailingOff  (  ) 
Can be used to control better the tailingoff effect.
If this function is called, the next LPsolution is ignored in the tailingoff 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 LPvalue could be ignored in the tailingoff control. Only "real" cutting planes should be considered in the tailingoff control (this is only an example strategy that might not be practical in many situations, but sometimes turned out to be efficient).

protectedvirtual 
Can be redefined in order to implement primal heuristics for finding feasible solutions.
The default implementation does nothing.
primalValue  Should hold the value of the feasible solution, if a better one is found. 
Reimplemented in ogdf::cluster_planarity::MaxCPlanarSub, and ogdf::cluster_planarity::CPlanaritySub.

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

privatevirtual 
Should be called if a subproblem turns out to be infeasible.
It sets the dual bound of the subproblem correctly.

protectedvirtual 
Initializes the active constraint set.
maxCon  The maximal number of constraints of the subproblem. 

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.

protectedvirtual 
Initializes the active variable set.
maxVar  The maximal number of variables of the subproblem. 

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.
infeasCon  The infeasible constraints. 
newVars  The variables that might restore feasibility should be added here. 
pool  A pointer to the pool to which the new variables should be added. If this is a 0pointer the variables are added to the default variable pool. The default value is 0. 

protected 
Can be used to check if the solution of the LPrelaxation 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.

inline 
Can be used to access the lower of an active variable of the subproblem.
i  The number of the variable. 

inline 

inline 

inline 

inline 

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.
branchRule  A pointer to a branching rule. 
iterLimit  The 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 LPsolver). The default value is 1. 

inline 

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.
Reimplemented in ogdf::cluster_planarity::MaxCPlanarSub, and ogdf::cluster_planarity::CPlanaritySub.

inline 

inline 

inline 
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.
max  The maximal number of iterations. 

inline 

inline 

inline 

inlineprivatevirtual 

inline 

protectedvirtual 
Retrieves the dynamic constraints with slack exceeding the value given by the parameter ConElimEps
.
remove  Stores the nonbinding constraints. 

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

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().
Reimplemented in ogdf::cluster_planarity::MaxCPlanarSub, and ogdf::cluster_planarity::CPlanaritySub.

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.

protectedvirtual 
Is called before a branching step to remove constraints.
lastIteration  This argument is always set to true in the function call. 

inlineprotectedvirtual 
Should generate inactive variables which do not price out correctly.
The default implementation does nothing and returns 0.
Reimplemented in ogdf::cluster_planarity::MaxCPlanarSub, and ogdf::cluster_planarity::CPlanaritySub.

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

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.
branchRule  A pointer to a branching rule. 

protectedvirtual 
Computes for each branching rule of a branching sample a rank with the function rankBranchingRule().
sample  A branching sample. 
rank  An array storing the rank for each branching rule in the sample after the function call. 

protected 
Retrieves all variables with "wrong" reduced costs.
remove  The variables with "wrong" reduced cost are stored in this buffer. 

inline 

inlinevirtual 

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.
remove  The constraints which should be removed. 

protectedvirtual 

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.
i  The variable which should be removed. 
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.
remove  The variables which should be removed. 

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

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().
nSamples  The number of branching samples. 
samples  An array of pointer to buffers storing the branching rules of each sample. 

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().
variable  Holds the branching variable if one is found. 
Reimplemented in ogdf::cluster_planarity::MaxCPlanarSub, and ogdf::cluster_planarity::CPlanaritySub.

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 nonfixed and nonset 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.
candidates  The candidates for branching variables are stored in this buffer. We try to find as many variables as fit into the buffer. 
Reimplemented in ogdf::cluster_planarity::MaxCPlanarSub, and ogdf::cluster_planarity::CPlanaritySub.

inlineprotectedvirtual 

inlineprotectedvirtual 

protectedvirtual 
Must be redefined in derived classes for the generation of cutting planes.
The default implementation does nothing.
Reimplemented in ogdf::MinSteinerTreeDirectedCut< T >::Sub, ogdf::cluster_planarity::MaxCPlanarSub, and ogdf::cluster_planarity::CPlanaritySub.

protectedvirtual 
Sets a variable.
i  The number of the variable being set. 
newStat  A pointer to the object storing the new status of the the variable. 
newValue  If the variable is set to a value different from the one of the last LPsolution, newValue is set to true. Otherwise, it is set to false. 

protectedvirtual 
Sets a variable.
i  The number of the variable being set. 
newStat  The new status of the variable. 
newValue  If the variable is set to a value different from the one of the last LPsolution, newValue is set to true. Otherwise, it is set to false. 

protectedvirtual 
Sets a variable.
i  The number of the variable being set. 
newStat  The new status of the variable. 
value  The value the variable is set to. 
newValue  If the variable is set to a value different from the one of the last LPsolution, newValue is set to true. Otherwise, it is set to false. 

inlineprotectedvirtual 
The default implementation of setByLogImp() does nothing.
In derived classes this function can be reimplemented.
variable  The variables which should be set have to be inserted in this buffer. 
status  The status of the set variables. 

protectedvirtual 
Tries to set variables according to the reduced cost criterion.

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.
newValues  The parameter newValues becomes true if variables are fixed to other values as in the current LPsolution (setByRedCost() cannot set variables to new values). 

inline 

inlineprotectedvirtual 

protectedvirtual 
Solves the LPrelaxation of the subproblem.
As soon as the LPrelaxation becomes infeasible in a static branch and cut algorithm the respective subproblem can be fathomed. Otherwise, we memorize the value of the LPsolution to control the tailing off effect.
We assume that the LP is never primal unbounded.
Reimplemented in ogdf::cluster_planarity::MaxCPlanarSub, and ogdf::cluster_planarity::CPlanaritySub.

inline 

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

inline 
Can be used to access the upper of an active variable of the subproblem.
i  The number of the variable. 

inline 

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.

inline 

protectedvirtual 
Entry point for application specific variable elimination.
The default implementation selects the variables with the function redCostVarEliminate().
remove  The variables that should be removed have to be stored in this buffer. 

inline 

protectedvirtual 
Tries to generate inactive variables from a pool.
ranking  This 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. 
pool  The pool the variables are generated from. If pool is 0, then the default variable pool is used. The default value of pool is 0. 
minViolation  A violated constraint/variable is only added if the absolute value of its violation is at least minAbsViolation. The default value is 0.001. 

protectedvirtual 
Reallocates memory that at most newSize variables can be handled in the subproblem.
newSize  The new maximal number of variables in the subproblem. 

inline 

inline 

friend 

friend 

friend 

protected 

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.

protected 

protected 

protected 

protected 

protected 

protected 

private 

protected 

protected 

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

protected 

private 
If this flag is set to true then the next LPsolution is ignored in the tailingoff control.
The default value of the variable is false. It can be set to true by the function ignoreInTailingOff().

protected 

protected 

protected 

protected 

private 

protected 

private 

private 

protected 

protected 

protected 

private 

private 

protected 

private 

private 

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.

protected 

protected 

private 

private 

protected 

protected 

private 

protected 