Solution of TSP instances. More...

#include <solver.hpp>

Collaboration diagram for CMR::Solver:

[legend]

Classes
struct	CutSel
	Which separation routines should be called. More...

struct	PivStats
	Tracking objective values of pivots within a cut_and_piv loop. More...

Public Types
enum	Aug : char { Init = 'I', Piv = 'P', Xtour = 'X', Branch = 'B' }
	Types of augmentations that can take place. More...

using	AugObj = std::pair< Aug, double >

Public Member Functions
void	set_lowerbound (double lb)
	Set a target for early termination.

LP::PivType	cutting_loop (bool do_price, bool try_recover, bool pure_cut)
	Run a primal cutting plane loop of pivoting and cut generation.

template<typename SelectionRule >
LP::PivType	abc (bool do_price)
	Augment-branch-cut search. More...

const Data::Instance &	inst_info () const

const Graph::CoreGraph &	graph_info () const

const Data::BestGroup &	best_info () const

const LP::ActiveTour &	active_tour () const

const LP::CoreLP &	get_core_lp () const

void	choose_cuts (CutSel::Presets preset)
	Set the choice of cuts.

const std::vector< AugObj > &	get_aug_chart () const

template<typename Qtype >
bool	call_separator (const function< bool()> &sepcall, Qtype &sep_q, const std::string sep_name, PivType &piv, PivStats &piv_stats)
	This function template is used to add one class of cuts at a time, attempt to measure progress obtained, and return information on whether a further separation routine should be called. More...

TSPLIB constructors, each with or without specifying EdgePlan.
	Solver (const std::string &tsp_fname, int seed, Graph::EdgePlan eplan, OutPrefs outprefs)

	Solver (const std::string &tsp_fname, int seed, OutPrefs outprefs)

	Solver (const std::string &tsp_fname, const std::string &tour_fname, int seed, Graph::EdgePlan eplan, OutPrefs outprefs)
	Specify a starting tour from file.

	Solver (const std::string &tsp_fname, const std::string &tour_fname, int seed, OutPrefs outprefs)

Random Euclidean constructors, with or without EdgePlan.
	Solver (int seed, int node_count, int gridsize, Graph::EdgePlan eplan, OutPrefs outprefs)

	Solver (int seed, int node_count, int gridsize, OutPrefs outprefs)

Public Attributes
struct CMR::Solver::CutSel	cut_sel

Private Types
using	TimerCalled = std::pair< Timer, bool >

Private Member Functions
void	report_lp (LP::PivType piv)
	Report on `piv` and core_lp.

void	report_cuts ()
	Report the number and types of cuts in CoreLP.

void	report_aug (Aug aug_type)
	Output info about a new tour found. More...

void	initial_prints ()
	Handles writing initial data to file.

std::string	file_infix ()
	Returns an infix for data saved to file.

bool	restart_loop (LP::PivType piv, double delta_metric)
	Should cut_and_piv start again with the easier separation routines. More...

bool	return_pivot (LP::PivType piv)
	Should cut_and_piv return `piv` for augmentation or pricing.

bool	lb_fathom ()
	Does the current best tour match or beat target_lb.

LP::PivType	cut_and_piv (bool do_price)
	A loop of primal pivoting and cutting plane generation. More...

void	opt_check_prunable (bool do_price, ABC::BranchNode &prob)
	Check if `prob` is prunable based on an optimize/price estimate.

LP::PivType	abc_bcp (bool do_price)
	The branch-cut-price loop.

LP::PivType	frac_recover ()
	Use x-tour heuristic on fractional pivot.

template<typename Qtype >
bool	call_separator (const std::function< bool()> &sepcall, Qtype &sep_q, const std::string sep_name, LP::PivType &piv, PivStats &piv_stats)
	Method template for calling a separation routine in cut_and_piv.

void	place_pivot (double low_limit, double best_tourlen, double piv_val)

Separator resetting routines.
These methods reset their argument with data about the current pivot.
void	reset_separator (std::unique_ptr< Sep::Separator > &S)

void	reset_separator (std::unique_ptr< Sep::MetaCuts > &MS)

void	reset_separator (std::unique_ptr< Sep::SafeGomory > &GS)

Static Private Member Functions
static double	PH_delta (double new_val, double prev_val, double tourlen)
	Compute the Padberg-Hong-esque delta ratio.

Private Attributes
double	target_lb {-std::numeric_limits<double>::max() + 1.0}

Data::Instance	tsp_instance

Data::KarpPartition	karp_part

Graph::CoreGraph	core_graph

Data::BestGroup	best_data

LP::CoreLP	core_lp

std::unique_ptr< Price::Pricer >	edge_pricer

std::unique_ptr< ABC::BaseBrancher >	branch_controller

bool	branch_engaged = false
	Is an ABC search active.

OutPrefs	output_prefs

int	num_augs = 0

std::vector< AugObj >	aug_chart

std::array< char, 80 >	p_bar

Timer	time_overall {"Solver Overall"}

Timer	time_piv {"Pivoting", &time_overall}

Timer	time_price {"Pricing", &time_overall}

Timer	time_branch {"Branching", &time_overall}

std::map< std::string, TimerCalled >	sep_times

Detailed Description

Solution of TSP instances.

Member Enumeration Documentation

enum CMR::Solver::Aug : char

Types of augmentations that can take place.

Enumerator
Init	The starting tour.
Piv	An augmenting pivot.
Xtour	The x-tour/short LK heuristic.
Branch	An improving branch tour.

Member Function Documentation

template<typename SelectionRule >

LP::PivType CMR::Solver::abc ( bool do_price )

Augment-branch-cut search.

Template Parameters

SelectionRule the node selection to guide the ABC search. Should be a derived class of ABC::BaseBrancher.

Parameters

do_price will edge pricing be performed.

template<typename Qtype >

bool CMR::Solver::call_separator	(	const function< bool()> &	sepcall,
		Qtype &	sep_q,
		const std::string	sep_name,
		PivType &	piv,
		PivStats &	piv_stats
	)

This function template is used to add one class of cuts at a time, attempt to measure progress obtained, and return information on whether a further separation routine should be called.

Template Parameters

Qtype the queue representation of the cuts found by sepcall.

Parameters

[in]	sepcall	a function which returns true if cuts are found, in which case they are stored in `sep_q`.
[out]	piv	if cuts are found, this is the pivot type that occurred after they were added.
[in,out]	piv_stats	tracker for the pivot objective values seen this round.

PivType CMR::Solver::cut_and_piv ( bool do_price )

private

A loop of primal pivoting and cutting plane generation.

Parameters

do_price is edge pricing being performed for this instance. Used to control Gomory cut separation.

Returns: a LP::PivType corresponding to a non-degenerate pivot that was obtainedfrom repeated rounds of cut generation and pivoting.

void CMR::Solver::report_aug ( Aug aug_type )

private

Output info about a new tour found.

Prints the progress in tour improvement.

Parameters

aug_type the Solver::Aug describing the mode of augmentation.

bool CMR::Solver::restart_loop	(	LP::PivType	piv,
		double	delta_metric
	)

private

Should cut_and_piv start again with the easier separation routines.

Parameters

piv	the PivType of the last call to primal_pivot.
delta_metric	some measurement of the change obtained from the last round of cut generation.

Member Data Documentation

std::map<std::string, TimerCalled> CMR::Solver::sep_times

private

Initial value:

{
        {"CutPool", {Timer("CutPool", &time_overall), false}},
        {"SegmentCuts", {Timer("SegmentCuts", &time_overall), false}},
        {"ConnectCuts", {Timer("ConnectCuts", &time_overall), false}},
        {"ExactSub", {Timer("ExactSub", &time_overall), false}},
        {"FastBlossoms", {Timer("FastBlossoms", &time_overall), false}},
        {"ExactBlossoms", {Timer("FastBlossoms", &time_overall), false}},
        {"BlockCombs", {Timer("BlockCombs", &time_overall), false}},
        {"SimpleDP", {Timer("SimpleDP", &time_overall), false}},
        {"LocalCuts", {Timer("LocalCuts", &time_overall), false}},
        {"Decker", {Timer("Decker", &time_overall), false}},
        {"Handling", {Timer("Handling", &time_overall), false}},
        {"Teething", {Timer("Teething", &time_overall), false}},
        {"Consec1", {Timer("Consec1", &time_overall), false}},
        {"Tighten", {Timer("Tighten", &time_overall), false}},
        {"TightenPool", {Timer("TightenPool", &time_overall), false}},
        {"SafeGMI", {Timer("SafeGMI", &time_overall), false}},
    }

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

includes/solver.hpp
source/solver.cpp
source/solver_loops.cpp

Classes

Public Types

Public Member Functions

Public Attributes

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

Member Function Documentation

Member Data Documentation