abacus::BranchRule Class Reference

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

master

A 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

lp	A 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

sub	The 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

sub	A 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

lp	A 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:

• include/ogdf/lib/abacus/branchrule.h