Generated on Mon Feb 8 2021 00:00:00 for Gecode by doxygen 1.8.20
tsp.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2007
8  *
9  * Bugfixes provided by:
10  * Geoffrey Chu
11  *
12  * This file is part of Gecode, the generic constraint
13  * development environment:
14  * http://www.gecode.org
15  *
16  * Permission is hereby granted, free of charge, to any person obtaining
17  * a copy of this software and associated documentation files (the
18  * "Software"), to deal in the Software without restriction, including
19  * without limitation the rights to use, copy, modify, merge, publish,
20  * distribute, sublicense, and/or sell copies of the Software, and to
21  * permit persons to whom the Software is furnished to do so, subject to
22  * the following conditions:
23  *
24  * The above copyright notice and this permission notice shall be
25  * included in all copies or substantial portions of the Software.
26  *
27  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
28  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
29  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
30  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
31  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
32  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
33  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
34  *
35  */
36 
37 #include <gecode/driver.hh>
38 #include <gecode/int.hh>
39 #include <gecode/minimodel.hh>
40 
41 #include <algorithm>
42 
43 using namespace Gecode;
44 
46 namespace {
47 
49  const int PA_n = 7;
50  const int PA_d[PA_n*PA_n] = {
51  0,205,677,581,461,878,345,
52  205,0,882,427,390,1105,540,
53  677,882,0,619,316,201,470,
54  581,427,619,0,412,592,570,
55  461,390,316,412,0,517,190,
56  878,1105,201,592,517,0,691,
57  345,540,470,570,190,691,0
58  };
59 
61  const int PB_n = 10;
62  const int PB_d[PB_n*PB_n] = {
63  2,4,4,1,9,2,4,4,1,9,
64  2,9,5,5,5,2,9,5,5,5,
65  1,5,2,3,3,1,5,2,3,3,
66  2,6,8,9,5,2,6,8,9,5,
67  3,7,1,6,4,3,7,1,6,4,
68  1,2,4,1,7,1,2,4,1,7,
69  3,5,2,7,6,3,5,2,7,6,
70  2,7,9,5,5,2,7,9,5,5,
71  3,9,7,3,4,3,9,7,3,4,
72  4,1,5,9,2,4,1,5,9,2
73  };
74 
76  const int PC_n = 17;
77  const int PC_d[PC_n*PC_n] = {
78  0,3,5,48,48,8,8,5,5,3,3,0,3,5,8,8,5,
79  3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5,
80  5,3,0,72,72,48,48,24,24,3,3,5,3,0,48,48,24,
81  48,48,74,0,0,6,6,12,12,48,48,48,48,74,6,6,12,
82  48,48,74,0,0,6,6,12,12,48,48,48,48,74,6,6,12,
83  8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8,
84  8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8,
85  5,5,26,12,12,8,8,0,0,5,5,5,5,26,8,8,0,
86  5,5,26,12,12,8,8,0,0,5,5,5,5,26,8,8,0,
87  3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5,
88  3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5,
89  0,3,5,48,48,8,8,5,5,3,3,0,3,5,8,8,5,
90  3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5,
91  5,3,0,72,72,48,48,24,24,3,3,5,3,0,48,48,24,
92  8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8,
93  8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8,
94  5,5,26,12,12,8,8,0,0,5,5,5,5,26,8,8,0
95  };
96 
98  const int PD_n = 34;
99  const int PD_d[PD_n*PD_n] = {
100  0,26,82,65,100,147,134,69,117,42,89,125,38,13,38,31,22,103,
101  143,94,104,123,98,58,38,30,67,120,149,100,93,162,62,66,66,0,
102  56,39,109,156,140,135,183,108,155,190,104,79,104,97,88,130,176,121,
103  131,150,125,85,65,57,94,147,160,80,67,189,128,40,43,57,0,16,
104  53,100,84,107,155,85,132,168,81,56,81,74,65,146,186,137,147,166,
105  141,101,81,73,110,163,164,102,71,205,105,62,27,41,62,0,97,144,
106  131,96,144,69,116,152,65,40,65,58,49,130,170,121,131,150,125,85,
107  65,57,94,147,166,86,73,189,89,46,109,135,161,174,0,47,34,54,
108  102,67,114,175,97,96,128,135,131,198,193,203,213,232,207,167,147,139,
109  176,229,222,204,148,235,60,175,157,171,114,130,60,0,40,114,162,127,
110  174,235,157,156,188,188,179,258,253,251,239,258,203,215,195,187,172,207,
111  175,157,101,295,120,133,143,169,132,148,34,31,0,88,133,101,148,209,
112  131,130,162,169,165,232,227,237,247,266,221,201,181,173,190,225,193,175,
113  119,269,94,151,95,121,177,160,54,101,88,0,48,53,100,158,83,82,
114  114,121,117,184,179,189,199,218,193,153,133,125,162,215,244,195,188,221,
115  46,161,79,105,161,144,91,138,125,37,0,37,53,114,67,66,98,105,
116  101,137,132,149,183,202,177,137,117,109,146,199,228,179,172,174,57,145,
117  42,68,124,107,67,114,101,27,75,0,47,108,30,29,61,68,64,131,
118  126,136,146,165,140,100,80,72,109,162,191,142,135,168,20,108,83,109,
119  165,148,108,155,142,68,88,41,0,61,71,70,102,109,105,84,79,96,
120  144,163,175,141,121,113,150,203,232,183,176,121,61,149,204,230,286,269,
121  216,255,237,162,125,162,123,0,192,191,223,230,226,144,139,156,184,165,
122  215,249,242,234,251,282,332,297,297,113,182,270,38,64,120,103,88,135,
123  122,57,105,30,77,87,0,25,31,38,47,110,105,122,142,161,136,96,
124  76,68,105,158,187,138,131,147,50,104,13,39,95,78,87,134,121,56,
125  104,29,76,112,25,0,32,39,35,116,130,107,117,136,111,71,51,43,
126  80,133,162,113,106,172,49,79,38,48,104,87,119,166,153,88,136,61,
127  108,118,31,32,0,7,16,123,136,114,124,143,118,78,58,50,87,140,
128  169,120,115,178,81,88,31,41,97,80,115,162,149,84,132,57,104,114,
129  27,28,7,0,9,116,132,107,117,136,111,71,51,43,80,133,162,113,
130  108,174,77,81,22,32,88,71,122,169,156,91,139,64,111,123,36,35,
131  16,9,0,107,141,98,108,127,102,62,42,34,71,124,153,104,99,166,
132  84,72,108,134,190,173,133,180,167,93,113,66,85,60,96,95,127,134,
133  130,0,46,63,116,135,147,166,146,138,175,221,257,208,201,120,86,174,
134  127,153,209,192,152,199,186,112,132,85,104,79,115,114,146,153,149,19,
135  0,17,70,89,101,135,148,157,137,175,219,183,220,85,105,193,153,179,
136  235,218,178,225,212,138,158,111,130,105,141,140,172,179,175,45,57,0,
137  53,72,84,118,131,183,120,158,202,166,241,68,131,214,179,165,199,204,
138  243,290,277,203,223,176,195,165,206,192,199,192,183,110,112,82,0,19,
139  31,65,78,149,67,105,149,113,188,95,196,161,212,205,239,244,237,284,
140  271,197,217,170,189,146,200,199,231,232,223,104,93,63,40,0,71,105,
141  118,189,107,117,167,153,228,76,190,201,148,134,168,173,212,259,246,172,
142  192,145,164,139,175,161,168,161,152,79,125,70,36,55,0,34,47,118,
143  36,89,118,82,157,131,165,130,153,146,180,185,178,225,212,138,158,111,
144  130,105,141,140,172,173,164,45,91,36,46,65,77,0,59,130,48,101,
145  130,94,169,104,131,142,173,166,200,205,198,245,232,158,178,131,150,125,
146  161,160,192,193,184,65,111,56,66,85,97,20,0,150,68,121,150,114,
147  189,124,151,162,30,16,72,55,125,172,156,99,147,72,119,133,68,43,
148  50,43,34,73,119,64,74,93,68,28,8,0,37,90,119,70,83,132,
149  92,56,112,98,132,137,185,232,216,181,223,154,195,170,150,125,132,125,
150  116,110,156,101,67,86,31,65,78,82,0,53,82,46,121,162,174,94,
151  144,130,164,169,217,256,225,213,261,186,233,234,182,157,164,157,148,174,
152  209,165,131,116,95,129,122,114,93,0,50,78,147,192,206,126,94,80,
153  114,119,167,214,198,163,211,136,183,197,132,107,114,107,98,137,183,128,
154  110,129,74,92,72,64,43,57,0,28,103,196,156,76,66,52,101,91,
155  154,201,185,135,183,108,155,169,104,79,86,79,70,109,155,100,82,101,
156  46,64,44,36,15,68,97,0,90,168,128,63,113,108,70,86,84,131,
157  115,138,186,151,198,225,151,126,142,135,126,165,211,156,138,157,102,120,
158  100,92,71,124,93,56,0,224,144,32,146,172,228,211,171,218,205,131,
159  151,104,123,80,134,133,165,172,168,38,27,44,75,76,106,140,153,176,
160  142,180,224,188,239,0,124,212,102,128,184,167,61,108,95,7,55,60,
161  107,165,90,89,121,128,124,191,186,196,206,225,200,160,140,132,169,222,
162  251,202,195,228,0,168,81,95,38,54,91,138,122,145,193,123,170,206,
163  119,94,119,112,103,184,224,175,165,184,129,139,119,111,98,151,120,83,
164  27,243,143,0
165  };
166 
168  class Problem {
169  private:
170  const int _n;
171  const int* _d;
172  public:
174  Problem(const int n, const int* d);
176  int size(void) const;
178  int d(int i, int j) const;
180  const int* d(void) const;
182  int max(void) const;
183  };
184 
185  inline
186  Problem::Problem(const int n, const int* d)
187  : _n(n), _d(d) {}
188  inline int
189  Problem::size(void) const {
190  return _n;
191  }
192  inline int
193  Problem::d(int i, int j) const {
194  return _d[i*_n+j];
195  }
196  inline const int*
197  Problem::d(void) const {
198  return _d;
199  }
200  inline int
201  Problem::max(void) const {
202  int m=0;
203  for (int i=0; i<_n*_n; i++)
204  m = std::max(m,_d[i]);
205  return m*_n;
206  }
207 
208  Problem PA(PA_n,PA_d);
209  Problem PB(PB_n,PB_d);
210  Problem PC(PC_n,PC_d);
211  Problem PD(PD_n,PD_d);
212 
213  Problem ps[] = {PA,PB,PC,PD};
214  const unsigned int ps_n = sizeof(ps) / sizeof(Problem);
215 
216 }
217 
227 class TSP : public IntMinimizeScript {
228 protected:
230  Problem p;
235 public:
239  p(ps[opt.size()]),
240  succ(*this, p.size(), 0, p.size()-1),
241  total(*this, 0, p.max()) {
242  int n = p.size();
243 
244  // Cost matrix
245  IntArgs c(n*n, p.d());
246 
247  // Disallow disconnected nodes
248  for (int i=0; i<n; i++)
249  for (int j=0; j<n; j++)
250  if (p.d(i,j) == 0)
251  rel(*this, succ[i], IRT_NQ, j);
252 
253  // Cost of each edge
255 
256  // Enforce that the succesors yield a tour with appropriate costs
257  circuit(*this, c, succ, costs, total, opt.ipl());
258 
259  // Just assume that the circle starts forwards
260  {
261  IntVar p0(*this, 0, n-1);
262  element(*this, succ, p0, 0);
263  rel(*this, p0, IRT_LE, succ[0]);
264  }
265 
266  // First enumerate cost values, prefer those that maximize cost reduction
267  branch(*this, costs, INT_VAR_REGRET_MAX_MAX(), INT_VAL_MIN());
268 
269  // Then fix the remaining successors
270  branch(*this, succ, INT_VAR_MIN_MIN(), INT_VAL_MIN());
271  }
273  virtual IntVar cost(void) const {
274  return total;
275  }
277  TSP(TSP& s) : IntMinimizeScript(s), p(s.p) {
278  succ.update(*this, s.succ);
279  total.update(*this, s.total);
280  }
282  virtual Space*
283  copy(void) {
284  return new TSP(*this);
285  }
287  virtual void
288  print(std::ostream& os) const {
289  bool assigned = true;
290  for (int i=0; i<succ.size(); i++) {
291  if (!succ[i].assigned()) {
292  assigned = false;
293  break;
294  }
295  }
296  if (assigned) {
297  os << "\tTour: ";
298  int i=0;
299  do {
300  os << i << " -> ";
301  i=succ[i].val();
302  } while (i != 0);
303  os << 0 << std::endl;
304  os << "\tCost: " << total << std::endl;
305  } else {
306  os << "\tTour: " << std::endl;
307  for (int i=0; i<succ.size(); i++) {
308  os << "\t" << i << " -> " << succ[i] << std::endl;
309  }
310  os << "\tCost: " << total << std::endl;
311  }
312  }
313 };
314 
315 
316 
320 int
321 main(int argc, char* argv[]) {
322  SizeOptions opt("TSP");
323  opt.solutions(0);
324  opt.ipl(IPL_DOM);
325  opt.parse(argc,argv);
326 
327  if (opt.size() >= ps_n) {
328  std::cerr << "Error: size must be between 0 and "
329  << ps_n-1 << std::endl;
330  return 1;
331  }
332 
333  IntMinimizeScript::run<TSP,BAB,SizeOptions>(opt);
334  return 0;
335 }
336 
337 // STATISTICS: example-any
virtual Space * copy(void)
Copy during cloning.
Definition: tsp.cpp:283
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
IntVar total
Total cost of travel.
Definition: tsp.cpp:234
TSP(const SizeOptions &opt)
Actual model.
Definition: tsp.cpp:237
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl)
Select variable with smallest min.
Definition: var.hpp:186
Passing integer variables.
Definition: int.hh:656
void element(Home home, IntSharedArray c, IntVar x0, IntVar x1, IntPropLevel)
Post domain consistent propagator for .
Definition: element.cpp:39
unsigned int size(I &i)
Size of all ranges of range iterator i.
Problem p
Problem instance to be solved.
Definition: tsp.cpp:230
@ IRT_LE
Less ( )
Definition: int.hh:929
TSP(TSP &s)
Constructor for cloning s.
Definition: tsp.cpp:277
IntVarArray succ
Successor edges.
Definition: tsp.cpp:232
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
void branch(Home home, const IntVarArgs &x, const BoolVarArgs &y, IntBoolVarBranch vars, IntValBranch vals)
Branch function for integer and Boolean variables.
Definition: branch.cpp:120
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
Multi _d(Gecode::IntArgs({3, 2, 1}))
Computation spaces.
Definition: core.hpp:1742
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:55
Integer variable array.
Definition: int.hh:763
virtual IntVar cost(void) const
Return solution cost.
Definition: tsp.cpp:273
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:926
Gecode toplevel namespace
Options opt
The options.
Definition: test.cpp:97
Parametric base-class for scripts.
Definition: driver.hh:729
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition: int.hh:979
void circuit(Home home, int offset, const IntVarArgs &x, IntPropLevel ipl)
Post propagator such that x forms a circuit.
Definition: circuit.cpp:41
Integer variables.
Definition: int.hh:371
virtual void print(std::ostream &os) const
Print solution.
Definition: tsp.cpp:288
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
Example: Travelling salesman problem (TSP)
Definition: tsp.cpp:227
Gecode::IntSet d(v, 7)
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition: var.hpp:116
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition: test.cpp:120
@ IRT_NQ
Disequality ( )
Definition: int.hh:927
int main(int argc, char *argv[])
Main-function.
Definition: tsp.cpp:321
Gecode::FloatVal c(-8, 8)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Passing integer arguments.
Definition: int.hh:628
Gecode::IntArgs i({1, 2, 3, 4})
IntVarBranch INT_VAR_REGRET_MAX_MAX(BranchTbl tbl)
Select variable with largest max-regret.
Definition: var.hpp:301
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1013
Options for scripts with additional size parameter
Definition: driver.hh:675