CMR::ABC Namespace Reference

Augment-Branch-Cut solution. More...

Namespaces
	SB
	Constants related to branch selection.

Classes
class	BaseBrancher
	Abstract base class for implementing a branching node selection rule. More...
struct	BranchNode
class	BranchTourFind
	Compute branch tours for estimation and instatement, managing their edges. More...
class	DFSbrancher
	Depth-first search branching. More...
class	Executor
class	InterBrancher
	Interleaved best-estimate and best-first search branching. More...
class	QprefBrancher
	Class template for branching with priority queue via some preference rule. More...
struct	ScoreTuple

Typedefs
using	TourBrancher = QprefBrancher< BranchNode::tour_worse >
	Alias declaration for "best tour" branching. More...
using	BoundBrancher = QprefBrancher< BranchNode::bound_worse >
	Alias declaration for best-first search branching. More...
using	BranchHistory = std::list< BranchNode >
using	EndsDir = std::pair< EndPts, BranchNode::Dir >
	Alias declaration for EndPts and branching direction.

Functions
BranchNode::Dir	dir_from_int (int entry)
	Turn a 0-1 value entry into a BranchNode::Dir.
std::string	bnode_brief (const BranchNode &B)
	A concise "label" for the BranchNode B.
std::ostream &	operator<< (std::ostream &os, const BranchNode::Dir &dir)
std::ostream &	operator<< (std::ostream &os, const BranchNode &B)
int	large_len (int ncount, const std::vector< Graph::Edge > &edges)
	Return a "large" edge length relative to the capacities in ecap.
double	var_score (double mult, double v0, double v1)
	Rank a branching variable in terms of its down and up estimates. More...
std::vector< int >	length_weighted_cands (const std::vector< Graph::Edge > &edges, const std::vector< int > &indices, const std::vector< double > &x, const int num_return)
	Get a list of candidate branch edges using fractional long edge branching.
std::ostream &	operator<< (std::ostream &os, const ScoreTuple &T)
std::vector< ScoreTuple >	ranked_cands (const std::vector< int > &cand_inds, std::vector< LP::Estimate > &down_est, std::vector< LP::Estimate > &up_est, const std::vector< Graph::Edge > &edges, std::vector< LP::Basis > &contra_bases, double mult, double ub, int num_return)
	Produce a list of fixed max size containing ranked scored branching edges.
ostream &	operator<< (ostream &os, const BranchNode::Dir &dir)
ostream &	operator<< (ostream &os, const BranchNode &B)
int	large_len (int ncount, const vector< Graph::Edge > &edges)
	The intended use is that the negative return value of this function should be assigned as the edge weight to fix edges in a branching tour. More...
vector< int >	length_weighted_cands (const vector< Graph::Edge > &edges, const vector< int > &indices, const vector< double > &x, const int num_return)
ostream &	operator<< (ostream &os, const ScoreTuple &T)
vector< ScoreTuple >	ranked_cands (const vector< int > &cand_inds, vector< LP::Estimate > &down_est, vector< LP::Estimate > &up_est, const vector< Graph::Edge > &edges, vector< LP::Basis > &contra_bases, double mult, double ub, int num_return)

Variables
constexpr int	IntMax = std::numeric_limits<int>::max()
constexpr double	DoubleMax = std::numeric_limits<double>::max()
constexpr int	Int32Max = 2147483647

Detailed Description

Augment-Branch-Cut solution.

Typedef Documentation

using CMR::ABC::BoundBrancher = typedef QprefBrancher<BranchNode::bound_worse>

Alias declaration for best-first search branching.

See also

BranchNode::bound_worse for implementation and tie-breaking rules.

using CMR::ABC::TourBrancher = typedef QprefBrancher<BranchNode::tour_worse>

Alias declaration for "best tour" branching.

See also

BranchNode::tour_worse for implementation and tie-breaking rules.

Function Documentation

int CMR::ABC::large_len	(	int	ncount,
		const vector< Graph::Edge > &	edges
	)

The intended use is that the negative return value of this function should be assigned as the edge weight to fix edges in a branching tour.

Returns

a large edge length for an instance with ncount nodes and edge weights ecap.

Remarks

this is a re-write of a subroutine from build_sparse_dat in getdata.c from Concorde.

vector<int> CMR::ABC::length_weighted_cands	(	const vector< Graph::Edge > &	edges,
		const vector< int > &	indices,
		const vector< double > &	x,
		const int	num_return
	)

Parameters

[in]	edges	the list of Edges in the core lp.
[in]	indices	the indices of fractional basic variables from edges
[in]	x	the lp solution
[in]	num_return	the maximum number of candidate indices returned.

vector<ScoreTuple> CMR::ABC::ranked_cands	(	const vector< int > &	cand_inds,
		vector< LP::Estimate > &	down_est,
		vector< LP::Estimate > &	up_est,
		const vector< Graph::Edge > &	edges,
		vector< LP::Basis > &	contra_bases,
		double	mult,
		double	ub,
		int	num_return
	)

Parameters

[in]	cand_inds	the candidate indices to be ranked.
[in]	down_est	estimates for setting corresponding entry of cand_inds to zero.
[in]	up_est	like down_est but for setting to one.
[in]	mult	the multiplier used to generate the variable score.
[in]	ub	current upperbound for the problem. If a variable has down or up estimate bigger than this that is a hint the LP was infeasible or can be pruned by lower bound.
[in]	num_return	return at most this many ranked candidates.

Precondition

cand_inds.size() == down_est.size() == up_est.size()

Returns

a vector of ScoreTuple objects sorted in non-increasing order by score.

double CMR::ABC::var_score	(	double	mult,
		double	v0,
		double	v1
	)

Rank a branching variable in terms of its down and up estimates.

For some estimation metric, evaluate a priority score for branching on a given variable.

Parameters

[in]	v0	the estimate obtained for fixing a variable to zero
[in]	v1	the estimate obtained for fixing the same variable to one
[in]	mult	the weighting factor.

Returns

where is mult.