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-2024 Zuse Institute Berlin (ZIB) */
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
40using namespace std;
41using namespace scip;
42
43
44/** pricer class */
45class ObjPricerVRP : public ObjPricer
46{
47public:
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 */
76 SCIP* scip, /**< SCIP data structure */
77 bool isfarkas /**< whether we perform Farkas pricing */
78 ) const;
79
80 /** add tour variable to problem */
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
93protected:
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 */
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
161private:
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
int num_nodes() const
Definition: pricer_vrp.h:96
virtual SCIP_DECL_PRICERINIT(scip_init)
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)
Definition: pricer_vrp.cpp:50
virtual ~ObjPricerVRP()
Definition: pricer_vrp.cpp:73
virtual SCIP_DECL_PRICERREDCOST(scip_redcost)
SCIP_RETCODE pricing(SCIP *scip, bool isfarkas) const
Definition: pricer_vrp.cpp:106
virtual SCIP_DECL_PRICERFARKAS(scip_farkas)
int capacity() const
Definition: pricer_vrp.h:102
bool have_edge(const int i, const int j) const
Definition: pricer_vrp.h:151
SCIP_RETCODE add_tour_variable(SCIP *scip, const list< int > &tour) const
Definition: pricer_vrp.cpp:258
SCIP_CONS * arc_con(const int i, const int j) const
Definition: pricer_vrp.h:134
double distance(const int i, const int j) const
Definition: pricer_vrp.h:116
int demand(const int i) const
Definition: pricer_vrp.h:108
double find_shortest_tour(const vector< vector< double > > &length, list< int > &tour) const
Definition: pricer_vrp.cpp:373
SCIP_VAR * arc_var(const int i, const int j) const
Definition: pricer_vrp.h:125
SCIP_CONS * part_con(const int i) const
Definition: pricer_vrp.h:143
C++ wrapper for variable pricer.
Definition: objpricer.h:53
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
Definition: pqueue.h:38
C++ wrapper classes for SCIP.
public methods for problem variables
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63