Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::cluster_planarity::MaxCPlanarSub Class Reference

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

Protected Member Functions

int addPoolCons (ArrayBuffer< abacus::Constraint * > &cons, abacus::StandardPool< abacus::Constraint, abacus::Variable > *pool)
 Adds the given constraints to the given pool. More...
 
bool checkCConnectivity (const GraphCopy &support)
 Checks if the cluster induced graphs and their complement are connected in the current solution. More...
 
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. More...
 
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 More...
 
virtual int improve (double &primalValue) override
 Can be redefined in order to implement primal heuristics for finding feasible solutions. More...
 
virtual int makeFeasible () override
 The default implementation of makeFeasible()does nothing. More...
 
virtual int optimize () override
 Performs the optimization of the subproblem. More...
 
virtual int pricing () override
 Should generate inactive variables which do not price out correctly. More...
 
int repair ()
 
virtual int selectBranchingVariable (int &variable) override
 Chooses a branching variable. More...
 
virtual int selectBranchingVariableCandidates (ArrayBuffer< int > &candidates) override
 Selects candidates for branching variables. More...
 
virtual int separate () override
 Must be redefined in derived classes for the generation of cutting planes. More...
 
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. More...
 
int separateRealO (double minViolate)
 
virtual int solveLp () override
 Solves the LP-relaxation of the subproblem. More...
 
- Protected Member Functions inherited from abacus::Sub
virtual void activate ()
 Can be used as an entrance point for problem specific activations. More...
 
virtual int addCons (ArrayBuffer< Constraint * > &constraints, Pool< Constraint, Variable > *pool=nullptr, ArrayBuffer< bool > *keepInPool=nullptr, ArrayBuffer< double > *rank=nullptr)
 Tries to add new constraints to the constraint buffer and a pool. More...
 
virtual int addCons (ArrayBuffer< PoolSlot< Constraint, Variable > * > &newCons)
 Adds constraints to the active constraints and the linear program. More...
 
virtual int addVars (ArrayBuffer< PoolSlot< Variable, Constraint > * > &newVars)
 Adds both the variables in newVars to the set of active variables and to the linear program of the subproblem. More...
 
virtual int addVars (ArrayBuffer< Variable * > &variables, Pool< Variable, Constraint > *pool=nullptr, ArrayBuffer< bool > *keepInPool=nullptr, ArrayBuffer< double > *rank=nullptr)
 Tries to add new variables to the variable buffer and a pool. More...
 
virtual void basicConEliminate (ArrayBuffer< int > &remove)
 Retrieves all dynamic constraints having basic slack variable. More...
 
bool betterDual (double x) const
 Returns true if x is better than the best known dual bound of the subproblem, false otherwise. More...
 
bool boundCrash () const
 Returns true if the dual bound is worse than the best known primal bound, false otherwise. More...
 
virtual PHASE branching ()
 Performs branching. More...
 
virtual int branchingOnVariable (ArrayBuffer< BranchRule * > &rules)
 Generates branching rules for two new subproblems by selecting a branching variable with the function selectBranchingVariable(). More...
 
virtual LP::METHOD chooseLpMethod (int nVarRemoved, int nConRemoved, int nVarAdded, int nConAdded)
 Controls the method used to solve a linear programming relaxation. More...
 
int closeHalf (ArrayBuffer< int > &branchVar, VarType::TYPE branchVarType)
 Searches searches several possible branching variable of type branchVarType, with fraction as close to \(0.5\) as possible. More...
 
int closeHalf (int &branchVar, VarType::TYPE branchVarType)
 Searches a branching variable of type branchVarType, with fraction as close to \(0.5\) as possible. More...
 
int closeHalfExpensive (ArrayBuffer< int > &variables, VarType::TYPE branchVarType)
 Selects several candidates for branching variables of type branchVarType. More...
 
int closeHalfExpensive (int &branchVar, VarType::TYPE branchVarType)
 Selects a single branching variable of type branchVarType, with fractional part close to \(0.5\) and high absolute objective function coefficient. More...
 
virtual int compareBranchingSampleRanks (Array< double > &rank1, Array< double > &rank2)
 Compares the ranks of two branching samples. More...
 
virtual void conEliminate (ArrayBuffer< int > &remove)
 Can be used as an entry point for application specific elimination of constraints. More...
 
virtual void conRealloc (int newSize)
 Reallocates memory that at most newSize constraints can be handled in the subproblem. More...
 
virtual int constraintPoolSeparation (int ranking=0, Pool< Constraint, Variable > *pool=nullptr, double minViolation=0.001)
 Tries to generate inactive constraints from a pool. More...
 
virtual PHASE cutting ()
 Iteratively solves the LP-relaxation, generates constraints and/or variables. More...
 
virtual void deactivate ()
 Can be used as entrance point for problem specific deactivations after the subproblem optimization. More...
 
virtual double dualRound (double x)
 
virtual bool exceptionBranch ()
 Can be used to specify a problem specific criteria for enforcing a branching step. More...
 
virtual bool exceptionFathom ()
 Can be used to specify a problem specific fathoming criterium that is checked before the separation or pricing. More...
 
virtual void fathom (bool reoptimize)
 Fathoms a node and recursively tries to fathom its father. More...
 
virtual PHASE fathoming ()
 Fathoms the node, and if certain conditions are satisfied, also its ancestor. More...
 
virtual void fathomTheSubTree ()
 Fathoms all nodes in the subtree rooted at this subproblem. More...
 
int findNonFixedSet (ArrayBuffer< int > &branchVar, VarType::TYPE branchVarType)
 Selects the first variables that are neither fixed nor set. More...
 
int findNonFixedSet (int &branchVar, VarType::TYPE branchVarType)
 Selects the first variable that is neither fixed nor set. More...
 
virtual int fix (int i, FSVarStat *newStat, bool &newValue)
 Fixes a variable. More...
 
virtual int fixAndSet (bool &newValues)
 Tries to fix and set variables both by logical implications and reduced cost criteria. More...
 
virtual bool fixAndSetTime ()
 Controls if variables should be fixed or set when all variables price out correctly. More...
 
virtual void fixByLogImp (ArrayBuffer< int > &variables, ArrayBuffer< FSVarStat * > &status)
 Should collect the numbers of the variables to be fixed in variable and the respective statuses in status. More...
 
virtual int fixByRedCost (bool &newValues, bool saveCand)
 Tries to fix variables according to the reduced cost criterion. More...
 
virtual int fixing (bool &newValues, bool saveCand=false)
 Tries to fix variables by reduced cost criteria and logical implications. More...
 
virtual int generateBranchRules (ArrayBuffer< BranchRule * > &rules)
 Tries to find rules for splitting the current subproblem in further subproblems. More...
 
virtual LpSubgenerateLp ()
 Instantiates an LP for the solution of the LP-relaxation in this subproblem. More...
 
virtual 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
 
bool infeasible ()
 Returns true if the subproblem does not contain a feasible solution, false otherwise. More...
 
virtual void initializeCons (int maxCon)
 Initializes the active constraint set. More...
 
virtual int initializeLp ()
 Initializes the linear program. More...
 
virtual void initializeVars (int maxVar)
 Initializes the active variable set. More...
 
virtual int initMakeFeas (ArrayBuffer< InfeasCon * > &infeasCon, ArrayBuffer< Variable * > &newVars, Pool< Variable, Constraint > **pool)
 The default implementation of the virtual initMakeFeas() does nothing. More...
 
bool integerFeasible ()
 Can be used to check if the solution of the LP-relaxation is primally feasible if integrality is suficinet. More...
 
double lpRankBranchingRule (BranchRule *branchRule, int iterLimit=-1)
 Computes the rank of a branching rule by modifying the linear programming relaxation of the subproblem according to the branching rule and solving it. More...
 
virtual void nonBindingConEliminate (ArrayBuffer< int > &remove)
 Retrieves the dynamic constraints with slack exceeding the value given by the parameter ConElimEps. 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 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 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 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 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...
 

Private Member Functions

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

Detailed Description

Definition at line 46 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 256 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 261 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 164 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
ruleThe 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 91 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
primalValueShould 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 68 of file MaxCPlanarSub.h.

◆ master()

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

Definition at line 175 of file MaxCPlanarSub.h.

◆ myAddVars()

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

Definition at line 191 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 75 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 142 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
variableHolds 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
candidatesThe candidates for branching variables are stored in this buffer. We try to find as many variables as fit into the buffer.
Returns
0 If a candidate is found, 1 otherwise.

Reimplemented 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 138 of file MaxCPlanarSub.h.

◆ separateConnPool()

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

Definition at line 267 of file MaxCPlanarSub.h.

◆ separateCutPool()

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

Definition at line 168 of file MaxCPlanarSub.h.

◆ separateKuraPool()

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

Definition at line 272 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 122 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 188 of file MaxCPlanarSub.h.

◆ criticalSinceBranching

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

Definition at line 187 of file MaxCPlanarSub.h.

◆ detectedInfeasibility

bool ogdf::cluster_planarity::MaxCPlanarSub::detectedInfeasibility
private

Definition at line 180 of file MaxCPlanarSub.h.

◆ inOrigSolveLp

bool ogdf::cluster_planarity::MaxCPlanarSub::inOrigSolveLp
private

Definition at line 181 of file MaxCPlanarSub.h.

◆ m_constraintsFound

bool ogdf::cluster_planarity::MaxCPlanarSub::m_constraintsFound
private

Definition at line 179 of file MaxCPlanarSub.h.

◆ m_reportCreation

int ogdf::cluster_planarity::MaxCPlanarSub::m_reportCreation
private

Definition at line 185 of file MaxCPlanarSub.h.

◆ m_sepFirst

bool ogdf::cluster_planarity::MaxCPlanarSub::m_sepFirst
private

Definition at line 186 of file MaxCPlanarSub.h.

◆ realDualBound

double ogdf::cluster_planarity::MaxCPlanarSub::realDualBound
private

Definition at line 182 of file MaxCPlanarSub.h.


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