CMR::Price::Pricer Class Reference

Get reduced costs for edges not in the core lp. More...

#include <pricer.hpp>

Collaboration diagram for CMR::Price::Pricer:

Classes
struct	edgegen_impl

Public Member Functions
	Pricer (LP::CoreLP &core, const Data::Instance &_inst, Graph::CoreGraph &core_graph_)
	Construct a Pricer using data from an ongoing solution process. More...
ScanStat	gen_edges (LP::PivType piv_stat, bool try_elim)
	Generate/add edges to core. More...
bool	feas_recover ()
	Generate/add edges to recover LP feasibility. More...
util::Fixed64	exact_lb (bool full)
	Compute a lower bound in Fixed64 arithmetic.
util::Fixed64	exact_lb (bool full, std::vector< PrEdge< util::Fixed64 >> &priced_edges)
	As above, but return the reduced costs of the edges scanned.
void	elim_edges (bool make_opt)
	Eliminate edges from the core.
template<typename numtype >
void	price_edges (std::vector< PrEdge< numtype >> &target_edges, std::unique_ptr< LP::DualGroup< numtype >> &duals, bool include_len)
	Compute reduced costs for a set of edges. More...

Public Attributes
int	verbose = 0

Private Member Functions
std::vector< Graph::Edge >	pool_chunk (std::vector< PrEdge< double >> &edge_q)
bool	scan_adjlist (std::vector< PrEdge< util::Fixed64 >> &gen_edges, int &node_index)
bool	scan_edges (std::vector< PrEdge< util::Fixed64 >> &gen_edges, int &loop1, int &loop2)
bool	feas_gen_edges (std::vector< PrEdge< double >> &price_elist, int start_ind, int &end1, int &end2)

Private Attributes
LP::CoreLP &	core_lp
	The LP relaxation to query/modify.
const Data::Instance &	inst
	To get lengths for edges not in core_lp.
const Sep::ExternalCuts &	ext_cuts
	For computing duals.
Graph::CoreGraph &	core_graph
	Graph data for the core_lp.
const int	gen_max
	The max number of edges to generate at a time.
std::vector< int >	gen_elist
	Raw node-node list of generated edges.
std::vector< int >	gen_elen
	Unused dummy parameter to pass.
std::unique_ptr< LP::DualGroup< double > >	reg_duals
std::unique_ptr< LP::DualGroup< util::Fixed64 > >	ex_duals
std::unique_ptr< edgegen_impl >	eg_inside
	The edge generator implementation. More...
std::unique_ptr< edgegen_impl >	eg_full
	Complete graph generator.
util::EdgeHash	edge_hash
	Hash table for tracking generated edges.

Detailed Description

Get reduced costs for edges not in the core lp.

Constructor & Destructor Documentation

CMR::Price::Pricer::Pricer	(	LP::CoreLP &	core,
		const Data::Instance &	_inst,
		Graph::CoreGraph &	core_graph_
	)

Construct a Pricer using data from an ongoing solution process.

Parameters

[in]	_relax	the Relaxation for grabbing dual values
[in]	_inst	the TSP instance for generating edges
[in]	_ext_cuts	the HyperGraph representation of the cuts in _relax.

Member Function Documentation

bool CMR::Price::Pricer::feas_recover

(

)

Generate/add edges to recover LP feasibility.

Returns

true if adding edges was able to recover feasibility, false if the LP is genuinely infeasible.

ScanStat CMR::Price::Pricer::gen_edges	(	LP::PivType	piv_stat,
		bool	try_elim
	)

Generate/add edges to core.

Parameters

[in]

piv_stat

the PivType from the solution when edge generation is called. The partial edge set is scanned iff piv_stat is PivType::Tour. Full edge set may be scanned if piv_stat is PivType::FathomedTour, or PivType::Tour with a small enough graph, or if a partial scan finds no edges to add.

Returns

a ScanStat indicating the outcome of the pricing scan.

template<typename numtype >

void CMR::Price::Pricer::price_edges	(	std::vector< PrEdge< numtype >> &	target_edges,
		std::unique_ptr< LP::DualGroup< numtype >> &	duals,
		bool	include_len
	)

Compute reduced costs for a set of edges.

Template Parameters

numtype

the number type for computing reduced costs. Should be double or util::fixed64.

Parameters

target_edges	the edges to be priced.
duals	the dual solution info for computing reduced costs.
include_len	true iff the length of an edge will be included in its price. Should always be true except when pricing edges to recover an infeasible LP.

Member Data Documentation

std::unique_ptr<edgegen_impl> CMR::Price::Pricer::eg_inside

private

The edge generator implementation.

50-nearest generator.

---

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

• includes/pricer.hpp
• source/price_exact.cpp
• source/price_gen.cpp
• source/price_recover.cpp