Generated on Wed Jan 1 2020 10:37:59 for Gecode by doxygen 1.8.16
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 
54 namespace 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
70  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  }
149  xs.update(*this,s.xs);
150  }
152  virtual Space* copy(void) {
153  return new OneArray(*this);
154  }
157  IntArgs a(xs.size());
158  for (int i = 0 ; i < a.size() ; ++i)
159  a[i] = xs[i].val();
160  return a;
161  }
163  virtual IntArgs* expectedSolutions(void) { return NULL; }
164  };
165 
166 #ifdef GECODE_HAS_SET_VARS
167  class OneArraySet : public Space {
169  public:
173  OneArraySet(int n, int l, int u) : xs(*this,n, IntSet::empty, l,u) {
174  }
177  xs.update(*this,s.xs);
178  }
180  virtual Space* copy(void) {
181  return new OneArraySet(*this);
182  }
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  }
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) {}
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
224  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) {}
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  }
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  }
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  }
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  }
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  }
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  }
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  }
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  }
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  }
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  }
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  }
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  }
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;
771  s << ValueSequenceSymmetry(values, 3);
772  branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
773  }
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;
807  s << ValueSequenceSymmetry(values, 3);
808  branch(home, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
809  }
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  }
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  }
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  }
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  }
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  }
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  }
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  }
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  }
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  }
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 
1104  class VarValSym1 {
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  }
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.
1156  Latin(Latin& s) : Space(s)
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  };
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  }
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  }
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  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 
1330  class SetVarSym1 {
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  }
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 
1380  class SetValSym1 {
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  }
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 
1419  class SetValSym2 {
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  }
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  }
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  }
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 
1523  class ReflectSym1 {
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  }
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 
1560  class ReflectSym2 {
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  }
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  }
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
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl)
Post constraint .
Definition: aliases.hpp:143
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Test for variable symmetry
Definition: ldsb.cpp:400
IntSetArgs solution(void)
Return the solution as IntSetArgs.
Definition: ldsb.cpp:184
LDSBSet< SetValSym1 > setvalsym1("SetValSym1")
static std::vector< IntSetArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1436
LDSB< VarSym3 > varsym3("VarSym3")
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:591
static std::vector< IntSetArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1395
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1569
Test for variable symmetry
Definition: ldsb.cpp:280
Region r
Definition: region.cpp:65
SymmetryHandle rows_interchange(const Matrix< A > &m)
Interchangeable rows symmetry specification.
Definition: ldsb.hpp:40
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:838
LDSB< VarSym1b > varsym1b("VarSym1b")
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: base.hpp:46
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
Definition: tuple-set.hpp:142
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
Definition: array.hpp:76
Combine variable selection criteria for tie-breaking.
Definition: tiebreak.hpp:38
Test for variable symmetry
Definition: ldsb.cpp:254
SymmetryHandle columns_interchange(const Matrix< A > &m)
Interchangeable columns symmetry specification.
Definition: ldsb.hpp:51
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:910
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1299
Search engine options
Definition: search.hh:746
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:96
static void setup(Home home, SetVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1339
OneArraySet(int n, int l, int u)
Constructor for creation.
Definition: ldsb.cpp:173
unsigned int c_d
Recomputation distance.
Definition: ldsb.cpp:229
Test for handling of recomputation
Definition: ldsb.cpp:1220
SymmetryHandle ValueSymmetry(IntVar x)
All values in the domain of the given variable are interchangeable.
Definition: ldsb.cpp:87
OneArray(OneArray &s)
Constructor for cloning s.
Definition: ldsb.cpp:148
Test for set variable symmetry
Definition: ldsb.cpp:1330
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:867
Passing integer variables.
Definition: int.hh:656
SymmetryHandle ValueSequenceSymmetry(const IntArgs &vs, int ss)
Value sequences in v of size ss are interchangeable.
Definition: ldsb.cpp:102
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:409
unsigned int size(I &i)
Size of all ranges of range iterator i.
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:271
static const IntSet empty
Empty set.
Definition: int.hh:283
Slice< A > row(int r) const
Access row r.
Definition: matrix.hpp:177
LDSBSet< SetVarSeqSym1 > setvarseqsym1("SetVarSeqSym1")
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:380
LDSB< SimIntVarSym1 > simintvarsym1("SimIntVarSym1")
LDSBSet(std::string label, unsigned int c=0, unsigned int a=0)
Initialize test.
Definition: ldsb.cpp:233
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:635
LDSB< ValSym1 > valsym1("ValSym1")
IntValBranch INT_VAL_MED(void)
Select greatest value not greater than the median.
Definition: val.hpp:60
Test for LDSB infrastructure with Latin square problem
Definition: ldsb.cpp:1136
LDSBSet< SetValSym2 > setvalsym2("SetValSym2", 0, 1)
OneArraySet(OneArraySet &s)
Constructor for cloning s.
Definition: ldsb.cpp:176
Test for LDSB infrastructure
Definition: ldsb.cpp:226
NodeType t
Type of node.
Definition: bool-expr.cpp:230
IntSetArgs ISA(int n,...)
Convenient way to make IntSetArgs.
Definition: ldsb.cpp:1309
Test for variable symmetry
Definition: ldsb.cpp:432
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:373
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:722
Computation spaces.
Definition: core.hpp:1742
SymmetryHandle values_reflect(const IntVar &x)
Definition: ldsb.cpp:121
SymmetryHandle rows_reflect(const Matrix< A > &m)
Reflect rows symmetry specification.
Definition: ldsb.hpp:62
void branch(Home home, const SetVarArgs &x, TieBreak< SetVarBranch > vars, SetValBranch vals, const Symmetries &syms, SetBranchFilter bf, SetVarValPrint vvp)
Branch over x with tie-breaking variable selection vars and value selection vals with symmetry breaki...
Definition: ldsb.cpp:171
bool run(void)
Perform actual tests.
Definition: ldsb.cpp:210
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:55
Depth-first search engine.
Definition: search.hh:1036
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:296
SetVarBranch SET_VAR_NONE(void)
Definition: var.hpp:96
LDSB< ValSym3 > valsym3("ValSym3")
LDSB< Action1 > action1("Action1")
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:473
Integer variable array.
Definition: int.hh:763
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:942
IntVarArray xs
Definition: ldsb.cpp:1141
Test for variable symmetry
Definition: ldsb.cpp:305
LDSB< Recomputation > recomp("Recomputation", 999, 999)
IntArgs solution(void)
Return the solution as IntArgs.
Definition: ldsb.cpp:156
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:926
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1168
LDSBSet< SetVarSeqSym2 > setvarseqsym2("SetVarSeqSym2")
LDSB< ValSym2b > valsym2b("ValSym2b")
Intersection
Definition: set.hh:663
Test for matrix symmetry
Definition: ldsb.cpp:514
LDSB< MatSym3 > matsym3("MatSym3")
Latin square space
Definition: ldsb.cpp:1139
LDSB< VarValSym1 > varvalsym1("VarValSym1")
Collection of symmetries.
Definition: int.hh:5292
union Gecode::@602::NNF::@65 u
Union depending on nodetype t.
Gecode toplevel namespace
LDSB< VarSym5 > varsym5("VarSym5")
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:289
static std::vector< IntSetArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1496
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1090
Base class for all tests to be run
Definition: test.hh:103
virtual Space * copy(void)
Copy during cloning.
Definition: ldsb.cpp:152
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:321
Test with action
Definition: ldsb.cpp:1591
Integer sets.
Definition: int.hh:174
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:745
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
Definition: search.hh:755
LDSB< VarSym1 > varsym1("VarSym1")
SymmetryHandle VariableSymmetry(const SetVarArgs &x)
Definition: ldsb.cpp:44
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:530
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1120
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
Options opt
The options.
Definition: test.cpp:97
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:628
Equality ( )
Definition: set.hh:644
LDSB< ValSym4 > valsym4("ValSym4")
LDSBSet< SetVarSym1 > setvarsym1("SetVarSym1")
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1080
Test for value sequence symmetry
Definition: ldsb.cpp:787
Home class for posting propagators
Definition: core.hpp:856
bool check(DFS< T > &e, std::vector< VarArgsType > expected)
Checks found solutions against expected solutions.
Definition: ldsb.cpp:102
SymmetryHandle columns_reflect(const Matrix< A > &m)
Reflect columns symmetry specification.
Definition: ldsb.hpp:85
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:766
Test for value symmetry
Definition: ldsb.cpp:1003
static std::vector< IntSetArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1345
SetVarArray xs
Variables.
Definition: ldsb.cpp:171
Test for reflection symmetry
Definition: ldsb.cpp:1523
Test for set value symmetry
Definition: ldsb.cpp:1380
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1057
Test for value symmetry
Definition: ldsb.cpp:901
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:663
SetValBranch SET_VAL_MIN_INC(void)
Definition: val.hpp:55
virtual IntArgs * expectedSolutions(void)
Expected solutions.
Definition: ldsb.cpp:163
static void setup(Home home, SetVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1489
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:677
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:859
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:441
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1575
LDSB< MatSym2 > matsym2("MatSym2")
Test for value symmetry
Definition: ldsb.cpp:965
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1608
LDSB< SimIntValSym3 > simintvalsym3("SimIntValSym3")
bool run(void)
Perform actual tests.
Definition: ldsb.cpp:237
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:753
LinIntExpr cardinality(const SetExpr &e)
Cardinality of set expression.
Definition: set-expr.cpp:817
unsigned int a_d
Adaptation distance.
Definition: ldsb.cpp:231
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:917
Test for matrix symmetry
Definition: ldsb.cpp:464
Latin(int n=4)
Definition: ldsb.cpp:1142
Test for set variable sequence symmetry
Definition: ldsb.cpp:1449
IntVarBranch INT_VAR_DEGREE_MAX(BranchTbl tbl)
Select variable with largest degree.
Definition: var.hpp:121
SymmetryHandle VariableSequenceSymmetry(const SetVarArgs &x, int ss)
Variable sequences in x of size ss are interchangeable.
Definition: ldsb.cpp:50
Integer variables.
Definition: int.hh:371
LDSB(std::string label, unsigned int c=0, unsigned int a=0)
Initialize test.
Definition: ldsb.cpp:206
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1049
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:811
Slice< A > slice(int fc, int tc, int fr, int tr) const
Access slice of the matrix.
Definition: matrix.hpp:171
LDSB< MatSym4 > matsym4("MatSym4")
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:974
Class represeting a set of tuples.
Definition: int.hh:2191
LDSB< ValSym1b > valsym1b("ValSym1b")
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:583
virtual Space * copy(void)
Copying member function.
Definition: ldsb.cpp:1158
LDSBLatin latin("Latin")
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:41
Test for matrix symmetry
Definition: ldsb.cpp:619
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1020
Matrix-interface for arrays.
Definition: minimodel.hh:2087
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
LDSB< ReflectSym1 > reflectsym1("ReflectSym1")
Test for value sequence symmetry
Definition: ldsb.cpp:757
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1282
static void setup(Home home, SetVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1428
OneArray(int n, int l, int u)
Constructor for creation.
Definition: ldsb.cpp:145
Test for value symmetry
Definition: ldsb.cpp:1040
LDSBLatin(std::string label)
Initialize test.
Definition: ldsb.cpp:1179
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:830
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition: linear.cpp:41
LDSB< ValSym2 > valsym2("ValSym2")
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1532
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:480
Test for reflection symmetry
Definition: ldsb.cpp:1560
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
Test for value symmetry
Definition: ldsb.cpp:876
Test for variable and value symmetry
Definition: ldsb.cpp:1104
Slice< A > col(int c) const
Access column c.
Definition: matrix.hpp:183
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:796
LDSB< ValSym5 > valsym5("ValSym5")
Test for set value symmetry
Definition: ldsb.cpp:1419
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:523
LDSB< VarSym2 > varsym2("VarSym2")
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1240
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:263
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:775
Test for value symmetry
Definition: ldsb.cpp:850
IntArgs solution(void)
Definition: ldsb.cpp:1160
Test for variable sequence symmetry
Definition: ldsb.cpp:709
unsigned int a_d
Adaptation distance.
Definition: ldsb.cpp:204
Latin(Latin &s)
Definition: ldsb.cpp:1156
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:418
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:314
Test for set variable sequence symmetry
Definition: ldsb.cpp:1480
unsigned int c_d
Recomputation distance.
Definition: ldsb.cpp:202
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:980
Test for variable symmetry
Definition: ldsb.cpp:364
Test space
Definition: ldsb.cpp:140
Test for LDSB infrastructure
Definition: ldsb.cpp:199
LDSB< SimIntValSym1 > simintvalsym1("SimIntValSym1")
General test support.
Definition: afc.cpp:39
virtual Space * copy(void)
Copy during cloning.
Definition: ldsb.cpp:180
LDSB< MatSym1 > matsym1("MatSym1")
Iterator for the greatest lower bound ranges of a set variable.
Definition: set.hh:270
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:885
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntPropLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
Test for value sequence symmetry
Definition: ldsb.cpp:821
Equality ( )
Definition: int.hh:926
LDSB< SimIntValSym2 > simintvalsym2("SimIntValSym2")
bool run(void)
Perform actual tests.
Definition: ldsb.cpp:1181
LDSB< VarSym4 > varsym4("VarSym4")
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl)
Post propagator for for all .
Definition: distinct.cpp:46
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:450
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:113
Test for matrix symmetry
Definition: ldsb.cpp:574
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
Definition: search.hh:115
LDSB< SimIntVarSym2 > simintvarsym2("SimIntVarSym2")
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1012
static const Options def
Default options.
Definition: search.hh:771
Gecode::FloatVal c(-8, 8)
Set variable array
Definition: set.hh:570
static void setup(Home home, SetVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1458
Test for value symmetry
Definition: ldsb.cpp:1071
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1113
LDSB< TieBreak > tiebreak("TieBreak")
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:935
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1600
Test space (set version)
Definition: ldsb.cpp:168
LDSB< ReflectSym2 > reflectsym2("ReflectSym2")
static void setup(Home home, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1229
Passing integer arguments.
Definition: int.hh:628
static void setup(Home home, SetVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1389
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:892
LDSB< ValSym1c > valsym1c("ValSym1c")
virtual IntSetArgs * expectedSolutions(void)
Expected solutions.
Definition: ldsb.cpp:193
Value iterator for integer sets.
Definition: int.hh:333
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1548
std::ostringstream olog
Stream used for logging.
Definition: test.cpp:53
Gecode::IntArgs i({1, 2, 3, 4})
IntVarArray xs
Variables.
Definition: ldsb.cpp:143
static std::vector< IntSetArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1468
IntVarBranch INT_VAR_MERIT_MAX(IntBranchMerit bm, BranchTbl tbl)
Select variable with highest merit according to branch merit function bm.
Definition: var.hpp:111
IntValBranch INT_VAL_MAX(void)
Select largest value.
Definition: val.hpp:65
Test for value symmetry
Definition: ldsb.cpp:926
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1013
Test for variable sequence symmetry
Definition: ldsb.cpp:654
double position(const Space &home, IntVar x, int i)
Definition: ldsb.cpp:1266
IntVarBranch INT_VAR_ACTION_MIN(double d, BranchTbl tbl)
Select variable with lowest action with decay factor d.
Definition: var.hpp:146