Generated on Wed Jan 4 17:49:07 2006 for Gecode by doxygen 1.4.6

packing.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2003
00008  *     Mikael Lagerkvist, 2005
00009  *
00010  *  Last modified:
00011  *     $Date: 2005-11-04 22:52:06 +0100 (Fri, 04 Nov 2005) $ by $Author: schulte $
00012  *     $Revision: 2507 $
00013  *
00014  *  This file is part of Gecode, the generic constraint
00015  *  development environment:
00016  *     http://www.gecode.org
00017  *
00018  *  See the file "LICENSE" for information on usage and
00019  *  redistribution of this file, and for a
00020  *     DISCLAIMER OF ALL WARRANTIES.
00021  *
00022  */
00023 
00024 #include "examples/support.hh"
00025 #include "minimodel.hh"
00026 
00032 //@
00034 class PackingSpec {
00035 public:
00036   int x; int y;
00037   int n; const int* s;
00038   PackingSpec(int x0, int y0, const int s0[]) :
00039     x(x0), y(y0), s(s0) {
00040     int i = 0;
00041     while (s[i]) i++;
00042     n = i;
00043   }
00044 };
00045 
00046 static const int s0_s[] = {2,2,2,2,0};
00047 static const PackingSpec s0(4,4,s0_s);
00048 
00049 static const int s1_s[] = {3,2,2,1,1,1,0};
00050 static const PackingSpec s1(5,4,s1_s);
00051 
00052 static const int s2_s[] = {6,4,4,4,2,2,2,2,0};
00053 static PackingSpec s2(10,10,s2_s);
00054 
00055 static const int s3_s[] = {9,8,8,7,5,4,4,4,4,4,3,3,3,2,2,1,1,0};
00056 static const PackingSpec s3(20,20,s3_s);
00057 
00058 static const int s4_s[] = {18,15,14,10,9,8,7,4,1,0};
00059 static const PackingSpec s4(32,33,s4_s);
00060 
00061 static const int s5_s[] = {25,24,23,22,19,17,11,6,5,3,0};
00062 static const PackingSpec s5(65,47,s5_s);
00063 
00064 static const int s6_s[] = {50,42,37,35,33,29,27,25,24,19,18,
00065                            17,16,15,11,9,8,7,6,4,2,0};
00066 static const PackingSpec s6(112,112,s6_s);
00067 
00068 static const int s7_s[] = {81,64,56,55,51,43,39,38,35,33,31,30,29,20,
00069                            18,16,14,9,8,5,4,3,2,1,0};
00070 static const PackingSpec s7(175,175,s7_s);
00071 
00072 static const PackingSpec* specs[] = {&s0,&s1,&s2,&s3,&s4,&s5,&s6,&s7};
00073 static const unsigned int n_examples = sizeof(specs) / sizeof(PackingSpec*);
00075 
00081 class Packing : public Example {
00082 protected:
00084   const PackingSpec& s;
00086   IntVarArray x;
00088   IntVarArray y;
00089 public:
00091   Packing(const Options& opt)
00092     : s(*specs[opt.size]), 
00093       x(this,s.n,0,s.x-1), 
00094       y(this,s.n,0,s.y-1) {
00095     // Restrict position according to square size
00096     for (int i=s.n; i--; ) {
00097       rel(this, x[i], IRT_LQ, s.x-s.s[i]);
00098       rel(this, y[i], IRT_LQ, s.y-s.s[i]);
00099     }
00100     // Squares do not overlap
00101     {
00102       BoolVarArgs b(4);
00103       for (int i=0; i<s.n; i++) {
00104         for (int j=i+1; j<s.n; j++) {
00105           b[0]=post(this, ~(x[j]-x[i] >= s.s[i]));
00106           b[1]=post(this, ~(x[i]-x[j] >= s.s[j]));
00107           b[2]=post(this, ~(y[j]-y[i] >= s.s[i]));
00108           b[3]=post(this, ~(y[i]-y[j] >= s.s[j]));
00109           linear(this, b, IRT_GQ, 1);
00110         }
00111       }
00112     }
00113 
00114     /*
00115      * Symmetry breaking
00116      *
00117      */
00118     for (int i=s.n-1; i--; )
00119       if (s.s[i] == s.s[i+1])
00120         rel(this, x[i], IRT_LQ, x[i+1]);
00121 
00122     /*
00123      * Capacity constraints
00124      *
00125      */
00126     if (opt.naive) {
00127       IntArgs sa(s.n,s.s);
00128       BoolVarArgs b(s.n);
00129       for (int cx=0; cx<s.x; cx++) {
00130         for (int i=0; i<s.n; i++) {
00131           BoolVar b_cx(this,0,1);
00132           dom(this, x[i], cx-s.s[i]+1, cx, b_cx);
00133           b[i] = b_cx;
00134         }
00135         linear(this, sa, b, IRT_EQ, s.y);
00136       }
00137       for (int cy=0; cy<s.y; cy++) {
00138         for (int i=0; i<s.n; i++) {
00139           BoolVar b_cy(this,0,1);
00140           dom(this, y[i], cy-s.s[i]+1, cy, b_cy);
00141           b[i] = b_cy;
00142         }
00143         linear(this, sa, b, IRT_EQ, s.x);
00144       }
00145     } else {
00146       IntArgs m(s.n), dh(s.n);
00147       for (int i = s.n; i--; ) {
00148         m[i]  = 0;
00149         dh[i] = s.s[i];
00150       }
00151       IntVarArgs e(s.n);
00152       IntArgs limit(1);
00153       {
00154         // x-direction
00155         for (int i = s.n; i--; ) {
00156           IntVar ei(this, 0, s.x);
00157           e[i] = ei;
00158         }
00159         limit[0] = s.y;
00160         cumulatives(this, m, x, dh, e, dh, limit,  true);
00161         cumulatives(this, m, x, dh, e, dh, limit, false);
00162       }
00163       { 
00164         // y-direction
00165         for (int i = s.n; i--; ) {
00166           IntVar ei(this, 0, s.y);
00167           e[i] = ei;
00168         }
00169         limit[0] = s.x;
00170         cumulatives(this, m, y, dh, e, dh, limit,  true);
00171         cumulatives(this, m, y, dh, e, dh, limit, false);
00172       }
00173     }
00174 
00175     branch(this, x, BVAR_MIN_MIN, BVAL_MIN);
00176     branch(this, y, BVAR_MIN_MIN, BVAL_MIN);
00177   }
00178 
00180   Packing(bool share, Packing& s) : Example(share,s), s(s.s) {
00181     x.update(this, share, s.x);
00182     y.update(this, share, s.y);
00183   }
00185   virtual Space*
00186   copy(bool share) {
00187     return new Packing(share,*this);
00188   }
00190   virtual void
00191   print(void) {
00192     std::cout << "\t";
00193     for (int i=0; i<s.n; i++)
00194       std::cout << "(" << x[i] << "," << y[i] << ") ";
00195     std::cout << std::endl;
00196   }
00197 };
00198 
00202 int
00203 main(int argc, char** argv) {
00204   Options opt("Packing");
00205   opt.naive = true;
00206   opt.size  = 7;
00207   opt.parse(argc,argv);
00208   if (opt.size >= n_examples) {
00209     std::cerr << "Error: size must be between 0 and " << n_examples - 1
00210               << std::endl;
00211     return 1;
00212   }
00213   Example::run<Packing,DFS>(opt);
00214   return 0;
00215 }
00216 
00217 // STATISTICS: example-any
00218