Scippy

SCIP

Solving Constraint Integer Programs

ObjPricerVRP Class Reference

Detailed Description

pricer class

Definition at line 45 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)
 
 ObjPricer (const ObjPricer &o)
 
 ObjPricer (ObjPricer &&o)
 
virtual ~ObjPricer ()
 
ObjPriceroperator= (const ObjPricer &o)=delete
 
ObjPriceroperator= (ObjPricer &&o)=delete
 
virtual SCIP_DECL_PRICERFREE (scip_free)
 
virtual SCIP_DECL_PRICERINIT (scip_init)
 
virtual SCIP_DECL_PRICEREXIT (scip_exit)
 
virtual SCIP_DECL_PRICERINITSOL (scip_initsol)
 
virtual SCIP_DECL_PRICEREXITSOL (scip_exitsol)
 
virtual SCIP_DECL_PRICERREDCOST (scip_redcost)=0
 
virtual SCIP_DECL_PRICERFARKAS (scip_farkas)
 
- Public Member Functions inherited from scip::ObjProbCloneable
virtual ~ObjProbCloneable ()
 
ObjProbCloneableoperator= (const ObjProbCloneable &o)=delete
 
ObjProbCloneableoperator= (ObjProbCloneable &&o)=delete
 
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_VARarc_var (const int i, const int j) const
 
SCIP_CONSarc_con (const int i, const int j) const
 
SCIP_CONSpart_con (const int i) const
 
bool have_edge (const int i, const int j) const
 

Additional Inherited Members

- Data Fields inherited from scip::ObjPricer
SCIPscip_
 
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

Constructs the pricer object with the data needed

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

Parameters
scipSCIP pointer
p_namename of pricer
p_num_nodesnumber of nodes
p_capacityvehicle capacity
p_demanddemand array
p_distancematrix of distances
p_arc_varmatrix of arc variables
p_arc_conmatrix of arc constraints
p_part_conarray of partitioning constraints

Definition at line 50 of file pricer_vrp.cpp.

◆ ~ObjPricerVRP()

ObjPricerVRP::~ObjPricerVRP ( )
virtual

Destructs the pricer object.

Definition at line 73 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

perform pricing

Parameters
scipSCIP data structure
isfarkaswhether we perform Farkas pricing

Definition at line 106 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().

◆ add_tour_variable()

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

add tour variable to problem

Parameters
scipSCIP data structure
tourlist of nodes in tour

Definition at line 258 of file pricer_vrp.cpp.

References arc_con(), NULL, num_nodes(), part_con(), SCIP_CALL, SCIP_OKAY, 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)

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
lengthmatrix of lengths
tourlist of nodes in tour

Definition at line 373 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 96 of file pricer_vrp.h.

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

◆ capacity()

int ObjPricerVRP::capacity ( ) const
inlineprotected

return vehicle capacity

Definition at line 102 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
inode

Definition at line 108 of file pricer_vrp.h.

Referenced by find_shortest_tour().

◆ distance()

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

return distance between nodes i and j

Parameters
ifirst node
jsecond node

Definition at line 116 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
ifirst node
jsecond node

Definition at line 125 of file pricer_vrp.h.

Referenced by have_edge().

◆ 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
ifirst node
jsecond node

Definition at line 134 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
inode

Definition at line 143 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
ifirst node
jsecond node

Definition at line 151 of file pricer_vrp.h.

References arc_var(), and SCIPvarGetUbLocal().

Referenced by find_shortest_tour().