#include <ogdf/cluster/internal/MaxCPlanarSub.h>

Inheritance diagram for ogdf::cluster_planarity::MaxCPlanarSub:

Public Member Functions
	MaxCPlanarSub (abacus::Master *master)

	MaxCPlanarSub (abacus::Master master, abacus::Sub father, abacus::BranchRule branchRule, List< abacus::Constraint > &criticalConstraints)

virtual	~MaxCPlanarSub ()

virtual abacus::Sub *	generateSon (abacus::BranchRule *rule) override
	Returns a pointer to an object of a problem specific subproblem, which is generated from the current subproblem by branching rule rule.

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.

virtual	~Sub ()
	The destructor only deletes the sons of the node.

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
int	addPoolCons (ArrayBuffer< abacus::Constraint * > &cons, abacus::StandardPool< abacus::Constraint, abacus::Variable > *pool)
	Adds the given constraints to the given pool.

bool	checkCConnectivity (const GraphCopy &support)
	Checks if the cluster induced graphs and their complement are connected in the current solution.

bool	checkCConnectivityOld (const GraphCopy &support)

int	clusterBags (ClusterGraph &CG, cluster c)

virtual bool	feasible () override
	Must check the feasibility of a solution of the LP-relaxation.

node	getRepresentative (node v, NodeArray< node > &parent)
	run through the pointer list parent and return the representative i.e. the node with parent[v] == v

virtual int	improve (double &primalValue) override
	Can be redefined in order to implement primal heuristics for finding feasible solutions.

virtual int	makeFeasible () override
	The default implementation of makeFeasible()does nothing.

virtual int	optimize () override
	Performs the optimization of the subproblem.

virtual int	pricing () override
	Should generate inactive variables which do not price out correctly.

int	repair ()

virtual int	selectBranchingVariable (int &variable) override
	Chooses a branching variable.

virtual int	selectBranchingVariableCandidates (ArrayBuffer< int > &candidates) override
	Selects candidates for branching variables.

virtual int	separate () override
	Must be redefined in derived classes for the generation of cutting planes.

int	separateCutPool (abacus::StandardPool< abacus::Constraint, abacus::Variable > *pool, double minViolation)

int	separateReal (double minViolate)
	these functions are mainly reporting to let abacus think everthing is normal.

int	separateRealO (double minViolate)

virtual int	solveLp () override
	Solves the LP-relaxation of the subproblem.

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

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 void	nonBindingConEliminate (ArrayBuffer< int > &remove)
	Retrieves the dynamic constraints with slack exceeding the value given by the parameter `ConElimEps`.

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 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 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 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
int	addCutCons (ArrayBuffer< abacus::Constraint * > cons)
	Adds the given constraints to the connectivity cut pool.

int	addKuraCons (ArrayBuffer< abacus::Constraint * > cons)
	Adds the given constraints to the planarity cut pool.

void	childClusterSpanningTree (GraphCopy &GC, List< edgeValue > &clusterEdges, List< NodePair > &MSTEdges)

void	clusterSpanningTree (ClusterGraph &C, cluster c, ClusterArray< List< NodePair > > &treeEdges, ClusterArray< List< edgeValue > > &clusterEdges)

void	connectivitySupportGraph (GraphCopy &support, EdgeArray< double > &weight)

int	createVariablesForBufferedConstraints ()

int	getArrayIndex (double lpValue)

double	heuristicImprovePrimalBound (List< NodePair > &originalEdges, List< NodePair > &connectionEdges, List< edge > &deletedEdges)

void	intSolutionInducedGraph (GraphCopy &support)

void	kuratowskiSupportGraph (GraphCopy &support, double low, double high)

MaxCPlanarMaster *	master () const

void	myAddVars (ArrayBuffer< abacus::Variable * > &b)

int	separateConnPool (double minViolation)

int	separateKuraPool (double minViolation)

double	subdivisionLefthandSide (SListConstIterator< KuratowskiWrapper > it, GraphCopy *gc)

void	updateSolution ()

Private Attributes
ArrayBuffer< abacus::Constraint * >	bufferedForCreation

List< abacus::Constraint * >	criticalSinceBranching

bool	detectedInfeasibility

bool	inOrigSolveLp

bool	m_constraintsFound

int	m_reportCreation

bool	m_sepFirst

double	realDualBound

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

Definition at line 47 of file MaxCPlanarSub.h.

Constructor & Destructor Documentation

◆ MaxCPlanarSub() [1/2]

ogdf::cluster_planarity::MaxCPlanarSub::MaxCPlanarSub ( abacus::Master * master )

explicit

◆ MaxCPlanarSub() [2/2]

ogdf::cluster_planarity::MaxCPlanarSub::MaxCPlanarSub	(	abacus::Master *	master,
		abacus::Sub *	father,
		abacus::BranchRule *	branchRule,
		List< abacus::Constraint * > &	criticalConstraints
	)

◆ ~MaxCPlanarSub()

virtual ogdf::cluster_planarity::MaxCPlanarSub::~MaxCPlanarSub ( )

virtual

Member Function Documentation

◆ addCutCons()

int ogdf::cluster_planarity::MaxCPlanarSub::addCutCons ( ArrayBuffer< abacus::Constraint * > cons )

inlineprivate

Adds the given constraints to the connectivity cut pool.

Definition at line 248 of file MaxCPlanarSub.h.

◆ addKuraCons()

int ogdf::cluster_planarity::MaxCPlanarSub::addKuraCons ( ArrayBuffer< abacus::Constraint * > cons )

inlineprivate

Adds the given constraints to the planarity cut pool.

Definition at line 253 of file MaxCPlanarSub.h.

◆ addPoolCons()

int ogdf::cluster_planarity::MaxCPlanarSub::addPoolCons	(	ArrayBuffer< abacus::Constraint * > &	cons,
		abacus::StandardPool< abacus::Constraint, abacus::Variable > *	pool
	)

inlineprotected

Adds the given constraints to the given pool.

Definition at line 170 of file MaxCPlanarSub.h.

◆ checkCConnectivity()

bool ogdf::cluster_planarity::MaxCPlanarSub::checkCConnectivity ( const GraphCopy & support )

protected

Checks if the cluster induced graphs and their complement are connected in the current solution.

◆ checkCConnectivityOld()

bool ogdf::cluster_planarity::MaxCPlanarSub::checkCConnectivityOld ( const GraphCopy & support )

protected

◆ childClusterSpanningTree()

void ogdf::cluster_planarity::MaxCPlanarSub::childClusterSpanningTree	(	GraphCopy &	GC,
		List< edgeValue > &	clusterEdges,
		List< NodePair > &	MSTEdges
	)

private

◆ clusterBags()

int ogdf::cluster_planarity::MaxCPlanarSub::clusterBags	(	ClusterGraph &	CG,
		cluster	c
	)

protected

◆ clusterSpanningTree()

void ogdf::cluster_planarity::MaxCPlanarSub::clusterSpanningTree	(	ClusterGraph &	C,
		cluster	c,
		ClusterArray< List< NodePair > > &	treeEdges,
		ClusterArray< List< edgeValue > > &	clusterEdges
	)

private

◆ connectivitySupportGraph()

void ogdf::cluster_planarity::MaxCPlanarSub::connectivitySupportGraph	(	GraphCopy &	support,
		EdgeArray< double > &	weight
	)

private

◆ createVariablesForBufferedConstraints()

int ogdf::cluster_planarity::MaxCPlanarSub::createVariablesForBufferedConstraints ( )

private

◆ feasible()

virtual bool ogdf::cluster_planarity::MaxCPlanarSub::feasible ( )

overrideprotectedvirtual

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

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

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

Implements abacus::Sub.

◆ generateSon()

virtual abacus::Sub * ogdf::cluster_planarity::MaxCPlanarSub::generateSon ( abacus::BranchRule * rule )

overridevirtual

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

Parameters

rule	The branching rule with which the subproblem is generated.

Implements abacus::Sub.

◆ getArrayIndex()

int ogdf::cluster_planarity::MaxCPlanarSub::getArrayIndex ( double lpValue )

private

◆ getRepresentative()

node ogdf::cluster_planarity::MaxCPlanarSub::getRepresentative	(	node	v,
		NodeArray< node > &	parent
	)

inlineprotected

run through the pointer list parent and return the representative i.e. the node with parent[v] == v

Definition at line 90 of file MaxCPlanarSub.h.

◆ heuristicImprovePrimalBound()

double ogdf::cluster_planarity::MaxCPlanarSub::heuristicImprovePrimalBound	(	List< NodePair > &	originalEdges,
		List< NodePair > &	connectionEdges,
		List< edge > &	deletedEdges
	)

private

◆ improve()

virtual int ogdf::cluster_planarity::MaxCPlanarSub::improve ( double & primalValue )

overrideprotectedvirtual

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

The default implementation does nothing.

Returns: 0 If no better solution could be found, 1 otherwise.

Parameters

primalValue Should hold the value of the feasible solution, if a better one is found.

Reimplemented from abacus::Sub.

◆ intSolutionInducedGraph()

void ogdf::cluster_planarity::MaxCPlanarSub::intSolutionInducedGraph ( GraphCopy & support )

private

◆ kuratowskiSupportGraph()

void ogdf::cluster_planarity::MaxCPlanarSub::kuratowskiSupportGraph	(	GraphCopy &	support,
		double	low,
		double	high
	)

private

◆ makeFeasible()

virtual int ogdf::cluster_planarity::MaxCPlanarSub::makeFeasible ( )

inlineoverrideprotectedvirtual

The default implementation of makeFeasible()does nothing.

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

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

Returns: 0 If feasibility can be restored, 1 otherwise.

Reimplemented from abacus::Sub.

Definition at line 66 of file MaxCPlanarSub.h.

◆ master()

MaxCPlanarMaster * ogdf::cluster_planarity::MaxCPlanarSub::master ( ) const

inlineprivate

Definition at line 181 of file MaxCPlanarSub.h.

◆ myAddVars()

void ogdf::cluster_planarity::MaxCPlanarSub::myAddVars ( ArrayBuffer< abacus::Variable * > & b )

inlineprivate

Definition at line 197 of file MaxCPlanarSub.h.

◆ optimize()

virtual int ogdf::cluster_planarity::MaxCPlanarSub::optimize ( )

inlineoverrideprotectedvirtual

Performs the optimization of the subproblem.

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

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

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

Reimplemented from abacus::Sub.

Definition at line 73 of file MaxCPlanarSub.h.

◆ pricing()

virtual int ogdf::cluster_planarity::MaxCPlanarSub::pricing ( )

inlineoverrideprotectedvirtual

Should generate inactive variables which do not price out correctly.

The default implementation does nothing and returns 0.

Returns: The number of new variables.

Reimplemented from abacus::Sub.

Definition at line 144 of file MaxCPlanarSub.h.

◆ repair()

int ogdf::cluster_planarity::MaxCPlanarSub::repair ( )

protected

◆ selectBranchingVariable()

virtual int ogdf::cluster_planarity::MaxCPlanarSub::selectBranchingVariable ( int & variable )

overrideprotectedvirtual

Chooses a branching variable.

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

Parameters

variable Holds the branching variable if one is found.

Returns: 0 If a branching variable is found, 1 otherwise.

Reimplemented from abacus::Sub.

◆ selectBranchingVariableCandidates()

virtual int ogdf::cluster_planarity::MaxCPlanarSub::selectBranchingVariableCandidates ( ArrayBuffer< int > & candidates )

overrideprotectedvirtual

Selects candidates for branching variables.

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

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

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

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

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

Parameters

candidates The candidates for branching variables are stored in this buffer. We try to find as many variables as fit into the buffer.

Returns: 0 If a candidate is found, 1 otherwise.

Reimplemented from abacus::Sub.

◆ separate()

virtual int ogdf::cluster_planarity::MaxCPlanarSub::separate ( )

inlineoverrideprotectedvirtual

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

The default implementation does nothing.

Returns: The number of generated cutting planes.

Reimplemented from abacus::Sub.

Definition at line 137 of file MaxCPlanarSub.h.

◆ separateConnPool()

int ogdf::cluster_planarity::MaxCPlanarSub::separateConnPool ( double minViolation )

inlineprivate

Definition at line 258 of file MaxCPlanarSub.h.

◆ separateCutPool()

int ogdf::cluster_planarity::MaxCPlanarSub::separateCutPool	(	abacus::StandardPool< abacus::Constraint, abacus::Variable > *	pool,
		double	minViolation
	)

inlineprotected

Definition at line 175 of file MaxCPlanarSub.h.

◆ separateKuraPool()

int ogdf::cluster_planarity::MaxCPlanarSub::separateKuraPool ( double minViolation )

inlineprivate

Definition at line 264 of file MaxCPlanarSub.h.

◆ separateReal()

int ogdf::cluster_planarity::MaxCPlanarSub::separateReal ( double minViolate )

protected

these functions are mainly reporting to let abacus think everthing is normal.

the actual work is done by separateReal() and pricingReal(). The steering of this process is performed in solveLp()

◆ separateRealO()

int ogdf::cluster_planarity::MaxCPlanarSub::separateRealO ( double minViolate )

inlineprotected

Definition at line 121 of file MaxCPlanarSub.h.

◆ solveLp()

virtual int ogdf::cluster_planarity::MaxCPlanarSub::solveLp ( )

overrideprotectedvirtual

Solves the LP-relaxation of the subproblem.

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

We assume that the LP is never primal unbounded.

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

Reimplemented from abacus::Sub.

◆ subdivisionLefthandSide()

double ogdf::cluster_planarity::MaxCPlanarSub::subdivisionLefthandSide	(	SListConstIterator< KuratowskiWrapper >	it,
		GraphCopy *	gc
	)

private

◆ updateSolution()

void ogdf::cluster_planarity::MaxCPlanarSub::updateSolution ( )

private

Member Data Documentation

◆ bufferedForCreation

ArrayBuffer<abacus::Constraint*> ogdf::cluster_planarity::MaxCPlanarSub::bufferedForCreation

private

Definition at line 194 of file MaxCPlanarSub.h.

◆ criticalSinceBranching

List<abacus::Constraint*> ogdf::cluster_planarity::MaxCPlanarSub::criticalSinceBranching

private

Definition at line 193 of file MaxCPlanarSub.h.

◆ detectedInfeasibility

bool ogdf::cluster_planarity::MaxCPlanarSub::detectedInfeasibility

private

Definition at line 186 of file MaxCPlanarSub.h.

◆ inOrigSolveLp

bool ogdf::cluster_planarity::MaxCPlanarSub::inOrigSolveLp

private

Definition at line 187 of file MaxCPlanarSub.h.

◆ m_constraintsFound

bool ogdf::cluster_planarity::MaxCPlanarSub::m_constraintsFound

private

Definition at line 185 of file MaxCPlanarSub.h.

◆ m_reportCreation

int ogdf::cluster_planarity::MaxCPlanarSub::m_reportCreation

private

Definition at line 191 of file MaxCPlanarSub.h.

◆ m_sepFirst

bool ogdf::cluster_planarity::MaxCPlanarSub::m_sepFirst

private

Definition at line 192 of file MaxCPlanarSub.h.

◆ realDualBound

double ogdf::cluster_planarity::MaxCPlanarSub::realDualBound

private

Definition at line 188 of file MaxCPlanarSub.h.

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

include/ogdf/cluster/internal/MaxCPlanarSub.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ MaxCPlanarSub() [1/2]

◆ MaxCPlanarSub() [2/2]

◆ ~MaxCPlanarSub()

Member Function Documentation

◆ addCutCons()

◆ addKuraCons()

◆ addPoolCons()

◆ checkCConnectivity()

◆ checkCConnectivityOld()

◆ childClusterSpanningTree()

◆ clusterBags()

◆ clusterSpanningTree()

◆ connectivitySupportGraph()

◆ createVariablesForBufferedConstraints()

◆ feasible()

◆ generateSon()

◆ getArrayIndex()

◆ getRepresentative()

◆ heuristicImprovePrimalBound()

◆ improve()

◆ intSolutionInducedGraph()

◆ kuratowskiSupportGraph()

◆ makeFeasible()

◆ master()

◆ myAddVars()

◆ optimize()

◆ pricing()

◆ repair()

◆ selectBranchingVariable()

◆ selectBranchingVariableCandidates()

◆ separate()

◆ separateConnPool()

◆ separateCutPool()

◆ separateKuraPool()

◆ separateReal()

◆ separateRealO()

◆ solveLp()

◆ subdivisionLefthandSide()

◆ updateSolution()

Member Data Documentation

◆ bufferedForCreation

◆ criticalSinceBranching

◆ detectedInfeasibility

◆ inOrigSolveLp

◆ m_constraintsFound

◆ m_reportCreation

◆ m_sepFirst

◆ realDualBound

Open
Graph Drawing
Framework