Scippy

SCIP

Solving Constraint Integer Programs

pricer_vrp.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License. */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file pricer_vrp.h
17  * @brief VRP pricer plugin
18  * @author Andreas Bley
19  * @author Marc Pfetsch
20  */
21 
22 #ifndef __SCIP_PRICER_VRP_H__
23 #define __SCIP_PRICER_VRP_H__
24 
25 #include "objscip/objscip.h"
26 #include "scip/pub_var.h"
27 
28 #include <vector>
29 #include <list>
30 
31 using namespace std;
32 using namespace scip;
33 
34 
35 /** pricer class */
36 class ObjPricerVRP : public ObjPricer
37 {
38 public:
39 
40  /** Constructs the pricer object with the data needed */
42  SCIP* scip, /**< SCIP pointer */
43  const char* p_name, /**< name of pricer */
44  const int p_num_nodes, /**< number of nodes */
45  const int p_capacity, /**< vehicle capacity */
46  const vector< int >& p_demand, /**< demand array */
47  const vector< vector<int> >& p_distance, /**< matrix of distances */
48  const vector< vector<SCIP_VAR*> >& p_arc_var, /**< matrix of arc variables */
49  const vector< vector<SCIP_CONS*> >& p_arc_con, /**< matrix of arc constraints */
50  const vector<SCIP_CONS* >& p_part_con /**< array of partitioning constraints */
51  );
52 
53  /** Destructs the pricer object. */
54  virtual ~ObjPricerVRP();
55 
56  /** initialization method of variable pricer (called after problem was transformed) */
57  virtual SCIP_DECL_PRICERINIT(scip_init);
58 
59  /** reduced cost pricing method of variable pricer for feasible LPs */
60  virtual SCIP_DECL_PRICERREDCOST(scip_redcost);
61 
62  /** farkas pricing method of variable pricer for infeasible LPs */
63  virtual SCIP_DECL_PRICERFARKAS(scip_farkas);
64 
65  /** perform pricing */
67  SCIP* scip, /**< SCIP data structure */
68  bool isfarkas /**< whether we perform Farkas pricing */
69  ) const;
70 
71  /** add tour variable to problem */
72  SCIP_RETCODE add_tour_variable(
73  SCIP* scip, /**< SCIP data structure */
74  const list<int>& tour /**< list of nodes in tour */
75  ) const;
76 
77  /** return negative reduced cost tour (uses restricted shortest path dynamic programming algorithm) */
78  double find_shortest_tour(
79  const vector< vector<double> >& length, /**< matrix of lengths */
80  list<int>& tour /**< list of nodes in tour */
81  ) const;
82 
83 
84 protected:
85 
86  /** return number of nodes */
87  inline int num_nodes() const
88  {
89  return _num_nodes;
90  }
91 
92  /** return vehicle capacity */
93  inline int capacity() const
94  {
95  return _capacity;
96  }
97 
98  /** return demand of node i*/
99  inline int demand(
100  const int i /**< node */
101  ) const
102  {
103  return _demand[i]; /*lint !e747 !e732*/
104  }
105 
106  /** return distance between nodes i and j */
107  inline double distance(
108  const int i, /**< first node */
109  const int j /**< second node */
110  ) const
111  {
112  return ( i > j ? _distance[i][j] : _distance[j][i] ); /*lint !e747 !e732*/
113  }
114 
115  /** return variable corresponding to arc between i and j */
116  inline SCIP_VAR* arc_var(
117  const int i, /**< first node */
118  const int j /**< second node */
119  ) const
120  {
121  return ( i > j ? _arc_var[i][j] : _arc_var[j][i] ); /*lint !e747 !e732*/
122  }
123 
124  /** return constraint corresponding to arc between i and j */
126  const int i, /**< first node */
127  const int j /**< second node */
128  ) const
129  {
130  return ( i > j ? _arc_con[i][j] : _arc_con[j][i] ); /*lint !e747 !e732*/
131  }
132 
133  /** return partitioning constraint for node i */
135  const int i /**< node */
136  ) const
137  {
138  return _part_con[i]; /*lint !e747 !e732*/
139  }
140 
141  /** whether edge between node i and j exists */
142  inline bool have_edge(
143  const int i, /**< first node */
144  const int j /**< second node */
145  ) const
146  {
147  /* return whether variable is not fixed to 0 */
148  return ( SCIPvarGetUbLocal( arc_var(i, j) ) > 0.5 );
149  }
150 
151 
152 private:
153 
154  const int _num_nodes; /**< number of nodes */
155  const int _capacity; /**< vehicle capacity */
156  const vector< int > _demand; /**< demand array */
157  const vector< vector<int> > _distance; /**< distance matrix */
158 
159  vector< vector<SCIP_VAR*> > _arc_var; /**< matrix of arc variables */
160  vector< vector<SCIP_CONS*> > _arc_con; /**< matrix of arc constraints */
161  vector<SCIP_CONS* > _part_con; /**< array of partitioning constraints */
162 };
163 
164 #endif
SCIP_VAR * arc_var(const int i, const int j) const
Definition: pricer_vrp.h:116
C++ wrapper for variable pricer.
Definition: objpricer.h:42
int num_nodes() const
Definition: pricer_vrp.h:87
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
public methods for problem variables
bool have_edge(const int i, const int j) const
Definition: pricer_vrp.h:142
SCIP_CONS * arc_con(const int i, const int j) const
Definition: pricer_vrp.h:125
int capacity() const
Definition: pricer_vrp.h:93
Definition: pqueue.h:28
static SCIP_RETCODE pricing(SCIP *scip, SCIP_PRICER *pricer, SCIP_Real *lowerbound, SCIP_Bool farkas)
Definition: pricer_stp.c:176
C++ wrapper classes for SCIP.
SCIP_DECL_PRICERINIT(ObjPricerVRP::scip_init)
Definition: pricer_vrp.cpp:74
double distance(const int i, const int j) const
Definition: pricer_vrp.h:107
SCIP_DECL_PRICERFARKAS(ObjPricerVRP::scip_farkas)
Definition: pricer_vrp.cpp:237
SCIP_DECL_PRICERREDCOST(ObjPricerVRP::scip_redcost)
Definition: pricer_vrp.cpp:216
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17733
int demand(const int i) const
Definition: pricer_vrp.h:99
SCIP_CONS * part_con(const int i) const
Definition: pricer_vrp.h:134