00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
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
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
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
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
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
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
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
00218