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.

BranchRule *	branchRule () const
	Returns a pointer to the branching rule of the subproblem.

Constraint *	constraint (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 Sub *	father () 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.

FSVarStat *	fsVarStat (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.

LpSub *	lp () const
	Returns a pointer to the linear program of the subproblem.

LPVARSTAT *	lpVarStat (int i) const
	Returns a pointer to the status of the variable i in the last solved linear program.

Master *	master ()
	Returns the master of the optimization.

const Master *	master () 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.

SlackStat *	slackStat (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.

Variable *	variable (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 LpSub *	generateLp ()
	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 Sub *	generateSon (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

Master *	m_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 char *	onOff (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.

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

BranchRule *	branchRule_
	The branching rule for the subproblem.

double	dualBound_
	The dual bound of the subproblem.

Sub *	father_
	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.

LpSub *	lp_
	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.

Master *	master_
	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.

TailOff *	tailOff_
	A pointer to the tailing off manager.

Array< double > *	uBound_
	A pointer to an array with the local upper bounds of the active variables.

double *	xVal_
	The last LP-solution.

double *	yVal_
	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.