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