Generated on Sat Feb 7 2015 02:01:23 for Gecode by doxygen 1.8.9.1
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: 2013-07-05 15:44:26 +0200 (Fri, 05 Jul 2013) $ by $Author: schulte $
11  * $Revision: 13814 $
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  }
151  OneArray(bool share, OneArray& s) : Space(share,s) {
152  xs.update(*this,share,s.xs);
153  }
155  virtual Space* copy(bool share) {
156  return new OneArray(share,*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  }
179  OneArraySet(bool share, OneArraySet& s) : Space(share,s) {
180  xs.update(*this,share,s.xs);
181  }
183  virtual Space* copy(bool share) {
184  return new OneArraySet(share,*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 h, IntVarArray& xs) {
267  Symmetries syms;
268  IntArgs indices(4, 0,1,2,3);
269  syms << VariableSymmetry(xs, indices);
270  distinct(h, xs);
271  branch(h, 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 h, IntVarArray& xs) {
293  distinct(h, xs);
294  Symmetries syms;
295  syms << VariableSymmetry(xs);
296  branch(h, 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 h, IntVarArray& xs) {
318  Symmetries syms;
319  IntArgs indices(4, 0,1,2,3);
320  syms << VariableSymmetry(xs);
321  branch(h, 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 h, IntVarArray& xs) {
377  Symmetries syms;
378  distinct(h, xs);
379  syms << VariableSymmetry(IntVarArgs() << xs[0] << xs[1]);
380  branch(h, 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 h, IntVarArray& xs) {
413  distinct(h, xs);
414  Symmetries s;
415  IntVarArgs symvars;
416  symvars << xs[0];
417  s << VariableSymmetry(symvars);
418  branch(h, 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 h, IntVarArray& xs) {
445  distinct(h, 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(h, 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 h, IntVarArray& xs) {
477  Matrix<IntVarArray> m(xs, 2, 3);
478  Symmetries s;
479  s << rows_interchange(m);
480  branch(h, 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 h, IntVarArray& xs) {
527  Matrix<IntVarArray> m(xs, 2, 3);
528  Symmetries s;
529  s << columns_interchange(m);
530  branch(h, 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 h, IntVarArray& xs) {
587  Matrix<IntVarArray> m(xs, 2, 3);
588  Symmetries s;
589  s << rows_interchange(m);
590  s << columns_interchange(m);
591  branch(h, 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 h, IntVarArray& xs) {
632  Matrix<IntVarArray> m(xs, 1, 4);
633  Symmetries s;
634  s << rows_reflect(m);
635  branch(h, 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 h, IntVarArray& xs) {
667  Matrix<IntVarArray> m(xs, 3, 4);
668  // The values in the first column are distinct.
669  distinct(h, m.col(0));
670  // Each row sums to 3.
671  for (int i = 0 ; i < 4 ; ++i)
672  linear(h, m.row(i), IRT_EQ, 3);
673 
674  // Rows are interchangeable.
675  Symmetries s;
676  s << VariableSequenceSymmetry(xs, 3);
677  branch(h, 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 h, IntVarArray& xs) {
726  Matrix<IntVarArray> m(xs, 3, 4);
727  // The values in the first column are distinct.
728  distinct(h, m.col(0));
729  // Each row sums to 3.
730  for (int i = 0 ; i < nrows ; ++i)
731  linear(h, 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(h, 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 h, IntVarArray& xs) {
770  rel(h, 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(h, 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 h, IntVarArray& xs) {
800  TupleSet tuples;
801  tuples.add(IntArgs(3, 1,1,1));
802  tuples.add(IntArgs(3, 4,4,4));
803  tuples.add(IntArgs(3, 7,7,7));
804  tuples.add(IntArgs(3, 0,1,5));
805  tuples.add(IntArgs(3, 0,1,8));
806  tuples.add(IntArgs(3, 3,4,2));
807  tuples.add(IntArgs(3, 3,4,8));
808  tuples.add(IntArgs(3, 6,7,2));
809  tuples.add(IntArgs(3, 6,7,5));
810  tuples.finalize();
811  extensional(h, xs, tuples);
812 
813  // Values 0,1,2 are symmetric with 3,4,5, and with 6,7,8.
814  IntArgs values(9, 0,1,2, 3,4,5, 6,7,8);
815  Symmetries s;
816  s << ValueSequenceSymmetry(values, 3);
817  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
818  }
820  static std::vector<IntArgs> expectedSolutions(void) {
821  static std::vector<IntArgs> expected;
822  expected.clear();
823  expected.push_back(IntArgs(3, 0,1,5));
824  expected.push_back(IntArgs(3, 1,1,1));
825  return expected;
826  }
827  };
828 
831  public:
833  static const int n = 2;
835  static const int l = 0;
837  static const int u = 6;
839  static void setup(Home h, IntVarArray& xs) {
840  rel(h, xs[0] + xs[1] == 6);
841  Symmetries s;
842  // Values 0,1,2 are symmetric with 6,5,4.
843  s << values_reflect(0,6);
844  branch(h, xs, INT_VAR_NONE(), INT_VAL_MED(), s);
845  }
847  static std::vector<IntArgs> expectedSolutions(void) {
848  static std::vector<IntArgs> expected;
849  expected.clear();
850  expected.push_back(IntArgs(2, 3,3));
851  expected.push_back(IntArgs(2, 2,4));
852  expected.push_back(IntArgs(2, 1,5));
853  expected.push_back(IntArgs(2, 0,6));
854  return expected;
855  }
856  };
857 
859  class ValSym1 {
860  public:
862  static const int n = 4;
864  static const int l = 0;
866  static const int u = 3;
868  static void setup(Home h, IntVarArray& xs) {
869  distinct(h, xs);
870  Symmetries s;
871  IntArgs indices(4, 0,1,2,3);
872  s << ValueSymmetry(indices);
873  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
874  }
876  static std::vector<IntArgs> expectedSolutions(void) {
877  static std::vector<IntArgs> expected;
878  expected.clear();
879  expected.push_back(IntArgs(4, 0,1,2,3));
880  return expected;
881  }
882  };
883 
885  class ValSym1b {
886  public:
888  static const int n = 4;
890  static const int l = 0;
892  static const int u = 3;
894  static void setup(Home h, IntVarArray& xs) {
895  distinct(h, xs);
896  Symmetries s;
897  s << ValueSymmetry(xs[0]);
898  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
899  }
901  static std::vector<IntArgs> expectedSolutions(void) {
902  static std::vector<IntArgs> expected;
903  expected.clear();
904  expected.push_back(IntArgs(4, 0,1,2,3));
905  return expected;
906  }
907  };
908 
910  class ValSym1c {
911  public:
913  static const int n = 4;
915  static const int l = 0;
917  static const int u = 3;
919  static void setup(Home h, IntVarArray& xs) {
920  distinct(h, xs);
921  Symmetries s;
922  s << ValueSymmetry(xs[0]);
923  branch(h, xs, INT_VAR_NONE(), INT_VAL_MAX(), s);
924  }
926  static std::vector<IntArgs> expectedSolutions(void) {
927  static std::vector<IntArgs> expected;
928  expected.clear();
929  expected.push_back(IntArgs(4, 3,2,1,0));
930  return expected;
931  }
932  };
933 
935  class ValSym2 {
936  public:
938  static const int n = 4;
940  static const int l = 0;
942  static const int u = 3;
944  static void setup(Home h, IntVarArray& xs) {
945  Symmetries s;
946  IntArgs indices(4, 0,1,2,3);
947  s << ValueSymmetry(indices);
948  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
949  }
951  static std::vector<IntArgs> expectedSolutions(void) {
952  static std::vector<IntArgs> expected;
953  expected.clear();
954  expected.push_back(IntArgs(4, 0,0,0,0));
955  expected.push_back(IntArgs(4, 0,0,0,1));
956  expected.push_back(IntArgs(4, 0,0,1,0));
957  expected.push_back(IntArgs(4, 0,0,1,1));
958  expected.push_back(IntArgs(4, 0,0,1,2));
959  expected.push_back(IntArgs(4, 0,1,0,0));
960  expected.push_back(IntArgs(4, 0,1,0,1));
961  expected.push_back(IntArgs(4, 0,1,0,2));
962  expected.push_back(IntArgs(4, 0,1,1,0));
963  expected.push_back(IntArgs(4, 0,1,1,1));
964  expected.push_back(IntArgs(4, 0,1,1,2));
965  expected.push_back(IntArgs(4, 0,1,2,0));
966  expected.push_back(IntArgs(4, 0,1,2,1));
967  expected.push_back(IntArgs(4, 0,1,2,2));
968  expected.push_back(IntArgs(4, 0,1,2,3));
969  return expected;
970  }
971  };
972 
974  class ValSym2b {
975  public:
977  static const int n = 4;
979  static const int l = 0;
981  static const int u = 3;
983  static void setup(Home h, IntVarArray& xs) {
984  Symmetries s;
985  s << ValueSymmetry(xs[0]);
986  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
987  }
989  static std::vector<IntArgs> expectedSolutions(void) {
990  static std::vector<IntArgs> expected;
991  expected.clear();
992  expected.push_back(IntArgs(4, 0,0,0,0));
993  expected.push_back(IntArgs(4, 0,0,0,1));
994  expected.push_back(IntArgs(4, 0,0,1,0));
995  expected.push_back(IntArgs(4, 0,0,1,1));
996  expected.push_back(IntArgs(4, 0,0,1,2));
997  expected.push_back(IntArgs(4, 0,1,0,0));
998  expected.push_back(IntArgs(4, 0,1,0,1));
999  expected.push_back(IntArgs(4, 0,1,0,2));
1000  expected.push_back(IntArgs(4, 0,1,1,0));
1001  expected.push_back(IntArgs(4, 0,1,1,1));
1002  expected.push_back(IntArgs(4, 0,1,1,2));
1003  expected.push_back(IntArgs(4, 0,1,2,0));
1004  expected.push_back(IntArgs(4, 0,1,2,1));
1005  expected.push_back(IntArgs(4, 0,1,2,2));
1006  expected.push_back(IntArgs(4, 0,1,2,3));
1007  return expected;
1008  }
1009  };
1010 
1012  class ValSym3 {
1013  public:
1015  static const int n = 4;
1017  static const int l = 0;
1019  static const int u = 3;
1021  static void setup(Home h, IntVarArray& xs) {
1022  distinct(h, xs);
1023  Symmetries s;
1024  IntArgs indices(2, 0,1);
1025  s << ValueSymmetry(indices);
1026  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
1027  }
1029  static std::vector<IntArgs> expectedSolutions(void) {
1030  static std::vector<IntArgs> expected;
1031  expected.clear();
1032  expected.push_back(IntArgs(4, 0,1,2,3));
1033  expected.push_back(IntArgs(4, 0,1,3,2));
1034  expected.push_back(IntArgs(4, 0,2,1,3));
1035  expected.push_back(IntArgs(4, 0,2,3,1));
1036  expected.push_back(IntArgs(4, 0,3,1,2));
1037  expected.push_back(IntArgs(4, 0,3,2,1));
1038  expected.push_back(IntArgs(4, 2,0,1,3));
1039  expected.push_back(IntArgs(4, 2,0,3,1));
1040  expected.push_back(IntArgs(4, 2,3,0,1));
1041  expected.push_back(IntArgs(4, 3,0,1,2));
1042  expected.push_back(IntArgs(4, 3,0,2,1));
1043  expected.push_back(IntArgs(4, 3,2,0,1));
1044  return expected;
1045  }
1046  };
1047 
1049  class ValSym4 {
1050  public:
1052  static const int n = 3;
1054  static const int l = 0;
1056  static const int u = 2;
1058  static void setup(Home h, IntVarArray& xs) {
1059  distinct(h, xs);
1060  Symmetries s;
1061  IntArgs indices(1, 0);
1062  s << ValueSymmetry(indices);
1063  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
1064  }
1066  static std::vector<IntArgs> expectedSolutions(void) {
1067  static std::vector<IntArgs> expected;
1068  expected.clear();
1069  expected.push_back(IntArgs(3, 0,1,2));
1070  expected.push_back(IntArgs(3, 0,2,1));
1071  expected.push_back(IntArgs(3, 1,0,2));
1072  expected.push_back(IntArgs(3, 1,2,0));
1073  expected.push_back(IntArgs(3, 2,0,1));
1074  expected.push_back(IntArgs(3, 2,1,0));
1075  return expected;
1076  }
1077  };
1078 
1080  class ValSym5 {
1081  public:
1083  static const int n = 4;
1085  static const int l = 0;
1087  static const int u = 3;
1089  static void setup(Home h, IntVarArray& xs) {
1090  distinct(h, xs);
1091  Symmetries s;
1092  IntArgs indices0(2, 0,1);
1093  IntArgs indices1(2, 2,3);
1094  s << ValueSymmetry(indices0);
1095  s << ValueSymmetry(indices1);
1096  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
1097  }
1099  static std::vector<IntArgs> expectedSolutions(void) {
1100  static std::vector<IntArgs> expected;
1101  expected.clear();
1102  expected.push_back(IntArgs(4, 0,1,2,3));
1103  expected.push_back(IntArgs(4, 0,2,1,3));
1104  expected.push_back(IntArgs(4, 0,2,3,1));
1105  expected.push_back(IntArgs(4, 2,0,1,3));
1106  expected.push_back(IntArgs(4, 2,0,3,1));
1107  expected.push_back(IntArgs(4, 2,3,0,1));
1108  return expected;
1109  }
1110  };
1111 
1113  class VarValSym1 {
1114  public:
1116  static const int n = 4;
1118  static const int l = 0;
1120  static const int u = 3;
1122  static void setup(Home h, IntVarArray& xs) {
1123  Symmetries s;
1124  s << VariableSymmetry(xs);
1125  s << ValueSymmetry(IntArgs::create(4,0));
1126  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
1127  }
1129  static std::vector<IntArgs> expectedSolutions(void) {
1130  static std::vector<IntArgs> expected;
1131  expected.clear();
1132  expected.push_back(IntArgs(4, 0,0,0,0));
1133  expected.push_back(IntArgs(4, 0,0,0,1));
1134  expected.push_back(IntArgs(4, 0,0,1,1));
1135  expected.push_back(IntArgs(4, 0,0,1,2));
1136  expected.push_back(IntArgs(4, 0,1,1,1));
1137  expected.push_back(IntArgs(4, 0,1,1,2));
1138  expected.push_back(IntArgs(4, 0,1,2,2)); // This solution is symmetric to the previous one.
1139  expected.push_back(IntArgs(4, 0,1,2,3));
1140  return expected;
1141  }
1142  };
1143 
1145  class LDSBLatin : public Base {
1146  public:
1148  class Latin : public Space {
1149  public:
1151  Latin(int n = 4) : xs(*this, n*n, 1, n)
1152  {
1153  Matrix<IntVarArray> m(xs, n, n);
1154  for (int i = 0 ; i < n ; i++) {
1155  distinct(*this, m.col(i));
1156  distinct(*this, m.row(i));
1157  }
1158  Symmetries s;
1159  s << rows_interchange(m);
1160  s << columns_interchange(m);
1161  s << ValueSymmetry(IntSet(1,n));
1162  branch(*this, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
1163  }
1164  // Search support.
1165  Latin(bool share, Latin& s) : Space(share, s)
1166  { xs.update(*this, share, s.xs); }
1167  virtual Space* copy(bool share)
1168  { return new Latin(share,*this); }
1170  IntArgs a(xs.size());
1171  for (int i = 0 ; i < a.size() ; ++i)
1172  a[i] = xs[i].val();
1173  return a;
1174  }
1175 
1177  static std::vector<IntArgs> expectedSolutions(void) {
1178  static std::vector<IntArgs> expected;
1179  expected.clear();
1180  expected.push_back(IntArgs(16, 1,2,3,4, 2,1,4,3, 3,4,1,2, 4,3,2,1));
1181  expected.push_back(IntArgs(16, 1,2,3,4, 2,1,4,3, 3,4,2,1, 4,3,1,2));
1182  expected.push_back(IntArgs(16, 1,2,3,4, 2,3,4,1, 3,4,1,2, 4,1,2,3));
1183  expected.push_back(IntArgs(16, 1,2,3,4, 2,4,1,3, 3,1,4,2, 4,3,2,1));
1184  return expected;
1185  }
1186  };
1188  LDSBLatin(std::string label) : Test::Base("LDSB::" + label) {}
1190  bool run(void) {
1191  Latin *s = new Latin();
1192  DFS<Latin> e(s);
1193  bool r = check(e, Latin::expectedSolutions());
1194  delete s;
1195  return r;
1196  }
1197  };
1198 
1199  /* This test should fail if the recomputation-handling does not work
1200  * properly.
1201  *
1202  * Why recomputation can be a problem
1203  * ==================================
1204  *
1205  * Every branch point in LDSB is binary, with a left and a right
1206  * branch. Whenever backtracking happens -- when a right branch is
1207  * explored -- LDSB computes a set of symmetric literals to
1208  * exclude.
1209  *
1210  * !!! This calculation may depend on the current domains of the
1211  * !!! variables.
1212  *
1213  * During recomputation, parts of the search tree are replayed. To
1214  * be specific, the branching constraints are posted, but no
1215  * propagation happens. This means that at a given branch point,
1216  * the domains during recomputation may be different (weaker) than
1217  * they were the first time during search.
1218  *
1219  * !!! This *cannot* cause solutions to be missed --- LDSB will not
1220  * !!! be incorrect --- but it *does* change what will be pruned.
1221  *
1222  * If recomputation is not handled properly, the difference in
1223  * domains will cause extra solutions to be found. This is a result
1224  * of symmetries failing to be broken.
1225  *
1226  */
1227 
1230  public:
1232  static const int n = 4;
1234  static const int l = 0;
1236  static const int u = 1;
1238  static void setup(Home h, IntVarArray& xs) {
1239  TupleSet t;
1240  t.add(IntArgs(2, 0,0));
1241  t.add(IntArgs(2, 1,1));
1242  t.finalize();
1243  IntVarArgs va;
1244  va << xs[0] << xs[2];
1245  extensional(h, va, t);
1246  Symmetries syms;
1247  syms << VariableSequenceSymmetry(xs, 2);
1248  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), syms);
1249  }
1251  static std::vector<IntArgs> expectedSolutions(void) {
1252  static std::vector<IntArgs> expected;
1253  expected.clear();
1254  expected.push_back(IntArgs(4, 0,0,0,0));
1255  expected.push_back(IntArgs(4, 0,0,0,1));
1256 
1257  // This is the solution that will be found if recomputation is
1258  // not handled. After branching on x[0]=0, we try x[1]=0. When
1259  // x[1]=0 backtracks, the symmetry [x[0],x[1]] <-> [x[2],x[3]]
1260  // is active --- but only after propagation! (Without
1261  // propagation, we do not have x[2]=0.) If propagation happens,
1262  // we know that symmetry is active and we can post x[3]!=0. If
1263  // it doesn't, we don't use the symmetry and we find a solution
1264  // where x[3]=0.
1265 
1266  // expected.push_back(IntArgs(4, 0,1,0,0));
1267 
1268  expected.push_back(IntArgs(4, 0,1,0,1));
1269 
1270  expected.push_back(IntArgs(4, 1,0,1,0));
1271  expected.push_back(IntArgs(4, 1,0,1,1));
1272  expected.push_back(IntArgs(4, 1,1,1,1));
1273  return expected;
1274  }
1275  };
1276 
1277  double position(const Space& home, IntVar x, int i) {
1278  (void) home;
1279  (void) x;
1280  return i;
1281  }
1282 
1284  class TieBreak {
1285  public:
1287  static const int n = 4;
1289  static const int l = 0;
1291  static const int u = 3;
1293  static void setup(Home h, IntVarArray& xs) {
1294  Symmetries syms;
1295  IntArgs indices(4, 0,1,2,3);
1296  syms << VariableSymmetry(xs, indices);
1297  distinct(h, xs);
1298  // This redundant constraint is to trick the variable
1299  // heuristic.
1300  rel(h, xs[1] != xs[2]);
1301  // xs[1] and xs[2] have higher degree than the others, so they
1302  // are considered first. xs[2] is higher than x[1] by the merit
1303  // function, so it is assigned first. Now all remaining
1304  // variables have the same degree, so they are searched in
1305  // reverse order (according to the merit function). So, the
1306  // solution found is {3, 2, 0, 1}.
1308  }
1310  static std::vector<IntArgs> expectedSolutions(void) {
1311  static std::vector<IntArgs> expected;
1312  expected.clear();
1313  expected.push_back(IntArgs(4, 3,2,0,1));
1314  return expected;
1315  }
1316  };
1317 
1318 #ifdef GECODE_HAS_SET_VARS
1319  IntSetArgs ISA(int n, ...) {
1321  IntSetArgs sets;
1322  va_list args;
1323  va_start(args, n);
1324  int i = 0;
1325  IntArgs a;
1326  while (i < n) {
1327  int x = va_arg(args,int);
1328  if (x == -1) {
1329  i++;
1330  sets << IntSet(a);
1331  a = IntArgs();
1332  } else {
1333  a << x;
1334  }
1335  }
1336  va_end(args);
1337  return sets;
1338  }
1339 
1341  class SetVarSym1 {
1342  public:
1344  static const int n = 2;
1346  static const int l = 0;
1348  static const int u = 1;
1350  static void setup(Home h, SetVarArray& xs) {
1351  Symmetries syms;
1352  syms << VariableSymmetry(xs);
1353  branch(h, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
1354  }
1356  static std::vector<IntSetArgs> expectedSolutions(void) {
1357  static std::vector<IntSetArgs> expected;
1358  expected.clear();
1359  expected.push_back(ISA(2, 0,1,-1, 0,1,-1));
1360  expected.push_back(ISA(2, 0,1,-1, 0, -1));
1361  expected.push_back(ISA(2, 0,1,-1, 1,-1));
1362  expected.push_back(ISA(2, 0,1,-1, -1));
1363  expected.push_back(ISA(2, 0, -1, 0,1,-1));
1364  expected.push_back(ISA(2, 0, -1, 0, -1));
1365  expected.push_back(ISA(2, 0, -1, 1,-1));
1366  expected.push_back(ISA(2, 0, -1, -1));
1367  // expected.push_back(ISA(2, 1,-1, 0,1,-1));
1368  // expected.push_back(ISA(2, 1,-1, 0, -1));
1369  expected.push_back(ISA(2, 1,-1, 1,-1));
1370  expected.push_back(ISA(2, 1,-1, -1));
1371  // expected.push_back(ISA(2, -1, 0,1,-1));
1372  // expected.push_back(ISA(2, -1, 0, -1));
1373  // expected.push_back(ISA(2, -1, 1,-1));
1374  expected.push_back(ISA(2, -1, -1));
1375  return expected;
1376  }
1377  };
1378 
1379  /*
1380  * This tests the special handling of value symmetries on set
1381  * values. Look at the third solution (commented out) below. The
1382  * first variable has been assigned to {0,1}. If the value symmetry
1383  * is not handled specially, then we will consider the value
1384  * symmetry broken because the search has touched each value.
1385  * However, because both values have been assigned to the same
1386  * variable, 0 and 1 are still symmetric. Therefore, the third
1387  * solution is symmetric to the second one and should be excluded.
1388  */
1389 
1391  class SetValSym1 {
1392  public:
1394  static const int n = 2;
1396  static const int l = 0;
1398  static const int u = 1;
1400  static void setup(Home h, SetVarArray& xs) {
1401  Symmetries syms;
1402  syms << ValueSymmetry(IntArgs(2, 0,1));
1403  branch(h, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
1404  }
1406  static std::vector<IntSetArgs> expectedSolutions(void) {
1407  static std::vector<IntSetArgs> expected;
1408  expected.clear();
1409  expected.push_back(ISA(2, 0,1,-1, 0,1,-1));
1410  expected.push_back(ISA(2, 0,1,-1, 0, -1));
1411  // expected.push_back(ISA(2, 0,1,-1, 1,-1)); // XXXXX bad solution
1412  expected.push_back(ISA(2, 0,1,-1, -1));
1413  expected.push_back(ISA(2, 0, -1, 0,1,-1));
1414  expected.push_back(ISA(2, 0, -1, 0, -1));
1415  expected.push_back(ISA(2, 0, -1, 1,-1));
1416  expected.push_back(ISA(2, 0, -1, -1));
1417  // expected.push_back(ISA(2, 1,-1, 0,1,-1));
1418  // expected.push_back(ISA(2, 1,-1, 0, -1));
1419  // expected.push_back(ISA(2, 1,-1, 1,-1));
1420  // expected.push_back(ISA(2, 1,-1, -1));
1421  expected.push_back(ISA(2, -1, 0,1,-1));
1422  expected.push_back(ISA(2, -1, 0, -1));
1423  // expected.push_back(ISA(2, -1, 1,-1));
1424  expected.push_back(ISA(2, -1, -1));
1425  return expected;
1426  }
1427  };
1428 
1430  class SetValSym2 {
1431  public:
1433  static const int n = 3;
1435  static const int l = 1;
1437  static const int u = 4;
1439  static void setup(Home h, SetVarArray& xs) {
1440  Symmetries syms;
1441  syms << ValueSymmetry(IntArgs(4, 1,2,3,4));
1442  for (int i = 0 ; i < 3 ; i++)
1443  cardinality(h, xs[i], 1, 1);
1444  branch(h, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
1445  }
1447  static std::vector<IntSetArgs> expectedSolutions(void) {
1448  static std::vector<IntSetArgs> expected;
1449  expected.clear();
1450  expected.push_back(ISA(3, 1,-1, 1,-1, 1,-1));
1451  expected.push_back(ISA(3, 1,-1, 1,-1, 2,-1));
1452  expected.push_back(ISA(3, 1,-1, 2,-1, 1,-1));
1453  expected.push_back(ISA(3, 1,-1, 2,-1, 2,-1));
1454  expected.push_back(ISA(3, 1,-1, 2,-1, 3,-1));
1455  return expected;
1456  }
1457  };
1458 
1461  public:
1463  static const int n = 4;
1465  static const int l = 0;
1467  static const int u = 1;
1469  static void setup(Home h, SetVarArray& xs) {
1470  Symmetries syms;
1471  syms << VariableSequenceSymmetry(xs,2);
1472  rel(h, xs[0], SOT_INTER, xs[1], SRT_EQ, IntSet::empty);
1473  rel(h, xs[2], SOT_INTER, xs[3], SRT_EQ, IntSet::empty);
1474  for (int i = 0 ; i < 4 ; i++)
1475  cardinality(h, xs[i], 1, 1);
1476  branch(h, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
1477  }
1479  static std::vector<IntSetArgs> expectedSolutions(void) {
1480  static std::vector<IntSetArgs> expected;
1481  expected.clear();
1482  expected.push_back(ISA(4, 0,-1, 1,-1, 0,-1, 1,-1));
1483  expected.push_back(ISA(4, 0,-1, 1,-1, 1,-1, 0,-1));
1484  // expected.push_back(ISA(4, 1,-1, 0,-1, 0,-1, 1,-1));
1485  expected.push_back(ISA(4, 1,-1, 0,-1, 1,-1, 0,-1));
1486  return expected;
1487  }
1488  };
1489 
1492  public:
1494  static const int n = 4;
1496  static const int l = 0;
1498  static const int u = 0;
1500  static void setup(Home h, SetVarArray& xs) {
1501  Symmetries syms;
1502  syms << VariableSequenceSymmetry(xs,2);
1503  rel(h, xs[0], SRT_EQ, xs[2]);
1504  branch(h, xs, SET_VAR_NONE(), SET_VAL_MIN_INC(), syms);
1505  }
1507  static std::vector<IntSetArgs> expectedSolutions(void) {
1508  static std::vector<IntSetArgs> expected;
1509  expected.clear();
1510 
1511  // Symmetric solutions are commented out.
1512  expected.push_back(ISA(4, 0, -1,0,-1,0,-1,0,-1));
1513  expected.push_back(ISA(4, 0, -1,0,-1,0,-1, -1));
1514  // expected.push_back(ISA(4, 0, -1,0,-1, -1,0,-1));
1515  // expected.push_back(ISA(4, 0, -1,0,-1, -1, -1));
1516  // expected.push_back(ISA(4, 0, -1, -1,0,-1,0,-1));
1517  expected.push_back(ISA(4, 0, -1, -1,0,-1, -1));
1518  // expected.push_back(ISA(4, 0, -1, -1, -1,0,-1));
1519  // expected.push_back(ISA(4, 0, -1, -1, -1, -1));
1520  // expected.push_back(ISA(4, -1,0,-1,0,-1,0,-1));
1521  // expected.push_back(ISA(4, -1,0,-1,0,-1, -1));
1522  expected.push_back(ISA(4, -1,0,-1, -1,0,-1));
1523  expected.push_back(ISA(4, -1,0,-1, -1, -1));
1524  // expected.push_back(ISA(4, -1, -1,0,-1,0,-1));
1525  // expected.push_back(ISA(4, -1, -1,0,-1, -1));
1526  // expected.push_back(ISA(4, -1, -1, -1,0,-1));
1527  expected.push_back(ISA(4, -1, -1, -1, -1));
1528 
1529  return expected;
1530  }
1531  };
1532 
1534  class ReflectSym1 {
1535  public:
1537  static const int n = 6;
1539  static const int l = 0;
1541  static const int u = 6;
1543  static void setup(Home h, IntVarArray& xs) {
1544  Matrix<IntVarArray> m(xs, 3, 2);
1545 
1546  distinct(h, xs);
1547  rel(h, abs(m(0,0)-m(1,0))==1);
1548  rel(h, abs(m(0,1)-m(1,1))==1);
1549  rel(h, abs(m(1,0)-m(2,0))==1);
1550  rel(h, abs(m(1,1)-m(2,1))==1);
1551 
1552  Symmetries s;
1553  s << values_reflect(l, u);
1554  s << rows_interchange(m);
1555  s << columns_reflect(m);
1556  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
1557  }
1559  static std::vector<IntArgs> expectedSolutions(void) {
1560  static std::vector<IntArgs> expected;
1561  expected.clear();
1562  expected.push_back(IntArgs(6, 0,1,2,3,4,5));
1563  expected.push_back(IntArgs(6, 0,1,2,4,5,6));
1564  expected.push_back(IntArgs(6, 0,1,2,5,4,3));
1565  expected.push_back(IntArgs(6, 0,1,2,6,5,4));
1566  return expected;
1567  }
1568  };
1569 
1571  class ReflectSym2 {
1572  public:
1574  static const int n = 2;
1576  static const int l = 0;
1578  static const int u = 3;
1580  static void setup(Home h, IntVarArray& xs) {
1581  Symmetries s;
1582  s << values_reflect(l, u);
1583  branch(h, xs, INT_VAR_NONE(), INT_VAL_MIN(), s);
1584  }
1586  static std::vector<IntArgs> expectedSolutions(void) {
1587  static std::vector<IntArgs> expected;
1588  expected.clear();
1589  expected.push_back(IntArgs(2, 0,0));
1590  expected.push_back(IntArgs(2, 0,1));
1591  expected.push_back(IntArgs(2, 0,2));
1592  expected.push_back(IntArgs(2, 0,3));
1593  expected.push_back(IntArgs(2, 1,0));
1594  expected.push_back(IntArgs(2, 1,1));
1595  expected.push_back(IntArgs(2, 1,2));
1596  expected.push_back(IntArgs(2, 1,3));
1597  return expected;
1598  }
1599  };
1600 
1602  class Activity1 {
1603  public:
1605  static const int n = 4;
1607  static const int l = 0;
1609  static const int u = 3;
1611  static void setup(Home h, IntVarArray& xs) {
1612  distinct(h, xs);
1613  Symmetries s;
1614  s << VariableSymmetry(xs);
1615  s << ValueSymmetry(IntArgs::create(4,0));
1616  branch(h, xs, INT_VAR_ACTIVITY_MIN(0.8), INT_VAL_MIN(), s);
1617  }
1619  static std::vector<IntArgs> expectedSolutions(void) {
1620  static std::vector<IntArgs> expected;
1621  expected.clear();
1622  expected.push_back(IntArgs(4, 0,1,2,3));
1623  return expected;
1624  }
1625  };
1626 
1627 #endif
1628 
1629  LDSB<VarSym1> varsym1("VarSym1");
1630  LDSB<VarSym1b> varsym1b("VarSym1b");
1631  LDSB<VarSym2> varsym2("VarSym2");
1632  LDSB<VarSym3> varsym3("VarSym3");
1633  LDSB<VarSym4> varsym4("VarSym4");
1634  LDSB<VarSym5> varsym5("VarSym5");
1635  LDSB<MatSym1> matsym1("MatSym1");
1636  LDSB<MatSym2> matsym2("MatSym2");
1637  LDSB<MatSym3> matsym3("MatSym3");
1638  LDSB<MatSym4> matsym4("MatSym4");
1639  LDSB<SimIntVarSym1> simintvarsym1("SimIntVarSym1");
1640  LDSB<SimIntVarSym2> simintvarsym2("SimIntVarSym2");
1641  LDSB<SimIntValSym1> simintvalsym1("SimIntValSym1");
1642  LDSB<SimIntValSym2> simintvalsym2("SimIntValSym2");
1643  LDSB<SimIntValSym3> simintvalsym3("SimIntValSym3");
1644  LDSB<ValSym1> valsym1("ValSym1");
1645  LDSB<ValSym1b> valsym1b("ValSym1b");
1646  LDSB<ValSym1c> valsym1c("ValSym1c");
1647  LDSB<ValSym2> valsym2("ValSym2");
1648  LDSB<ValSym2b> valsym2b("ValSym2b");
1649  LDSB<ValSym3> valsym3("ValSym3");
1650  LDSB<ValSym4> valsym4("ValSym4");
1651  LDSB<ValSym5> valsym5("ValSym5");
1652  LDSB<VarValSym1> varvalsym1("VarValSym1");
1653  LDSBLatin latin("Latin");
1654  LDSB<Recomputation> recomp("Recomputation", 999,999);
1655  LDSB<TieBreak> tiebreak("TieBreak");
1656 
1657 #ifdef GECODE_HAS_SET_VARS
1658  LDSB<ReflectSym1> reflectsym1("ReflectSym1");
1659  LDSB<ReflectSym2> reflectsym2("ReflectSym2");
1660  LDSB<Activity1> activity1("Activity1");
1661 
1662  LDSBSet<SetVarSym1> setvarsym1("SetVarSym1");
1663  LDSBSet<SetValSym1> setvalsym1("SetValSym1");
1664  LDSBSet<SetValSym2> setvalsym2("SetValSym2", 0, 1);
1665  LDSBSet<SetVarSeqSym1> setvarseqsym1("SetVarSeqSym1");
1666  LDSBSet<SetVarSeqSym2> setvarseqsym2("SetVarSeqSym2");
1667 #endif
1668 }}
1669 
1670 // 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:213
virtual Space * copy(bool share)
Copy during cloning.
Definition: ldsb.cpp:155
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
SymmetryHandle VariableSequenceSymmetry(const SetVarArgs &x, int ss)
Variable sequences in x of size ss are interchangeable.
Definition: ldsb.cpp:54
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
static void setup(Home h, SetVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1350
Test for matrix symmetry
Definition: ldsb.cpp:517
LDSB< ReflectSym2 > reflectsym2("ReflectSym2")
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:799
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1619
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:769
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:894
Test for set value symmetry
Definition: ldsb.cpp:1391
NodeType t
Type of node.
Definition: bool-expr.cpp:234
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:108
Combine variable selection criteria for tie-breaking.
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:266
IntVarBranch INT_VAR_MERIT_MAX(IntBranchMerit bm, BranchTbl tbl)
Select variable with highest merit according to branch merit function bm.
Definition: var.hpp:130
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatNum c)
Post propagator for .
Definition: linear.cpp:45
void finalize(void)
Finalize tuple set.
Definition: tuple-set.hpp:111
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
LDSB< VarSym2 > varsym2("VarSym2")
SetVarBranch SET_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:91
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:847
IntVarArray xs
Variables.
Definition: ldsb.cpp:146
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1543
static std::vector< IntSetArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1479
IntSetArgs ISA(int n,...)
Convenient way to make IntSetArgs.
Definition: ldsb.cpp:1320
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
static void setup(Home h, SetVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1439
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1021
virtual Space * copy(bool share)
Copying member function.
Definition: ldsb.cpp:1167
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:211
Search engine options
Definition: search.hh:204
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:49
static void setup(Home h, SetVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1469
Test for value symmetry
Definition: ldsb.cpp:1049
Test for value sequence symmetry
Definition: ldsb.cpp:760
Test for variable symmetry
Definition: ldsb.cpp:283
LDSB< MatSym2 > matsym2("MatSym2")
LDSBLatin(std::string label)
Initialize test.
Definition: ldsb.cpp:1188
SetValBranch SET_VAL_MIN_INC(void)
Include smallest element.
Definition: val.hpp:59
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
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:944
Collection of symmetries.
Definition: int.hh:4300
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:919
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1099
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:1148
Integer variable array.
Definition: int.hh:741
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:951
LDSB< VarSym5 > varsym5("VarSym5")
Test for matrix symmetry
Definition: ldsb.cpp:467
SymmetryHandle VariableSymmetry(const SetVarArgs &x)
Variables in x are interchangeable.
Definition: ldsb.cpp:48
Test for value symmetry
Definition: ldsb.cpp:859
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:533
Test for set variable sequence symmetry
Definition: ldsb.cpp:1460
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:1430
Test for variable and value symmetry
Definition: ldsb.cpp:1113
LDSB< ValSym1c > valsym1c("ValSym1c")
LDSB< VarSym3 > varsym3("VarSym3")
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:666
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1580
Test for variable sequence symmetry
Definition: ldsb.cpp:657
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:876
LDSB< Activity1 > activity1("Activity1")
Test for value symmetry
Definition: ldsb.cpp:974
Computation spaces.
Definition: core.hpp:1362
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1122
static std::vector< IntSetArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1356
LDSB< ValSym4 > valsym4("ValSym4")
bool run(void)
Perform actual tests.
Definition: ldsb.cpp:1190
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:983
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:830
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
static void setup(Home h, SetVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1500
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1072
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:1447
Gecode::FloatVal c(-8, 8)
Test for value symmetry
Definition: ldsb.cpp:1080
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:839
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:904
IntVarBranch INT_VAR_DEGREE_MAX(BranchTbl tbl)
Select variable with largest degree.
Definition: var.hpp:147
Options opt
The options.
Definition: test.cpp:101
IntVarBranch INT_VAR_ACTIVITY_MIN(double d, BranchTbl tbl)
Select variable with lowest activity with decay factor d.
Definition: var.hpp:172
Test for reflection symmetry
Definition: ldsb.cpp:1534
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:820
LDSBSet< SetVarSeqSym1 > setvarseqsym1("SetVarSeqSym1")
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
virtual IntSetArgs * expectedSolutions(void)
Expected solutions.
Definition: ldsb.cpp:196
SymmetryHandle ValueSequenceSymmetry(const IntArgs &vs, int ss)
Value sequences in v of size ss are interchangeable.
Definition: ldsb.cpp:106
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:631
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:748
Test for value symmetry
Definition: ldsb.cpp:885
static const Options def
Default options.
Definition: search.hh:221
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:99
LDSBSet< SetVarSym1 > setvarsym1("SetVarSym1")
Test for value symmetry
Definition: ldsb.cpp:935
OneArray(int n, int l, int u)
Constructor for creation.
Definition: ldsb.cpp:148
Test for set variable sequence symmetry
Definition: ldsb.cpp:1491
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:1586
LDSB< SimIntValSym2 > simintvalsym2("SimIntValSym2")
Test for variable symmetry
Definition: ldsb.cpp:367
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:68
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:680
Test with activity
Definition: ldsb.cpp:1602
unsigned int size(I &i)
Size of all ranges of range iterator i.
Latin(bool share, Latin &s)
Definition: ldsb.cpp:1165
bool run(void)
Perform actual tests.
Definition: ldsb.cpp:240
Base class for all tests to be run
Definition: test.hh:107
Iterator for the greatest lower bound ranges of a set variable.
Definition: set.hh:272
Slice< A > row(int r) const
Access row r.
Definition: matrix.hpp:181
LDSB< VarSym1 > varsym1("VarSym1")
static void setup(Home h, SetVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1400
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:526
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:412
LDSB< TieBreak > tiebreak("TieBreak")
static std::vector< IntSetArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1507
Test for matrix symmetry
Definition: ldsb.cpp:577
Intersection
Definition: set.hh:664
virtual Space * copy(bool share)
Copy during cloning.
Definition: ldsb.cpp:183
LDSB< SimIntValSym1 > simintvalsym1("SimIntValSym1")
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:324
Integer sets.
Definition: int.hh:171
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1066
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:868
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1129
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:317
OneArraySet(int n, int l, int u)
Constructor for creation.
Definition: ldsb.cpp:176
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1310
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1293
Passing integer variables.
Definition: int.hh:636
unsigned int a_d
Adaptation distance.
Definition: ldsb.cpp:207
Passing integer arguments.
Definition: int.hh:607
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:725
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1058
static const IntSet empty
Empty set.
Definition: int.hh:262
IntArgs solution(void)
Definition: ldsb.cpp:1169
OneArray(bool share, OneArray &s)
Constructor for cloning s.
Definition: ldsb.cpp:151
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:989
LinIntExpr cardinality(const SetExpr &e)
Cardinality of set expression.
Definition: set-expr.cpp:815
double position(const Space &home, IntVar x, int i)
Definition: ldsb.cpp:1277
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
Class represeting a set of tuples.
Definition: int.hh:2022
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:483
Test for reflection symmetry
Definition: ldsb.cpp:1571
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntConLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
Definition: extensional.cpp:45
IntValBranch INT_VAL_MAX(void)
Select largest value.
Definition: val.hpp:78
General test support.
Definition: afc.cpp:43
void values(Home home, const IntVarArgs &x, IntSet y, IntConLevel icl=ICL_DEF)
Post constraint .
Definition: minimodel.hh:1869
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1559
Test for set variable symmetry
Definition: ldsb.cpp:1341
static std::vector< IntSetArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1406
Test for value symmetry
Definition: ldsb.cpp:910
Test space
Definition: ldsb.cpp:143
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1251
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
virtual IntArgs * expectedSolutions(void)
Expected solutions.
Definition: ldsb.cpp:166
static void setup(Home h, 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:299
LDSB< ValSym2b > valsym2b("ValSym2b")
Test for variable symmetry
Definition: ldsb.cpp:403
OneArraySet(bool share, OneArraySet &s)
Constructor for cloning s.
Definition: ldsb.cpp:179
unsigned int a_d
Adaptation distance.
Definition: ldsb.cpp:234
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1611
Integer variables.
Definition: int.hh:350
T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: dfs.hpp:52
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:1177
Test space (set version)
Definition: ldsb.cpp:171
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:901
Value iterator for integer sets.
Definition: int.hh:312
IntValBranch INT_VAL_MED(void)
Select greatest value not greater than the median.
Definition: val.hpp:73
SymmetryHandle rows_interchange(const Matrix< A > &m)
Interchangeable rows symmetry specification.
Definition: ldsb.hpp:44
Equality ( )
Definition: set.hh:645
Test for variable symmetry
Definition: ldsb.cpp:257
void distinct(Home home, const IntVarArgs &x, IntConLevel icl)
Post propagator for for all .
Definition: distinct.cpp:47
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:376
LDSB< MatSym1 > matsym1("MatSym1")
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:97
SymmetryHandle values_reflect(const IntVar &x)
Definition: ldsb.cpp:125
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1089
static std::vector< IntArgs > expectedSolutions(void)
Compute list of expected solutions.
Definition: ldsb.cpp:1029
Matrix-interface for arrays.
Definition: minimodel.hh:1924
LDSB< SimIntValSym3 > simintvalsym3("SimIntValSym3")
int val(void) const
Return current value.
Test for handling of recomputation
Definition: ldsb.cpp:1229
LDSB< SimIntVarSym1 > simintvarsym1("SimIntVarSym1")
Set variable array
Definition: set.hh:571
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:476
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:586
Gecode toplevel namespace
LDSB< VarSym4 > varsym4("VarSym4")
BrancherHandle 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:174
Slice< A > col(int c) const
Access column c.
Definition: matrix.hpp:187
LDSBLatin latin("Latin")
void add(const IntArgs &tuple)
Add tuple to tuple set.
Definition: tuple-set.hpp:98
Test for LDSB infrastructure
Definition: ldsb.cpp:229
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:778
Test for variable symmetry
Definition: ldsb.cpp:435
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:292
Home class for posting propagators
Definition: core.hpp:717
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:985
LDSB< ValSym1 > valsym1("ValSym1")
Test for LDSB infrastructure with Latin square problem
Definition: ldsb.cpp:1145
bool run(void)
Perform actual tests.
Definition: ldsb.cpp:213
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
Depth-first search engine.
Definition: search.hh:494
LDSB< Recomputation > recomp("Recomputation", 999, 999)
Test for value symmetry
Definition: ldsb.cpp:1012
Test for value sequence symmetry
Definition: ldsb.cpp:790
static void setup(Home h, IntVarArray &xs)
Setup problem constraints and symmetries.
Definition: ldsb.cpp:1238
LDSBSet< SetVarSeqSym2 > setvarseqsym2("SetVarSeqSym2")
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:926
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")