tsp.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2007 00008 * 00009 * Bugfixes provided by: 00010 * Geoffrey Chu 00011 * 00012 * Last modified: 00013 * $Date: 2010-10-07 11:52:01 +0200 (Thu, 07 Oct 2010) $ by $Author: schulte $ 00014 * $Revision: 11473 $ 00015 * 00016 * This file is part of Gecode, the generic constraint 00017 * development environment: 00018 * http://www.gecode.org 00019 * 00020 * Permission is hereby granted, free of charge, to any person obtaining 00021 * a copy of this software and associated documentation files (the 00022 * "Software"), to deal in the Software without restriction, including 00023 * without limitation the rights to use, copy, modify, merge, publish, 00024 * distribute, sublicense, and/or sell copies of the Software, and to 00025 * permit persons to whom the Software is furnished to do so, subject to 00026 * the following conditions: 00027 * 00028 * The above copyright notice and this permission notice shall be 00029 * included in all copies or substantial portions of the Software. 00030 * 00031 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00032 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00033 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00034 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00035 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00036 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00037 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00038 * 00039 */ 00040 00041 #include <gecode/driver.hh> 00042 #include <gecode/int.hh> 00043 #include <gecode/minimodel.hh> 00044 #include <gecode/graph.hh> 00045 00046 #include <algorithm> 00047 00048 using namespace Gecode; 00049 00051 namespace { 00052 00054 const int PA_n = 7; 00055 const int PA_d[PA_n*PA_n] = { 00056 0,205,677,581,461,878,345, 00057 205,0,882,427,390,1105,540, 00058 677,882,0,619,316,201,470, 00059 581,427,619,0,412,592,570, 00060 461,390,316,412,0,517,190, 00061 878,1105,201,592,517,0,691, 00062 345,540,470,570,190,691,0 00063 }; 00064 00066 const int PB_n = 10; 00067 const int PB_d[PB_n*PB_n] = { 00068 2,4,4,1,9,2,4,4,1,9, 00069 2,9,5,5,5,2,9,5,5,5, 00070 1,5,2,3,3,1,5,2,3,3, 00071 2,6,8,9,5,2,6,8,9,5, 00072 3,7,1,6,4,3,7,1,6,4, 00073 1,2,4,1,7,1,2,4,1,7, 00074 3,5,2,7,6,3,5,2,7,6, 00075 2,7,9,5,5,2,7,9,5,5, 00076 3,9,7,3,4,3,9,7,3,4, 00077 4,1,5,9,2,4,1,5,9,2 00078 }; 00079 00081 const int PC_n = 17; 00082 const int PC_d[PC_n*PC_n] = { 00083 0,3,5,48,48,8,8,5,5,3,3,0,3,5,8,8,5, 00084 3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5, 00085 5,3,0,72,72,48,48,24,24,3,3,5,3,0,48,48,24, 00086 48,48,74,0,0,6,6,12,12,48,48,48,48,74,6,6,12, 00087 48,48,74,0,0,6,6,12,12,48,48,48,48,74,6,6,12, 00088 8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8, 00089 8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8, 00090 5,5,26,12,12,8,8,0,0,5,5,5,5,26,8,8,0, 00091 5,5,26,12,12,8,8,0,0,5,5,5,5,26,8,8,0, 00092 3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5, 00093 3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5, 00094 0,3,5,48,48,8,8,5,5,3,3,0,3,5,8,8,5, 00095 3,0,3,48,48,8,8,5,5,0,0,3,0,3,8,8,5, 00096 5,3,0,72,72,48,48,24,24,3,3,5,3,0,48,48,24, 00097 8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8, 00098 8,8,50,6,6,0,0,8,8,8,8,8,8,50,0,0,8, 00099 5,5,26,12,12,8,8,0,0,5,5,5,5,26,8,8,0 00100 }; 00101 00103 const int PD_n = 34; 00104 const int PD_d[PD_n*PD_n] = { 00105 0,26,82,65,100,147,134,69,117,42,89,125,38,13,38,31,22,103, 00106 143,94,104,123,98,58,38,30,67,120,149,100,93,162,62,66,66,0, 00107 56,39,109,156,140,135,183,108,155,190,104,79,104,97,88,130,176,121, 00108 131,150,125,85,65,57,94,147,160,80,67,189,128,40,43,57,0,16, 00109 53,100,84,107,155,85,132,168,81,56,81,74,65,146,186,137,147,166, 00110 141,101,81,73,110,163,164,102,71,205,105,62,27,41,62,0,97,144, 00111 131,96,144,69,116,152,65,40,65,58,49,130,170,121,131,150,125,85, 00112 65,57,94,147,166,86,73,189,89,46,109,135,161,174,0,47,34,54, 00113 102,67,114,175,97,96,128,135,131,198,193,203,213,232,207,167,147,139, 00114 176,229,222,204,148,235,60,175,157,171,114,130,60,0,40,114,162,127, 00115 174,235,157,156,188,188,179,258,253,251,239,258,203,215,195,187,172,207, 00116 175,157,101,295,120,133,143,169,132,148,34,31,0,88,133,101,148,209, 00117 131,130,162,169,165,232,227,237,247,266,221,201,181,173,190,225,193,175, 00118 119,269,94,151,95,121,177,160,54,101,88,0,48,53,100,158,83,82, 00119 114,121,117,184,179,189,199,218,193,153,133,125,162,215,244,195,188,221, 00120 46,161,79,105,161,144,91,138,125,37,0,37,53,114,67,66,98,105, 00121 101,137,132,149,183,202,177,137,117,109,146,199,228,179,172,174,57,145, 00122 42,68,124,107,67,114,101,27,75,0,47,108,30,29,61,68,64,131, 00123 126,136,146,165,140,100,80,72,109,162,191,142,135,168,20,108,83,109, 00124 165,148,108,155,142,68,88,41,0,61,71,70,102,109,105,84,79,96, 00125 144,163,175,141,121,113,150,203,232,183,176,121,61,149,204,230,286,269, 00126 216,255,237,162,125,162,123,0,192,191,223,230,226,144,139,156,184,165, 00127 215,249,242,234,251,282,332,297,297,113,182,270,38,64,120,103,88,135, 00128 122,57,105,30,77,87,0,25,31,38,47,110,105,122,142,161,136,96, 00129 76,68,105,158,187,138,131,147,50,104,13,39,95,78,87,134,121,56, 00130 104,29,76,112,25,0,32,39,35,116,130,107,117,136,111,71,51,43, 00131 80,133,162,113,106,172,49,79,38,48,104,87,119,166,153,88,136,61, 00132 108,118,31,32,0,7,16,123,136,114,124,143,118,78,58,50,87,140, 00133 169,120,115,178,81,88,31,41,97,80,115,162,149,84,132,57,104,114, 00134 27,28,7,0,9,116,132,107,117,136,111,71,51,43,80,133,162,113, 00135 108,174,77,81,22,32,88,71,122,169,156,91,139,64,111,123,36,35, 00136 16,9,0,107,141,98,108,127,102,62,42,34,71,124,153,104,99,166, 00137 84,72,108,134,190,173,133,180,167,93,113,66,85,60,96,95,127,134, 00138 130,0,46,63,116,135,147,166,146,138,175,221,257,208,201,120,86,174, 00139 127,153,209,192,152,199,186,112,132,85,104,79,115,114,146,153,149,19, 00140 0,17,70,89,101,135,148,157,137,175,219,183,220,85,105,193,153,179, 00141 235,218,178,225,212,138,158,111,130,105,141,140,172,179,175,45,57,0, 00142 53,72,84,118,131,183,120,158,202,166,241,68,131,214,179,165,199,204, 00143 243,290,277,203,223,176,195,165,206,192,199,192,183,110,112,82,0,19, 00144 31,65,78,149,67,105,149,113,188,95,196,161,212,205,239,244,237,284, 00145 271,197,217,170,189,146,200,199,231,232,223,104,93,63,40,0,71,105, 00146 118,189,107,117,167,153,228,76,190,201,148,134,168,173,212,259,246,172, 00147 192,145,164,139,175,161,168,161,152,79,125,70,36,55,0,34,47,118, 00148 36,89,118,82,157,131,165,130,153,146,180,185,178,225,212,138,158,111, 00149 130,105,141,140,172,173,164,45,91,36,46,65,77,0,59,130,48,101, 00150 130,94,169,104,131,142,173,166,200,205,198,245,232,158,178,131,150,125, 00151 161,160,192,193,184,65,111,56,66,85,97,20,0,150,68,121,150,114, 00152 189,124,151,162,30,16,72,55,125,172,156,99,147,72,119,133,68,43, 00153 50,43,34,73,119,64,74,93,68,28,8,0,37,90,119,70,83,132, 00154 92,56,112,98,132,137,185,232,216,181,223,154,195,170,150,125,132,125, 00155 116,110,156,101,67,86,31,65,78,82,0,53,82,46,121,162,174,94, 00156 144,130,164,169,217,256,225,213,261,186,233,234,182,157,164,157,148,174, 00157 209,165,131,116,95,129,122,114,93,0,50,78,147,192,206,126,94,80, 00158 114,119,167,214,198,163,211,136,183,197,132,107,114,107,98,137,183,128, 00159 110,129,74,92,72,64,43,57,0,28,103,196,156,76,66,52,101,91, 00160 154,201,185,135,183,108,155,169,104,79,86,79,70,109,155,100,82,101, 00161 46,64,44,36,15,68,97,0,90,168,128,63,113,108,70,86,84,131, 00162 115,138,186,151,198,225,151,126,142,135,126,165,211,156,138,157,102,120, 00163 100,92,71,124,93,56,0,224,144,32,146,172,228,211,171,218,205,131, 00164 151,104,123,80,134,133,165,172,168,38,27,44,75,76,106,140,153,176, 00165 142,180,224,188,239,0,124,212,102,128,184,167,61,108,95,7,55,60, 00166 107,165,90,89,121,128,124,191,186,196,206,225,200,160,140,132,169,222, 00167 251,202,195,228,0,168,81,95,38,54,91,138,122,145,193,123,170,206, 00168 119,94,119,112,103,184,224,175,165,184,129,139,119,111,98,151,120,83, 00169 27,243,143,0 00170 }; 00171 00173 class Problem { 00174 private: 00175 const int _n; 00176 const int* _d; 00177 public: 00179 Problem(const int n, const int* d); 00181 int size(void) const; 00183 int d(int i, int j) const; 00185 const int* d(void) const; 00187 int max(void) const; 00188 }; 00189 00190 inline 00191 Problem::Problem(const int n, const int* d) 00192 : _n(n), _d(d) {} 00193 inline int 00194 Problem::size(void) const { 00195 return _n; 00196 } 00197 inline int 00198 Problem::d(int i, int j) const { 00199 return _d[i*_n+j]; 00200 } 00201 inline const int* 00202 Problem::d(void) const { 00203 return _d; 00204 } 00205 inline int 00206 Problem::max(void) const { 00207 int m=0; 00208 for (int i=_n*_n; i--; ) 00209 m = std::max(m,_d[i]); 00210 return m*_n; 00211 } 00212 00213 Problem PA(PA_n,PA_d); 00214 Problem PB(PB_n,PB_d); 00215 Problem PC(PC_n,PC_d); 00216 Problem PD(PD_n,PD_d); 00217 00218 Problem ps[] = {PA,PB,PC,PD}; 00219 const unsigned int ps_n = sizeof(ps) / sizeof(Problem); 00220 00221 } 00222 00232 class TSP : public MinimizeScript { 00233 protected: 00235 Problem p; 00237 IntVarArray succ; 00239 IntVar total; 00240 public: 00242 TSP(const SizeOptions& opt) 00243 : p(ps[opt.size()]), 00244 succ(*this, p.size(), 0, p.size()-1), 00245 total(*this, 0, p.max()) { 00246 int n = p.size(); 00247 00248 // Cost matrix 00249 IntArgs c(n*n, p.d()); 00250 00251 for (int i=n; i--; ) 00252 for (int j=n; j--; ) 00253 if (p.d(i,j) == 0) 00254 rel(*this, succ[i], IRT_NQ, j); 00255 00256 // Cost of each edge 00257 IntVarArgs costs(*this, n, Int::Limits::min, Int::Limits::max); 00258 00259 // Enforce that the succesors yield a tour with appropriate costs 00260 circuit(*this, c, succ, costs, total, opt.icl()); 00261 00262 // Just assume that the circle starts forwards 00263 { 00264 IntVar p0(*this, 0, n-1); 00265 element(*this, succ, p0, 0); 00266 rel(*this, p0, IRT_LE, succ[0]); 00267 } 00268 00269 // First enumerate cost values, prefer those that maximize cost reduction 00270 branch(*this, costs, INT_VAR_REGRET_MAX_MAX, INT_VAL_SPLIT_MIN); 00271 00272 // Then fix the remaining successors 00273 branch(*this, succ, INT_VAR_MIN_MIN, INT_VAL_MIN); 00274 } 00276 virtual IntVar cost(void) const { 00277 return total; 00278 } 00280 TSP(bool share, TSP& s) : MinimizeScript(share,s), p(s.p) { 00281 succ.update(*this, share, s.succ); 00282 total.update(*this, share, s.total); 00283 } 00285 virtual Space* 00286 copy(bool share) { 00287 return new TSP(share,*this); 00288 } 00290 virtual void 00291 print(std::ostream& os) const { 00292 bool assigned = true; 00293 for (int i=0; i<succ.size(); i++) { 00294 if (!succ[i].assigned()) { 00295 assigned = false; 00296 break; 00297 } 00298 } 00299 if (assigned) { 00300 os << "\tTour: "; 00301 int i=0; 00302 do { 00303 os << i << " -> "; 00304 i=succ[i].val(); 00305 } while (i != 0); 00306 os << 0 << std::endl; 00307 os << "\tCost: " << total << std::endl; 00308 } else { 00309 os << "\tTour: " << std::endl; 00310 for (int i=0; i<succ.size(); i++) { 00311 os << "\t" << i << " -> " << succ[i] << std::endl; 00312 } 00313 os << "\tCost: " << total << std::endl; 00314 } 00315 } 00316 }; 00317 00318 00319 00323 int 00324 main(int argc, char* argv[]) { 00325 SizeOptions opt("TSP"); 00326 opt.solutions(0); 00327 opt.icl(ICL_DOM); 00328 opt.parse(argc,argv); 00329 00330 if (opt.size() >= ps_n) { 00331 std::cerr << "Error: size must be between 0 and " 00332 << ps_n-1 << std::endl; 00333 return 1; 00334 } 00335 00336 MinimizeScript::run<TSP,BAB,SizeOptions>(opt); 00337 return 0; 00338 } 00339 00340 // STATISTICS: example-any