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 2002-2022 Zuse Institute Berlin */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file pricer_vrp.h
26  * @brief VRP pricer plugin
27  * @author Andreas Bley
28  * @author Marc Pfetsch
29  */
30 
31 #ifndef __SCIP_PRICER_VRP_H__
32 #define __SCIP_PRICER_VRP_H__
33 
34 #include "objscip/objscip.h"
35 #include "scip/pub_var.h"
36 
37 #include <vector>
38 #include <list>
39 
40 using namespace std;
41 using namespace scip;
42 
43 
44 /** pricer class */
45 class ObjPricerVRP : public ObjPricer
46 {
47 public:
48 
49  /** Constructs the pricer object with the data needed */
51  SCIP* scip, /**< SCIP pointer */
52  const char* p_name, /**< name of pricer */
53  const int p_num_nodes, /**< number of nodes */
54  const int p_capacity, /**< vehicle capacity */
55  const vector< int >& p_demand, /**< demand array */
56  const vector< vector<int> >& p_distance, /**< matrix of distances */
57  const vector< vector<SCIP_VAR*> >& p_arc_var, /**< matrix of arc variables */
58  const vector< vector<SCIP_CONS*> >& p_arc_con, /**< matrix of arc constraints */
59  const vector<SCIP_CONS* >& p_part_con /**< array of partitioning constraints */
60  );
61 
62  /** Destructs the pricer object. */
63  virtual ~ObjPricerVRP();
64 
65  /** initialization method of variable pricer (called after problem was transformed) */
66  virtual SCIP_DECL_PRICERINIT(scip_init);
67 
68  /** reduced cost pricing method of variable pricer for feasible LPs */
69  virtual SCIP_DECL_PRICERREDCOST(scip_redcost);
70 
71  /** farkas pricing method of variable pricer for infeasible LPs */
72  virtual SCIP_DECL_PRICERFARKAS(scip_farkas);
73 
74  /** perform pricing */
75  SCIP_RETCODE pricing(
76  SCIP* scip, /**< SCIP data structure */
77  bool isfarkas /**< whether we perform Farkas pricing */
78  ) const;
79 
80  /** add tour variable to problem */
81  SCIP_RETCODE add_tour_variable(
82  SCIP* scip, /**< SCIP data structure */
83  const list<int>& tour /**< list of nodes in tour */
84  ) const;
85 
86  /** return negative reduced cost tour (uses restricted shortest path dynamic programming algorithm) */
87  double find_shortest_tour(
88  const vector< vector<double> >& length, /**< matrix of lengths */
89  list<int>& tour /**< list of nodes in tour */
90  ) const;
91 
92 
93 protected:
94 
95  /** return number of nodes */
96  inline int num_nodes() const
97  {
98  return _num_nodes;
99  }
100 
101  /** return vehicle capacity */
102  inline int capacity() const
103  {
104  return _capacity;
105  }
106 
107  /** return demand of node i*/
108  inline int demand(
109  const int i /**< node */
110  ) const
111  {
112  return _demand[i]; /*lint !e747 !e732*/
113  }
114 
115  /** return distance between nodes i and j */
116  inline double distance(
117  const int i, /**< first node */
118  const int j /**< second node */
119  ) const
120  {
121  return ( i > j ? _distance[i][j] : _distance[j][i] ); /*lint !e747 !e732*/
122  }
123 
124  /** return variable corresponding to arc between i and j */
125  inline SCIP_VAR* arc_var(
126  const int i, /**< first node */
127  const int j /**< second node */
128  ) const
129  {
130  return ( i > j ? _arc_var[i][j] : _arc_var[j][i] ); /*lint !e747 !e732*/
131  }
132 
133  /** return constraint corresponding to arc between i and j */
135  const int i, /**< first node */
136  const int j /**< second node */
137  ) const
138  {
139  return ( i > j ? _arc_con[i][j] : _arc_con[j][i] ); /*lint !e747 !e732*/
140  }
141 
142  /** return partitioning constraint for node i */
144  const int i /**< node */
145  ) const
146  {
147  return _part_con[i]; /*lint !e747 !e732*/
148  }
149 
150  /** whether edge between node i and j exists */
151  inline bool have_edge(
152  const int i, /**< first node */
153  const int j /**< second node */
154  ) const
155  {
156  /* return whether variable is not fixed to 0 */
157  return ( SCIPvarGetUbLocal( arc_var(i, j) ) > 0.5 );
158  }
159 
160 
161 private:
162 
163  const int _num_nodes; /**< number of nodes */
164  const int _capacity; /**< vehicle capacity */
165  const vector< int > _demand; /**< demand array */
166  const vector< vector<int> > _distance; /**< distance matrix */
167 
168  vector< vector<SCIP_VAR*> > _arc_var; /**< matrix of arc variables */
169  vector< vector<SCIP_CONS*> > _arc_con; /**< matrix of arc constraints */
170  vector<SCIP_CONS* > _part_con; /**< array of partitioning constraints */
171 };
172 
173 #endif
SCIP_VAR * arc_var(const int i, const int j) const
Definition: pricer_vrp.h:125
C++ wrapper for variable pricer.
Definition: objpricer.h:52
int num_nodes() const
Definition: pricer_vrp.h:96
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
public methods for problem variables
bool have_edge(const int i, const int j) const
Definition: pricer_vrp.h:151
SCIP_CONS * arc_con(const int i, const int j) const
Definition: pricer_vrp.h:134
int capacity() const
Definition: pricer_vrp.h:102
Definition: pqueue.h:37
C++ wrapper classes for SCIP.
SCIP_DECL_PRICERINIT(ObjPricerVRP::scip_init)
Definition: pricer_vrp.cpp:83
double distance(const int i, const int j) const
Definition: pricer_vrp.h:116
SCIP_DECL_PRICERFARKAS(ObjPricerVRP::scip_farkas)
Definition: pricer_vrp.cpp:246
SCIP_DECL_PRICERREDCOST(ObjPricerVRP::scip_redcost)
Definition: pricer_vrp.cpp:225
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17985
int demand(const int i) const
Definition: pricer_vrp.h:108
SCIP_CONS * part_con(const int i) const
Definition: pricer_vrp.h:143