Detailed Description

pricer class

Definition at line 36 of file pricer_vrp.h.

#include <pricer_vrp.h>

Public Member Functions
	ObjPricerVRP (SCIP scip, const char p_name, const int p_num_nodes, const int p_capacity, const vector< int > &p_demand, const vector< vector< int > > &p_distance, const vector< vector< SCIP_VAR > > &p_arc_var, const vector< vector< SCIP_CONS > > &p_arc_con, const vector< SCIP_CONS * > &p_part_con)

virtual	~ObjPricerVRP ()

virtual	SCIP_DECL_PRICERINIT (scip_init)

virtual	SCIP_DECL_PRICERREDCOST (scip_redcost)

virtual	SCIP_DECL_PRICERFARKAS (scip_farkas)

SCIP_RETCODE	pricing (SCIP *scip, bool isfarkas) const

SCIP_RETCODE	add_tour_variable (SCIP *scip, const list< int > &tour) const

double	find_shortest_tour (const vector< vector< double > > &length, list< int > &tour) const

Public Member Functions inherited from scip::ObjPricer
	ObjPricer (SCIP scip, const char name, const char *desc, int priority, SCIP_Bool delay)

virtual	~ObjPricer ()

virtual	SCIP_DECL_PRICERFREE (scip_free)

virtual	SCIP_DECL_PRICEREXIT (scip_exit)

virtual	SCIP_DECL_PRICERINITSOL (scip_initsol)

virtual	SCIP_DECL_PRICEREXITSOL (scip_exitsol)

Public Member Functions inherited from scip::ObjProbCloneable
virtual	~ObjProbCloneable ()

virtual	SCIP_DECL_OBJPROBCLONE (ObjProbCloneable *clone)

virtual	SCIP_DECL_OBJPROBISCLONEABLE (iscloneable)

Protected Member Functions
int	num_nodes () const

int	capacity () const

int	demand (const int i) const

double	distance (const int i, const int j) const

SCIP_VAR *	arc_var (const int i, const int j) const

SCIP_CONS *	arc_con (const int i, const int j) const

SCIP_CONS *	part_con (const int i) const

bool	have_edge (const int i, const int j) const

Additional Inherited Members
Data Fields inherited from scip::ObjPricer
SCIP *	scip_

char *	scip_name_

char *	scip_desc_

const int	scip_priority_

const SCIP_Bool	scip_delay_

Constructor & Destructor Documentation

◆ ObjPricerVRP()

ObjPricerVRP::ObjPricerVRP	(	SCIP *	scip,
		const char *	p_name,
		const int	p_num_nodes,
		const int	p_capacity,
		const vector< int > &	p_demand,
		const vector< vector< int > > &	p_distance,
		const vector< vector< SCIP_VAR *> > &	p_arc_var,
		const vector< vector< SCIP_CONS *> > &	p_arc_con,
		const vector< SCIP_CONS * > &	p_part_con
	)

Constructs the pricer object with the data needed

An alternative is to have a problem data class which allows to access the data.

Parameters

scip	SCIP pointer
p_name	name of pricer
p_num_nodes	number of nodes
p_capacity	vehicle capacity
p_demand	demand array
p_distance	matrix of distances
p_arc_var	matrix of arc variables
p_arc_con	matrix of arc constraints
p_part_con	array of partitioning constraints

Definition at line 41 of file pricer_vrp.cpp.

◆ ~ObjPricerVRP()

ObjPricerVRP::~ObjPricerVRP ( )

virtual

Destructs the pricer object.

Definition at line 64 of file pricer_vrp.cpp.

Member Function Documentation

◆ SCIP_DECL_PRICERINIT()

virtual ObjPricerVRP::SCIP_DECL_PRICERINIT ( scip_init )

virtual

initialization method of variable pricer (called after problem was transformed)

Reimplemented from scip::ObjPricer.

◆ SCIP_DECL_PRICERREDCOST()

virtual ObjPricerVRP::SCIP_DECL_PRICERREDCOST ( scip_redcost )

virtual

reduced cost pricing method of variable pricer for feasible LPs

Implements scip::ObjPricer.

◆ SCIP_DECL_PRICERFARKAS()

virtual ObjPricerVRP::SCIP_DECL_PRICERFARKAS ( scip_farkas )

virtual

farkas pricing method of variable pricer for infeasible LPs

Reimplemented from scip::ObjPricer.

◆ pricing()

SCIP_RETCODE ObjPricerVRP::pricing	(	SCIP *	scip,
		bool	isfarkas
	)		const

perform pricing

Parameters

scip	SCIP data structure
isfarkas	whether we perform Farkas pricing

Definition at line 97 of file pricer_vrp.cpp.

References add_tour_variable(), arc_con(), FALSE, find_shortest_tour(), NULL, num_nodes(), part_con(), r, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetDualfarkasLinear(), SCIPgetDualsolLinear(), SCIPinfoMessage(), SCIPisNegative(), and SCIPwriteTransProblem().

Referenced by SCIP_DECL_PRICERFARKAS(), and SCIP_DECL_PRICERREDCOST().

◆ add_tour_variable()

SCIP_RETCODE ObjPricerVRP::add_tour_variable	(	SCIP *	scip,
		const list< int > &	tour
	)		const

add tour variable to problem

Parameters

scip	SCIP data structure
tour	list of nodes in tour

Definition at line 249 of file pricer_vrp.cpp.

References arc_con(), demand(), eps, NULL, num_nodes(), part_con(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPaddCoefLinear(), SCIPaddPricedVar(), SCIPcreateVar(), SCIPdebugMsg, SCIPinfinity(), SCIPreleaseVar(), and SCIPsnprintf().

Referenced by pricing().

◆ find_shortest_tour()

SCIP_Real ObjPricerVRP::find_shortest_tour	(	const vector< vector< double > > &	length,
		list< int > &	tour
	)		const

return negative reduced cost tour (uses restricted shortest path dynamic programming algorithm)

The algorithm uses the priority queue implementation in pqueue.h. SCIP's implementation of priority queues cannot be used, since it currently does not support removal of elements that are not at the top.

Parameters

length	matrix of lengths
tour	list of nodes in tour

Definition at line 364 of file pricer_vrp.cpp.

References capacity(), demand(), eps, have_edge(), num_nodes(), SCIP_Real, and SCIPdebugMessage.

Referenced by pricing().

◆ num_nodes()

int ObjPricerVRP::num_nodes ( ) const

inlineprotected

return number of nodes

Definition at line 87 of file pricer_vrp.h.

Referenced by add_tour_variable(), find_shortest_tour(), pricing(), and SCIP_DECL_PRICERINIT().

◆ capacity()

int ObjPricerVRP::capacity ( ) const

inlineprotected

return vehicle capacity

Definition at line 93 of file pricer_vrp.h.

Referenced by find_shortest_tour().

◆ demand()

int ObjPricerVRP::demand ( const int i ) const

inlineprotected

return demand of node i

Parameters

i node

Definition at line 99 of file pricer_vrp.h.

Referenced by add_tour_variable(), and find_shortest_tour().

◆ distance()

double ObjPricerVRP::distance	(	const int	i,
		const int	j
	)		const

inlineprotected

return distance between nodes i and j

Parameters

i	first node
j	second node

Definition at line 107 of file pricer_vrp.h.

◆ arc_var()

SCIP_VAR* ObjPricerVRP::arc_var	(	const int	i,
		const int	j
	)		const

inlineprotected

return variable corresponding to arc between i and j

Parameters

i	first node
j	second node

Definition at line 116 of file pricer_vrp.h.

◆ arc_con()

SCIP_CONS* ObjPricerVRP::arc_con	(	const int	i,
		const int	j
	)		const

inlineprotected

return constraint corresponding to arc between i and j

Parameters

i	first node
j	second node

Definition at line 125 of file pricer_vrp.h.

Referenced by add_tour_variable(), and pricing().

◆ part_con()

SCIP_CONS* ObjPricerVRP::part_con ( const int i ) const

inlineprotected

return partitioning constraint for node i

Parameters

i node

Definition at line 134 of file pricer_vrp.h.

Referenced by add_tour_variable(), and pricing().

◆ have_edge()

bool ObjPricerVRP::have_edge	(	const int	i,
		const int	j
	)		const

inlineprotected

whether edge between node i and j exists

Parameters

i	first node
j	second node

Definition at line 142 of file pricer_vrp.h.

References SCIPvarGetUbLocal().

Referenced by find_shortest_tour().

SCIP

Detailed Description

Public Member Functions

Protected Member Functions

Additional Inherited Members

Constructor & Destructor Documentation

◆ ObjPricerVRP()

◆ ~ObjPricerVRP()

Member Function Documentation

◆ SCIP_DECL_PRICERINIT()

◆ SCIP_DECL_PRICERREDCOST()

◆ SCIP_DECL_PRICERFARKAS()

◆ pricing()

◆ add_tour_variable()

◆ find_shortest_tour()

◆ num_nodes()

◆ capacity()

◆ demand()

◆ distance()

◆ arc_var()

◆ arc_con()

◆ part_con()

◆ have_edge()