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