this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christopher Mears <chris.mears@monash.edu>
5 *
6 * Copyright:
7 * Christopher Mears, 2012
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/kernel.hh>
35#include <gecode/int.hh>
36#include <gecode/int/branch.hh>
37
38#ifdef GECODE_HAS_SET_VARS
39#include <gecode/set.hh>
40#include <gecode/set/branch.hh>
41#include <stdarg.h>
42#endif
43
44#include <gecode/minimodel.hh>
45
46#include "test/test.hh"
47
48#include <vector>
49
50/**
51 * \namespace Test::LDSB
52 * \brief Testing for LDSB
53 */
54namespace Test { namespace LDSB {
55
56 using namespace Gecode;
57
58 /// Returns true iff a and b are equal (they have the same size and
59 /// the same elements in the same positions).
60 bool
61 equal(const IntArgs& a, const IntArgs& b) {
62 if (a.size() != b.size()) return false;
63 for (int i = 0 ; i < a.size() ; ++i)
64 if (a[i] != b[i])
65 return false;
66 return true;
67 }
68
69#ifdef GECODE_HAS_SET_VARS
70 /// Returns true iff a and b are equal (they have the same size and
71 /// the same elements in the same positions).
72 bool
73 equal(const IntSetArgs& a, const IntSetArgs& b) {
74 if (a.size() != b.size()) return false;
75 for (int i = 0 ; i < a.size() ; ++i) {
76 // Compare the two sets a[i] and b[i].
77 // Perhaps TODO: use Iter::Ranges::equal instead.
78 if (a[i].size() != b[i].size()) return false;
79 IntSetValues x(a[i]);
80 IntSetValues y(b[i]);
81 while (x() && y()) {
82 if (x.val() != y.val()) return false;
83 ++x;
84 ++y;
85 }
86 }
87 return true;
88 }
89#endif
90
91 /**
92 * \brief Checks found solutions against expected solutions
93 *
94 * Iterates through the solutions returned by the search engine and
95 * checks each one against the array of expected solutions. The
96 * order of solutions must be the same. Returns true if the
97 * expected solutions match the found solutions exactly, otherwise
98 * prints an explanation to standard error and returns false.
99 */
100 template <class T, class VarArgsType>
101 bool
102 check(DFS<T>& e, std::vector<VarArgsType> expected) {
103 int nexpected = expected.size();
104 for (int i = 0 ; i < nexpected ; ++i) {
105 T* s = e.next();
106 if (s == nullptr) {
107 if (opt.log) {
108 olog << "Expected a solution but there are no more solutions." << std::endl;
109 olog << "(Expected " << nexpected << " but only found " << i << ")" << std::endl;
110 olog << "Expected: " << expected[i] << std::endl;
111 }
112 return false;
113 }
114 if (!equal(s->solution(), expected[i])) {
115 if (opt.log) {
116 olog << "Solution does not match expected." << std::endl;
117 olog << "Solution: " << s->solution() << std::endl;
118 olog << "Expected: " << expected[i] << std::endl;
119 }
120 return false;
121 }
122 delete s;
123 }
124 T* s = e.next();
125 if (s != nullptr) {
126 if (opt.log) {
127 olog << "More solutions than expected:" << std::endl;
128 olog << "(Expected only " << nexpected << ")" << std::endl;
129 olog << s->solution() << std::endl;
130 }
131 return false;
132 }
133
134 // Nothing went wrong.
135 return true;
136 }
137
138
139 /// %Test space
140 class OneArray : public Space {
141 public:
142 /// Variables
143 IntVarArray xs;
144 /// Constructor for creation
145 OneArray(int n, int l, int u) : xs(*this,n,l,u) {
146 }
147 /// Constructor for cloning \a s
148 OneArray(OneArray& s) : Space(s) {
149 xs.update(*this,s.xs);
150 }
151 /// Copy during cloning
152 virtual Space* copy(void) {
153 return new OneArray(*this);
154 }
155 /// Return the solution as IntArgs
156 IntArgs solution(void) {
157 IntArgs a(xs.size());
158 for (int i = 0 ; i < a.size() ; ++i)
159 a[i] = xs[i].val();
160 return a;
161 }
162 /// Expected solutions
163 virtual IntArgs* expectedSolutions(void) { return nullptr; }
164 };
165
166#ifdef GECODE_HAS_SET_VARS
167 /// %Test space (set version)
168 class OneArraySet : public Space {
169 public:
170 /// Variables
171 SetVarArray xs;
172 /// Constructor for creation
173 OneArraySet(int n, int l, int u) : xs(*this,n, IntSet::empty, l,u) {
174 }
175 /// Constructor for cloning \a s
176 OneArraySet(OneArraySet& s) : Space(s) {
177 xs.update(*this,s.xs);
178 }
179 /// Copy during cloning
180 virtual Space* copy(void) {
181 return new OneArraySet(*this);
182 }
183 /// Return the solution as IntSetArgs
184 IntSetArgs solution(void) {
185 IntSetArgs a(xs.size());
186 for (int i = 0 ; i < a.size() ; ++i) {
187 SetVarGlbRanges glbranges(xs[i]);
188 a[i] = IntSet(glbranges);
189 }
190 return a;
191 }
192 /// Expected solutions
193 virtual IntSetArgs* expectedSolutions(void) { return nullptr; }
194 };
195#endif
196
197 /// %Test for %LDSB infrastructure
198 template <class T>
199 class LDSB : public Base {
200 public:
201 /// Recomputation distance
202 unsigned int c_d;
203 /// Adaptation distance
204 unsigned int a_d;
205 /// Initialize test
206 LDSB(std::string label, unsigned int c=0, unsigned int a=0)
207 : Test::Base("LDSB::" + label),
208 c_d(c), a_d(a) {}
209 /// Perform actual tests
210 bool run(void) {
211 OneArray *s = new OneArray(T::n, T::l, T::u);
212 T::setup(*s, s->xs);
213 Search::Options o = Search::Options::def;
214 if (c_d != 0) o.c_d = c_d;
215 if (a_d != 0) o.a_d = a_d;
216 DFS<OneArray> e(s,o);
217 bool r = check(e, T::expectedSolutions());
218 delete s;
219 return r;
220 }
221 };
222
223#ifdef GECODE_HAS_SET_VARS
224 /// %Test for %LDSB infrastructure
225 template <class T>
226 class LDSBSet : public Base {
227 public:
228 /// Recomputation distance
229 unsigned int c_d;
230 /// Adaptation distance
231 unsigned int a_d;
232 /// Initialize test
233 LDSBSet(std::string label, unsigned int c=0, unsigned int a=0)
234 : Test::Base("LDSB::" + label),
235 c_d(c), a_d(a) {}
236 /// Perform actual tests
237 bool run(void) {
238 OneArraySet *s = new OneArraySet(T::n, T::l, T::u);
239 T::setup(*s, s->xs);
240 Search::Options o = Search::Options::def;
241 if (c_d != 0) o.c_d = c_d;
242 if (a_d != 0) o.a_d = a_d;
243 DFS<OneArraySet> e(s,o);
244 bool r = check(e, T::expectedSolutions());
245 delete s;
246 return r;
247 }
248 };
249#endif
250
251 // Test cases
252
253 /// %Test for variable symmetry
254 class VarSym1 {
255 public:
256 /// Number of variables
257 static const int n = 4;
258 /// Lower bound of values
259 static const int l = 0;
260 /// Upper bound of values
261 static const int u = 3;
262 /// Setup problem constraints and symmetries
263 static void setup(Home home, IntVarArray& xs) {
264 Symmetries syms;
265 IntArgs indices({0,1,2,3});
266 syms << VariableSymmetry(xs, indices);
267 distinct(home, xs);
268 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
269 }
270 /// Compute list of expected solutions
271 static std::vector<IntArgs> expectedSolutions(void) {
272 static std::vector<IntArgs> expected;
273 expected.clear();
274 expected.push_back(IntArgs({0,1,2,3}));
275 return expected;
276 }
277 };
278
279 /// %Test for variable symmetry
280 class VarSym1b {
281 public:
282 /// Number of variables
283 static const int n = 4;
284 /// Lower bound of values
285 static const int l = 0;
286 /// Upper bound of values
287 static const int u = 3;
288 /// Setup problem constraints and symmetries
289 static void setup(Home home, IntVarArray& xs) {
290 distinct(home, xs);
291 Symmetries syms;
292 syms << VariableSymmetry(xs);
293 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
294 }
295 /// Compute list of expected solutions
296 static std::vector<IntArgs> expectedSolutions(void) {
297 static std::vector<IntArgs> expected;
298 expected.clear();
299 expected.push_back(IntArgs({0,1,2,3}));
300 return expected;
301 }
302 };
303
304 /// %Test for variable symmetry
305 class VarSym2 {
306 public:
307 /// Number of variables
308 static const int n = 4;
309 /// Lower bound of values
310 static const int l = 0;
311 /// Upper bound of values
312 static const int u = 3;
313 /// Setup problem constraints and symmetries
314 static void setup(Home home, IntVarArray& xs) {
315 Symmetries syms;
316 IntArgs indices({0,1,2,3});
317 syms << VariableSymmetry(xs);
318 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
319 }
320 /// Compute list of expected solutions
321 static std::vector<IntArgs> expectedSolutions(void) {
322 static std::vector<IntArgs> expected;
323 expected.clear();
324 expected.push_back(IntArgs({0,0,0,0}));
325 expected.push_back(IntArgs({0,0,0,1}));
326 expected.push_back(IntArgs({0,0,0,2}));
327 expected.push_back(IntArgs({0,0,0,3}));
328 expected.push_back(IntArgs({0,0,1,1}));
329 expected.push_back(IntArgs({0,0,1,2}));
330 expected.push_back(IntArgs({0,0,1,3}));
331 expected.push_back(IntArgs({0,0,2,2}));
332 expected.push_back(IntArgs({0,0,2,3}));
333 expected.push_back(IntArgs({0,0,3,3}));
334 expected.push_back(IntArgs({0,1,1,1}));
335 expected.push_back(IntArgs({0,1,1,2}));
336 expected.push_back(IntArgs({0,1,1,3}));
337 expected.push_back(IntArgs({0,1,2,2}));
338 expected.push_back(IntArgs({0,1,2,3}));
339 expected.push_back(IntArgs({0,1,3,3}));
340 expected.push_back(IntArgs({0,2,2,2}));
341 expected.push_back(IntArgs({0,2,2,3}));
342 expected.push_back(IntArgs({0,2,3,3}));
343 expected.push_back(IntArgs({0,3,3,3}));
344 expected.push_back(IntArgs({1,1,1,1}));
345 expected.push_back(IntArgs({1,1,1,2}));
346 expected.push_back(IntArgs({1,1,1,3}));
347 expected.push_back(IntArgs({1,1,2,2}));
348 expected.push_back(IntArgs({1,1,2,3}));
349 expected.push_back(IntArgs({1,1,3,3}));
350 expected.push_back(IntArgs({1,2,2,2}));
351 expected.push_back(IntArgs({1,2,2,3}));
352 expected.push_back(IntArgs({1,2,3,3}));
353 expected.push_back(IntArgs({1,3,3,3}));
354 expected.push_back(IntArgs({2,2,2,2}));
355 expected.push_back(IntArgs({2,2,2,3}));
356 expected.push_back(IntArgs({2,2,3,3}));
357 expected.push_back(IntArgs({2,3,3,3}));
358 expected.push_back(IntArgs({3,3,3,3}));
359 return expected;
360 }
361 };
362
363 /// %Test for variable symmetry
364 class VarSym3 {
365 public:
366 /// Number of variables
367 static const int n = 4;
368 /// Lower bound of values
369 static const int l = 0;
370 /// Upper bound of values
371 static const int u = 3;
372 /// Setup problem constraints and symmetries
373 static void setup(Home home, IntVarArray& xs) {
374 Symmetries syms;
375 distinct(home, xs);
376 syms << VariableSymmetry(IntVarArgs() << xs[0] << xs[1]);
377 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
378 }
379 /// Compute list of expected solutions
380 static std::vector<IntArgs> expectedSolutions(void) {
381 static std::vector<IntArgs> expected;
382 expected.clear();
383 expected.push_back(IntArgs({0,1,2,3}));
384 expected.push_back(IntArgs({0,1,3,2}));
385 expected.push_back(IntArgs({0,2,1,3}));
386 expected.push_back(IntArgs({0,2,3,1}));
387 expected.push_back(IntArgs({0,3,1,2}));
388 expected.push_back(IntArgs({0,3,2,1}));
389 expected.push_back(IntArgs({1,2,0,3}));
390 expected.push_back(IntArgs({1,2,3,0}));
391 expected.push_back(IntArgs({1,3,0,2}));
392 expected.push_back(IntArgs({1,3,2,0}));
393 expected.push_back(IntArgs({2,3,0,1}));
394 expected.push_back(IntArgs({2,3,1,0}));
395 return expected;
396 }
397 };
398
399 /// %Test for variable symmetry
400 class VarSym4 {
401 public:
402 /// Number of variables
403 static const int n = 3;
404 /// Lower bound of values
405 static const int l = 0;
406 /// Upper bound of values
407 static const int u = 2;
408 /// Setup problem constraints and symmetries
409 static void setup(Home home, IntVarArray& xs) {
410 distinct(home, xs);
411 Symmetries s;
412 IntVarArgs symvars;
413 symvars << xs[0];
414 s << VariableSymmetry(symvars);
415 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
416 }
417 /// Compute list of expected solutions
418 static std::vector<IntArgs> expectedSolutions(void) {
419 static std::vector<IntArgs> expected;
420 expected.clear();
421 expected.push_back(IntArgs({0,1,2}));
422 expected.push_back(IntArgs({0,2,1}));
423 expected.push_back(IntArgs({1,0,2}));
424 expected.push_back(IntArgs({1,2,0}));
425 expected.push_back(IntArgs({2,0,1}));
426 expected.push_back(IntArgs({2,1,0}));
427 return expected;
428 }
429 };
430
431 /// %Test for variable symmetry
432 class VarSym5 {
433 public:
434 /// Number of variables
435 static const int n = 4;
436 /// Lower bound of values
437 static const int l = 0;
438 /// Upper bound of values
439 static const int u = 3;
440 /// Setup problem constraints and symmetries
441 static void setup(Home home, IntVarArray& xs) {
442 distinct(home, xs);
443 Matrix<IntVarArray> m(xs, 4, 1);
444 Symmetries s;
445 s << VariableSymmetry(m.slice(0,2, 0,1));
446 s << VariableSymmetry(m.slice(2,4, 0,1));
447 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
448 }
449 /// Compute list of expected solutions
450 static std::vector<IntArgs> expectedSolutions(void) {
451 static std::vector<IntArgs> expected;
452 expected.clear();
453 expected.push_back(IntArgs({0,1,2,3}));
454 expected.push_back(IntArgs({0,2,1,3}));
455 expected.push_back(IntArgs({0,3,1,2}));
456 expected.push_back(IntArgs({1,2,0,3}));
457 expected.push_back(IntArgs({1,3,0,2}));
458 expected.push_back(IntArgs({2,3,0,1}));
459 return expected;
460 }
461 };
462
463 /// %Test for matrix symmetry
464 class MatSym1 {
465 public:
466 /// Number of variables
467 static const int n = 6;
468 /// Lower bound of values
469 static const int l = 0;
470 /// Upper bound of values
471 static const int u = 1;
472 /// Setup problem constraints and symmetries
473 static void setup(Home home, IntVarArray& xs) {
474 Matrix<IntVarArray> m(xs, 2, 3);
475 Symmetries s;
476 s << rows_interchange(m);
477 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
478 }
479 /// Compute list of expected solutions
480 static std::vector<IntArgs> expectedSolutions(void) {
481 static std::vector<IntArgs> expected;
482 expected.clear();
483 expected.push_back(IntArgs({0,0, 0,0, 0,0}));
484 expected.push_back(IntArgs({0,0, 0,0, 0,1}));
485 expected.push_back(IntArgs({0,0, 0,0, 1,0}));
486 expected.push_back(IntArgs({0,0, 0,0, 1,1}));
487 expected.push_back(IntArgs({0,0, 0,1, 0,0}));
488 expected.push_back(IntArgs({0,0, 0,1, 0,1}));
489 expected.push_back(IntArgs({0,0, 0,1, 1,0}));
490 expected.push_back(IntArgs({0,0, 0,1, 1,1}));
491 expected.push_back(IntArgs({0,0, 1,0, 1,0}));
492 expected.push_back(IntArgs({0,0, 1,0, 1,1}));
493 expected.push_back(IntArgs({0,0, 1,1, 1,1}));
494 expected.push_back(IntArgs({0,1, 0,0, 0,0}));
495 expected.push_back(IntArgs({0,1, 0,0, 0,1}));
496 expected.push_back(IntArgs({0,1, 0,0, 1,0}));
497 expected.push_back(IntArgs({0,1, 0,0, 1,1}));
498 expected.push_back(IntArgs({0,1, 0,1, 0,0}));
499 expected.push_back(IntArgs({0,1, 0,1, 0,1}));
500 expected.push_back(IntArgs({0,1, 0,1, 1,0}));
501 expected.push_back(IntArgs({0,1, 0,1, 1,1}));
502 expected.push_back(IntArgs({0,1, 1,0, 1,0}));
503 expected.push_back(IntArgs({0,1, 1,0, 1,1}));
504 expected.push_back(IntArgs({0,1, 1,1, 1,1}));
505 expected.push_back(IntArgs({1,0, 1,0, 1,0}));
506 expected.push_back(IntArgs({1,0, 1,0, 1,1}));
507 expected.push_back(IntArgs({1,0, 1,1, 1,1}));
508 expected.push_back(IntArgs({1,1, 1,1, 1,1}));
509 return expected;
510 }
511 };
512
513 /// %Test for matrix symmetry
514 class MatSym2 {
515 public:
516 /// Number of variables
517 static const int n = 6;
518 /// Lower bound of values
519 static const int l = 0;
520 /// Upper bound of values
521 static const int u = 1;
522 /// Setup problem constraints and symmetries
523 static void setup(Home home, IntVarArray& xs) {
524 Matrix<IntVarArray> m(xs, 2, 3);
525 Symmetries s;
526 s << columns_interchange(m);
527 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
528 }
529 /// Compute list of expected solutions
530 static std::vector<IntArgs> expectedSolutions(void) {
531 static std::vector<IntArgs> expected;
532 expected.clear();
533 expected.push_back(IntArgs({0,0, 0,0, 0,0}));
534 expected.push_back(IntArgs({0,0, 0,0, 0,1}));
535 expected.push_back(IntArgs({0,0, 0,0, 1,1}));
536 expected.push_back(IntArgs({0,0, 0,1, 0,0}));
537 expected.push_back(IntArgs({0,0, 0,1, 0,1}));
538 expected.push_back(IntArgs({0,0, 0,1, 1,0}));
539 expected.push_back(IntArgs({0,0, 0,1, 1,1}));
540 expected.push_back(IntArgs({0,0, 1,1, 0,0}));
541 expected.push_back(IntArgs({0,0, 1,1, 0,1}));
542 expected.push_back(IntArgs({0,0, 1,1, 1,1}));
543 expected.push_back(IntArgs({0,1, 0,0, 0,0}));
544 expected.push_back(IntArgs({0,1, 0,0, 0,1}));
545 expected.push_back(IntArgs({0,1, 0,0, 1,0}));
546 expected.push_back(IntArgs({0,1, 0,0, 1,1}));
547 expected.push_back(IntArgs({0,1, 0,1, 0,0}));
548 expected.push_back(IntArgs({0,1, 0,1, 0,1}));
549 expected.push_back(IntArgs({0,1, 0,1, 1,0}));
550 expected.push_back(IntArgs({0,1, 0,1, 1,1}));
551 expected.push_back(IntArgs({0,1, 1,0, 0,0}));
552 expected.push_back(IntArgs({0,1, 1,0, 0,1}));
553 expected.push_back(IntArgs({0,1, 1,0, 1,0}));
554 expected.push_back(IntArgs({0,1, 1,0, 1,1}));
555 expected.push_back(IntArgs({0,1, 1,1, 0,0}));
556 expected.push_back(IntArgs({0,1, 1,1, 0,1}));
557 expected.push_back(IntArgs({0,1, 1,1, 1,0}));
558 expected.push_back(IntArgs({0,1, 1,1, 1,1}));
559 expected.push_back(IntArgs({1,1, 0,0, 0,0}));
560 expected.push_back(IntArgs({1,1, 0,0, 0,1}));
561 expected.push_back(IntArgs({1,1, 0,0, 1,1}));
562 expected.push_back(IntArgs({1,1, 0,1, 0,0}));
563 expected.push_back(IntArgs({1,1, 0,1, 0,1}));
564 expected.push_back(IntArgs({1,1, 0,1, 1,0}));
565 expected.push_back(IntArgs({1,1, 0,1, 1,1}));
566 expected.push_back(IntArgs({1,1, 1,1, 0,0}));
567 expected.push_back(IntArgs({1,1, 1,1, 0,1}));
568 expected.push_back(IntArgs({1,1, 1,1, 1,1}));
569 return expected;
570 }
571 };
572
573 /// %Test for matrix symmetry
574 class MatSym3 {
575 public:
576 /// Number of variables
577 static const int n = 6;
578 /// Lower bound of values
579 static const int l = 0;
580 /// Upper bound of values
581 static const int u = 1;
582 /// Setup problem constraints and symmetries
583 static void setup(Home home, IntVarArray& xs) {
584 Matrix<IntVarArray> m(xs, 2, 3);
585 Symmetries s;
586 s << rows_interchange(m);
587 s << columns_interchange(m);
588 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
589 }
590 /// Compute list of expected solutions
591 static std::vector<IntArgs> expectedSolutions(void) {
592 static std::vector<IntArgs> expected;
593 expected.clear();
594 expected.push_back(IntArgs({0,0, 0,0, 0,0}));
595 expected.push_back(IntArgs({0,0, 0,0, 0,1}));
596 expected.push_back(IntArgs({0,0, 0,0, 1,1}));
597 expected.push_back(IntArgs({0,0, 0,1, 0,0}));
598 expected.push_back(IntArgs({0,0, 0,1, 0,1}));
599 expected.push_back(IntArgs({0,0, 0,1, 1,0}));
600 expected.push_back(IntArgs({0,0, 0,1, 1,1}));
601 expected.push_back(IntArgs({0,0, 1,1, 1,1}));
602 expected.push_back(IntArgs({0,1, 0,0, 0,0}));
603 expected.push_back(IntArgs({0,1, 0,0, 0,1}));
604 expected.push_back(IntArgs({0,1, 0,0, 1,0}));
605 expected.push_back(IntArgs({0,1, 0,0, 1,1}));
606 expected.push_back(IntArgs({0,1, 0,1, 0,0}));
607 expected.push_back(IntArgs({0,1, 0,1, 0,1}));
608 expected.push_back(IntArgs({0,1, 0,1, 1,0}));
609 expected.push_back(IntArgs({0,1, 0,1, 1,1}));
610 expected.push_back(IntArgs({0,1, 1,0, 1,0}));
611 expected.push_back(IntArgs({0,1, 1,0, 1,1}));
612 expected.push_back(IntArgs({0,1, 1,1, 1,1}));
613 expected.push_back(IntArgs({1,1, 1,1, 1,1}));
614 return expected;
615 }
616 };
617
618 /// %Test for matrix symmetry
619 class MatSym4 {
620 public:
621 /// Number of variables
622 static const int n = 4;
623 /// Lower bound of values
624 static const int l = 0;
625 /// Upper bound of values
626 static const int u = 1;
627 /// Setup problem constraints and symmetries
628 static void setup(Home home, IntVarArray& xs) {
629 Matrix<IntVarArray> m(xs, 1, 4);
630 Symmetries s;
631 s << rows_reflect(m);
632 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
633 }
634 /// Compute list of expected solutions
635 static std::vector<IntArgs> expectedSolutions(void) {
636 static std::vector<IntArgs> expected;
637 expected.clear();
638 expected.push_back(IntArgs({0, 0, 0, 0}));
639 expected.push_back(IntArgs({0, 0, 0, 1}));
640 expected.push_back(IntArgs({0, 0, 1, 0}));
641 expected.push_back(IntArgs({0, 0, 1, 1}));
642 expected.push_back(IntArgs({0, 1, 0, 0}));
643 expected.push_back(IntArgs({0, 1, 0, 1}));
644 expected.push_back(IntArgs({0, 1, 1, 0}));
645 expected.push_back(IntArgs({0, 1, 1, 1}));
646 expected.push_back(IntArgs({1, 0, 0, 1}));
647 expected.push_back(IntArgs({1, 0, 1, 1}));
648 expected.push_back(IntArgs({1, 1, 1, 1}));
649 return expected;
650 }
651 };
652
653 /// %Test for variable sequence symmetry
654 class SimIntVarSym1 {
655 public:
656 /// Number of variables
657 static const int n = 12;
658 /// Lower bound of values
659 static const int l = 0;
660 /// Upper bound of values
661 static const int u = 3;
662 /// Setup problem constraints and symmetries
663 static void setup(Home home, IntVarArray& xs) {
664 Matrix<IntVarArray> m(xs, 3, 4);
665 // The values in the first column are distinct.
666 distinct(home, m.col(0));
667 // Each row sums to 3.
668 for (int i = 0 ; i < 4 ; ++i)
669 linear(home, m.row(i), IRT_EQ, 3);
670
671 // Rows are interchangeable.
672 Symmetries s;
673 s << VariableSequenceSymmetry(xs, 3);
674 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
675 }
676 /// Compute list of expected solutions
677 static std::vector<IntArgs> expectedSolutions(void) {
678 static std::vector<IntArgs> expected;
679 expected.clear();
680 expected.push_back(IntArgs({0,0,3, 1,0,2, 2,0,1, 3,0,0}));
681 expected.push_back(IntArgs({0,0,3, 1,0,2, 2,1,0, 3,0,0}));
682 expected.push_back(IntArgs({0,0,3, 1,1,1, 2,0,1, 3,0,0}));
683 expected.push_back(IntArgs({0,0,3, 1,1,1, 2,1,0, 3,0,0}));
684 expected.push_back(IntArgs({0,0,3, 1,2,0, 2,0,1, 3,0,0}));
685 expected.push_back(IntArgs({0,0,3, 1,2,0, 2,1,0, 3,0,0}));
686 expected.push_back(IntArgs({0,1,2, 1,0,2, 2,0,1, 3,0,0}));
687 expected.push_back(IntArgs({0,1,2, 1,0,2, 2,1,0, 3,0,0}));
688 expected.push_back(IntArgs({0,1,2, 1,1,1, 2,0,1, 3,0,0}));
689 expected.push_back(IntArgs({0,1,2, 1,1,1, 2,1,0, 3,0,0}));
690 expected.push_back(IntArgs({0,1,2, 1,2,0, 2,0,1, 3,0,0}));
691 expected.push_back(IntArgs({0,1,2, 1,2,0, 2,1,0, 3,0,0}));
692 expected.push_back(IntArgs({0,2,1, 1,0,2, 2,0,1, 3,0,0}));
693 expected.push_back(IntArgs({0,2,1, 1,0,2, 2,1,0, 3,0,0}));
694 expected.push_back(IntArgs({0,2,1, 1,1,1, 2,0,1, 3,0,0}));
695 expected.push_back(IntArgs({0,2,1, 1,1,1, 2,1,0, 3,0,0}));
696 expected.push_back(IntArgs({0,2,1, 1,2,0, 2,0,1, 3,0,0}));
697 expected.push_back(IntArgs({0,2,1, 1,2,0, 2,1,0, 3,0,0}));
698 expected.push_back(IntArgs({0,3,0, 1,0,2, 2,0,1, 3,0,0}));
699 expected.push_back(IntArgs({0,3,0, 1,0,2, 2,1,0, 3,0,0}));
700 expected.push_back(IntArgs({0,3,0, 1,1,1, 2,0,1, 3,0,0}));
701 expected.push_back(IntArgs({0,3,0, 1,1,1, 2,1,0, 3,0,0}));
702 expected.push_back(IntArgs({0,3,0, 1,2,0, 2,0,1, 3,0,0}));
703 expected.push_back(IntArgs({0,3,0, 1,2,0, 2,1,0, 3,0,0}));
704 return expected;
705 }
706 };
707
708 /// %Test for variable sequence symmetry
709 class SimIntVarSym2 {
710 /// Number of rows
711 static const int nrows = 4;
712 /// Number of columns
713 static const int ncols = 3;
714 public:
715 /// Number of variables
716 static const int n = nrows*ncols;
717 /// Lower bound of values
718 static const int l = 0;
719 /// Upper bound of values
720 static const int u = 3;
721 /// Setup problem constraints and symmetries
722 static void setup(Home home, IntVarArray& xs) {
723 Matrix<IntVarArray> m(xs, 3, 4);
724 // The values in the first column are distinct.
725 distinct(home, m.col(0));
726 // Each row sums to 3.
727 for (int i = 0 ; i < nrows ; ++i)
728 linear(home, m.row(i), IRT_EQ, 3);
729
730 Symmetries s;
731
732 IntArgs a = IntArgs::create(n, 0);
733 // Rows are interchangeable.
734 s << VariableSequenceSymmetry(xs, 3);
735 // Elements (i,1) and (i,2) in row i are interchangeable,
736 // separately for each row.
737 for (int i = 0 ; i < nrows ; i++) {
738 IntVarArgs symvars;
739 symvars << m(1,i) << m(2,i);
740 s << VariableSymmetry(symvars);
741 }
742 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
743 }
744 /// Compute list of expected solutions
745 static std::vector<IntArgs> expectedSolutions(void) {
746 static std::vector<IntArgs> expected;
747 expected.clear();
748 expected.push_back(IntArgs({0,0,3, 1,0,2, 2,0,1, 3,0,0}));
749 expected.push_back(IntArgs({0,0,3, 1,1,1, 2,0,1, 3,0,0}));
750 expected.push_back(IntArgs({0,1,2, 1,0,2, 2,0,1, 3,0,0}));
751 expected.push_back(IntArgs({0,1,2, 1,1,1, 2,0,1, 3,0,0}));
752 return expected;
753 }
754 };
755
756 /// %Test for value sequence symmetry
757 class SimIntValSym1 {
758 public:
759 /// Number of variables
760 static const int n = 2;
761 /// Lower bound of values
762 static const int l = 0;
763 /// Upper bound of values
764 static const int u = 6;
765 /// Setup problem constraints and symmetries
766 static void setup(Home home, IntVarArray& xs) {
767 rel(home, xs[0] + xs[1] == 6);
768 // Values 0,1,2 are symmetric with 6,5,4.
769 IntArgs values({0,1,2, 6,5,4});
770 Symmetries s;
771 s << ValueSequenceSymmetry(values, 3);
772 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
773 }
774 /// Compute list of expected solutions
775 static std::vector<IntArgs> expectedSolutions(void) {
776 static std::vector<IntArgs> expected;
777 expected.clear();
778 expected.push_back(IntArgs({0,6}));
779 expected.push_back(IntArgs({1,5}));
780 expected.push_back(IntArgs({2,4}));
781 expected.push_back(IntArgs({3,3}));
782 return expected;
783 }
784 };
785
786 /// %Test for value sequence symmetry
787 class SimIntValSym2 {
788 public:
789 /// Number of variables
790 static const int n = 3;
791 /// Lower bound of values
792 static const int l = 0;
793 /// Upper bound of values
794 static const int u = 8;
795 /// Setup problem constraints and symmetries
796 static void setup(Home home, IntVarArray& xs) {
797 TupleSet tuples(3);
798 tuples.add({1,1,1}).add({4,4,4}).add({7,7,7})
799 .add({0,1,5}).add({0,1,8}).add({3,4,2})
800 .add({3,4,8}).add({6,7,2}).add({6,7,5})
801 .finalize();
802 extensional(home, xs, tuples);
803
804 // Values 0,1,2 are symmetric with 3,4,5, and with 6,7,8.
805 IntArgs values({0,1,2, 3,4,5, 6,7,8});
806 Symmetries s;
807 s << ValueSequenceSymmetry(values, 3);
808 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
809 }
810 /// Compute list of expected solutions
811 static std::vector<IntArgs> expectedSolutions(void) {
812 static std::vector<IntArgs> expected;
813 expected.clear();
814 expected.push_back(IntArgs({0,1,5}));
815 expected.push_back(IntArgs({1,1,1}));
816 return expected;
817 }
818 };
819
820 /// %Test for value sequence symmetry
821 class SimIntValSym3 {
822 public:
823 /// Number of variables
824 static const int n = 2;
825 /// Lower bound of values
826 static const int l = 0;
827 /// Upper bound of values
828 static const int u = 6;
829 /// Setup problem constraints and symmetries
830 static void setup(Home home, IntVarArray& xs) {
831 rel(home, xs[0] + xs[1] == 6);
832 Symmetries s;
833 // Values 0,1,2 are symmetric with 6,5,4.
834 s << values_reflect(0,6);
835 branch(home, xs, INT_VAR_NONE(), INT_VAL_MED(), s);
836 }
837 /// Compute list of expected solutions
838 static std::vector<IntArgs> expectedSolutions(void) {
839 static std::vector<IntArgs> expected;
840 expected.clear();
841 expected.push_back(IntArgs({3,3}));
842 expected.push_back(IntArgs({2,4}));
843 expected.push_back(IntArgs({1,5}));
844 expected.push_back(IntArgs({0,6}));
845 return expected;
846 }
847 };
848
849 /// %Test for value symmetry
850 class ValSym1 {
851 public:
852 /// Number of variables
853 static const int n = 4;
854 /// Lower bound of values
855 static const int l = 0;
856 /// Upper bound of values
857 static const int u = 3;
858 /// Setup problem constraints and symmetries
859 static void setup(Home home, IntVarArray& xs) {
860 distinct(home, xs);
861 Symmetries s;
862 IntArgs indices({0,1,2,3});
863 s << ValueSymmetry(indices);
864 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
865 }
866 /// Compute list of expected solutions
867 static std::vector<IntArgs> expectedSolutions(void) {
868 static std::vector<IntArgs> expected;
869 expected.clear();
870 expected.push_back(IntArgs({0,1,2,3}));
871 return expected;
872 }
873 };
874
875 /// %Test for value symmetry
876 class ValSym1b {
877 public:
878 /// Number of variables
879 static const int n = 4;
880 /// Lower bound of values
881 static const int l = 0;
882 /// Upper bound of values
883 static const int u = 3;
884 /// Setup problem constraints and symmetries
885 static void setup(Home home, IntVarArray& xs) {
886 distinct(home, xs);
887 Symmetries s;
888 s << ValueSymmetry(xs[0]);
889 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
890 }
891 /// Compute list of expected solutions
892 static std::vector<IntArgs> expectedSolutions(void) {
893 static std::vector<IntArgs> expected;
894 expected.clear();
895 expected.push_back(IntArgs({0,1,2,3}));
896 return expected;
897 }
898 };
899
900 /// %Test for value symmetry
901 class ValSym1c {
902 public:
903 /// Number of variables
904 static const int n = 4;
905 /// Lower bound of values
906 static const int l = 0;
907 /// Upper bound of values
908 static const int u = 3;
909 /// Setup problem constraints and symmetries
910 static void setup(Home home, IntVarArray& xs) {
911 distinct(home, xs);
912 Symmetries s;
913 s << ValueSymmetry(xs[0]);
914 branch(home, xs, INT_VAR_NONE(), INT_VAL_MAX(), s);
915 }
916 /// Compute list of expected solutions
917 static std::vector<IntArgs> expectedSolutions(void) {
918 static std::vector<IntArgs> expected;
919 expected.clear();
920 expected.push_back(IntArgs({3,2,1,0}));
921 return expected;
922 }
923 };
924
925 /// %Test for value symmetry
926 class ValSym2 {
927 public:
928 /// Number of variables
929 static const int n = 4;
930 /// Lower bound of values
931 static const int l = 0;
932 /// Upper bound of values
933 static const int u = 3;
934 /// Setup problem constraints and symmetries
935 static void setup(Home home, IntVarArray& xs) {
936 Symmetries s;
937 IntArgs indices({0,1,2,3});
938 s << ValueSymmetry(indices);
939 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
940 }
941 /// Compute list of expected solutions
942 static std::vector<IntArgs> expectedSolutions(void) {
943 static std::vector<IntArgs> expected;
944 expected.clear();
945 expected.push_back(IntArgs({0,0,0,0}));
946 expected.push_back(IntArgs({0,0,0,1}));
947 expected.push_back(IntArgs({0,0,1,0}));
948 expected.push_back(IntArgs({0,0,1,1}));
949 expected.push_back(IntArgs({0,0,1,2}));
950 expected.push_back(IntArgs({0,1,0,0}));
951 expected.push_back(IntArgs({0,1,0,1}));
952 expected.push_back(IntArgs({0,1,0,2}));
953 expected.push_back(IntArgs({0,1,1,0}));
954 expected.push_back(IntArgs({0,1,1,1}));
955 expected.push_back(IntArgs({0,1,1,2}));
956 expected.push_back(IntArgs({0,1,2,0}));
957 expected.push_back(IntArgs({0,1,2,1}));
958 expected.push_back(IntArgs({0,1,2,2}));
959 expected.push_back(IntArgs({0,1,2,3}));
960 return expected;
961 }
962 };
963
964 /// %Test for value symmetry
965 class ValSym2b {
966 public:
967 /// Number of variables
968 static const int n = 4;
969 /// Lower bound of values
970 static const int l = 0;
971 /// Upper bound of values
972 static const int u = 3;
973 /// Setup problem constraints and symmetries
974 static void setup(Home home, IntVarArray& xs) {
975 Symmetries s;
976 s << ValueSymmetry(xs[0]);
977 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
978 }
979 /// Compute list of expected solutions
980 static std::vector<IntArgs> expectedSolutions(void) {
981 static std::vector<IntArgs> expected;
982 expected.clear();
983 expected.push_back(IntArgs({0,0,0,0}));
984 expected.push_back(IntArgs({0,0,0,1}));
985 expected.push_back(IntArgs({0,0,1,0}));
986 expected.push_back(IntArgs({0,0,1,1}));
987 expected.push_back(IntArgs({0,0,1,2}));
988 expected.push_back(IntArgs({0,1,0,0}));
989 expected.push_back(IntArgs({0,1,0,1}));
990 expected.push_back(IntArgs({0,1,0,2}));
991 expected.push_back(IntArgs({0,1,1,0}));
992 expected.push_back(IntArgs({0,1,1,1}));
993 expected.push_back(IntArgs({0,1,1,2}));
994 expected.push_back(IntArgs({0,1,2,0}));
995 expected.push_back(IntArgs({0,1,2,1}));
996 expected.push_back(IntArgs({0,1,2,2}));
997 expected.push_back(IntArgs({0,1,2,3}));
998 return expected;
999 }
1000 };
1001
1002 /// %Test for value symmetry
1003 class ValSym3 {
1004 public:
1005 /// Number of variables
1006 static const int n = 4;
1007 /// Lower bound of values
1008 static const int l = 0;
1009 /// Upper bound of values
1010 static const int u = 3;
1011 /// Setup problem constraints and symmetries
1012 static void setup(Home home, IntVarArray& xs) {
1013 distinct(home, xs);
1014 Symmetries s;
1015 IntArgs indices({0,1});
1016 s << ValueSymmetry(indices);
1017 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
1018 }
1019 /// Compute list of expected solutions
1020 static std::vector<IntArgs> expectedSolutions(void) {
1021 static std::vector<IntArgs> expected;
1022 expected.clear();
1023 expected.push_back(IntArgs({0,1,2,3}));
1024 expected.push_back(IntArgs({0,1,3,2}));
1025 expected.push_back(IntArgs({0,2,1,3}));
1026 expected.push_back(IntArgs({0,2,3,1}));
1027 expected.push_back(IntArgs({0,3,1,2}));
1028 expected.push_back(IntArgs({0,3,2,1}));
1029 expected.push_back(IntArgs({2,0,1,3}));
1030 expected.push_back(IntArgs({2,0,3,1}));
1031 expected.push_back(IntArgs({2,3,0,1}));
1032 expected.push_back(IntArgs({3,0,1,2}));
1033 expected.push_back(IntArgs({3,0,2,1}));
1034 expected.push_back(IntArgs({3,2,0,1}));
1035 return expected;
1036 }
1037 };
1038
1039 /// %Test for value symmetry
1040 class ValSym4 {
1041 public:
1042 /// Number of variables
1043 static const int n = 3;
1044 /// Lower bound of values
1045 static const int l = 0;
1046 /// Upper bound of values
1047 static const int u = 2;
1048 /// Setup problem constraints and symmetries
1049 static void setup(Home home, IntVarArray& xs) {
1050 distinct(home, xs);
1051 Symmetries s;
1052 IntArgs indices({0});
1053 s << ValueSymmetry(indices);
1054 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
1055 }
1056 /// Compute list of expected solutions
1057 static std::vector<IntArgs> expectedSolutions(void) {
1058 static std::vector<IntArgs> expected;
1059 expected.clear();
1060 expected.push_back(IntArgs({0,1,2}));
1061 expected.push_back(IntArgs({0,2,1}));
1062 expected.push_back(IntArgs({1,0,2}));
1063 expected.push_back(IntArgs({1,2,0}));
1064 expected.push_back(IntArgs({2,0,1}));
1065 expected.push_back(IntArgs({2,1,0}));
1066 return expected;
1067 }
1068 };
1069
1070 /// %Test for value symmetry
1071 class ValSym5 {
1072 public:
1073 /// Number of variables
1074 static const int n = 4;
1075 /// Lower bound of values
1076 static const int l = 0;
1077 /// Upper bound of values
1078 static const int u = 3;
1079 /// Setup problem constraints and symmetries
1080 static void setup(Home home, IntVarArray& xs) {
1081 distinct(home, xs);
1082 Symmetries s;
1083 IntArgs indices0({0,1});
1084 IntArgs indices1({2,3});
1085 s << ValueSymmetry(indices0);
1086 s << ValueSymmetry(indices1);
1087 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
1088 }
1089 /// Compute list of expected solutions
1090 static std::vector<IntArgs> expectedSolutions(void) {
1091 static std::vector<IntArgs> expected;
1092 expected.clear();
1093 expected.push_back(IntArgs({0,1,2,3}));
1094 expected.push_back(IntArgs({0,2,1,3}));
1095 expected.push_back(IntArgs({0,2,3,1}));
1096 expected.push_back(IntArgs({2,0,1,3}));
1097 expected.push_back(IntArgs({2,0,3,1}));
1098 expected.push_back(IntArgs({2,3,0,1}));
1099 return expected;
1100 }
1101 };
1102
1103 /// %Test for variable and value symmetry
1104 class VarValSym1 {
1105 public:
1106 /// Number of variables
1107 static const int n = 4;
1108 /// Lower bound of values
1109 static const int l = 0;
1110 /// Upper bound of values
1111 static const int u = 3;
1112 /// Setup problem constraints and symmetries
1113 static void setup(Home home, IntVarArray& xs) {
1114 Symmetries s;
1115 s << VariableSymmetry(xs);
1116 s << ValueSymmetry(IntArgs::create(4,0));
1117 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
1118 }
1119 /// Compute list of expected solutions
1120 static std::vector<IntArgs> expectedSolutions(void) {
1121 static std::vector<IntArgs> expected;
1122 expected.clear();
1123 expected.push_back(IntArgs({0,0,0,0}));
1124 expected.push_back(IntArgs({0,0,0,1}));
1125 expected.push_back(IntArgs({0,0,1,1}));
1126 expected.push_back(IntArgs({0,0,1,2}));
1127 expected.push_back(IntArgs({0,1,1,1}));
1128 expected.push_back(IntArgs({0,1,1,2}));
1129 expected.push_back(IntArgs({0,1,2,2})); // This solution is symmetric to the previous one.
1130 expected.push_back(IntArgs({0,1,2,3}));
1131 return expected;
1132 }
1133 };
1134
1135 /// %Test for %LDSB infrastructure with %Latin square problem
1136 class LDSBLatin : public Base {
1137 public:
1138 /// %Latin square space
1139 class Latin : public Space {
1140 public:
1141 IntVarArray xs;
1142 Latin(int n = 4) : xs(*this, n*n, 1, n)
1143 {
1144 Matrix<IntVarArray> m(xs, n, n);
1145 for (int i = 0 ; i < n ; i++) {
1146 distinct(*this, m.col(i));
1147 distinct(*this, m.row(i));
1148 }
1149 Symmetries s;
1150 s << rows_interchange(m);
1151 s << columns_interchange(m);
1152 s << ValueSymmetry(IntSet(1,n));
1153 branch(*this, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
1154 }
1155 // Search support.
1156 Latin(Latin& s) : Space(s)
1157 { xs.update(*this, s.xs); }
1158 virtual Space* copy(void)
1159 { return new Latin(*this); }
1160 IntArgs solution(void) {
1161 IntArgs a(xs.size());
1162 for (int i = 0 ; i < a.size() ; ++i)
1163 a[i] = xs[i].val();
1164 return a;
1165 }
1166
1167 /// Compute list of expected solutions
1168 static std::vector<IntArgs> expectedSolutions(void) {
1169 static std::vector<IntArgs> expected;
1170 expected.clear();
1171 expected.push_back(IntArgs({1,2,3,4, 2,1,4,3, 3,4,1,2, 4,3,2,1}));
1172 expected.push_back(IntArgs({1,2,3,4, 2,1,4,3, 3,4,2,1, 4,3,1,2}));
1173 expected.push_back(IntArgs({1,2,3,4, 2,3,4,1, 3,4,1,2, 4,1,2,3}));
1174 expected.push_back(IntArgs({1,2,3,4, 2,4,1,3, 3,1,4,2, 4,3,2,1}));
1175 return expected;
1176 }
1177 };
1178 /// Initialize test
1179 LDSBLatin(std::string label) : Test::Base("LDSB::" + label) {}
1180 /// Perform actual tests
1181 bool run(void) {
1182 Latin *s = new Latin();
1183 DFS<Latin> e(s);
1184 bool r = check(e, Latin::expectedSolutions());
1185 delete s;
1186 return r;
1187 }
1188 };
1189
1190 /* This test should fail if the recomputation-handling does not work
1191 * properly.
1192 *
1193 * Why recomputation can be a problem
1194 * ==================================
1195 *
1196 * Every branch point in LDSB is binary, with a left and a right
1197 * branch. Whenever backtracking happens -- when a right branch is
1198 * explored -- LDSB computes a set of symmetric literals to
1199 * exclude.
1200 *
1201 * !!! This calculation may depend on the current domains of the
1202 * !!! variables.
1203 *
1204 * During recomputation, parts of the search tree are replayed. To
1205 * be specific, the branching constraints are posted, but no
1206 * propagation happens. This means that at a given branch point,
1207 * the domains during recomputation may be different (weaker) than
1208 * they were the first time during search.
1209 *
1210 * !!! This *cannot* cause solutions to be missed --- LDSB will not
1211 * !!! be incorrect --- but it *does* change what will be pruned.
1212 *
1213 * If recomputation is not handled properly, the difference in
1214 * domains will cause extra solutions to be found. This is a result
1215 * of symmetries failing to be broken.
1216 *
1217 */
1218
1219 /// %Test for handling of recomputation
1220 class Recomputation {
1221 public:
1222 /// Number of variables
1223 static const int n = 4;
1224 /// Lower bound of values
1225 static const int l = 0;
1226 /// Upper bound of values
1227 static const int u = 1;
1228 /// Setup problem constraints and symmetries
1229 static void setup(Home home, IntVarArray& xs) {
1230 TupleSet t(2);
1231 t.add({0,0}).add({1,1}).finalize();
1232 IntVarArgs va;
1233 va << xs[0] << xs[2];
1234 extensional(home, va, t);
1235 Symmetries syms;
1236 syms << VariableSequenceSymmetry(xs, 2);
1237 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
1238 }
1239 /// Compute list of expected solutions
1240 static std::vector<IntArgs> expectedSolutions(void) {
1241 static std::vector<IntArgs> expected;
1242 expected.clear();
1243 expected.push_back(IntArgs({0,0,0,0}));
1244 expected.push_back(IntArgs({0,0,0,1}));
1245
1246 // This is the solution that will be found if recomputation is
1247 // not handled. After branching on x[0]=0, we try x[1]=0. When
1248 // x[1]=0 backtracks, the symmetry [x[0],x[1]] <-> [x[2],x[3]]
1249 // is active --- but only after propagation! (Without
1250 // propagation, we do not have x[2]=0.) If propagation happens,
1251 // we know that symmetry is active and we can post x[3]!=0. If
1252 // it doesn't, we don't use the symmetry and we find a solution
1253 // where x[3]=0.
1254
1255 // expected.push_back(IntArgs({0,1,0,0}));
1256
1257 expected.push_back(IntArgs({0,1,0,1}));
1258
1259 expected.push_back(IntArgs({1,0,1,0}));
1260 expected.push_back(IntArgs({1,0,1,1}));
1261 expected.push_back(IntArgs({1,1,1,1}));
1262 return expected;
1263 }
1264 };
1265
1266 double position(const Space& home, IntVar x, int i) {
1267 (void) home;
1268 (void) x;
1269 return i;
1270 }
1271
1272 /// %Test tiebreaking variable heuristic.
1273 class TieBreak {
1274 public:
1275 /// Number of variables
1276 static const int n = 4;
1277 /// Lower bound of values
1278 static const int l = 0;
1279 /// Upper bound of values
1280 static const int u = 3;
1281 /// Setup problem constraints and symmetries
1282 static void setup(Home home, IntVarArray& xs) {
1283 Symmetries syms;
1284 IntArgs indices({0,1,2,3});
1285 syms << VariableSymmetry(xs, indices);
1286 distinct(home, xs);
1287 // This redundant constraint is to trick the variable
1288 // heuristic.
1289 rel(home, xs[1] != xs[2]);
1290 // xs[1] and xs[2] have higher degree than the others, so they
1291 // are considered first. xs[2] is higher than x[1] by the merit
1292 // function, so it is assigned first. Now all remaining
1293 // variables have the same degree, so they are searched in
1294 // reverse order (according to the merit function). So, the
1295 // solution found is {3, 2, 0, 1}.
1296 branch(home, xs, tiebreak(INT_VAR_DEGREE_MAX(), INT_VAR_MERIT_MAX(position)), INT_VAL_MIN(), syms);
1297 }
1298 /// Compute list of expected solutions
1299 static std::vector<IntArgs> expectedSolutions(void) {
1300 static std::vector<IntArgs> expected;
1301 expected.clear();
1302 expected.push_back(IntArgs({3,2,0,1}));
1303 return expected;
1304 }
1305 };
1306
1307#ifdef GECODE_HAS_SET_VARS
1308 /// Convenient way to make IntSetArgs
1309 IntSetArgs ISA(int n, ...) {
1310 IntSetArgs sets;
1311 va_list args;
1312 va_start(args, n);
1313 int i = 0;
1314 IntArgs a;
1315 while (i < n) {
1316 int x = va_arg(args,int);
1317 if (x == -1) {
1318 i++;
1319 sets << IntSet(a);
1320 a = IntArgs();
1321 } else {
1322 a << x;
1323 }
1324 }
1325 va_end(args);
1326 return sets;
1327 }
1328
1329 /// %Test for set variable symmetry
1330 class SetVarSym1 {
1331 public:
1332 /// Number of variables
1333 static const int n = 2;
1334 /// Lower bound of values
1335 static const int l = 0;
1336 /// Upper bound of values
1337 static const int u = 1;
1338 /// Setup problem constraints and symmetries
1339 static void setup(Home home, SetVarArray& xs) {
1340 Symmetries syms;
1341 syms << VariableSymmetry(xs);
1342 branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
1343 }
1344 /// Compute list of expected solutions
1345 static std::vector<IntSetArgs> expectedSolutions(void) {
1346 static std::vector<IntSetArgs> expected;
1347 expected.clear();
1348 expected.push_back(ISA(2, 0,1,-1, 0,1,-1));
1349 expected.push_back(ISA(2, 0,1,-1, 0, -1));
1350 expected.push_back(ISA(2, 0,1,-1, 1,-1));
1351 expected.push_back(ISA(2, 0,1,-1, -1));
1352 expected.push_back(ISA(2, 0, -1, 0,1,-1));
1353 expected.push_back(ISA(2, 0, -1, 0, -1));
1354 expected.push_back(ISA(2, 0, -1, 1,-1));
1355 expected.push_back(ISA(2, 0, -1, -1));
1356 // expected.push_back(ISA(2, 1,-1, 0,1,-1));
1357 // expected.push_back(ISA(2, 1,-1, 0, -1));
1358 expected.push_back(ISA(2, 1,-1, 1,-1));
1359 expected.push_back(ISA(2, 1,-1, -1));
1360 // expected.push_back(ISA(2, -1, 0,1,-1));
1361 // expected.push_back(ISA(2, -1, 0, -1));
1362 // expected.push_back(ISA(2, -1, 1,-1));
1363 expected.push_back(ISA(2, -1, -1));
1364 return expected;
1365 }
1366 };
1367
1368 /*
1369 * This tests the special handling of value symmetries on set
1370 * values. Look at the third solution (commented out) below. The
1371 * first variable has been assigned to {0,1}. If the value symmetry
1372 * is not handled specially, then we will consider the value
1373 * symmetry broken because the search has touched each value.
1374 * However, because both values have been assigned to the same
1375 * variable, 0 and 1 are still symmetric. Therefore, the third
1376 * solution is symmetric to the second one and should be excluded.
1377 */
1378
1379 /// %Test for set value symmetry
1380 class SetValSym1 {
1381 public:
1382 /// Number of variables
1383 static const int n = 2;
1384 /// Lower bound of values
1385 static const int l = 0;
1386 /// Upper bound of values
1387 static const int u = 1;
1388 /// Setup problem constraints and symmetries
1389 static void setup(Home home, SetVarArray& xs) {
1390 Symmetries syms;
1391 syms << ValueSymmetry(IntArgs({0,1}));
1392 branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
1393 }
1394 /// Compute list of expected solutions
1395 static std::vector<IntSetArgs> expectedSolutions(void) {
1396 static std::vector<IntSetArgs> expected;
1397 expected.clear();
1398 expected.push_back(ISA(2, 0,1,-1, 0,1,-1));
1399 expected.push_back(ISA(2, 0,1,-1, 0, -1));
1400 // expected.push_back(ISA(2, 0,1,-1, 1,-1)); // XXXXX bad solution
1401 expected.push_back(ISA(2, 0,1,-1, -1));
1402 expected.push_back(ISA(2, 0, -1, 0,1,-1));
1403 expected.push_back(ISA(2, 0, -1, 0, -1));
1404 expected.push_back(ISA(2, 0, -1, 1,-1));
1405 expected.push_back(ISA(2, 0, -1, -1));
1406 // expected.push_back(ISA(2, 1,-1, 0,1,-1));
1407 // expected.push_back(ISA(2, 1,-1, 0, -1));
1408 // expected.push_back(ISA(2, 1,-1, 1,-1));
1409 // expected.push_back(ISA(2, 1,-1, -1));
1410 expected.push_back(ISA(2, -1, 0,1,-1));
1411 expected.push_back(ISA(2, -1, 0, -1));
1412 // expected.push_back(ISA(2, -1, 1,-1));
1413 expected.push_back(ISA(2, -1, -1));
1414 return expected;
1415 }
1416 };
1417
1418 /// %Test for set value symmetry
1419 class SetValSym2 {
1420 public:
1421 /// Number of variables
1422 static const int n = 3;
1423 /// Lower bound of values
1424 static const int l = 1;
1425 /// Upper bound of values
1426 static const int u = 4;
1427 /// Setup problem constraints and symmetries
1428 static void setup(Home home, SetVarArray& xs) {
1429 Symmetries syms;
1430 syms << ValueSymmetry(IntArgs({1,2,3,4}));
1431 for (int i = 0 ; i < 3 ; i++)
1432 cardinality(home, xs[i], 1, 1);
1433 branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
1434 }
1435 /// Compute list of expected solutions
1436 static std::vector<IntSetArgs> expectedSolutions(void) {
1437 static std::vector<IntSetArgs> expected;
1438 expected.clear();
1439 expected.push_back(ISA(3, 1,-1, 1,-1, 1,-1));
1440 expected.push_back(ISA(3, 1,-1, 1,-1, 2,-1));
1441 expected.push_back(ISA(3, 1,-1, 2,-1, 1,-1));
1442 expected.push_back(ISA(3, 1,-1, 2,-1, 2,-1));
1443 expected.push_back(ISA(3, 1,-1, 2,-1, 3,-1));
1444 return expected;
1445 }
1446 };
1447
1448 /// %Test for set variable sequence symmetry
1449 class SetVarSeqSym1 {
1450 public:
1451 /// Number of variables
1452 static const int n = 4;
1453 /// Lower bound of values
1454 static const int l = 0;
1455 /// Upper bound of values
1456 static const int u = 1;
1457 /// Setup problem constraints and symmetries
1458 static void setup(Home home, SetVarArray& xs) {
1459 Symmetries syms;
1460 syms << VariableSequenceSymmetry(xs,2);
1461 rel(home, xs[0], SOT_INTER, xs[1], SRT_EQ, IntSet::empty);
1462 rel(home, xs[2], SOT_INTER, xs[3], SRT_EQ, IntSet::empty);
1463 for (int i = 0 ; i < 4 ; i++)
1464 cardinality(home, xs[i], 1, 1);
1465 branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
1466 }
1467 /// Compute list of expected solutions
1468 static std::vector<IntSetArgs> expectedSolutions(void) {
1469 static std::vector<IntSetArgs> expected;
1470 expected.clear();
1471 expected.push_back(ISA(4, 0,-1, 1,-1, 0,-1, 1,-1));
1472 expected.push_back(ISA(4, 0,-1, 1,-1, 1,-1, 0,-1));
1473 // expected.push_back(ISA(4, 1,-1, 0,-1, 0,-1, 1,-1));
1474 expected.push_back(ISA(4, 1,-1, 0,-1, 1,-1, 0,-1));
1475 return expected;
1476 }
1477 };
1478
1479 /// %Test for set variable sequence symmetry
1480 class SetVarSeqSym2 {
1481 public:
1482 /// Number of variables
1483 static const int n = 4;
1484 /// Lower bound of values
1485 static const int l = 0;
1486 /// Upper bound of values
1487 static const int u = 0;
1488 /// Setup problem constraints and symmetries
1489 static void setup(Home home, SetVarArray& xs) {
1490 Symmetries syms;
1491 syms << VariableSequenceSymmetry(xs,2);
1492 rel(home, xs[0], SRT_EQ, xs[2]);
1493 branch(home, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
1494 }
1495 /// Compute list of expected solutions
1496 static std::vector<IntSetArgs> expectedSolutions(void) {
1497 static std::vector<IntSetArgs> expected;
1498 expected.clear();
1499
1500 // Symmetric solutions are commented out.
1501 expected.push_back(ISA(4, 0, -1,0,-1,0,-1,0,-1));
1502 expected.push_back(ISA(4, 0, -1,0,-1,0,-1, -1));
1503 // expected.push_back(ISA(4, 0, -1,0,-1, -1,0,-1));
1504 // expected.push_back(ISA(4, 0, -1,0,-1, -1, -1));
1505 // expected.push_back(ISA(4, 0, -1, -1,0,-1,0,-1));
1506 expected.push_back(ISA(4, 0, -1, -1,0,-1, -1));
1507 // expected.push_back(ISA(4, 0, -1, -1, -1,0,-1));
1508 // expected.push_back(ISA(4, 0, -1, -1, -1, -1));
1509 // expected.push_back(ISA(4, -1,0,-1,0,-1,0,-1));
1510 // expected.push_back(ISA(4, -1,0,-1,0,-1, -1));
1511 expected.push_back(ISA(4, -1,0,-1, -1,0,-1));
1512 expected.push_back(ISA(4, -1,0,-1, -1, -1));
1513 // expected.push_back(ISA(4, -1, -1,0,-1,0,-1));
1514 // expected.push_back(ISA(4, -1, -1,0,-1, -1));
1515 // expected.push_back(ISA(4, -1, -1, -1,0,-1));
1516 expected.push_back(ISA(4, -1, -1, -1, -1));
1517
1518 return expected;
1519 }
1520 };
1521
1522 /// %Test for reflection symmetry
1523 class ReflectSym1 {
1524 public:
1525 /// Number of variables
1526 static const int n = 6;
1527 /// Lower bound of values
1528 static const int l = 0;
1529 /// Upper bound of values
1530 static const int u = 6;
1531 /// Setup problem constraints and symmetries
1532 static void setup(Home home, IntVarArray& xs) {
1533 Matrix<IntVarArray> m(xs, 3, 2);
1534
1535 distinct(home, xs);
1536 rel(home, abs(m(0,0)-m(1,0))==1);
1537 rel(home, abs(m(0,1)-m(1,1))==1);
1538 rel(home, abs(m(1,0)-m(2,0))==1);
1539 rel(home, abs(m(1,1)-m(2,1))==1);
1540
1541 Symmetries s;
1542 s << values_reflect(l, u);
1543 s << rows_interchange(m);
1544 s << columns_reflect(m);
1545 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
1546 }
1547 /// Compute list of expected solutions
1548 static std::vector<IntArgs> expectedSolutions(void) {
1549 static std::vector<IntArgs> expected;
1550 expected.clear();
1551 expected.push_back(IntArgs({0,1,2,3,4,5}));
1552 expected.push_back(IntArgs({0,1,2,4,5,6}));
1553 expected.push_back(IntArgs({0,1,2,5,4,3}));
1554 expected.push_back(IntArgs({0,1,2,6,5,4}));
1555 return expected;
1556 }
1557 };
1558
1559 /// %Test for reflection symmetry
1560 class ReflectSym2 {
1561 public:
1562 /// Number of variables
1563 static const int n = 2;
1564 /// Lower bound of values
1565 static const int l = 0;
1566 /// Upper bound of values
1567 static const int u = 3;
1568 /// Setup problem constraints and symmetries
1569 static void setup(Home home, IntVarArray& xs) {
1570 Symmetries s;
1571 s << values_reflect(l, u);
1572 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
1573 }
1574 /// Compute list of expected solutions
1575 static std::vector<IntArgs> expectedSolutions(void) {
1576 static std::vector<IntArgs> expected;
1577 expected.clear();
1578 expected.push_back(IntArgs({0,0}));
1579 expected.push_back(IntArgs({0,1}));
1580 expected.push_back(IntArgs({0,2}));
1581 expected.push_back(IntArgs({0,3}));
1582 expected.push_back(IntArgs({1,0}));
1583 expected.push_back(IntArgs({1,1}));
1584 expected.push_back(IntArgs({1,2}));
1585 expected.push_back(IntArgs({1,3}));
1586 return expected;
1587 }
1588 };
1589
1590 /// %Test with action
1591 class Action1 {
1592 public:
1593 /// Number of variables
1594 static const int n = 4;
1595 /// Lower bound of values
1596 static const int l = 0;
1597 /// Upper bound of values
1598 static const int u = 3;
1599 /// Setup problem constraints and symmetries
1600 static void setup(Home home, IntVarArray& xs) {
1601 distinct(home, xs);
1602 Symmetries s;
1603 s << VariableSymmetry(xs);
1604 s << ValueSymmetry(IntArgs::create(4,0));
1605 branch(home, xs, INT_VAR_ACTION_MIN(0.8), INT_VAL_MIN(), s);
1606 }
1607 /// Compute list of expected solutions
1608 static std::vector<IntArgs> expectedSolutions(void) {
1609 static std::vector<IntArgs> expected;
1610 expected.clear();
1611 expected.push_back(IntArgs({0,1,2,3}));
1612 return expected;
1613 }
1614 };
1615
1616#endif
1617
1618 LDSB<VarSym1> varsym1("VarSym1");
1619 LDSB<VarSym1b> varsym1b("VarSym1b");
1620 LDSB<VarSym2> varsym2("VarSym2");
1621 LDSB<VarSym3> varsym3("VarSym3");
1622 LDSB<VarSym4> varsym4("VarSym4");
1623 LDSB<VarSym5> varsym5("VarSym5");
1624 LDSB<MatSym1> matsym1("MatSym1");
1625 LDSB<MatSym2> matsym2("MatSym2");
1626 LDSB<MatSym3> matsym3("MatSym3");
1627 LDSB<MatSym4> matsym4("MatSym4");
1628 LDSB<SimIntVarSym1> simintvarsym1("SimIntVarSym1");
1629 LDSB<SimIntVarSym2> simintvarsym2("SimIntVarSym2");
1630 LDSB<SimIntValSym1> simintvalsym1("SimIntValSym1");
1631 LDSB<SimIntValSym2> simintvalsym2("SimIntValSym2");
1632 LDSB<SimIntValSym3> simintvalsym3("SimIntValSym3");
1633 LDSB<ValSym1> valsym1("ValSym1");
1634 LDSB<ValSym1b> valsym1b("ValSym1b");
1635 LDSB<ValSym1c> valsym1c("ValSym1c");
1636 LDSB<ValSym2> valsym2("ValSym2");
1637 LDSB<ValSym2b> valsym2b("ValSym2b");
1638 LDSB<ValSym3> valsym3("ValSym3");
1639 LDSB<ValSym4> valsym4("ValSym4");
1640 LDSB<ValSym5> valsym5("ValSym5");
1641 LDSB<VarValSym1> varvalsym1("VarValSym1");
1642 LDSBLatin latin("Latin");
1643 LDSB<Recomputation> recomp("Recomputation", 999,999);
1644 LDSB<TieBreak> tiebreak("TieBreak");
1645
1646#ifdef GECODE_HAS_SET_VARS
1647 LDSB<ReflectSym1> reflectsym1("ReflectSym1");
1648 LDSB<ReflectSym2> reflectsym2("ReflectSym2");
1649 LDSB<Action1> action1("Action1");
1650
1651 LDSBSet<SetVarSym1> setvarsym1("SetVarSym1");
1652 LDSBSet<SetValSym1> setvalsym1("SetValSym1");
1653 LDSBSet<SetValSym2> setvalsym2("SetValSym2", 0, 1);
1654 LDSBSet<SetVarSeqSym1> setvarseqsym1("SetVarSeqSym1");
1655 LDSBSet<SetVarSeqSym2> setvarseqsym2("SetVarSeqSym2");
1656#endif
1657}}
1658
1659// STATISTICS: test-core