Generated on Wed Jul 27 2011 15:08:34 for Gecode by doxygen 1.7.4
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