Interleaved best-estimate and best-first search branching. More...

Inheritance diagram for CMR::ABC::InterBrancher:

Collaboration diagram for CMR::ABC::InterBrancher:

[legend]

Public Member Functions
	InterBrancher (const Data::Instance &inst, const Data::BestGroup &best_data, const Graph::CoreGraph &core_graph, LP::CoreLP &core_lp)

BranchHistory::iterator	next_prob ()
	Return the next subproblem to be examined.

Public Member Functions inherited from CMR::ABC::BaseBrancher
	BaseBrancher (const Data::Instance &inst, const Data::BestGroup &bestdata, const Graph::CoreGraph &coregraph, LP::CoreLP &core)

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 ()

Protected Member Functions
void	fetch_next ()
	Set next_itr to the next subproblem to be examined. More...

void	enqueue_split (BranchNode::Split prob_array)
	Make a heap insertion of the nodes in `prob_array` to ensure with respect to an ordering that prioritizes unvisited nodes with good tours.

Protected Member Functions inherited from CMR::ABC::BaseBrancher
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...

Static Private Member Functions
Priority queue adaptors.
This class effectively uses a priority queue of problems, but the actual std::priority_queue cannot be used because occasionally we need to extract the lowest bound element. These functions adapt std::push_heap, std::make_heap, and std::pop_heap to modify prob_q on best tour calls.
static void	heap_push (std::vector< BranchHistory::iterator > &target_q, BranchHistory::iterator itr)

static void	heap_make (std::vector< BranchHistory::iterator > &target_q)

static void	heap_pop (std::vector< BranchHistory::iterator > &target_q)

static bool	better_bound (const BranchHistory::iterator &A, const BranchHistory::iterator &B)
	returns true iff `A` has a better (i.e., lower )estimate than `B`. More...

Private Attributes
int	node_num = 1

std::vector< BranchHistory::iterator >	prob_q

Additional Inherited Members
Public Attributes inherited from CMR::ABC::BaseBrancher
int	verbose = 0

Protected Attributes inherited from CMR::ABC::BaseBrancher
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

Interleaved best-estimate and best-first search branching.

Tour length is used as the primary node selection criterion, with a best bound node selected every InterBrancher::BestFreq nodes.

Member Function Documentation

static bool CMR::ABC::InterBrancher::better_bound	(	const BranchHistory::iterator &	A,
		const BranchHistory::iterator &	B
	)

inlinestaticprivate

returns true iff A has a better (i.e., lower )estimate than B.

void CMR::ABC::InterBrancher::fetch_next ( )

protectedvirtual

Set next_itr to the next subproblem to be examined.

This is effectively the implementation of the node selection rule.

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