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-2014 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 email to scip@zib.de. */
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 */
66  SCIP_RETCODE pricing(
67  SCIP* scip, /**< SCIP data structure */
68  bool isfarkas /**< whether we perform Farkas pricing */
69  );
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  );
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  );
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];
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] );
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] );
122  }
123 
124  /** return constraint corresponding to arc between i and j */
125  inline SCIP_CONS* arc_con(
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] );
131  }
132 
133  /** return partitioning constraint for node i */
134  inline SCIP_CONS* part_con(
135  const int i /**< node */
136  ) const
137  {
138  return _part_con[i];
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
165