this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 * Mikael Lagerkvist <lagerkvist@gecode.org>
6 *
7 * Copyright:
8 * Christian Schulte, 2003
9 * Mikael Lagerkvist, 2005
10 *
11 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.org
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
36#include <gecode/driver.hh>
37#include <gecode/int.hh>
38#include <gecode/minimodel.hh>
39
40using namespace Gecode;
41
42/**
43 * \name Specifications for perfect square problems
44 *
45 * The first element is the number of squares to be placed, the
46 * second the size of the master square, and the remaining the
47 * sizes of the squares to be packed.
48 *
49 * The data is taken from: C. J. Bouwkamp and A. J. W.
50 * Duijvestijn, Catalogue of Simple Perfect Squared Squares of Orders
51 * 21 Through 25, Eindhoven Univ. Technology, Dept. of Math.,
52 * Report 92-WSK-03, Nov. 1992.
53 *
54 * \relates PerfectSquare
55 */
56//@
57const int s00[] = {
58 21, 112,
59 50,42,37,35,33,29,27,25,24,19,18,17,16,15,11,9,8,7,6,4,2
60};
61const int s01[] = {
62 22, 110,
63 60,50,28,27,26,24,23,22,21,18,17,16,15,14,13,12,8,7,6,4,3,2
64};
65const int s02[] = {
66 22, 192,
67 86,71,62,59,57,49,47,41,37,36,35,31,28,26,19,17,14,12,10,9,8,4
68};
69const int s03[] = {
70 23, 110,
71 44,41,38,37,32,31,29,28,21,19,16,15,14,13,12,10,8,7,5,4,3,2,1
72};
73const int s04[] = {
74 23, 332,
75 129,123,120,112,91,89,83,68,58,56,53,50,49,48,47,38,31,30,26,24,17,15,1
76};
77const int s05[] = {
78 24, 120,
79 47,46,41,40,34,33,32,25,23,20,19,17,16,15,14,13,12,10,9,8,6,5,4,3
80};
81const int s06[] = {
82 24, 479,
83 175,174,164,160,155,150,140,130,86,77,68,60,52,44,43,35,29,28,26,24,23,17,6,5
84};
85const int s07[] = {
86 25, 147,
87 74,73,41,40,34,33,32,27,25,23,20,19,17,16,15,14,13,12,10,9,8,6,5,4,3
88};
89const int s08[] = {
90 25, 661,
91 262,248,238,210,203,196,175,161,111,106,102,84,83,77,73,64,41,38,36,31,23,18,17,7,5
92};
93const int s09[] = {
94 26, 212,
95 99,85,65,62,57,56,55,48,39,38,32,28,26,24,23,20,19,17,16,12,7,6,5,4,2,1
96};
97const int s10[] = {
98 26, 214,
99 86,72,67,64,61,56,55,44,43,39,36,35,34,32,30,29,27,26,23,20,19,10,9,8,6,5
100};
101const int s11[] = {
102 26, 825,
103 304,302,288,277,246,235,233,189,157,135,127,117,109,92,90,83,81,76,57,53,49,37,26,25,8,5
104};
105const int s12[] = {
106 27, 180,
107 89,56,51,50,48,43,41,40,39,36,34,31,29,25,23,21,19,16,15,13,12,10,9,7,6,4,1
108};
109const int s13[] = {
110 27, 1179,
111 484,440,387,379,360,352,316,308,198,194,168,149,145,119,114,108,82,80,69,66,63,50,42,35,29,24,18
112};
113const int s14[] = {
114 28, 201,
115 77,70,68,67,64,56,54,39,38,36,34,32,30,24,22,21,18,17,16,13,12,11,10,6,4,3,2,1
116};
117const int s15[] = {
118 28, 1544,
119 649,615,510,473,456,439,419,385,260,216,214,208,203,175,147,135,125,116,104,94,81,55,49,17,12,7,6,4
120};
121const int s16[] = {
122 29, 255,
123 112,107,84,75,68,64,59,51,49,43,37,36,31,29,28,27,26,25,24,22,17,15,13,11,8,7,6,2,1
124};
125const int s17[] = {
126 29, 2134,
127 855,769,761,717,648,604,562,518,338,293,292,286,265,226,224,204,186,179,174,165,161,109,100,91,69,45,43,17,9
128};
129const int s18[] = {
130 30, 237,
131 88,82,79,76,73,56,53,46,45,43,40,39,36,34,33,32,29,27,25,24,23,21,20,16,11,10,9,5,3,1
132};
133const int s19[] = {
134 30, 2710,
135 992,981,948,936,826,782,781,737,465,440,418,289,272,264,260,242,227,210,208,154,140,124,122,108,92,64,29,16,15,4
136};
137const int s20[] = {
138 40, 510,
139 219,173,156,135,134,128,124,118,114,95,81,79,71,65,63,59,58,55,54,51,49,46,34,33,32,31,28,24,21,20,19,18,17,16,14,10,8,4,3,1
140};
141const int s21[] = {
142 40, 1121,
143 409,408,396,345,317,316,242,238,221,198,166,159,157,143,130,123,120,117,109,102,101,93,87,79,76,67,64,55,53,49,46,44,39,33,21,19,14,13,5,3
144};
145const int s22[] = {
146 50, 788,
147 301,300,246,242,187,182,177,168,145,139,135,128,114,110,103,93,87,84,82,81,79,73,69,63,58,57,52,51,49,47,41,40,34,33,26,23,22,21,20,19,18,15,13,11,10,9,8,7,4,2
148};
149const int s23[] = {
150 50, 1034,
151 588,446,305,283,175,163,160,138,132,130,128,124,120,116,110,107,106,103,101,100,94,86,85,82,80,77,74,64,63,62,61,60,57,54,47,46,45,43,40,39,32,30,28,27,26,25,22,7,6,1
152};
153const int s24[] = {
154 60, 1097,
155 645,452,268,264,204,188,184,176,172,165,161,143,132,127,116,114,108,104,100,94,92,90,88,84,75,74,72,71,69,68,67,64,62,61,56,51,46,36,34,30,29,28,26,25,21,20,19,18,17,16,15,14,12,10,9,7,5,4,2,1
156};
157const int s25[] = {
158 60, 1192,
159 638,554,335,303,285,271,219,180,174,159,149,148,136,125,110,98,94,85,77,76,75,74,72,71,69,65,63,62,61,60,59,57,55,51,50,49,48,47,46,45,44,43,40,39,37,35,32,31,25,16,15,14,12,10,9,8,6,4,2,1
160};
161const int s26[] = {
162 75, 1412,
163 793,619,473,320,287,207,188,181,179,170,167,153,151,149,142,140,132,127,121,117,116,106,105,103,97,93,92,91,90,87,84,83,82,76,74,73,72,71,70,69,67,66,65,64,63,61,54,53,49,45,39,38,35,34,33,32,30,29,28,27,26,24,21,20,19,18,15,14,13,11,10,9,6,5,3
164};
165
166
167const int* specs[] = {
168 &s00[0],&s01[0],&s02[0],&s03[0],&s04[0],
169 &s05[0],&s06[0],&s07[0],&s08[0],&s09[0],
170 &s10[0],&s11[0],&s12[0],&s13[0],&s14[0],
171 &s15[0],&s16[0],&s17[0],&s18[0],&s19[0],
172 &s20[0],&s21[0],&s22[0],&s23[0],&s24[0],
173 &s25[0],&s26[0]
174};
175const unsigned int n_specs = sizeof(specs) / sizeof(int*);
176//@}
177
178/**
179 * \brief %Example: Packing squares into a rectangle
180 *
181 * See problem 9 at http://www.csplib.org/.
182 *
183 * \ingroup Example
184 */
185class PerfectSquare : public Script {
186protected:
187 /// Array of x-coordinates of squares
188 IntVarArray x;
189 /// Array of y-coordinates of squares
190 IntVarArray y;
191public:
192 /// Propagation to use for model
193 enum {
194 PROP_REIFIED, ///< Use reified constraints
195 PROP_CUMULATIVES ///< Use cumulatives constraint
196 };
197 /// Actual model
198 PerfectSquare(const SizeOptions& opt)
199 : Script(opt),
200 x(*this,specs[opt.size()][0],0,specs[opt.size()][1]-1),
201 y(*this,specs[opt.size()][0],0,specs[opt.size()][1]-1) {
202
203 const int* s = specs[opt.size()];
204 int n = *s++;
205 int w = *s++;
206
207 // Restrict position according to square size
208 for (int i=0; i<n; i++) {
209 rel(*this, x[i], IRT_LQ, w-s[i]);
210 rel(*this, y[i], IRT_LQ, w-s[i]);
211 }
212
213 IntArgs sa(n,s);
214
215 // Squares do not overlap
216 nooverlap(*this, x, sa, y, sa);
217
218 /*
219 * Capacity constraints
220 *
221 */
222 switch (opt.propagation()) {
223 case PROP_REIFIED:
224 {
225 for (int cx=0; cx<w; cx++) {
226 BoolVarArgs bx(*this,n,0,1);
227 for (int i=0; i<n; i++)
228 dom(*this, x[i], cx-s[i]+1, cx, bx[i]);
229 linear(*this, sa, bx, IRT_EQ, w);
230 }
231 for (int cy=0; cy<w; cy++) {
232 BoolVarArgs by(*this,n,0,1);
233 for (int i=0; i<n; i++)
234 dom(*this, y[i], cy-s[i]+1, cy, by[i]);
235 linear(*this, sa, by, IRT_EQ, w);
236 }
237 }
238 break;
239 case PROP_CUMULATIVES:
240 {
241 IntArgs m(n), dh(n);
242 for (int i=0; i<n; i++) {
243 m[i]=0; dh[i]=s[i];
244 }
245 IntArgs limit({w});
246 {
247 // x-direction
248 IntVarArgs e(n);
249 for (int i=0; i<n; i++)
250 e[i]=expr(*this, x[i]+dh[i]);
251 cumulatives(*this, m, x, dh, e, dh, limit, true);
252 cumulatives(*this, m, x, dh, e, dh, limit, false);
253 }
254 {
255 // y-direction
256 IntVarArgs e(n);
257 for (int i=0; i<n; i++)
258 e[i]=expr(*this, y[i]+dh[i]);
259 cumulatives(*this, m, y, dh, e, dh, limit, true);
260 cumulatives(*this, m, y, dh, e, dh, limit, false);
261 }
262 }
263 break;
264 default:
265 GECODE_NEVER;
266 }
267
268 branch(*this, x, INT_VAR_MIN_MIN(), INT_VAL_MIN());
269 branch(*this, y, INT_VAR_MIN_MIN(), INT_VAL_MIN());
270 }
271
272 /// Constructor for cloning \a s
273 PerfectSquare(PerfectSquare& s) : Script(s) {
274 x.update(*this, s.x);
275 y.update(*this, s.y);
276 }
277 /// Copy during cloning
278 virtual Space*
279 copy(void) {
280 return new PerfectSquare(*this);
281 }
282 /// Print solution
283 virtual void
284 print(std::ostream& os) const {
285 os << "\t";
286 for (int i=0; i<x.size(); i++)
287 os << "(" << x[i] << "," << y[i] << ") ";
288 os << std::endl;
289 }
290};
291
292/** \brief Main-function
293 * \relates PerfectSquare
294 */
295int
296main(int argc, char* argv[]) {
297 SizeOptions opt("PerfectSquare");
298 opt.propagation(PerfectSquare::PROP_REIFIED);
299 opt.propagation(PerfectSquare::PROP_REIFIED, "reified");
300 opt.propagation(PerfectSquare::PROP_CUMULATIVES, "cumulatives");
301 opt.a_d(5);
302 opt.c_d(20);
303 opt.parse(argc,argv);
304 if (opt.size() >= n_specs) {
305 std::cerr << "Error: size must be between 0 and " << n_specs - 1
306 << std::endl;
307 return 1;
308 }
309 Script::run<PerfectSquare,DFS,SizeOptions>(opt);
310 return 0;
311}
312
313// STATISTICS: example-any
314