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