Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
ldsb.cpp
Go to the documentation of this file.
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
54namespace Test { namespace LDSB {
55
56 using namespace Gecode;
57
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
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
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 == NULL) {
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 != NULL) {
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
140 class OneArray : public Space {
141 public:
145 OneArray(int n, int l, int u) : xs(*this,n,l,u) {
146 }
147
149 xs.update(*this,s.xs);
150 }
151
152 virtual Space* copy(void) {
153 return new OneArray(*this);
154 }
155
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
163 virtual IntArgs* expectedSolutions(void) { return NULL; }
164 };
165
166#ifdef GECODE_HAS_SET_VARS
168 class OneArraySet : public Space {
169 public:
173 OneArraySet(int n, int l, int u) : xs(*this,n, IntSet::empty, l,u) {
174 }
175
177 xs.update(*this,s.xs);
178 }
179
180 virtual Space* copy(void) {
181 return new OneArraySet(*this);
182 }
183
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
193 virtual IntSetArgs* expectedSolutions(void) { return NULL; }
194 };
195#endif
196
198 template <class T>
199 class LDSB : public Base {
200 public:
202 unsigned int c_d;
204 unsigned int a_d;
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
210 bool run(void) {
211 OneArray *s = new OneArray(T::n, T::l, T::u);
212 T::setup(*s, s->xs);
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
225 template <class T>
226 class LDSBSet : public Base {
227 public:
229 unsigned int c_d;
231 unsigned int a_d;
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
237 bool run(void) {
238 OneArraySet *s = new OneArraySet(T::n, T::l, T::u);
239 T::setup(*s, s->xs);
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
254 class VarSym1 {
255 public:
257 static const int n = 4;
259 static const int l = 0;
261 static const int u = 3;
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
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
280 class VarSym1b {
281 public:
283 static const int n = 4;
285 static const int l = 0;
287 static const int u = 3;
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
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
305 class VarSym2 {
306 public:
308 static const int n = 4;
310 static const int l = 0;
312 static const int u = 3;
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
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
364 class VarSym3 {
365 public:
367 static const int n = 4;
369 static const int l = 0;
371 static const int u = 3;
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
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
400 class VarSym4 {
401 public:
403 static const int n = 3;
405 static const int l = 0;
407 static const int u = 2;
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
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
432 class VarSym5 {
433 public:
435 static const int n = 4;
437 static const int l = 0;
439 static const int u = 3;
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
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
464 class MatSym1 {
465 public:
467 static const int n = 6;
469 static const int l = 0;
471 static const int u = 1;
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
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
514 class MatSym2 {
515 public:
517 static const int n = 6;
519 static const int l = 0;
521 static const int u = 1;
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
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
574 class MatSym3 {
575 public:
577 static const int n = 6;
579 static const int l = 0;
581 static const int u = 1;
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
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
619 class MatSym4 {
620 public:
622 static const int n = 4;
624 static const int l = 0;
626 static const int u = 1;
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
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
655 public:
657 static const int n = 12;
659 static const int l = 0;
661 static const int u = 3;
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
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
711 static const int nrows = 4;
713 static const int ncols = 3;
714 public:
716 static const int n = nrows*ncols;
718 static const int l = 0;
720 static const int u = 3;
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
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
758 public:
760 static const int n = 2;
762 static const int l = 0;
764 static const int u = 6;
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;
772 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
773 }
774
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
788 public:
790 static const int n = 3;
792 static const int l = 0;
794 static const int u = 8;
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;
808 branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
809 }
810
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
822 public:
824 static const int n = 2;
826 static const int l = 0;
828 static const int u = 6;
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
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
850 class ValSym1 {
851 public:
853 static const int n = 4;
855 static const int l = 0;
857 static const int u = 3;
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
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
876 class ValSym1b {
877 public:
879 static const int n = 4;
881 static const int l = 0;
883 static const int u = 3;
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
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
901 class ValSym1c {
902 public:
904 static const int n = 4;
906 static const int l = 0;
908 static const int u = 3;
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
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
926 class ValSym2 {
927 public:
929 static const int n = 4;
931 static const int l = 0;
933 static const int u = 3;
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
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
965 class ValSym2b {
966 public:
968 static const int n = 4;
970 static const int l = 0;
972 static const int u = 3;
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
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
1003 class ValSym3 {
1004 public:
1006 static const int n = 4;
1008 static const int l = 0;
1010 static const int u = 3;
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
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
1040 class ValSym4 {
1041 public:
1043 static const int n = 3;
1045 static const int l = 0;
1047 static const int u = 2;
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
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
1071 class ValSym5 {
1072 public:
1074 static const int n = 4;
1076 static const int l = 0;
1078 static const int u = 3;
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
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
1105 public:
1107 static const int n = 4;
1109 static const int l = 0;
1111 static const int u = 3;
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
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
1136 class LDSBLatin : public Base {
1137 public:
1139 class Latin : public Space {
1140 public:
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.
1157 { xs.update(*this, s.xs); }
1158 virtual Space* copy(void)
1159 { return new Latin(*this); }
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
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
1179 LDSBLatin(std::string label) : Test::Base("LDSB::" + label) {}
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
1221 public:
1223 static const int n = 4;
1225 static const int l = 0;
1227 static const int u = 1;
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
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
1273 class TieBreak {
1274 public:
1276 static const int n = 4;
1278 static const int l = 0;
1280 static const int u = 3;
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}.
1297 }
1298
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
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
1331 public:
1333 static const int n = 2;
1335 static const int l = 0;
1337 static const int u = 1;
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
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
1381 public:
1383 static const int n = 2;
1385 static const int l = 0;
1387 static const int u = 1;
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
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
1420 public:
1422 static const int n = 3;
1424 static const int l = 1;
1426 static const int u = 4;
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
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
1450 public:
1452 static const int n = 4;
1454 static const int l = 0;
1456 static const int u = 1;
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
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
1481 public:
1483 static const int n = 4;
1485 static const int l = 0;
1487 static const int u = 0;
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
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
1524 public:
1526 static const int n = 6;
1528 static const int l = 0;
1530 static const int u = 6;
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
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
1561 public:
1563 static const int n = 2;
1565 static const int l = 0;
1567 static const int u = 3;
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
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
1591 class Action1 {
1592 public:
1594 static const int n = 4;
1596 static const int l = 0;
1598 static const int u = 3;
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
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
1643 LDSB<Recomputation> recomp("Recomputation", 999,999);
1645
1646#ifdef GECODE_HAS_SET_VARS
1650
1653 LDSBSet<SetValSym2> setvalsym2("SetValSym2", 0, 1);
1656#endif
1657}}
1658
1659// STATISTICS: test-core
Depth-first search engine.
Definition search.hh:1036
FloatNum size(void) const
Return size of float value (distance between maximum and minimum)
Definition val.hpp:78
Home class for posting propagators
Definition core.hpp:856
Passing integer arguments.
Definition int.hh:634
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
Definition array.hpp:76
Value iterator for integer sets.
Definition int.hh:333
Integer sets.
Definition int.hh:174
static const IntSet empty
Empty set.
Definition int.hh:283
Passing integer variables.
Definition int.hh:662
Integer variable array.
Definition int.hh:772
Integer variables.
Definition int.hh:371
Matrix-interface for arrays.
Slice< A > slice(int fc, int tc, int fr, int tr) const
Access slice of the matrix.
Definition matrix.hpp:171
Slice< A > col(int c) const
Access column c.
Definition matrix.hpp:183
Slice< A > row(int r) const
Access row r.
Definition matrix.hpp:177
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition base.hpp:46
Search engine options
Definition search.hh:746
static const Options def
Default options.
Definition search.hh:771
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition search.hh:753
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
Definition search.hh:755
Set variable array
Definition set.hh:573
Iterator for the greatest lower bound ranges of a set variable.
Definition set.hh:273
Computation spaces.
Definition core.hpp:1744
Collection of symmetries.
Definition int.hh:5307
Combine variable selection criteria for tie-breaking.
Definition tiebreak.hpp:38
Class represeting a set of tuples.
Definition int.hh:2206
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
Base(const std::string &s)
Create and register test with name s.
Definition test.cpp:59
Test with action
Definition ldsb.cpp:1591
static const int u
Upper bound of values.
Definition ldsb.cpp:1598
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:1608
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:1600
static const int l
Lower bound of values.
Definition ldsb.cpp:1596
static const int n
Number of variables.
Definition ldsb.cpp:1594
Latin square space
Definition ldsb.cpp:1139
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:1168
virtual Space * copy(void)
Copying member function.
Definition ldsb.cpp:1158
Test for LDSB infrastructure with Latin square problem
Definition ldsb.cpp:1136
bool run(void)
Perform actual tests.
Definition ldsb.cpp:1181
LDSBLatin(std::string label)
Initialize test.
Definition ldsb.cpp:1179
Test for LDSB infrastructure
Definition ldsb.cpp:226
LDSBSet(std::string label, unsigned int c=0, unsigned int a=0)
Initialize test.
Definition ldsb.cpp:233
bool run(void)
Perform actual tests.
Definition ldsb.cpp:237
unsigned int a_d
Adaptation distance.
Definition ldsb.cpp:231
unsigned int c_d
Recomputation distance.
Definition ldsb.cpp:229
bool run(void)
Perform actual tests.
Definition ldsb.cpp:210
LDSB(std::string label, unsigned int c=0, unsigned int a=0)
Initialize test.
Definition ldsb.cpp:206
unsigned int c_d
Recomputation distance.
Definition ldsb.cpp:202
unsigned int a_d
Adaptation distance.
Definition ldsb.cpp:204
Test for matrix symmetry
Definition ldsb.cpp:464
static const int n
Number of variables.
Definition ldsb.cpp:467
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:480
static const int l
Lower bound of values.
Definition ldsb.cpp:469
static const int u
Upper bound of values.
Definition ldsb.cpp:471
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:473
Test for matrix symmetry
Definition ldsb.cpp:514
static const int n
Number of variables.
Definition ldsb.cpp:517
static const int l
Lower bound of values.
Definition ldsb.cpp:519
static const int u
Upper bound of values.
Definition ldsb.cpp:521
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:523
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:530
Test for matrix symmetry
Definition ldsb.cpp:574
static const int u
Upper bound of values.
Definition ldsb.cpp:581
static const int n
Number of variables.
Definition ldsb.cpp:577
static const int l
Lower bound of values.
Definition ldsb.cpp:579
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:591
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:583
Test for matrix symmetry
Definition ldsb.cpp:619
static const int n
Number of variables.
Definition ldsb.cpp:622
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:628
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:635
static const int l
Lower bound of values.
Definition ldsb.cpp:624
static const int u
Upper bound of values.
Definition ldsb.cpp:626
Test space (set version)
Definition ldsb.cpp:168
IntSetArgs solution(void)
Return the solution as IntSetArgs.
Definition ldsb.cpp:184
virtual Space * copy(void)
Copy during cloning.
Definition ldsb.cpp:180
SetVarArray xs
Variables.
Definition ldsb.cpp:171
OneArraySet(int n, int l, int u)
Constructor for creation.
Definition ldsb.cpp:173
OneArraySet(OneArraySet &s)
Constructor for cloning s.
Definition ldsb.cpp:176
virtual IntSetArgs * expectedSolutions(void)
Expected solutions.
Definition ldsb.cpp:193
virtual Space * copy(void)
Copy during cloning.
Definition ldsb.cpp:152
OneArray(int n, int l, int u)
Constructor for creation.
Definition ldsb.cpp:145
virtual IntArgs * expectedSolutions(void)
Expected solutions.
Definition ldsb.cpp:163
OneArray(OneArray &s)
Constructor for cloning s.
Definition ldsb.cpp:148
IntVarArray xs
Variables.
Definition ldsb.cpp:143
IntArgs solution(void)
Return the solution as IntArgs.
Definition ldsb.cpp:156
Test for handling of recomputation
Definition ldsb.cpp:1220
static const int u
Upper bound of values.
Definition ldsb.cpp:1227
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:1229
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:1240
static const int n
Number of variables.
Definition ldsb.cpp:1223
static const int l
Lower bound of values.
Definition ldsb.cpp:1225
Test for reflection symmetry
Definition ldsb.cpp:1523
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:1548
static const int n
Number of variables.
Definition ldsb.cpp:1526
static const int l
Lower bound of values.
Definition ldsb.cpp:1528
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:1532
static const int u
Upper bound of values.
Definition ldsb.cpp:1530
Test for reflection symmetry
Definition ldsb.cpp:1560
static const int u
Upper bound of values.
Definition ldsb.cpp:1567
static const int n
Number of variables.
Definition ldsb.cpp:1563
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:1575
static const int l
Lower bound of values.
Definition ldsb.cpp:1565
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:1569
Test for set value symmetry
Definition ldsb.cpp:1380
static void setup(Home home, SetVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:1389
static const int l
Lower bound of values.
Definition ldsb.cpp:1385
static const int n
Number of variables.
Definition ldsb.cpp:1383
static std::vector< IntSetArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:1395
static const int u
Upper bound of values.
Definition ldsb.cpp:1387
Test for set value symmetry
Definition ldsb.cpp:1419
static const int l
Lower bound of values.
Definition ldsb.cpp:1424
static std::vector< IntSetArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:1436
static void setup(Home home, SetVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:1428
static const int u
Upper bound of values.
Definition ldsb.cpp:1426
static const int n
Number of variables.
Definition ldsb.cpp:1422
Test for set variable sequence symmetry
Definition ldsb.cpp:1449
static const int n
Number of variables.
Definition ldsb.cpp:1452
static const int l
Lower bound of values.
Definition ldsb.cpp:1454
static const int u
Upper bound of values.
Definition ldsb.cpp:1456
static void setup(Home home, SetVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:1458
static std::vector< IntSetArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:1468
Test for set variable sequence symmetry
Definition ldsb.cpp:1480
static const int n
Number of variables.
Definition ldsb.cpp:1483
static const int u
Upper bound of values.
Definition ldsb.cpp:1487
static void setup(Home home, SetVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:1489
static const int l
Lower bound of values.
Definition ldsb.cpp:1485
static std::vector< IntSetArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:1496
Test for set variable symmetry
Definition ldsb.cpp:1330
static const int u
Upper bound of values.
Definition ldsb.cpp:1337
static void setup(Home home, SetVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:1339
static const int l
Lower bound of values.
Definition ldsb.cpp:1335
static const int n
Number of variables.
Definition ldsb.cpp:1333
static std::vector< IntSetArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:1345
Test for value sequence symmetry
Definition ldsb.cpp:757
static const int n
Number of variables.
Definition ldsb.cpp:760
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:775
static const int l
Lower bound of values.
Definition ldsb.cpp:762
static const int u
Upper bound of values.
Definition ldsb.cpp:764
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:766
Test for value sequence symmetry
Definition ldsb.cpp:787
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:796
static const int u
Upper bound of values.
Definition ldsb.cpp:794
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:811
static const int l
Lower bound of values.
Definition ldsb.cpp:792
static const int n
Number of variables.
Definition ldsb.cpp:790
Test for value sequence symmetry
Definition ldsb.cpp:821
static const int n
Number of variables.
Definition ldsb.cpp:824
static const int u
Upper bound of values.
Definition ldsb.cpp:828
static const int l
Lower bound of values.
Definition ldsb.cpp:826
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:838
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:830
Test for variable sequence symmetry
Definition ldsb.cpp:654
static const int l
Lower bound of values.
Definition ldsb.cpp:659
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:663
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:677
static const int n
Number of variables.
Definition ldsb.cpp:657
static const int u
Upper bound of values.
Definition ldsb.cpp:661
Test for variable sequence symmetry
Definition ldsb.cpp:709
static const int l
Lower bound of values.
Definition ldsb.cpp:718
static const int u
Upper bound of values.
Definition ldsb.cpp:720
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:745
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:722
static const int n
Number of variables.
Definition ldsb.cpp:716
static const int l
Lower bound of values.
Definition ldsb.cpp:1278
static const int u
Upper bound of values.
Definition ldsb.cpp:1280
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:1299
static const int n
Number of variables.
Definition ldsb.cpp:1276
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:1282
Test for value symmetry
Definition ldsb.cpp:850
static const int n
Number of variables.
Definition ldsb.cpp:853
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:859
static const int l
Lower bound of values.
Definition ldsb.cpp:855
static const int u
Upper bound of values.
Definition ldsb.cpp:857
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:867
Test for value symmetry
Definition ldsb.cpp:876
static const int u
Upper bound of values.
Definition ldsb.cpp:883
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:885
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:892
static const int l
Lower bound of values.
Definition ldsb.cpp:881
static const int n
Number of variables.
Definition ldsb.cpp:879
Test for value symmetry
Definition ldsb.cpp:901
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:910
static const int u
Upper bound of values.
Definition ldsb.cpp:908
static const int l
Lower bound of values.
Definition ldsb.cpp:906
static const int n
Number of variables.
Definition ldsb.cpp:904
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:917
Test for value symmetry
Definition ldsb.cpp:926
static const int n
Number of variables.
Definition ldsb.cpp:929
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:942
static const int l
Lower bound of values.
Definition ldsb.cpp:931
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:935
static const int u
Upper bound of values.
Definition ldsb.cpp:933
Test for value symmetry
Definition ldsb.cpp:965
static const int l
Lower bound of values.
Definition ldsb.cpp:970
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:980
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:974
static const int u
Upper bound of values.
Definition ldsb.cpp:972
static const int n
Number of variables.
Definition ldsb.cpp:968
Test for value symmetry
Definition ldsb.cpp:1003
static const int u
Upper bound of values.
Definition ldsb.cpp:1010
static const int n
Number of variables.
Definition ldsb.cpp:1006
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:1012
static const int l
Lower bound of values.
Definition ldsb.cpp:1008
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:1020
Test for value symmetry
Definition ldsb.cpp:1040
static const int n
Number of variables.
Definition ldsb.cpp:1043
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:1057
static const int l
Lower bound of values.
Definition ldsb.cpp:1045
static const int u
Upper bound of values.
Definition ldsb.cpp:1047
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:1049
Test for value symmetry
Definition ldsb.cpp:1071
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:1080
static const int n
Number of variables.
Definition ldsb.cpp:1074
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:1090
static const int l
Lower bound of values.
Definition ldsb.cpp:1076
static const int u
Upper bound of values.
Definition ldsb.cpp:1078
Test for variable symmetry
Definition ldsb.cpp:254
static const int n
Number of variables.
Definition ldsb.cpp:257
static const int u
Upper bound of values.
Definition ldsb.cpp:261
static const int l
Lower bound of values.
Definition ldsb.cpp:259
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:271
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:263
Test for variable symmetry
Definition ldsb.cpp:280
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:296
static const int u
Upper bound of values.
Definition ldsb.cpp:287
static const int l
Lower bound of values.
Definition ldsb.cpp:285
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:289
static const int n
Number of variables.
Definition ldsb.cpp:283
Test for variable symmetry
Definition ldsb.cpp:305
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:321
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:314
static const int l
Lower bound of values.
Definition ldsb.cpp:310
static const int u
Upper bound of values.
Definition ldsb.cpp:312
static const int n
Number of variables.
Definition ldsb.cpp:308
Test for variable symmetry
Definition ldsb.cpp:364
static const int n
Number of variables.
Definition ldsb.cpp:367
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:373
static const int l
Lower bound of values.
Definition ldsb.cpp:369
static const int u
Upper bound of values.
Definition ldsb.cpp:371
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:380
Test for variable symmetry
Definition ldsb.cpp:400
static const int u
Upper bound of values.
Definition ldsb.cpp:407
static const int n
Number of variables.
Definition ldsb.cpp:403
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:409
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:418
static const int l
Lower bound of values.
Definition ldsb.cpp:405
Test for variable symmetry
Definition ldsb.cpp:432
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:450
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:441
static const int l
Lower bound of values.
Definition ldsb.cpp:437
static const int u
Upper bound of values.
Definition ldsb.cpp:439
static const int n
Number of variables.
Definition ldsb.cpp:435
Test for variable and value symmetry
Definition ldsb.cpp:1104
static const int l
Lower bound of values.
Definition ldsb.cpp:1109
static const int n
Number of variables.
Definition ldsb.cpp:1107
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition ldsb.cpp:1120
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition ldsb.cpp:1113
static const int u
Upper bound of values.
Definition ldsb.cpp:1111
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition linear.cpp:41
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
void extensional(Home home, const IntVarArgs &x, DFA d, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for extensional constraint described by a DFA.
@ IRT_EQ
Equality ( )
Definition int.hh:941
Space(void)
Default constructor.
Definition core.cpp:115
@ SOT_INTER
Intersection
Definition set.hh:669
@ SRT_EQ
Equality ( )
Definition set.hh:650
Symmetry breaking for integer variables.
Definition int.hh:5261
Gecode toplevel namespace
ArgArray< IntSet > IntSetArgs
Passing set arguments.
Definition int.hh:625
SymmetryHandle ValueSymmetry(const IntArgs &v)
Values in v are interchangeable.
Definition ldsb.cpp:81
SymmetryHandle ValueSequenceSymmetry(const IntArgs &v, int ss)
Value sequences in v of size ss are interchangeable.
Definition ldsb.cpp:102
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
SymmetryHandle values_reflect(int lower, int upper)
The values from lower to upper (inclusive) can be reflected.
Definition ldsb.cpp:106
SymmetryHandle rows_reflect(const Matrix< A > &m)
Reflect rows symmetry specification.
Definition ldsb.hpp:62
Select first unassigned variable SetVarBranch SET_VAR_NONE(void)
Definition var.hpp:96
IntVarBranch INT_VAR_DEGREE_MAX(BranchTbl tbl=nullptr)
Select variable with largest degree.
Definition var.hpp:121
IntValBranch INT_VAL_MED(void)
Select greatest value not greater than the median.
Definition val.hpp:60
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
Definition tiebreak.hpp:80
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Definition distinct.cpp:46
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
IntValBranch INT_VAL_MAX(void)
Select largest value.
Definition val.hpp:65
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition aliases.hpp:143
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:773
SymmetryHandle columns_reflect(const Matrix< A > &m)
Reflect columns symmetry specification.
Definition ldsb.hpp:85
SymmetryHandle rows_interchange(const Matrix< A > &m)
Interchangeable rows symmetry specification.
Definition ldsb.hpp:40
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
SymmetryHandle VariableSymmetry(const IntVarArgs &x)
Variables in x are interchangeable.
Definition ldsb.cpp:62
IntVarBranch INT_VAR_ACTION_MIN(double d=1.0, BranchTbl tbl=nullptr)
Select variable with lowest action with decay factor d.
Definition var.hpp:146
Include smallest element SetValBranch SET_VAL_MIN_INC(void)
Definition val.hpp:55
SymmetryHandle VariableSequenceSymmetry(const IntVarArgs &x, int ss)
Variable sequences in x of size ss are interchangeable.
Definition ldsb.cpp:90
LinIntExpr cardinality(const SetExpr &)
Cardinality of set expression.
Definition set-expr.cpp:817
IntVarBranch INT_VAR_MERIT_MAX(IntBranchMerit bm, BranchTbl tbl=nullptr)
Select variable with highest merit according to branch merit function bm.
Definition var.hpp:111
Post propagator for SetVar x
Definition set.hh:773
SymmetryHandle columns_interchange(const Matrix< A > &m)
Interchangeable columns symmetry specification.
Definition ldsb.hpp:51
LDSB< ValSym4 > valsym4("ValSym4")
LDSB< Action1 > action1("Action1")
double position(const Space &home, IntVar x, int i)
Definition ldsb.cpp:1266
LDSB< MatSym1 > matsym1("MatSym1")
LDSB< VarSym1 > varsym1("VarSym1")
LDSB< SimIntValSym3 > simintvalsym3("SimIntValSym3")
LDSB< VarSym3 > varsym3("VarSym3")
LDSB< MatSym3 > matsym3("MatSym3")
LDSB< VarSym2 > varsym2("VarSym2")
LDSB< ValSym1c > valsym1c("ValSym1c")
LDSB< SimIntVarSym1 > simintvarsym1("SimIntVarSym1")
LDSB< VarSym4 > varsym4("VarSym4")
LDSB< TieBreak > tiebreak("TieBreak")
LDSB< SimIntValSym1 > simintvalsym1("SimIntValSym1")
LDSB< ValSym5 > valsym5("ValSym5")
LDSB< ReflectSym2 > reflectsym2("ReflectSym2")
LDSB< MatSym2 > matsym2("MatSym2")
LDSB< MatSym4 > matsym4("MatSym4")
LDSBLatin latin("Latin")
LDSB< Recomputation > recomp("Recomputation", 999, 999)
LDSB< SimIntVarSym2 > simintvarsym2("SimIntVarSym2")
LDSB< ValSym2 > valsym2("ValSym2")
LDSBSet< SetVarSym1 > setvarsym1("SetVarSym1")
IntSetArgs ISA(int n,...)
Convenient way to make IntSetArgs.
Definition ldsb.cpp:1309
LDSBSet< SetVarSeqSym1 > setvarseqsym1("SetVarSeqSym1")
LDSB< ValSym1b > valsym1b("ValSym1b")
LDSB< ValSym1 > valsym1("ValSym1")
LDSB< SimIntValSym2 > simintvalsym2("SimIntValSym2")
LDSB< ValSym3 > valsym3("ValSym3")
LDSBSet< SetValSym1 > setvalsym1("SetValSym1")
bool check(DFS< T > &e, std::vector< VarArgsType > expected)
Checks found solutions against expected solutions.
Definition ldsb.cpp:102
LDSB< ValSym2b > valsym2b("ValSym2b")
LDSBSet< SetVarSeqSym2 > setvarseqsym2("SetVarSeqSym2")
LDSB< ReflectSym1 > reflectsym1("ReflectSym1")
LDSB< VarSym5 > varsym5("VarSym5")
LDSB< VarSym1b > varsym1b("VarSym1b")
LDSBSet< SetValSym2 > setvalsym2("SetValSym2", 0, 1)
LDSB< VarValSym1 > varvalsym1("VarValSym1")
bool equal(const IntArgs &a, const IntArgs &b)
Returns true iff a and b are equal (they have the same size and the same elements in the same positio...
Definition ldsb.cpp:61
General test support.
Definition afc.cpp:39
std::ostringstream olog
Stream used for logging.
Definition test.cpp:53
Options opt
The options.
Definition test.cpp:97