Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
ogdf::MinSteinerTreeDirectedCut< T >::Sub Class Reference

Subproblem of Steiner tree algorithm. More...

#include <ogdf/graphalg/MinSteinerTreeDirectedCut.h>

+ Inheritance diagram for ogdf::MinSteinerTreeDirectedCut< T >::Sub:

Public Member Functions

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

Protected Member Functions

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

Private Member Functions

virtual SubgenerateSon (abacus::BranchRule *rule) override
 generates a b&b node
 

Private Attributes

int m_alreadySeparated
 nr of already separated cuts, default is -1
 
int m_callPrimalHeuristic
 Strategy for primal heuristic (PH) calls.
 
bool m_computeBackCuts
 
bool m_computeNestedCuts
 
int m_maxNrCuttingPlanes
 maximum nr of cutting planes to be added
 
bool m_minCardinalityCuts
 
Masterm_pMaster
 the master problem of the b&c algorithm
 
int m_saturationStrategy
 
int m_separationStrategy
 
bool m_shuffleTerminals
 

Additional Inherited Members

- Public Types inherited from abacus::Sub
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...
 
- Static Public Member Functions inherited from abacus::AbacusRoot
static bool ascii2bool (const string &str)
 Converts the string str to a boolean value.
 
static bool endsWith (const string &str, const string &end)
 Returns true if str ends with end, false otherwise.
 
static double fracPart (double x)
 Returns the absolute value of the fractional part of x.
 
static const charonOff (bool value)
 Converts a boolean variable to the strings "on" and "off".
 
- Protected Attributes inherited from abacus::Sub
Active< Constraint, Variable > * actCon_
 The active constraints of the subproblem.
 
Active< Variable, Constraint > * actVar_
 The active variables of the subproblem.
 
CutBuffer< Constraint, Variable > * addConBuffer_
 The buffer of the newly generated constraints.
 
CutBuffer< Variable, Constraint > * addVarBuffer_
 The buffer of the newly generated variables.
 
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.
 
doublebInvRow_
 A row of the basis inverse associated with the infeasible variable infeasVar_ or slack variable infeasCon_.
 
BranchRulebranchRule_
 The branching rule for the subproblem.
 
double dualBound_
 The dual bound of the subproblem.
 
Subfather_
 A pointer to the father in the branch-and-cut tree.
 
Array< FSVarStat * > * fsVarStat_
 A pointer to an array storing the status of fixing and setting of the active variables.
 
bool genNonLiftCons_
 If true, then the management of non-liftable constraints is performed.
 
int infeasCon_
 The number of an infeasible constraint.
 
int infeasVar_
 The number of an infeasible variable.
 
int lastIterConAdd_
 The last iteration in which constraints have been added.
 
int lastIterVarAdd_
 The last iteration in which variables have been added.
 
Array< double > * lBound_
 A pointer to an array with the local lower bound of the active variables.
 
LpSublp_
 A pointer to the corresponding linear program.
 
LP::METHOD lpMethod_
 The solution method for the next linear program.
 
Array< LPVARSTAT * > * lpVarStat_
 A pointer to an array storing the status of each active variable in the linear program.
 
Mastermaster_
 A pointer to the corresponding master of the optimization.
 
int nIter_
 The number of iterations in the cutting plane phase.
 
ArrayBuffer< int > * removeConBuffer_
 The buffer of the constraints which are removed at the beginning of the next iteration.
 
ArrayBuffer< int > * removeVarBuffer_
 The buffer of the variables which are removed at the beginning of the next iteration.
 
Array< SlackStat * > * slackStat_
 A pointer to an array storing the statuses of the slack variables of the last solved linear program.
 
TailOfftailOff_
 A pointer to the tailing off manager.
 
Array< double > * uBound_
 A pointer to an array with the local upper bounds of the active variables.
 
doublexVal_
 The last LP-solution.
 
doubleyVal_
 The dual variables of the last linear program.
 

Detailed Description

template<typename T>
class ogdf::MinSteinerTreeDirectedCut< T >::Sub

Subproblem of Steiner tree algorithm.

Definition at line 652 of file MinSteinerTreeDirectedCut.h.

Constructor & Destructor Documentation

◆ Sub() [1/2]

template<typename T >
ogdf::MinSteinerTreeDirectedCut< T >::Sub::Sub ( abacus::Master master)
explicit

Constructor for the root problem of the b&b tree.

Definition at line 1435 of file MinSteinerTreeDirectedCut.h.

◆ Sub() [2/2]

template<typename T >
ogdf::MinSteinerTreeDirectedCut< T >::Sub::Sub ( abacus::Master master,
abacus::Sub father,
abacus::BranchRule branchRule 
)

Constructor for non-root problems of the b&b tree.

Definition at line 1449 of file MinSteinerTreeDirectedCut.h.

◆ ~Sub()

template<typename T >
virtual ogdf::MinSteinerTreeDirectedCut< T >::Sub::~Sub ( )
inlinevirtual

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 from abacus::Sub.

Definition at line 660 of file MinSteinerTreeDirectedCut.h.

Member Function Documentation

◆ feasible()

template<typename T >
bool ogdf::MinSteinerTreeDirectedCut< T >::Sub::feasible ( )
overrideprotectedvirtual

checks if the current solution is feasible, i.e., calls mySeparate()

Implements abacus::Sub.

Definition at line 1500 of file MinSteinerTreeDirectedCut.h.

◆ generateSon()

template<typename T >
virtual Sub * ogdf::MinSteinerTreeDirectedCut< T >::Sub::generateSon ( abacus::BranchRule rule)
inlineoverrideprivatevirtual

generates a b&b node

Implements abacus::Sub.

Definition at line 727 of file MinSteinerTreeDirectedCut.h.

◆ myImprove()

template<typename T >
void ogdf::MinSteinerTreeDirectedCut< T >::Sub::myImprove ( )
protected

primal heuristic procedure

Definition at line 1875 of file MinSteinerTreeDirectedCut.h.

◆ mySeparate()

template<typename T >
int ogdf::MinSteinerTreeDirectedCut< T >::Sub::mySeparate ( )
protected

separation procedure

Definition at line 1596 of file MinSteinerTreeDirectedCut.h.

◆ separate()

template<typename T >
virtual int ogdf::MinSteinerTreeDirectedCut< T >::Sub::separate ( )
inlineoverrideprotectedvirtual

calls mySeparate() if mySeparate wasn't called in another procedure

Reimplemented from abacus::Sub.

Definition at line 672 of file MinSteinerTreeDirectedCut.h.

Member Data Documentation

◆ m_alreadySeparated

template<typename T >
int ogdf::MinSteinerTreeDirectedCut< T >::Sub::m_alreadySeparated
private

nr of already separated cuts, default is -1

Definition at line 701 of file MinSteinerTreeDirectedCut.h.

◆ m_callPrimalHeuristic

template<typename T >
int ogdf::MinSteinerTreeDirectedCut< T >::Sub::m_callPrimalHeuristic
private

Strategy for primal heuristic (PH) calls.

Definition at line 724 of file MinSteinerTreeDirectedCut.h.

◆ m_computeBackCuts

template<typename T >
bool ogdf::MinSteinerTreeDirectedCut< T >::Sub::m_computeBackCuts
private

Definition at line 712 of file MinSteinerTreeDirectedCut.h.

◆ m_computeNestedCuts

template<typename T >
bool ogdf::MinSteinerTreeDirectedCut< T >::Sub::m_computeNestedCuts
private

Definition at line 706 of file MinSteinerTreeDirectedCut.h.

◆ m_maxNrCuttingPlanes

template<typename T >
int ogdf::MinSteinerTreeDirectedCut< T >::Sub::m_maxNrCuttingPlanes
private

maximum nr of cutting planes to be added

Definition at line 704 of file MinSteinerTreeDirectedCut.h.

◆ m_minCardinalityCuts

template<typename T >
bool ogdf::MinSteinerTreeDirectedCut< T >::Sub::m_minCardinalityCuts
private

Definition at line 716 of file MinSteinerTreeDirectedCut.h.

◆ m_pMaster

template<typename T >
Master* ogdf::MinSteinerTreeDirectedCut< T >::Sub::m_pMaster
private

the master problem of the b&c algorithm

Definition at line 698 of file MinSteinerTreeDirectedCut.h.

◆ m_saturationStrategy

template<typename T >
int ogdf::MinSteinerTreeDirectedCut< T >::Sub::m_saturationStrategy
private

Definition at line 710 of file MinSteinerTreeDirectedCut.h.

◆ m_separationStrategy

template<typename T >
int ogdf::MinSteinerTreeDirectedCut< T >::Sub::m_separationStrategy
private

Definition at line 708 of file MinSteinerTreeDirectedCut.h.

◆ m_shuffleTerminals

template<typename T >
bool ogdf::MinSteinerTreeDirectedCut< T >::Sub::m_shuffleTerminals
private

Definition at line 714 of file MinSteinerTreeDirectedCut.h.


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