Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

abacus::BranchRule Class Referenceabstract

Abstract base class for all branching rules. More...

#include <ogdf/lib/abacus/branchrule.h>

+ Inheritance diagram for abacus::BranchRule:

Public Member Functions

 BranchRule (Master *master)
 Initializes a branching rule. More...
 
virtual ~BranchRule ()
 
virtual bool branchOnSetVar ()
 Should indicate if the branching is performed by setting a binary variable. More...
 
virtual void extract (LpSub *lp)
 Should modify the linear programming relaxation |lp| in order to determine the quality of the branching rule in an LP-based branching rule selection. More...
 
virtual int extract (Sub *sub)=0
 Modifies a subproblem by setting the branching variable. More...
 
virtual void initialize (Sub *sub)
 Called from the constructor of a subproblem. More...
 
virtual void unExtract (LpSub *lp)
 Should undo the modifictions of the linear programming relaxtion |lp|. More...
 
- Public Member Functions inherited from abacus::AbacusRoot
virtual ~AbacusRoot ()
 The destructor. More...
 

Protected Attributes

Mastermaster_
 A pointer to the corresponding master of the optimization. More...
 

Additional Inherited Members

- Static Public Member Functions inherited from abacus::AbacusRoot
static bool ascii2bool (const string &str)
 Converts the string str to a boolean value. More...
 
static bool endsWith (const string &str, const string &end)
 Returns true if str ends with end, false otherwise. More...
 
static double fracPart (double x)
 Returns the absolute value of the fractional part of x. More...
 
static const char * onOff (bool value)
 Converts a boolean variable to the strings "on" and "off". More...
 

Detailed Description

Abstract base class for all branching rules.

Branching should be very flexible within a branch-and-cut framework. Therefore in a branching step each generated subproblem receives an object of the class BranchRule. When the subproblem is activated, it copies the active variables, their bounds and statuses, and the active constraints from the father, and then modifies the subproblem according to the branching rule.

This class is an abstract base class for all branching rules within this framework. We provide by non-abstract derived classes standard branching schemes for setting a binary variable to its lower or upper bound (SetBranchRule), for setting an integer variable to a certain value (ValBranchRule), for changing the bounds of an integer variable (ConBranchRule), and for adding a branching constraint (ConBranchRule).

Definition at line 59 of file branchrule.h.

Constructor & Destructor Documentation

◆ BranchRule()

abacus::BranchRule::BranchRule ( Master master)
inline

Initializes a branching rule.

Parameters
masterA pointer to the corresponding master of the optimization.

Definition at line 66 of file branchrule.h.

◆ ~BranchRule()

virtual abacus::BranchRule::~BranchRule ( )
inlinevirtual

Definition at line 69 of file branchrule.h.

Member Function Documentation

◆ branchOnSetVar()

virtual bool abacus::BranchRule::branchOnSetVar ( )
inlinevirtual

Should indicate if the branching is performed by setting a binary variable.

This is only required as in the current version of the GNU-compiler run time type information is not satisfactorily implemented.

This function is currently required to determine global validity of Gomory cuts for general s.

Returns
The default implementation returns always false. This function must be redefined in SetBranchRule, where it has to return true.

Reimplemented in abacus::SetBranchRule.

Definition at line 114 of file branchrule.h.

◆ extract() [1/2]

virtual void abacus::BranchRule::extract ( LpSub lp)
virtual

Should modify the linear programming relaxation |lp| in order to determine the quality of the branching rule in an LP-based branching rule selection.

The default implementation does nothing except writing a warning to the error stream. If a derived concrete branching rule should be used in LP-based branching rule selection then this function has to be redefined.

Parameters
lpA pointer to a the linear programming relaxtion of a subproblem.

Reimplemented in abacus::ConBranchRule, abacus::SetBranchRule, abacus::ValBranchRule, and abacus::BoundBranchRule.

◆ extract() [2/2]

virtual int abacus::BranchRule::extract ( Sub sub)
pure virtual

Modifies a subproblem by setting the branching variable.

Parameters
subThe subproblem being modified.
Returns
0 If the subproblem can be modified according to the branching rule.
1 If a contradiction occurs.

Implemented in abacus::ConBranchRule, abacus::SetBranchRule, abacus::ValBranchRule, and abacus::BoundBranchRule.

◆ initialize()

virtual void abacus::BranchRule::initialize ( Sub sub)
inlinevirtual

Called from the constructor of a subproblem.

It can be used to perform initializations of the branching rule that can only be done after the generation of the subproblem.

The default implementation does nothing.

Parameters
subA pointer to the subproblem that should be used for the initialization.

Reimplemented in abacus::ConBranchRule.

Definition at line 128 of file branchrule.h.

◆ unExtract()

virtual void abacus::BranchRule::unExtract ( LpSub lp)
virtual

Should undo the modifictions of the linear programming relaxtion |lp|.

This function has to be redefined in a derived class if extract(LpSub*) is redefined there.

Parameters
lpA pointer to a the linear programming relaxtion of a subproblem.

Reimplemented in abacus::ConBranchRule, abacus::SetBranchRule, abacus::ValBranchRule, and abacus::BoundBranchRule.

Member Data Documentation

◆ master_

Master* abacus::BranchRule::master_
protected

A pointer to the corresponding master of the optimization.

Definition at line 131 of file branchrule.h.


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