52 const int PA_d[PA_n*PA_n] = {
53 0,205,677,581,461,878,345,
54 205,0,882,427,390,1105,540,
55 677,882,0,619,316,201,470,
56 581,427,619,0,412,592,570,
57 461,390,316,412,0,517,190,
58 878,1105,201,592,517,0,691,
59 345,540,470,570,190,691,0
64 const int PB_d[PB_n*PB_n] = {
65 2,4,4,1,9,2,4,4,1,9,
66 2,9,5,5,5,2,9,5,5,5,
67 1,5,2,3,3,1,5,2,3,3,
68 2,6,8,9,5,2,6,8,9,5,
69 3,7,1,6,4,3,7,1,6,4,
70 1,2,4,1,7,1,2,4,1,7,
71 3,5,2,7,6,3,5,2,7,6,
72 2,7,9,5,5,2,7,9,5,5,
73 3,9,7,3,4,3,9,7,3,4,
79 const int PC_d[PC_n*PC_n] = {
80 0,3,5,48,48,8,8,5,5,3,3,0,3,5,8,8,5,
81 3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5,
82 5,3,0,72,72,48,48,24,24,3,3,5,3,0,48,48,24,
83 48,48,74,0,0,6,6,12,12,48,48,48,48,74,6,6,12,
84 48,48,74,0,0,6,6,12,12,48,48,48,48,74,6,6,12,
85 8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8,
86 8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8,
87 5,5,26,12,12,8,8,0,0,5,5,5,5,26,8,8,0,
88 5,5,26,12,12,8,8,0,0,5,5,5,5,26,8,8,0,
89 3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5,
90 3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5,
91 0,3,5,48,48,8,8,5,5,3,3,0,3,5,8,8,5,
92 3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5,
93 5,3,0,72,72,48,48,24,24,3,3,5,3,0,48,48,24,
94 8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8,
95 8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8,
96 5,5,26,12,12,8,8,0,0,5,5,5,5,26,8,8,0
101 const int PD_d[PD_n*PD_n] = {
102 0,26,82,65,100,147,134,69,117,42,89,125,38,13,38,31,22,103,
103 143,94,104,123,98,58,38,30,67,120,149,100,93,162,62,66,66,0,
104 56,39,109,156,140,135,183,108,155,190,104,79,104,97,88,130,176,121,
105 131,150,125,85,65,57,94,147,160,80,67,189,128,40,43,57,0,16,
106 53,100,84,107,155,85,132,168,81,56,81,74,65,146,186,137,147,166,
107 141,101,81,73,110,163,164,102,71,205,105,62,27,41,62,0,97,144,
108 131,96,144,69,116,152,65,40,65,58,49,130,170,121,131,150,125,85,
109 65,57,94,147,166,86,73,189,89,46,109,135,161,174,0,47,34,54,
110 102,67,114,175,97,96,128,135,131,198,193,203,213,232,207,167,147,139,
111 176,229,222,204,148,235,60,175,157,171,114,130,60,0,40,114,162,127,
112 174,235,157,156,188,188,179,258,253,251,239,258,203,215,195,187,172,207,
113 175,157,101,295,120,133,143,169,132,148,34,31,0,88,133,101,148,209,
114 131,130,162,169,165,232,227,237,247,266,221,201,181,173,190,225,193,175,
115 119,269,94,151,95,121,177,160,54,101,88,0,48,53,100,158,83,82,
116 114,121,117,184,179,189,199,218,193,153,133,125,162,215,244,195,188,221,
117 46,161,79,105,161,144,91,138,125,37,0,37,53,114,67,66,98,105,
118 101,137,132,149,183,202,177,137,117,109,146,199,228,179,172,174,57,145,
119 42,68,124,107,67,114,101,27,75,0,47,108,30,29,61,68,64,131,
120 126,136,146,165,140,100,80,72,109,162,191,142,135,168,20,108,83,109,
121 165,148,108,155,142,68,88,41,0,61,71,70,102,109,105,84,79,96,
122 144,163,175,141,121,113,150,203,232,183,176,121,61,149,204,230,286,269,
123 216,255,237,162,125,162,123,0,192,191,223,230,226,144,139,156,184,165,
124 215,249,242,234,251,282,332,297,297,113,182,270,38,64,120,103,88,135,
125 122,57,105,30,77,87,0,25,31,38,47,110,105,122,142,161,136,96,
126 76,68,105,158,187,138,131,147,50,104,13,39,95,78,87,134,121,56,
127 104,29,76,112,25,0,32,39,35,116,130,107,117,136,111,71,51,43,
128 80,133,162,113,106,172,49,79,38,48,104,87,119,166,153,88,136,61,
129 108,118,31,32,0,7,16,123,136,114,124,143,118,78,58,50,87,140,
130 169,120,115,178,81,88,31,41,97,80,115,162,149,84,132,57,104,114,
131 27,28,7,0,9,116,132,107,117,136,111,71,51,43,80,133,162,113,
132 108,174,77,81,22,32,88,71,122,169,156,91,139,64,111,123,36,35,
133 16,9,0,107,141,98,108,127,102,62,42,34,71,124,153,104,99,166,
134 84,72,108,134,190,173,133,180,167,93,113,66,85,60,96,95,127,134,
135 130,0,46,63,116,135,147,166,146,138,175,221,257,208,201,120,86,174,
136 127,153,209,192,152,199,186,112,132,85,104,79,115,114,146,153,149,19,
137 0,17,70,89,101,135,148,157,137,175,219,183,220,85,105,193,153,179,
138 235,218,178,225,212,138,158,111,130,105,141,140,172,179,175,45,57,0,
139 53,72,84,118,131,183,120,158,202,166,241,68,131,214,179,165,199,204,
140 243,290,277,203,223,176,195,165,206,192,199,192,183,110,112,82,0,19,
141 31,65,78,149,67,105,149,113,188,95,196,161,212,205,239,244,237,284,
142 271,197,217,170,189,146,200,199,231,232,223,104,93,63,40,0,71,105,
143 118,189,107,117,167,153,228,76,190,201,148,134,168,173,212,259,246,172,
144 192,145,164,139,175,161,168,161,152,79,125,70,36,55,0,34,47,118,
145 36,89,118,82,157,131,165,130,153,146,180,185,178,225,212,138,158,111,
146 130,105,141,140,172,173,164,45,91,36,46,65,77,0,59,130,48,101,
147 130,94,169,104,131,142,173,166,200,205,198,245,232,158,178,131,150,125,
148 161,160,192,193,184,65,111,56,66,85,97,20,0,150,68,121,150,114,
149 189,124,151,162,30,16,72,55,125,172,156,99,147,72,119,133,68,43,
150 50,43,34,73,119,64,74,93,68,28,8,0,37,90,119,70,83,132,
151 92,56,112,98,132,137,185,232,216,181,223,154,195,170,150,125,132,125,
152 116,110,156,101,67,86,31,65,78,82,0,53,82,46,121,162,174,94,
153 144,130,164,169,217,256,225,213,261,186,233,234,182,157,164,157,148,174,
154 209,165,131,116,95,129,122,114,93,0,50,78,147,192,206,126,94,80,
155 114,119,167,214,198,163,211,136,183,197,132,107,114,107,98,137,183,128,
156 110,129,74,92,72,64,43,57,0,28,103,196,156,76,66,52,101,91,
157 154,201,185,135,183,108,155,169,104,79,86,79,70,109,155,100,82,101,
158 46,64,44,36,15,68,97,0,90,168,128,63,113,108,70,86,84,131,
159 115,138,186,151,198,225,151,126,142,135,126,165,211,156,138,157,102,120,
160 100,92,71,124,93,56,0,224,144,32,146,172,228,211,171,218,205,131,
161 151,104,123,80,134,133,165,172,168,38,27,44,75,76,106,140,153,176,
162 142,180,224,188,239,0,124,212,102,128,184,167,61,108,95,7,55,60,
163 107,165,90,89,121,128,124,191,186,196,206,225,200,160,140,132,169,222,
164 251,202,195,228,0,168,81,95,38,54,91,138,122,145,193,123,170,206,
165 119,94,119,112,103,184,224,175,165,184,129,139,119,111,98,151,120,83,
179 Problem(
const int n,
const int* d);
181 Problem(
const int n,
const IntArgs& d);
183 bool valid(
void)
const;
185 int size(
void)
const;
187 int d(
int i,
int j)
const;
189 const int*
d(
void)
const;
195 Problem::Problem(
void)
196 : _n(0),
_d(nullptr) {}
198 Problem::Problem(
const int n,
const int* d)
201 Problem::Problem(
const int n,
const IntArgs& d)
202 : _n(n), _s(
d),
_d(&_s[0]) {}
204 Problem::valid(
void)
const {
208 Problem::size(
void)
const {
212 Problem::d(
int i,
int j)
const {
216 Problem::d(
void)
const {
220 Problem::max(
void)
const {
222 for (
int i=0;
i<_n*_n;
i++)
223 m = std::max(m,_d[i]);
227 Problem PA(PA_n,PA_d);
228 Problem PB(PB_n,PB_d);
229 Problem PC(PC_n,PC_d);
230 Problem PD(PD_n,PD_d);
232 Problem ps[] = {PA,PB,PC,PD};
233 const unsigned int ps_n =
sizeof(ps) /
sizeof(Problem);
249sections until "EOF" {
250 "NAME : {name:rest}" optional
251 "TYPE : {type:word}" optional
252 "DIMENSION : {n:2..46340}"
253 "EDGE_WEIGHT_TYPE : {edge_weight_type:word}" optional
254 "EDGE_WEIGHT_FORMAT : {edge_weight_format:word}" optional
255 "NODE_COORD_TYPE : {node_coord_type:word}" optional
256 "DISPLAY_DATA_TYPE : {display_data_type:word}" optional
257 "NODE_COORD_SECTION" optional {
258 repeat n { node: int x: float y: float }
260 "EDGE_WEIGHT_SECTION" optional {
261 if !defined(edge_weight_format) { let edge_weight_format = "FULL_MATRIX" }
262 weight[n][n]: 0..gecode.int_max / n layout edge_weight_format
264 "DISPLAY_DATA_SECTION" optional {
265 repeat n { display_node: int display_x: float display_y: float }
268if !defined(edge_weight_type) { let edge_weight_type = "EXPLICIT" }
270if edge_weight_type == "EXPLICIT" {
271 check defined(weight) "no EDGE_WEIGHT_SECTION"
272 check size(weight) == n "edge weights do not match DIMENSION"
274 check edge_weight_type == "EUC_2D" || edge_weight_type == "CEIL_2D" || edge_weight_type == "ATT" ||
275 edge_weight_type == "GEO" "EDGE_WEIGHT_TYPE must be EXPLICIT, EUC_2D, CEIL_2D, ATT, or GEO"
276 check defined(x) "no NODE_COORD_SECTION"
277 check size(x) == n "coordinates do not match DIMENSION"
278 check x >= -1e9 && x <= 1e9 && y >= -1e9 && y <= 1e9 "coordinates must be between -1e9 and 1e9"
283 long long int nint(
double x) {
284 return static_cast<long long int>(x + 0.5);
288 double geo(
double x) {
289 const double pi = 3.141592;
292 double deg = std::trunc(x);
293 double min = x - deg;
294 return pi * (deg + 5.0 *
min / 3.0) / 180.0;
298 Instance::Error error(
const std::string& file,
const std::string& m) {
299 return Instance::Error(file +
": " + m);
310 IntArgs distances(
const Instance::Data& d,
const std::string& file) {
312 int n =
static_cast<int>(
d.integer(
"n"));
313 std::string type =
d.text(
"edge_weight_type");
314 if (type ==
"EXPLICIT")
315 return d.ints(
"weight");
316 ArgArray<double> x =
d.numbers(
"x"), y =
d.numbers(
"y");
318 for (
int i=0;
i<n;
i++)
319 for (
int j=0; j<n; j++) {
320 double dx = x[
i]-x[j], dy = y[
i]-y[j];
325 }
else if (type ==
"EUC_2D") {
326 v = nint(std::sqrt(dx*dx + dy*dy));
327 }
else if (type ==
"CEIL_2D") {
328 v =
static_cast<long long int>(std::ceil(std::sqrt(dx*dx + dy*dy)));
329 }
else if (type ==
"ATT") {
330 double r = std::sqrt((dx*dx + dy*dy) / 10.0);
331 long long int t = nint(r);
332 v = (
static_cast<double>(t) <
r) ? t+1 : t;
335 const double rrr = 6378.388;
336 double q1 = std::cos(geo(y[i]) - geo(y[j]));
337 double q2 = std::cos(geo(x[i]) - geo(x[j]));
338 double q3 = std::cos(geo(x[i]) + geo(x[j]));
340 double a = std::max(-1.0, std::min(1.0, 0.5*((1.0+q1)*q2 - (1.0-q1)*q3)));
341 v =
static_cast<long long int>(rrr * std::acos(a) + 1.0);
345 throw error(file,
"distance too large");
346 dist[
i*n+j] =
static_cast<int>(
v);
357 Problem problem(
const InstanceOptions& opt) {
360 return (i < ps_n) ? ps[
i] : Problem();
363 Instance::Data
d =
opt.data();
364 return Problem(
static_cast<int>(
d.integer(
"n")), distances(d,
opt.instance()));
394 succ(*this,
p.size(), 0,
p.size()-1),
432 return new TSP(*
this);
437 bool assigned =
true;
438 for (
int i=0; i<
succ.size(); i++) {
439 if (!
succ[i].assigned()) {
451 os << 0 << std::endl;
452 os <<
"\tCost: " <<
total << std::endl;
454 os <<
"\tTour: " << std::endl;
455 for (
int i=0; i<
succ.size(); i++) {
456 os <<
"\t" << i <<
" -> " <<
succ[i] << std::endl;
458 os <<
"\tCost: " <<
total << std::endl;
474 opt.
parse(argc,argv);
477 if (!problem(opt).valid()) {
478 std::cerr <<
"Error: instance must be a number between 0 and " << ps_n-1 <<
" or a TSPLIB file" << std::endl;
482 std::cerr << e.
what() << std::endl;
static void run(const Options &opt, Script *s=nullptr)
Options for scripts with additional instance parameter
Exception for errors in specs and instance files
virtual const char * what(void) const noexcept override
Return the full message.
Passing integer arguments.
Passing integer variables.
int main(int argc, char *argv[])
Main-function.
IntVar total
Total cost of travel.
const char * instance_spec
Reader spec for TSPLIB files.
virtual void print(std::ostream &os) const
Print solution.
TSP(TSP &s)
Constructor for cloning s.
IntVarArray succ
Successor edges.
virtual Space * copy(void)
Copy during cloning.
virtual IntVar cost(void) const
Return solution cost.
Problem p
Problem instance to be solved.
TSP(const InstanceOptions &opt)
Actual model.
void parse(int argc, char *argv[])
Parse commandline arguments.
Driver::ScriptBase< Driver::IgnoreStepOption< IntMinimizeSpace > > IntMinimizeScript
Base-class for scripts for finding solution of lowest integer cost.
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
bool valid(const FloatVal &n)
Return whether float n is a valid number.
const int min
Smallest allowed integer value.
const int max
Largest allowed integer value.
unsigned int size(I &i)
Size of all ranges of range iterator i.
Gecode toplevel namespace
SharedArray< int > IntSharedArray
Arrays of integers that can be shared among several element constraints.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void element(Home home, IntSharedArray n, IntVar x0, IntVar x1, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for .
IntVarBranch INT_VAR_REGRET_MAX_MAX(BranchTbl tbl=nullptr)
Select variable with largest max-regret.
IntValBranch INT_VAL_MIN(void)
Select smallest value.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void circuit(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a circuit.
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl=nullptr)
Select variable with smallest min.
Gecode::FloatVal a(-8, 5)
Gecode::IntArgs i({1, 2, 3, 4})
Multi _d(Gecode::IntArgs({3, 2, 1}))