Generated on Mon May 10 06:46:30 2010 for Gecode by doxygen 1.6.3

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-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $
00014  *     $Revision: 10684 $
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(n);
00258 
00259     // Initialize cost variables for edges
00260     for (int i=n; i--; )
00261       costs[i].init(*this, Int::Limits::min, Int::Limits::max);
00262 
00263     // Enforce that the succesors yield a tour with appropriate costs
00264     circuit(*this, c, succ, costs, total, opt.icl());
00265 
00266     // Just assume that the circle starts forwards
00267     {
00268       IntVar p0(*this, 0, n-1);
00269       element(*this, succ, p0, 0);
00270       rel(*this, p0, IRT_LE, succ[0]);
00271     }
00272 
00273     // First enumerate cost values, prefer those that maximize cost reduction
00274     branch(*this, costs, INT_VAR_REGRET_MAX_MAX, INT_VAL_SPLIT_MIN);
00275 
00276     // Then fix the remaining successors
00277     branch(*this, succ,  INT_VAR_MIN_MIN, INT_VAL_MIN);
00278   }
00280   virtual IntVar cost(void) const {
00281     return total;
00282   }
00284   TSP(bool share, TSP& s) : MinimizeScript(share,s), p(s.p) {
00285     succ.update(*this, share, s.succ);
00286     total.update(*this, share, s.total);
00287   }
00289   virtual Space*
00290   copy(bool share) {
00291     return new TSP(share,*this);
00292   }
00294   virtual void
00295   print(std::ostream& os) const {
00296     bool assigned = true;
00297     for (int i=0; i<succ.size(); i++) {
00298       if (!succ[i].assigned()) {
00299         assigned = false;
00300         break;
00301       }
00302     }
00303     if (assigned) {
00304       os << "\tTour: ";
00305       int i=0;
00306       do {
00307         os << i << " -> ";
00308         i=succ[i].val();
00309       } while (i != 0);
00310       os << 0 << std::endl;
00311       os << "\tCost: " << total << std::endl;
00312     } else {
00313       os << "\tTour: " << std::endl;
00314       for (int i=0; i<succ.size(); i++) {
00315         os << "\t" << i << " -> " << succ[i] << std::endl;
00316       }
00317       os << "\tCost: " << total << std::endl;
00318     }
00319   }
00320 };
00321 
00322 
00323 
00327 int
00328 main(int argc, char* argv[]) {
00329   SizeOptions opt("TSP");
00330   opt.solutions(0);
00331   opt.icl(ICL_DOM);
00332   opt.parse(argc,argv);
00333 
00334   if (opt.size() >= ps_n) {
00335     std::cerr << "Error: size must be between 0 and "
00336               << ps_n-1 << std::endl;
00337     return 1;
00338   }
00339 
00340   MinimizeScript::run<TSP,BAB,SizeOptions>(opt);
00341   return 0;
00342 }
00343 
00344 // STATISTICS: example-any