CMR::ABC::BaseBrancher Class Reference

Abstract base class for implementing a branching node selection rule. More...

#include <base_brancher.hpp>

Inheritance diagram for CMR::ABC::BaseBrancher:

Collaboration diagram for CMR::ABC::BaseBrancher:

Public Member Functions
	BaseBrancher (const Data::Instance &inst, const Data::BestGroup &bestdata, const Graph::CoreGraph &coregraph, LP::CoreLP &core)
virtual BranchHistory::iterator	next_prob ()=0
	Return the next subproblem to be examined.
void	split_prob (BranchHistory::iterator &current)
	Split the current problem, adding the subproblems to branch_history.
void	do_branch (const BranchNode &B)
	Branch on B, enforcing its constraint and instating its tour.
void	do_unbranch (const BranchNode &B)
	Unbranch on B and all applicable ancestors to prep next problem.
const BranchHistory &	get_history ()

Public Attributes
int	verbose = 0

Protected Member Functions
virtual void	enqueue_split (BranchNode::Split prob_array)=0
	Adding child subproblems to branch_history. More...
void	common_prep_next (const BranchNode &done, const BranchNode &next)
	Execute variable changes if done was just done and next is next. More...
bool	prune_btour_edges (const BranchNode &done, const BranchNode &next, const BranchNode &common_anc)
	Should branch tour edges be pruned before going to the next problem. More...
virtual void	fetch_next ()=0
	Set next_itr to the next subproblem to be examined. More...

Protected Attributes
const Data::Instance &	instance
const Data::BestGroup &	best_data
const Graph::CoreGraph &	core_graph
LP::CoreLP &	core_lp
BranchTourFind	btour_find
Executor	exec
BranchHistory	branch_history
BranchHistory::iterator	next_itr

Detailed Description

Abstract base class for implementing a branching node selection rule.

Member Function Documentation

void CMR::ABC::BaseBrancher::common_prep_next ( const BranchNode &  done, const BranchNode &  next  )

protected

Execute variable changes if done was just done and next is next.

Parameters

done	the BranchNode that was just examined/pruned.
next	the BranchNode that will succeed done in the current search. Compute the common ancestor A of done and next, undoing all the clamps from done to A and doing all the clamps from A to the parent of next.

virtual void CMR::ABC::BaseBrancher::enqueue_split ( BranchNode::Split  prob_array )

protectedpure virtual

Adding child subproblems to branch_history.

Parameters

prob_array

the pair of child subproblems to be added. This function shall be implemented to add child subproblems to the list of problems to be processed in a way that preserves the ordering criteria of the node selection rule.

Implemented in CMR::ABC::InterBrancher, CMR::ABC::QprefBrancher< q_pref >, and CMR::ABC::DFSbrancher.

virtual void CMR::ABC::BaseBrancher::fetch_next ( )

protectedpure virtual

Set next_itr to the next subproblem to be examined.

This is effectively the implementation of the node selection rule.

Implemented in CMR::ABC::InterBrancher, CMR::ABC::QprefBrancher< q_pref >, and CMR::ABC::DFSbrancher.

bool CMR::ABC::BaseBrancher::prune_btour_edges ( const BranchNode &  done, const BranchNode &  next, const BranchNode &  common_anc  )

protected

Should branch tour edges be pruned before going to the next problem.

Parameters

done	the node that was just examined.
next	the next node as per the current node selection rule.
common_anc	the common ancestor of done and next.

Returns

true if, before examining the node next, edges added by branch tour computation should be removed.

Remarks

This function assumes that next is not a child of done, since common_anc is known. Possible implementation choices include familial relationship (e.g., return true unless siblings or cousins), depth of common_anc (e.g., return true if common ancestor depth is lower than some fixed value), or a combination of both.

---

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

• includes/base_brancher.hpp
• source/base_brancher.cpp