this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 * Guido Tack <tack@gecode.org>
6 *
7 * Contributing authors:
8 * Stefano Gualandi <stefano.gualandi@gmail.com>
9 * Mikael Lagerkvist <lagerkvist@gecode.org>
10 * David Rijsman <David.Rijsman@quintiq.com>
11 * Samuel Gagnon <samuel.gagnon92@gmail.com>
12 *
13 * Copyright:
14 * Stefano Gualandi, 2013
15 * Mikael Lagerkvist, 2006
16 * David Rijsman, 2009
17 * Christian Schulte, 2002
18 * Guido Tack, 2004
19 * Samuel Gagnon, 2018
20 *
21 * This file is part of Gecode, the generic constraint
22 * development environment:
23 * http://www.gecode.org
24 *
25 * Permission is hereby granted, free of charge, to any person obtaining
26 * a copy of this software and associated documentation files (the
27 * "Software"), to deal in the Software without restriction, including
28 * without limitation the rights to use, copy, modify, merge, publish,
29 * distribute, sublicense, and/or sell copies of the Software, and to
30 * permit persons to whom the Software is furnished to do so, subject to
31 * the following conditions:
32 *
33 * The above copyright notice and this permission notice shall be
34 * included in all copies or substantial portions of the Software.
35 *
36 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
37 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
38 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
39 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
40 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
41 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
42 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
43 *
44 */
45
46#ifndef GECODE_INT_HH
47#define GECODE_INT_HH
48
49#include <climits>
50#include <cfloat>
51
52#include <iostream>
53#include <vector>
54#include <unordered_map>
55#include <functional>
56#include <utility>
57#include <initializer_list>
58
59#include <gecode/kernel.hh>
60#include <gecode/search.hh>
61#include <gecode/iter.hh>
62
63/*
64 * Configure linking
65 *
66 */
67#if !defined(GECODE_STATIC_LIBS) && \
68 (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
69
70#ifdef GECODE_BUILD_INT
71#define GECODE_INT_EXPORT __declspec( dllexport )
72#else
73#define GECODE_INT_EXPORT __declspec( dllimport )
74#endif
75
76#else
77
78#ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
79#define GECODE_INT_EXPORT __attribute__ ((visibility("default")))
80#else
81#define GECODE_INT_EXPORT
82#endif
83
84#endif
85
86// Configure auto-linking
87#ifndef GECODE_BUILD_INT
88#define GECODE_LIBRARY_NAME "Int"
89#include <gecode/support/auto-link.hpp>
90#endif
91
92/**
93 * \namespace Gecode::Int
94 * \brief Finite domain integers
95 *
96 * The Gecode::Int namespace contains all functionality required
97 * to program propagators and branchers for finite domain integers.
98 * In addition, all propagators and branchers for finite domain
99 * integers provided by %Gecode are contained as nested namespaces.
100 *
101 */
102
103#include <gecode/int/exception.hpp>
104
105namespace Gecode { namespace Int {
106
107 /**
108 * \brief Numerical limits for integer variables
109 *
110 * The integer limits are chosen such changing the sign is always possible
111 * without overflow.
112 * \ingroup TaskModelIntVars
113 */
114 namespace Limits {
115 /// Largest allowed integer value
116 const int max = INT_MAX - 1;
117 /// Smallest allowed integer value
118 const int min = -max;
119 /// Infinity for integers
120 const int infinity = max + 1;
121 /// Largest allowed long long integer value
122 const long long int llmax = LLONG_MAX - 1;
123 /// Smallest allowed long long integer value
124 const long long int llmin = -llmax;
125 /// Infinity for long long integers
126 const long long int llinfinity = llmax + 1;
127 /// Return whether \a n is in range
128 bool valid(int n);
129 /// Return whether \a n is in range
130 bool valid(long long int n);
131 /// Check whether \a n is in range, otherwise throw out of limits with information \a l
132 void check(int n, const char* l);
133 /// Check whether \a n is in range, otherwise throw out of limits with information \a l
134 void check(long long int n, const char* l);
135 /// Check whether \a n is in range and strictly positive, otherwise throw out of limits with information \a l
136 void positive(int n, const char* l);
137 /// Check whether \a n is in range and strictly positive, otherwise throw out of limits with information \a l
138 void positive(long long int n, const char* l);
139 /// Check whether \a n is in range and nonnegative, otherwise throw out of limits with information \a l
140 void nonnegative(int n, const char* l);
141 /// Check whether \a n is in integer range and nonnegative, otherwise throw out of limits exception with information \a l
142 void nonnegative(long long int n, const char* l);
143 /// Check whether adding \a n and \a m would overflow
144 bool overflow_add(int n, int m);
145 /// Check whether adding \a n and \a m would overflow
146 bool overflow_add(long long int n, long long int m);
147 /// Check whether subtracting \a m from \a n would overflow
148 bool overflow_sub(int n, int m);
149 /// Check whether subtracting \a m from \a n would overflow
150 bool overflow_sub(long long int n, long long int m);
151 /// Check whether multiplying \a n and \a m would overflow
152 bool overflow_mul(int n, int m);
153 /// Check whether multiplying \a n and \a m would overflow
154 bool overflow_mul(long long int n, long long int m);
155 }
156
157}}
158
159#include <gecode/int/limits.hpp>
160
161namespace Gecode {
162
163 class IntSetRanges;
164
165 template<class I> class IntSetInit;
166
167 /**
168 * \brief Integer sets
169 *
170 * Integer sets are the means to specify arbitrary sets
171 * of integers to be used as domains for integer variables.
172 * \ingroup TaskModelIntVars TaskModelSetVars
173 */
174 class IntSet : public SharedHandle {
175 friend class IntSetRanges;
176 template<class I> friend class IntSetInit;
177 private:
178 /// %Range (intervals) of integers
179 class Range {
180 public:
181 int min, max;
182 };
183 class IntSetObject : public SharedHandle::Object {
184 public:
185 /// Size of set
186 unsigned int size;
187 /// Number of ranges
188 int n;
189 /// Array of ranges
190 Range* r;
191 /// Allocate object with \a m elements
192 GECODE_INT_EXPORT static IntSetObject* allocate(int m);
193 /// Check whether \a n is included in the set
194 GECODE_INT_EXPORT bool in(int n) const;
195 /// Perform equality test on ranges
196 GECODE_INT_EXPORT bool equal(const IntSetObject& so) const;
197 /// Delete object
198 GECODE_INT_EXPORT virtual ~IntSetObject(void);
199 };
200 /// Sort ranges according to increasing minimum
201 class MinInc;
202 /// Normalize the first \a n elements of \a r
203 GECODE_INT_EXPORT void normalize(Range* r, int n);
204 /// Initialize as range with minimum \a n and maximum \a m
205 GECODE_INT_EXPORT void init(int n, int m);
206 /// Initialize with \a n integers from array \a r
207 GECODE_INT_EXPORT void init(const int r[], int n);
208 /// Initialize with \a n ranges from array \a r
209 GECODE_INT_EXPORT void init(const int r[][2], int n);
210 public:
211 /// \name Constructors and initialization
212 //@{
213 /// Initialize as empty set
214 IntSet(void);
215 /** \brief Initialize as range with minimum \a n and maximum \a m
216 *
217 * Note that the set is empty if \a n is larger than \a m
218 */
219 explicit IntSet(int n, int m);
220 /// Initialize with \a n integers from array \a r
221 explicit IntSet(const int r[], int n);
222 /** \brief Initialize with \a n ranges from array \a r
223 *
224 * For position \a i in the array \a r, the minimum is \a r[\a i][0]
225 * and the maximum is \a r[\a i][1].
226 */
227 explicit IntSet(const int r[][2], int n);
228 /// Initialize with range iterator \a i
229 template<class I>
230 explicit IntSet(I& i);
231 /// Initialize with range iterator \a i
232 template<class I>
233 explicit IntSet(const I& i);
234 /// Initialize with integers from list \a r
235 GECODE_INT_EXPORT
236 explicit IntSet(std::initializer_list<int> r);
237 /** \brief Initialize with ranges from vector \a r
238 *
239 * The minimum is the first element and the maximum is the
240 * second element.
241 */
242 GECODE_INT_EXPORT
243 explicit IntSet(std::initializer_list<std::pair<int,int>> r);
244 //@}
245
246 /// \name Range access
247 //@{
248 /// Return number of ranges of the specification
249 int ranges(void) const;
250 /// Return minimum of range at position \a i
251 int min(int i) const;
252 /// Return maximum of range at position \a i
253 int max(int i) const;
254 /// Return width of range at position \a i
255 unsigned int width(int i) const;
256 //@}
257
258 /// \name Entire set access
259 //@{
260 /// Return whether \a n is included in the set
261 bool in(int n) const;
262 /// Return size (cardinality) of set
263 unsigned int size(void) const;
264 /// Return width of set (distance between maximum and minimum)
265 unsigned int width(void) const;
266 /// Return minimum of entire set
267 int min(void) const;
268 /// Return maximum of entire set
269 int max(void) const;
270 //@}
271
272 /// \name Equality tests
273 //@{
274 /// Return whether \a s is equal
275 bool operator ==(const IntSet& s) const;
276 /// Return whether \a s is not equal
277 bool operator !=(const IntSet& s) const;
278 //@}
279
280 /// \name Predefined value
281 //@{
282 /// Empty set
283 GECODE_INT_EXPORT static const IntSet empty;
284 //@}
285 };
286
287 /**
288 * \brief Range iterator for integer sets
289 *
290 * \ingroup TaskModelIntVars TaskModelSetVars
291 */
292 class IntSetRanges {
293 private:
294 /// Current range
295 const IntSet::Range* i;
296 /// End range
297 const IntSet::Range* e;
298 public:
299 /// \name Constructors and initialization
300 //@{
301 /// Default constructor
302 IntSetRanges(void);
303 /// Initialize with ranges for set \a s
304 IntSetRanges(const IntSet& s);
305 /// Initialize with ranges for set \a s
306 void init(const IntSet& s);
307 //@}
308
309 /// \name Iteration control
310 //@{
311 /// Test whether iterator is still at a range or done
312 bool operator ()(void) const;
313 /// Move iterator to next range (if possible)
314 void operator ++(void);
315 //@}
316
317 /// \name Range access
318 //@{
319 /// Return smallest value of range
320 int min(void) const;
321 /// Return largest value of range
322 int max(void) const;
323 /// Return width of range (distance between minimum and maximum)
324 unsigned int width(void) const;
325 //@}
326 };
327
328 /**
329 * \brief Value iterator for integer sets
330 *
331 * \ingroup TaskModelIntVars TaskModelSetVars
332 */
333 class IntSetValues : public Iter::Ranges::ToValues<IntSetRanges> {
334 public:
335 /// \name Constructors and initialization
336 //@{
337 /// Default constructor
338 IntSetValues(void);
339 /// Initialize with values for \a s
340 IntSetValues(const IntSet& s);
341 /// Initialize with values for \a s
342 void init(const IntSet& s);
343 //@}
344 };
345
346 /**
347 * \brief Print integer set \a s
348 * \relates Gecode::IntSet
349 */
350 template<class Char, class Traits>
351 std::basic_ostream<Char,Traits>&
352 operator <<(std::basic_ostream<Char,Traits>& os, const IntSet& s);
353
354}
355
356#include <gecode/int/int-set-1.hpp>
357
358#include <gecode/int/var-imp.hpp>
359
360namespace Gecode {
361
362 namespace Int {
363 class IntView;
364 }
365
366 /**
367 * \brief Integer variables
368 *
369 * \ingroup TaskModelIntVars
370 */
371 class IntVar : public VarImpVar<Int::IntVarImp> {
372 friend class IntVarArray;
373 friend class IntVarArgs;
374 private:
375 using VarImpVar<Int::IntVarImp>::x;
376 /**
377 * \brief Initialize variable with range domain
378 *
379 * The variable is created with a domain ranging from \a min
380 * to \a max. No exceptions are thrown.
381 */
382 void _init(Space& home, int min, int max);
383 /**
384 * \brief Initialize variable with arbitrary domain
385 *
386 * The variable is created with a domain described by \a d.
387 * No exceptions are thrown.
388 */
389 void _init(Space& home, const IntSet& d);
390 public:
391 /// \name Constructors and initialization
392 //@{
393 /// Default constructor
394 IntVar(void);
395 /// Initialize from integer variable \a y
396 IntVar(const IntVar& y);
397 /// Initialize from integer view \a y
398 IntVar(const Int::IntView& y);
399 /**
400 * \brief Initialize variable with range domain
401 *
402 * The variable is created with a domain ranging from \a min
403 * to \a max. The following exceptions might be thrown:
404 * - If \a min is greater than \a max, an exception of type
405 * Gecode::Int::VariableEmptyDomain is thrown.
406 * - If \a min or \a max exceed the limits for integers as defined
407 * in Gecode::Int::Limits, an exception of type
408 * Gecode::Int::OutOfLimits is thrown.
409 */
410 GECODE_INT_EXPORT IntVar(Space& home, int min, int max);
411 /**
412 * \brief Initialize variable with arbitrary domain
413 *
414 * The variable is created with a domain described by \a d.
415 * The following exceptions might be thrown:
416 * - If \a d is empty, an exception of type
417 * Gecode::Int::VariableEmptyDomain is thrown.
418 * - If \a d contains values that exceed the limits for integers
419 * as defined in Gecode::Int::Limits, an exception of type
420 * Gecode::Int::OutOfLimits is thrown.
421 */
422 GECODE_INT_EXPORT IntVar(Space& home, const IntSet& d);
423 //@}
424
425 /// \name Value access
426 //@{
427 /// Return minimum of domain
428 int min(void) const;
429 /// Return maximum of domain
430 int max(void) const;
431 /// Return median of domain (greatest element not greater than the median)
432 int med(void) const;
433 /**
434 * \brief Return assigned value
435 *
436 * Throws an exception of type Int::ValOfUnassignedVar if variable
437 * is not yet assigned.
438 *
439 */
440 int val(void) const;
441
442 /// Return size (cardinality) of domain
443 unsigned int size(void) const;
444 /// Return width of domain (distance between maximum and minimum)
445 unsigned int width(void) const;
446 /// Return regret of domain minimum (distance to next larger value)
447 unsigned int regret_min(void) const;
448 /// Return regret of domain maximum (distance to next smaller value)
449 unsigned int regret_max(void) const;
450 //@}
451
452 /// \name Domain tests
453 //@{
454 /// Test whether domain is a range
455 bool range(void) const;
456 /// Test whether \a n is contained in domain
457 bool in(int n) const;
458 //@}
459 };
460
461 /**
462 * \brief Print integer variable \a x
463 * \relates Gecode::IntVar
464 */
465 template<class Char, class Traits>
466 std::basic_ostream<Char,Traits>&
467 operator <<(std::basic_ostream<Char,Traits>& os, const IntVar& x);
468
469 /**
470 * \brief %Range iterator for integer variables
471 * \ingroup TaskModelIntVars
472 */
473 class IntVarRanges : public Int::IntVarImpFwd {
474 public:
475 /// \name Constructors and initialization
476 //@{
477 /// Default constructor
478 IntVarRanges(void);
479 /// Initialize with ranges for integer variable \a x
480 IntVarRanges(const IntVar& x);
481 /// Initialize with ranges for integer variable \a x
482 void init(const IntVar& x);
483 //@}
484 };
485
486 /**
487 * \brief Value iterator for integer variables
488 * \ingroup TaskModelIntVars
489 */
490 class IntVarValues : public Iter::Ranges::ToValues<IntVarRanges> {
491 public:
492 /// \name Constructors and initialization
493 //@{
494 /// Default constructor
495 IntVarValues(void);
496 /// Initialize with values for \a x
497 IntVarValues(const IntVar& x);
498 /// Initialize with values \a x
499 void init(const IntVar& x);
500 //@}
501 };
502
503 namespace Int {
504 class BoolView;
505 }
506
507 /**
508 * \brief Boolean integer variables
509 *
510 * \ingroup TaskModelIntVars
511 */
512 class BoolVar : public VarImpVar<Int::BoolVarImp> {
513 friend class BoolVarArray;
514 friend class BoolVarArgs;
515 private:
516 using VarImpVar<Int::BoolVarImp>::x;
517 /**
518 * \brief Initialize Boolean variable with range domain
519 *
520 * The variable is created with a domain ranging from \a min
521 * to \a max. No exceptions are thrown.
522 */
523 void _init(Space& home, int min, int max);
524 public:
525 /// \name Constructors and initialization
526 //@{
527 /// Default constructor
528 BoolVar(void);
529 /// Initialize from Boolean variable \a y
530 BoolVar(const BoolVar& y);
531 /// Initialize from Boolean view \a y
532 BoolVar(const Int::BoolView& y);
533 /**
534 * \brief Initialize Boolean variable with range domain
535 *
536 * The variable is created with a domain ranging from \a min
537 * to \a max. The following exceptions might be thrown:
538 * - If \a min is greater than \a max, an exception of type
539 * Gecode::Int::VariableEmptyDomain is thrown.
540 * - If \a min is less than 0 or \a max is greater than 1,
541 * an exception of type
542 * Gecode::Int::NotZeroOne is thrown.
543 */
544 GECODE_INT_EXPORT BoolVar(Space& home, int min, int max);
545 //@}
546
547 /// \name Value access
548 //@{
549 /// Return minimum of domain
550 int min(void) const;
551 /// Return maximum of domain
552 int max(void) const;
553 /// Return median of domain (greatest element not greater than the median)
554 int med(void) const;
555 /**
556 * \brief Return assigned value
557 *
558 * Throws an exception of type Int::ValOfUnassignedVar if variable
559 * is not yet assigned.
560 *
561 */
562 int val(void) const;
563
564 /// Return size (cardinality) of domain
565 unsigned int size(void) const;
566 /// Return width of domain (distance between maximum and minimum)
567 unsigned int width(void) const;
568 /// Return regret of domain minimum (distance to next larger value)
569 unsigned int regret_min(void) const;
570 /// Return regret of domain maximum (distance to next smaller value)
571 unsigned int regret_max(void) const;
572 //@}
573
574 /// \name Domain tests
575 //@{
576 /// Test whether domain is a range
577 bool range(void) const;
578 /// Test whether \a n is contained in domain
579 bool in(int n) const;
580 //@}
581
582 /// \name Boolean domain tests
583 //@{
584 /// Test whether domain is zero
585 bool zero(void) const;
586 /// Test whether domain is one
587 bool one(void) const;
588 /// Test whether domain is neither zero nor one
589 bool none(void) const;
590 //@}
591 };
592
593 /**
594 * \brief Print Boolean variable \a x
595 * \relates Gecode::BoolVar
596 */
597 template<class Char, class Traits>
598 std::basic_ostream<Char,Traits>&
599 operator <<(std::basic_ostream<Char,Traits>& os, const BoolVar& x);
600
601}
602
603
604#include <gecode/int/view.hpp>
605#include <gecode/int/propagator.hpp>
606
607namespace Gecode {
608
609 /**
610 * \defgroup TaskModelIntArgs Argument arrays
611 *
612 * Argument arrays are just good enough for passing arguments
613 * with automatic memory management.
614 * \ingroup TaskModelInt
615 */
616
617 //@{
618 /// Passing set arguments
619 typedef ArgArray<IntSet> IntSetArgs;
620
621}
622
623#include <gecode/int/array-traits.hpp>
624
625namespace Gecode {
626
627 /// Passing integer arguments
628 class IntArgs : public ArgArray<int> {
629 public:
630 /// \name Constructors and initialization
631 //@{
632 /// Allocate empty array
633 IntArgs(void);
634 /// Allocate array with \a n elements
635 explicit IntArgs(int n);
636 /// Allocate array and copy elements from \a x
637 IntArgs(const SharedArray<int>& x);
638 /// Allocate array and copy elements from \a x
639 IntArgs(const std::vector<int>& x);
640 /// Allocate array and copy elements from \a x
641 IntArgs(std::initializer_list<int> x);
642 /// Allocate array and copy elements from \a first to \a last
643 template<class InputIterator>
644 IntArgs(InputIterator first, InputIterator last);
645 /// Allocate array with \a n elements and initialize with elements from array \a e
646 IntArgs(int n, const int* e);
647 /// Initialize from primitive argument array \a a (copy elements)
648 IntArgs(const ArgArray<int>& a);
649
650 /// Allocate array with \a n elements such that for all \f$0\leq i<n: x_i=\text{start}+i\cdot\text{inc}\f$
651 static IntArgs create(int n, int start, int inc=1);
652 //@}
653 };
654
655 /// \brief Passing integer variables
656 class IntVarArgs : public VarArgArray<IntVar> {
657 public:
658 /// \name Constructors and initialization
659 //@{
660 /// Allocate empty array
661 IntVarArgs(void);
662 /// Allocate array with \a n elements
663 explicit IntVarArgs(int n);
664 /// Initialize from variable argument array \a a (copy elements)
665 IntVarArgs(const IntVarArgs& a);
666 /// Initialize from variable array \a a (copy elements)
667 IntVarArgs(const VarArray<IntVar>& a);
668 /// Initialize from \a a
669 IntVarArgs(const std::vector<IntVar>& a);
670 /// Initialize from \a a
671 IntVarArgs(std::initializer_list<IntVar> a);
672 /// Initialize from InputIterator \a first and \a last
673 template<class InputIterator>
674 IntVarArgs(InputIterator first, InputIterator last);
675 /**
676 * \brief Initialize array with \a n new variables
677 *
678 * The variables are created with a domain ranging from \a min
679 * to \a max. The following execptions might be thrown:
680 * - If \a min is greater than \a max, an exception of type
681 * Gecode::Int::VariableEmptyDomain is thrown.
682 * - If \a min or \a max exceed the limits for integers as defined
683 * in Gecode::Int::Limits, an exception of type
684 * Gecode::Int::OutOfLimits is thrown.
685 */
686 GECODE_INT_EXPORT
687 IntVarArgs(Space& home, int n, int min, int max);
688 /**
689 * \brief Initialize array with \a n new variables
690 *
691 * The variables are created with a domain described by \a s.
692 * The following execptions might be thrown:
693 * - If \a s is empty, an exception of type
694 * Gecode::Int::VariableEmptyDomain is thrown.
695 * - If \a s contains values that exceed the limits for integers
696 * as defined in Gecode::Int::Limits, an exception of type
697 * Gecode::Int::OutOfLimits is thrown.
698 */
699 GECODE_INT_EXPORT
700 IntVarArgs(Space& home, int n, const IntSet& s);
701 //@}
702 };
703
704 /** \brief Passing Boolean variables
705 *
706 * We could have used a simple typedef instead, but doxygen cannot
707 * resolve some overloading then, leading to unusable documentation for
708 * important parts of the library. As long as there is no fix for this,
709 * we will keep this workaround.
710 *
711 */
712 class BoolVarArgs : public VarArgArray<BoolVar> {
713 public:
714 /// \name Constructors and initialization
715 //@{
716 /// Allocate empty array
717 BoolVarArgs(void);
718 /// Allocate array with \a n elements
719 explicit BoolVarArgs(int n);
720 /// Initialize from variable argument array \a a (copy elements)
721 BoolVarArgs(const BoolVarArgs& a);
722 /// Initialize from variable array \a a (copy elements)
723 BoolVarArgs(const VarArray<BoolVar>& a);
724 /// Initialize from \a a
725 BoolVarArgs(const std::vector<BoolVar>& a);
726 /// Initialize from \a a
727 BoolVarArgs(std::initializer_list<BoolVar> a);
728 /// Initialize from InputIterator \a first and \a last
729 template<class InputIterator>
730 BoolVarArgs(InputIterator first, InputIterator last);
731 /**
732 * \brief Initialize array with \a n new variables
733 *
734 * The variables are created with a domain ranging from \a min
735 * to \a max. The following execptions might be thrown:
736 * - If \a min is greater than \a max, an exception of type
737 * Gecode::Int::VariableEmptyDomain is thrown.
738 * - If \a min is less than 0 or \a max is greater than 1,
739 * an exception of type
740 * Gecode::Int::NotZeroOne is thrown.
741 */
742 GECODE_INT_EXPORT
743 BoolVarArgs(Space& home, int n, int min, int max);
744 //@}
745 };
746 //@}
747
748 /**
749 * \defgroup TaskModelIntVarArrays Variable arrays
750 *
751 * Variable arrays can store variables. They are typically used
752 * for storing the variables being part of a solution (script). However,
753 * they can also be used for temporary purposes (even though
754 * memory is not reclaimed until the space it is created for
755 * is deleted).
756 * \ingroup TaskModelInt
757 */
758
759 /**
760 * \brief Integer variable array
761 * \ingroup TaskModelIntVarArrays
762 */
763 class IntVarArray : public VarArray<IntVar> {
764 public:
765 /// \name Creation and initialization
766 //@{
767 /// Default constructor (array of size 0)
768 IntVarArray(void);
769 /// Allocate array for \a n integer variables (variables are uninitialized)
770 IntVarArray(Space& home, int n);
771 /// Initialize from integer variable array \a a (share elements)
772 IntVarArray(const IntVarArray& a);
773 /// Initialize from integer variable argument array \a a (copy elements)
774 IntVarArray(Space& home, const IntVarArgs& a);
775 /**
776 * \brief Initialize array with \a n new variables
777 *
778 * The variables are created with a domain ranging from \a min
779 * to \a max. The following execptions might be thrown:
780 * - If \a min is greater than \a max, an exception of type
781 * Gecode::Int::VariableEmptyDomain is thrown.
782 * - If \a min or \a max exceed the limits for integers as defined
783 * in Gecode::Int::Limits, an exception of type
784 * Gecode::Int::OutOfLimits is thrown.
785 */
786 GECODE_INT_EXPORT
787 IntVarArray(Space& home, int n, int min, int max);
788 /**
789 * \brief Initialize array with \a n new variables
790 *
791 * The variables are created with a domain described by \a s.
792 * The following execptions might be thrown:
793 * - If \a s is empty, an exception of type
794 * Gecode::Int::VariableEmptyDomain is thrown.
795 * - If \a s contains values that exceed the limits for integers
796 * as defined in Gecode::Int::Limits, an exception of type
797 * Gecode::Int::OutOfLimits is thrown.
798 */
799 GECODE_INT_EXPORT
800 IntVarArray(Space& home, int n, const IntSet& s);
801 //@}
802 };
803
804 /**
805 * \brief Boolean variable array
806 * \ingroup TaskModelIntVarArrays
807 */
808 class BoolVarArray : public VarArray<BoolVar> {
809 public:
810 /// \name Creation and initialization
811 //@{
812 /// Default constructor (array of size 0)
813 BoolVarArray(void);
814 /// Allocate array for \a n Boolean variables (variables are uninitialized)
815 BoolVarArray(Space& home, int n);
816 /// Initialize from Boolean variable array \a a (share elements)
817 BoolVarArray(const BoolVarArray& a);
818 /// Initialize from Boolean variable argument array \a a (copy elements)
819 BoolVarArray(Space& home, const BoolVarArgs& a);
820 /**
821 * \brief Initialize array with \a n new variables
822 *
823 * The variables are created with a domain ranging from \a min
824 * to \a max. The following execptions might be thrown:
825 * - If \a min is greater than \a max, an exception of type
826 * Gecode::Int::VariableEmptyDomain is thrown.
827 * - If \a min is less than 0 or \a max is greater than 1,
828 * an exception of type
829 * Gecode::Int::NotZeroOne is thrown.
830 */
831 GECODE_INT_EXPORT
832 BoolVarArray(Space& home, int n, int min, int max);
833 //@}
834 };
835
836}
837
838#include <gecode/int/int-set-2.hpp>
839
840#include <gecode/int/array.hpp>
841
842namespace Gecode {
843
844 /**
845 * \brief Mode for reification
846 * \ingroup TaskModelInt
847 */
848 enum ReifyMode {
849 /**
850 * \brief Equivalence for reification (default)
851 *
852 * For a constraint \f$c\f$ and a Boolean control variable \f$b\f$
853 * defines that \f$b=1\Leftrightarrow c\f$ is propagated.
854 */
855 RM_EQV,
856 /**
857 * \brief Implication for reification
858 *
859 * For a constraint \f$c\f$ and a Boolean control variable \f$b\f$
860 * defines that \f$b=1\Leftarrow c\f$ is propagated.
861 */
862 RM_IMP,
863 /**
864 * \brief Inverse implication for reification
865 *
866 * For a constraint \f$c\f$ and a Boolean control variable \f$b\f$
867 * defines that \f$b=1\Rightarrow c\f$ is propagated.
868 */
869 RM_PMI
870 };
871
872 /**
873 * \brief Reification specification
874 * \ingroup TaskModelInt
875 */
876 class Reify {
877 protected:
878 /// The Boolean control variable
879 BoolVar x;
880 /// The reification mode
881 ReifyMode rm;
882 public:
883 /// Default constructor without proper initialization
884 Reify(void);
885 /// Construct reification specification
886 Reify(BoolVar x, ReifyMode rm=RM_EQV);
887 /// Return Boolean control variable
888 BoolVar var(void) const;
889 /// Return reification mode
890 ReifyMode mode(void) const;
891 /// Set Boolean control variable
892 void var(BoolVar x);
893 /// Set reification mode
894 void mode(ReifyMode rm);
895 };
896
897 /**
898 * \brief Use equivalence for reification
899 * \ingroup TaskModelInt
900 */
901 Reify eqv(BoolVar x);
902
903 /**
904 * \brief Use implication for reification
905 * \ingroup TaskModelInt
906 */
907 Reify imp(BoolVar x);
908
909 /**
910 * \brief Use reverse implication for reification
911 * \ingroup TaskModelInt
912 */
913 Reify pmi(BoolVar x);
914
915}
916
917#include <gecode/int/reify.hpp>
918
919namespace Gecode {
920
921 /**
922 * \brief Relation types for integers
923 * \ingroup TaskModelInt
924 */
925 enum IntRelType {
926 IRT_EQ, ///< Equality (\f$=\f$)
927 IRT_NQ, ///< Disequality (\f$\neq\f$)
928 IRT_LQ, ///< Less or equal (\f$\leq\f$)
929 IRT_LE, ///< Less (\f$<\f$)
930 IRT_GQ, ///< Greater or equal (\f$\geq\f$)
931 IRT_GR ///< Greater (\f$>\f$)
932 };
933
934 /// Return swapped relation type of \a irt
935 IntRelType swap(IntRelType irt);
936
937 /// Return negated relation type of \a irt
938 IntRelType neg(IntRelType irt);
939
940}
941
942#include <gecode/int/irt.hpp>
943
944namespace Gecode {
945
946 /**
947 * \brief Operation types for Booleans
948 * \ingroup TaskModelInt
949 */
950 enum BoolOpType {
951 BOT_AND, ///< Conjunction
952 BOT_OR, ///< Disjunction
953 BOT_IMP, ///< Implication
954 BOT_EQV, ///< Equivalence
955 BOT_XOR ///< Exclusive or
956 };
957
958 /**
959 * \brief Propagation levels for integer propagators
960 *
961 * The descriptions are meant to be approximate. It is not
962 * required that a propagator achieves full domain consistency or
963 * full bounds consistency. It is more like: which level
964 * of consistency comes closest to the level of propagation
965 * the propagator implements.
966 *
967 * If in the description of a constraint below no propagation level
968 * is mentioned, the propagation level for the constraint is domain
969 * propagation and the implementation in fact enforces domain
970 * consistency.
971 *
972 * \ingroup TaskModelInt
973 */
974 enum IntPropLevel {
975 /// Simple propagation levels
976 IPL_DEF = 0, ///< Default level of propagation
977 IPL_VAL = 1, ///< Value propagation
978 IPL_BND = 2, ///< Bounds propagation
979 IPL_DOM = 3, ///< Domain propagation
980 /// Options: basic versus advanced propagation
981 IPL_BASIC = 4, ///< Use basic propagation algorithm
982 IPL_ADVANCED = 8, ///< Use advanced propagation algorithm
983 IPL_BASIC_ADVANCED = IPL_BASIC | IPL_ADVANCED, ///< Use both
984 IPL_BITS_ = 4 ///< Number of bits required (internal)
985 };
986
987 /// Extract value, bounds, or domain propagation from propagation level
988 IntPropLevel vbd(IntPropLevel ipl);
989
990 /// Extract basic or advanced from propagation level
991 IntPropLevel ba(IntPropLevel ipl);
992
993}
994
995#include <gecode/int/ipl.hpp>
996
997namespace Gecode {
998
999 /**
1000 * \brief Type of task for scheduling constraints
1001 *
1002 * \ingroup TaskModelInt
1003 */
1004 enum TaskType {
1005 TT_FIXP, //< Task with fixed processing time
1006 TT_FIXS, //< Task with fixed start time
1007 TT_FIXE //< Task with fixed end time
1008 };
1009
1010 /**
1011 * \brief Argument arrays for passing task type arguments
1012 *
1013 * \ingroup TaskModelInt
1014 */
1015 typedef ArgArray<TaskType> TaskTypeArgs;
1016
1017 /// Traits of %TaskTypeArgs
1018 template<>
1019 class ArrayTraits<ArgArray<TaskType> > {
1020 public:
1021 typedef TaskTypeArgs StorageType;
1022 typedef TaskType ValueType;
1023 typedef TaskTypeArgs ArgsType;
1024 };
1025
1026
1027 /**
1028 * \defgroup TaskModelIntDomain Domain constraints
1029 * \ingroup TaskModelInt
1030 *
1031 */
1032
1033 //@{
1034 /// Propagates \f$x=n\f$
1035 GECODE_INT_EXPORT void
1036 dom(Home home, IntVar x, int n,
1037 IntPropLevel ipl=IPL_DEF);
1038 /// Propagates \f$ x_i=n\f$ for all \f$0\leq i<|x|\f$
1039 GECODE_INT_EXPORT void
1040 dom(Home home, const IntVarArgs& x, int n,
1041 IntPropLevel ipl=IPL_DEF);
1042
1043 /// Propagates \f$ l\leq x\leq m\f$
1044 GECODE_INT_EXPORT void
1045 dom(Home home, IntVar x, int l, int m,
1046 IntPropLevel ipl=IPL_DEF);
1047 /// Propagates \f$ l\leq x_i\leq m\f$ for all \f$0\leq i<|x|\f$
1048 GECODE_INT_EXPORT void
1049 dom(Home home, const IntVarArgs& x, int l, int m,
1050 IntPropLevel ipl=IPL_DEF);
1051
1052 /// Propagates \f$ x\in s \f$
1053 GECODE_INT_EXPORT void
1054 dom(Home home, IntVar x, const IntSet& s,
1055 IntPropLevel ipl=IPL_DEF);
1056 /// Propagates \f$ x_i\in s\f$ for all \f$0\leq i<|x|\f$
1057 GECODE_INT_EXPORT void
1058 dom(Home home, const IntVarArgs& x, const IntSet& s,
1059 IntPropLevel ipl=IPL_DEF);
1060
1061 /// Post domain consistent propagator for \f$ (x=n) \equiv r\f$
1062 GECODE_INT_EXPORT void
1063 dom(Home home, IntVar x, int n, Reify r,
1064 IntPropLevel ipl=IPL_DEF);
1065 /// Post domain consistent propagator for \f$ (l\leq x \leq m) \equiv r\f$
1066 GECODE_INT_EXPORT void
1067 dom(Home home, IntVar x, int l, int m, Reify r,
1068 IntPropLevel ipl=IPL_DEF);
1069 /// Post domain consistent propagator for \f$ (x \in s) \equiv r\f$
1070 GECODE_INT_EXPORT void
1071 dom(Home home, IntVar x, const IntSet& s, Reify r,
1072 IntPropLevel ipl=IPL_DEF);
1073
1074 /// Constrain domain of \a x according to domain of \a d
1075 GECODE_INT_EXPORT void
1076 dom(Home home, IntVar x, IntVar d,
1077 IntPropLevel ipl=IPL_DEF);
1078 /// Constrain domain of \a x according to domain of \a d
1079 GECODE_INT_EXPORT void
1080 dom(Home home, BoolVar x, BoolVar d,
1081 IntPropLevel ipl=IPL_DEF);
1082 /// Constrain domain of \f$ x_i \f$ according to domain of \f$ d_i \f$ for all \f$0\leq i<|x|\f$
1083 GECODE_INT_EXPORT void
1084 dom(Home home, const IntVarArgs& x, const IntVarArgs& d,
1085 IntPropLevel ipl=IPL_DEF);
1086 /// Constrain domain of \f$ x_i \f$ according to domain of \f$ d_i \f$ for all \f$0\leq i<|x|\f$
1087 GECODE_INT_EXPORT void
1088 dom(Home home, const BoolVarArgs& x, const BoolVarArgs& d,
1089 IntPropLevel ipl=IPL_DEF);
1090 //@}
1091
1092
1093 /**
1094 * \defgroup TaskModelIntRelInt Simple relation constraints over integer variables
1095 * \ingroup TaskModelInt
1096 */
1097 /** \brief Post propagator for \f$ x_0 \sim_{irt} x_1\f$
1098 *
1099 * Supports both bounds (\a ipl = IPL_BND) and
1100 * domain consistency (\a ipl = IPL_DOM, default).
1101 * \ingroup TaskModelIntRelInt
1102 */
1103 GECODE_INT_EXPORT void
1104 rel(Home home, IntVar x0, IntRelType irt, IntVar x1,
1105 IntPropLevel ipl=IPL_DEF);
1106 /** \brief Post propagator for \f$ x_i \sim_{irt} y \f$ for all \f$0\leq i<|x|\f$
1107 *
1108 * Supports both bounds (\a ipl = IPL_BND) and
1109 * domain consistency (\a ipl = IPL_DOM, default).
1110 * \ingroup TaskModelIntRelInt
1111 */
1112 GECODE_INT_EXPORT void
1113 rel(Home home, const IntVarArgs& x, IntRelType irt, IntVar y,
1114 IntPropLevel ipl=IPL_DEF);
1115 /** \brief Propagates \f$ x \sim_{irt} c\f$
1116 * \ingroup TaskModelIntRelInt
1117 */
1118 GECODE_INT_EXPORT void
1119 rel(Home home, IntVar x, IntRelType irt, int c,
1120 IntPropLevel ipl=IPL_DEF);
1121 /** \brief Propagates \f$ x_i \sim_{irt} c \f$ for all \f$0\leq i<|x|\f$
1122 * \ingroup TaskModelIntRelInt
1123 */
1124 GECODE_INT_EXPORT void
1125 rel(Home home, const IntVarArgs& x, IntRelType irt, int c,
1126 IntPropLevel ipl=IPL_DEF);
1127 /** \brief Post propagator for \f$ (x_0 \sim_{irt} x_1)\equiv r\f$
1128 *
1129 * Supports both bounds (\a ipl = IPL_BND) and
1130 * domain consistency (\a ipl = IPL_DOM, default).
1131 * \ingroup TaskModelIntRelInt
1132 */
1133 GECODE_INT_EXPORT void
1134 rel(Home home, IntVar x0, IntRelType irt, IntVar x1, Reify r,
1135 IntPropLevel ipl=IPL_DEF);
1136 /** \brief Post propagator for \f$(x \sim_{irt} c)\equiv r\f$
1137 *
1138 * Supports both bounds (\a ipl = IPL_BND) and
1139 * domain consistency (\a ipl = IPL_DOM, default).
1140 * \ingroup TaskModelIntRelInt
1141 */
1142 GECODE_INT_EXPORT void
1143 rel(Home home, IntVar x, IntRelType irt, int c, Reify r,
1144 IntPropLevel ipl=IPL_DEF);
1145 /** \brief Post propagator for relation among elements in \a x.
1146 *
1147 * States that the elements of \a x are in the following relation:
1148 * - if \a r = IRT_LE, \a r = IRT_LQ, \a r = IRT_GR, or \a r = IRT_GQ,
1149 * then the elements of \a x are ordered with respect to \a r.
1150 * Supports domain consistency (\a ipl = IPL_DOM, default).
1151 * - if \a r = IRT_EQ, then all elements of \a x must be equal.
1152 * Supports both bounds (\a ipl = IPL_BND) and
1153 * domain consistency (\a ipl = IPL_DOM, default).
1154 * - if \a r = IRT_NQ, then not all elements of \a x must be equal.
1155 * Supports domain consistency (\a ipl = IPL_DOM, default).
1156 *
1157 * \ingroup TaskModelIntRelInt
1158 */
1159 GECODE_INT_EXPORT void
1160 rel(Home home, const IntVarArgs& x, IntRelType irt,
1161 IntPropLevel ipl=IPL_DEF);
1162 /** \brief Post propagator for relation between \a x and \a y.
1163 *
1164 * Note that for the inequality relations this corresponds to
1165 * the lexical order between \a x and \a y.
1166 *
1167 * Supports both bounds (\a ipl = IPL_BND) and
1168 * domain consistency (\a ipl = IPL_DOM, default).
1169 *
1170 * Note that the constraint is also defined if \a x and \a y are of
1171 * different size. That means that if \a x and \a y are of different
1172 * size, then if \a r = IRT_EQ the constraint is false and if
1173 * \a r = IRT_NQ the constraint is subsumed.
1174 * \ingroup TaskModelIntRelInt
1175 */
1176 GECODE_INT_EXPORT void
1177 rel(Home home, const IntVarArgs& x, IntRelType irt, const IntVarArgs& y,
1178 IntPropLevel ipl=IPL_DEF);
1179 /** \brief Post propagator for relation between \a x and \a y.
1180 *
1181 * Note that for the inequality relations this corresponds to
1182 * the lexical order between \a x and \a y.
1183 *
1184 * Supports domain consistency.
1185 *
1186 * Note that the constraint is also defined if \a x and \a y are of
1187 * different size. That means that if \a x and \a y are of different
1188 * size, then if \a r = IRT_EQ the constraint is false and if
1189 * \a r = IRT_NQ the constraint is subsumed.
1190 * \ingroup TaskModelIntRelInt
1191 */
1192 GECODE_INT_EXPORT void
1193 rel(Home home, const IntVarArgs& x, IntRelType irt, const IntArgs& y,
1194 IntPropLevel ipl=IPL_DEF);
1195 /** \brief Post propagator for relation between \a x and \a y.
1196 *
1197 * Note that for the inequality relations this corresponds to
1198 * the lexical order between \a x and \a y.
1199 *
1200 * Supports domain consistency.
1201 *
1202 * Note that the constraint is also defined if \a x and \a y are of
1203 * different size. That means that if \a x and \a y are of different
1204 * size, then if \a r = IRT_EQ the constraint is false and if
1205 * \a r = IRT_NQ the constraint is subsumed.
1206 * \ingroup TaskModelIntRelInt
1207 */
1208 GECODE_INT_EXPORT void
1209 rel(Home home, const IntArgs& x, IntRelType irt, const IntVarArgs& y,
1210 IntPropLevel ipl=IPL_DEF);
1211
1212 /**
1213 * \defgroup TaskModelIntRelBool Simple relation constraints over Boolean variables
1214 * \ingroup TaskModelInt
1215 */
1216 /** \brief Post domain consistent propagator for \f$ x_0 \sim_{irt} x_1\f$
1217 * \ingroup TaskModelIntRelBool
1218 */
1219 GECODE_INT_EXPORT void
1220 rel(Home home, BoolVar x0, IntRelType irt, BoolVar x1,
1221 IntPropLevel ipl=IPL_DEF);
1222 /** \brief Post domain consistent propagator for \f$(x_0 \sim_{irt} x_1)\equiv r\f$
1223 * \ingroup TaskModelIntRelBool
1224 */
1225 GECODE_INT_EXPORT void
1226 rel(Home home, BoolVar x0, IntRelType irt, BoolVar x1, Reify r,
1227 IntPropLevel ipl=IPL_DEF);
1228 /** \brief Post domain consistent propagator for \f$ x_i \sim_{irt} y \f$ for all \f$0\leq i<|x|\f$
1229 * \ingroup TaskModelIntRelBool
1230 */
1231 GECODE_INT_EXPORT void
1232 rel(Home home, const BoolVarArgs& x, IntRelType irt, BoolVar y,
1233 IntPropLevel ipl=IPL_DEF);
1234 /**
1235 * \brief Propagates \f$ x \sim_{irt} n\f$
1236 *
1237 * Throws an exception of type Int::NotZeroOne, if \a n is neither
1238 * 0 or 1.
1239 * \ingroup TaskModelIntRelBool
1240 */
1241 GECODE_INT_EXPORT void
1242 rel(Home home, BoolVar x, IntRelType irt, int n,
1243 IntPropLevel ipl=IPL_DEF);
1244 /**
1245 * \brief Post domain consistent propagator for \f$(x \sim_{irt} n)\equiv r\f$
1246 *
1247 * Throws an exception of type Int::NotZeroOne, if \a n is neither
1248 * 0 or 1.
1249 * \ingroup TaskModelIntRelBool
1250 */
1251 GECODE_INT_EXPORT void
1252 rel(Home home, BoolVar x, IntRelType irt, int n, Reify r,
1253 IntPropLevel ipl=IPL_DEF);
1254 /**
1255 * \brief Propagates \f$ x_i \sim_{irt} n \f$ for all \f$0\leq i<|x|\f$
1256 *
1257 * Throws an exception of type Int::NotZeroOne, if \a n is neither
1258 * 0 or 1.
1259 * \ingroup TaskModelIntRelBool
1260 */
1261 GECODE_INT_EXPORT void
1262 rel(Home home, const BoolVarArgs& x, IntRelType irt, int n,
1263 IntPropLevel ipl=IPL_DEF);
1264 /** \brief Post domain consistent propagator for relation between \a x and \a y.
1265 *
1266 * Note that for the inequality relations this corresponds to
1267 * the lexical order between \a x and \a y.
1268 *
1269 * Note that the constraint is also defined if \a x and \a y are of
1270 * different size. That means that if \a x and \a y are of different
1271 * size, then if \a r = IRT_EQ the constraint is false and if
1272 * \a r = IRT_NQ the constraint is subsumed.
1273 *
1274 * \ingroup TaskModelIntRelBool
1275 */
1276 GECODE_INT_EXPORT void
1277 rel(Home home, const BoolVarArgs& x, IntRelType irt, const BoolVarArgs& y,
1278 IntPropLevel ipl=IPL_DEF);
1279 /** \brief Post domain consistent propagator for relation between \a x and \a y.
1280 *
1281 * Note that for the inequality relations this corresponds to
1282 * the lexical order between \a x and \a y.
1283 *
1284 * Note that the constraint is also defined if \a x and \a y are of
1285 * different size. That means that if \a x and \a y are of different
1286 * size, then if \a r = IRT_EQ the constraint is false and if
1287 * \a r = IRT_NQ the constraint is subsumed.
1288 *
1289 * \ingroup TaskModelIntRelBool
1290 */
1291 GECODE_INT_EXPORT void
1292 rel(Home home, const BoolVarArgs& x, IntRelType irt, const IntArgs& y,
1293 IntPropLevel ipl=IPL_DEF);
1294 /** \brief Post domain consistent propagator for relation between \a x and \a y.
1295 *
1296 * Note that for the inequality relations this corresponds to
1297 * the lexical order between \a x and \a y.
1298 *
1299 * Note that the constraint is also defined if \a x and \a y are of
1300 * different size. That means that if \a x and \a y are of different
1301 * size, then if \a r = IRT_EQ the constraint is false and if
1302 * \a r = IRT_NQ the constraint is subsumed.
1303 *
1304 * \ingroup TaskModelIntRelBool
1305 */
1306 GECODE_INT_EXPORT void
1307 rel(Home home, const IntArgs& x, IntRelType irt, const BoolVarArgs& y,
1308 IntPropLevel ipl=IPL_DEF);
1309 /** \brief Post domain consistent propagator for relation between elements in \a x.
1310 *
1311 * States that the elements of \a x are in the following relation:
1312 * - if \a r = IRT_LE, \a r = IRT_LQ, \a r = IRT_GR, or \a r = IRT_GQ,
1313 * then the elements of \a x are ordered with respect to \a r.
1314 * - if \a r = IRT_EQ, then all elements of \a x must be equal.
1315 * - if \a r = IRT_NQ, then not all elements of \a x must be equal.
1316 *
1317 * \ingroup TaskModelIntRelBool
1318 */
1319 GECODE_INT_EXPORT void
1320 rel(Home home, const BoolVarArgs& x, IntRelType irt,
1321 IntPropLevel ipl=IPL_DEF);
1322 /** \brief Post domain consistent propagator for Boolean operation on \a x0 and \a x1
1323 *
1324 * Posts propagator for \f$ x_0 \diamond_{\mathit{o}} x_1 = x_2\f$
1325 * \ingroup TaskModelIntRelBool
1326 */
1327 GECODE_INT_EXPORT void
1328 rel(Home home, BoolVar x0, BoolOpType o, BoolVar x1, BoolVar x2,
1329 IntPropLevel ipl=IPL_DEF);
1330 /** \brief Post domain consistent propagator for Boolean operation on \a x0 and \a x1
1331 *
1332 * Posts propagator for \f$ x_0 \diamond_{\mathit{o}} x_1 = n\f$
1333 *
1334 * Throws an exception of type Int::NotZeroOne, if \a n is neither
1335 * 0 or 1.
1336 * \ingroup TaskModelIntRelBool
1337 */
1338 GECODE_INT_EXPORT void
1339 rel(Home home, BoolVar x0, BoolOpType o, BoolVar x1, int n,
1340 IntPropLevel ipl=IPL_DEF);
1341 /** \brief Post domain consistent propagator for Boolean operation on \a x
1342 *
1343 * Posts propagator for \f$ x_0 \diamond_{\mathit{o}} \cdots
1344 * \diamond_{\mathit{o}} x_{|x|-1}= y\f$
1345 *
1346 * Throws an exception of type Int::TooFewArguments, if \f$|x|<2\f$
1347 * and \a o is BOT_IMP, BOT_EQV, or BOT_XOR.
1348 * \ingroup TaskModelIntRelBool
1349 */
1350 GECODE_INT_EXPORT void
1351 rel(Home home, BoolOpType o, const BoolVarArgs& x, BoolVar y,
1352 IntPropLevel ipl=IPL_DEF);
1353 /** \brief Post domain consistent propagator for Boolean operation on \a x
1354 *
1355 * Posts propagator for \f$ x_0 \diamond_{\mathit{o}} \cdots
1356 * \diamond_{\mathit{o}} x_{|x|-1}= n\f$
1357 *
1358 * Throws an exception of type Int::NotZeroOne, if \a n is neither
1359 * 0 or 1.
1360 *
1361 * Throws an exception of type Int::TooFewArguments, if \f$|x|<2\f$
1362 * and \a o is BOT_IMP, BOT_EQV, or BOT_XOR.
1363 * \ingroup TaskModelIntRelBool
1364 */
1365 GECODE_INT_EXPORT void
1366 rel(Home home, BoolOpType o, const BoolVarArgs& x, int n,
1367 IntPropLevel ipl=IPL_DEF);
1368 /** \brief Post domain consistent propagator for Boolean clause with positive variables \a x and negative variables \a y
1369 *
1370 * Posts propagator for \f$ x_0 \diamond_{\mathit{o}} \cdots
1371 * \diamond_{\mathit{o}} x_{|x|-1} \diamond_{\mathit{o}} \neg y_0
1372 * \diamond_{\mathit{o}} \cdots \diamond_{\mathit{o}} \neg y_{|y|-1}= z\f$
1373 *
1374 * Throws an exception of type Int::IllegalOperation, if \a o is different
1375 * from BOT_AND or BOT_OR.
1376 * \ingroup TaskModelIntRelBool
1377 */
1378 GECODE_INT_EXPORT void
1379 clause(Home home, BoolOpType o, const BoolVarArgs& x, const BoolVarArgs& y,
1380 BoolVar z, IntPropLevel ipl=IPL_DEF);
1381 /** \brief Post domain consistent propagator for Boolean clause with positive variables \a x and negative variables \a y
1382 *
1383 * Posts propagator for \f$ x_0 \diamond_{\mathit{o}} \cdots
1384 * \diamond_{\mathit{o}} x_{|x|-1} \diamond_{\mathit{o}} \neg y_0
1385 * \diamond_{\mathit{o}} \cdots \diamond_{\mathit{o}} \neg y_{|y|-1}= n\f$
1386 *
1387 * Throws an exception of type Int::NotZeroOne, if \a n is neither
1388 * 0 or 1.
1389 *
1390 * Throws an exception of type Int::IllegalOperation, if \a o is different
1391 * from BOT_AND or BOT_OR.
1392 * \ingroup TaskModelIntRelBool
1393 */
1394 GECODE_INT_EXPORT void
1395 clause(Home home, BoolOpType o, const BoolVarArgs& x, const BoolVarArgs& y,
1396 int n, IntPropLevel ipl=IPL_DEF);
1397 /** \brief Post propagator for if-then-else constraint
1398 *
1399 * Posts propagator for \f$ z = b ? x : y \f$
1400 *
1401 * Supports both bounds (\a ipl = IPL_BND) and
1402 * domain consistency (\a ipl = IPL_DOM, default).
1403 *
1404 * \ingroup TaskModelIntRelBool
1405 */
1406 GECODE_INT_EXPORT void
1407 ite(Home home, BoolVar b, IntVar x, IntVar y, IntVar z,
1408 IntPropLevel ipl=IPL_DEF);
1409 /** \brief Post propagator for if-then-else constraint
1410 *
1411 * Posts propagator for \f$ z = b ? x : y \f$
1412 *
1413 * \ingroup TaskModelIntRelBool
1414 */
1415 GECODE_INT_EXPORT void
1416 ite(Home home, BoolVar b, BoolVar x, BoolVar y, BoolVar z,
1417 IntPropLevel ipl=IPL_DEF);
1418
1419
1420 /**
1421 * \defgroup TaskModelIntPrecede Value precedence constraints over integer variables
1422 * \ingroup TaskModelInt
1423 */
1424 /** \brief Post propagator that \a s precedes \a t in \a x
1425 *
1426 * This constraint enforces that \f$x_0\neq t\f$ and
1427 * \f$x_j=t \to \bigvee_{0\leq i<j} x_i=s\f$ for \f$0\leq j<|x|\f$.
1428 * The propagator is domain consistent.
1429 * \ingroup TaskModelIntPrecede
1430 */
1431 GECODE_INT_EXPORT void
1432 precede(Home home, const IntVarArgs& x, int s, int t,
1433 IntPropLevel=IPL_DEF);
1434 /** \brief Post propagator that successive values in \a c precede each other in \a x
1435 *
1436 * This constraint enforces that \f$x_0\neq c_k\f$ for \f$0<k<|c|\f$ and
1437 * \f$x_j=c_{k} \to \bigvee_{0\leq i<j} x_i=c_{k-1}\f$ for \f$0\leq j<|x|\f$
1438 * and \f$0< k<|c|\f$.
1439 * \ingroup TaskModelIntPrecede
1440 */
1441 GECODE_INT_EXPORT void
1442 precede(Home home, const IntVarArgs& x, const IntArgs& c,
1443 IntPropLevel=IPL_DEF);
1444
1445
1446 /**
1447 * \defgroup TaskModelIntMember Membership constraints
1448 * \ingroup TaskModelInt
1449 */
1450 //@{
1451 /// Post domain consistent propagator for \f$y\in \{x_0,\ldots,x_{|x|-1}\}\f$
1452 GECODE_INT_EXPORT void
1453 member(Home home, const IntVarArgs& x, IntVar y,
1454 IntPropLevel ipl=IPL_DEF);
1455 /// Post domain consistent propagator for \f$y\in \{x_0,\ldots,x_{|x|-1}\}\f$
1456 GECODE_INT_EXPORT void
1457 member(Home home, const BoolVarArgs& x, BoolVar y,
1458 IntPropLevel ipl=IPL_DEF);
1459 /// Post domain consistent propagator for \f$\left(y\in \{x_0,\ldots,x_{|x|-1}\}\right)\equiv r\f$
1460 GECODE_INT_EXPORT void
1461 member(Home home, const IntVarArgs& x, IntVar y, Reify r,
1462 IntPropLevel ipl=IPL_DEF);
1463 /// Post domain consistent propagator for \f$\left(y\in \{x_0,\ldots,x_{|x|-1}\}\right)\equiv r\f$
1464 GECODE_INT_EXPORT void
1465 member(Home home, const BoolVarArgs& x, BoolVar y, Reify r,
1466 IntPropLevel ipl=IPL_DEF);
1467 //@}
1468
1469
1470 /**
1471 * \defgroup TaskModelIntElement Element constraints
1472 * \ingroup TaskModelInt
1473 */
1474
1475 //@{
1476 /// Arrays of integers that can be shared among several element constraints
1477 typedef SharedArray<int> IntSharedArray;
1478 /** \brief Post domain consistent propagator for \f$ n_{x_0}=x_1\f$
1479 *
1480 * Throws an exception of type Int::OutOfLimits, if
1481 * the integers in \a n exceed the limits in Int::Limits.
1482 */
1483 GECODE_INT_EXPORT void
1484 element(Home home, IntSharedArray n, IntVar x0, IntVar x1,
1485 IntPropLevel ipl=IPL_DEF);
1486 /** \brief Post domain consistent propagator for \f$ n_{x_0+offset}=x_1\f$
1487 *
1488 * Throws an exception of type Int::OutOfLimits, if
1489 * the integers in \a n exceed the limits in Int::Limits.
1490 */
1491 GECODE_INT_EXPORT void
1492 element(Home home, IntSharedArray n, IntVar x0, int offset, IntVar x1,
1493 IntPropLevel ipl=IPL_DEF);
1494 /** \brief Post domain consistent propagator for \f$ n_{x_0}=x_1\f$
1495 *
1496 * Throws an exception of type Int::OutOfLimits, if
1497 * the integers in \a n exceed the limits in Int::Limits.
1498 */
1499 GECODE_INT_EXPORT void
1500 element(Home home, IntSharedArray n, IntVar x0, BoolVar x1,
1501 IntPropLevel ipl=IPL_DEF);
1502 /** \brief Post domain consistent propagator for \f$ n_{x_0+offset}=x_1\f$
1503 *
1504 * Throws an exception of type Int::OutOfLimits, if
1505 * the integers in \a n exceed the limits in Int::Limits.
1506 */
1507 GECODE_INT_EXPORT void
1508 element(Home home, IntSharedArray n, IntVar x0, int offset, BoolVar x1,
1509 IntPropLevel ipl=IPL_DEF);
1510 /** \brief Post domain consistent propagator for \f$ n_{x_0}=x_1\f$
1511 *
1512 * Throws an exception of type Int::OutOfLimits, if
1513 * the integers in \a n exceed the limits in Int::Limits.
1514 */
1515 GECODE_INT_EXPORT void
1516 element(Home home, IntSharedArray n, IntVar x0, int x1,
1517 IntPropLevel ipl=IPL_DEF);
1518 /** \brief Post domain consistent propagator for \f$ n_{x_0+offset}=x_1\f$
1519 *
1520 * Throws an exception of type Int::OutOfLimits, if
1521 * the integers in \a n exceed the limits in Int::Limits.
1522 */
1523 GECODE_INT_EXPORT void
1524 element(Home home, IntSharedArray n, IntVar x0, int offset, int x1,
1525 IntPropLevel ipl=IPL_DEF);
1526 /** \brief Post propagator for \f$ x_{y_0}=y_1\f$
1527 *
1528 * Supports both bounds (\a ipl = IPL_BND) and
1529 * domain consistency (\a ipl = IPL_DOM, default).
1530 */
1531 GECODE_INT_EXPORT void
1532 element(Home home, const IntVarArgs& x, IntVar y0, IntVar y1,
1533 IntPropLevel ipl=IPL_DEF);
1534 /** \brief Post propagator for \f$ x_{y_0+offset}=y_1\f$
1535 *
1536 * Supports both bounds (\a ipl = IPL_BND) and
1537 * domain consistency (\a ipl = IPL_DOM, default).
1538 */
1539 GECODE_INT_EXPORT void
1540 element(Home home, const IntVarArgs& x, IntVar y0, int offset, IntVar y1,
1541 IntPropLevel ipl=IPL_DEF);
1542 /** \brief Post propagator for \f$ x_{y_0}=y_1\f$
1543 *
1544 * Supports both bounds (\a ipl = IPL_BND) and
1545 * domain consistency (\a ipl = IPL_DOM, default).
1546 */
1547 GECODE_INT_EXPORT void
1548 element(Home home, const IntVarArgs& x, IntVar y0, int y1,
1549 IntPropLevel ipl=IPL_DEF);
1550 /** \brief Post propagator for \f$ x_{y_0+offset}=y_1\f$
1551 *
1552 * Supports both bounds (\a ipl = IPL_BND) and
1553 * domain consistency (\a ipl = IPL_DOM, default).
1554 */
1555 GECODE_INT_EXPORT void
1556 element(Home home, const IntVarArgs& x, IntVar y0, int offset, int y1,
1557 IntPropLevel ipl=IPL_DEF);
1558 /// Post domain consistent propagator for \f$ x_{y_0}=y_1\f$
1559 GECODE_INT_EXPORT void
1560 element(Home home, const BoolVarArgs& x, IntVar y0, BoolVar y1,
1561 IntPropLevel ipl=IPL_DEF);
1562 /// Post domain consistent propagator for \f$ x_{y_0+offset}=y_1\f$
1563 GECODE_INT_EXPORT void
1564 element(Home home, const BoolVarArgs& x, IntVar y0, int offset, BoolVar y1,
1565 IntPropLevel ipl=IPL_DEF);
1566 /// Post domain consistent propagator for \f$ x_{y_0}=y_1\f$
1567 GECODE_INT_EXPORT void
1568 element(Home home, const BoolVarArgs& x, IntVar y0, int y1,
1569 IntPropLevel ipl=IPL_DEF);
1570 /// Post domain consistent propagator for \f$ x_{y_0+offset}=y_1\f$
1571 GECODE_INT_EXPORT void
1572 element(Home home, const BoolVarArgs& x, IntVar y0, int offset, int y1,
1573 IntPropLevel ipl=IPL_DEF);
1574
1575 /** \brief Post domain consistent propagator for \f$ a_{x+w\cdot y}=z\f$
1576 *
1577 * If \a a is regarded as a two-dimensional array in row-major
1578 * order of width \a w and height \a h, then \a z is constrained
1579 * to be the element in column \a x and row \a y.
1580 *
1581 * Throws an exception of type Int::OutOfLimits, if
1582 * the integers in \a n exceed the limits in Int::Limits.
1583 *
1584 * Throws an exception of type Int::ArgumentSizeMismatch, if
1585 * \f$ w\cdot h\neq|a|\f$.
1586 */
1587 GECODE_INT_EXPORT void
1588 element(Home home, IntSharedArray a,
1589 IntVar x, int w, IntVar y, int h, IntVar z,
1590 IntPropLevel ipl=IPL_DEF);
1591 /** \brief Post domain consistent propagator for \f$ a_{x+xoff+w\cdot (y+yoff)}=z\f$
1592 *
1593 * If \a a is regarded as a two-dimensional array in row-major
1594 * order of width \a w and height \a h, then \a z is constrained
1595 * to be the element in column \a x and row \a y, offset by
1596 * xoff and yoff.
1597 *
1598 * Throws an exception of type Int::OutOfLimits, if
1599 * the integers in \a n exceed the limits in Int::Limits.
1600 *
1601 * Throws an exception of type Int::ArgumentSizeMismatch, if
1602 * \f$ w\cdot h\neq|a|\f$.
1603 */
1604 GECODE_INT_EXPORT void
1605 element(Home home, IntSharedArray a,
1606 IntVar x, int xoff, int w, IntVar y, int yoff, int h, IntVar z,
1607 IntPropLevel ipl=IPL_DEF);
1608 /** \brief Post domain consistent propagator for \f$ a_{x+w\cdot y}=z\f$
1609 *
1610 * If \a a is regarded as a two-dimensional array in row-major
1611 * order of width \a w and height \a h, then \a z is constrained
1612 * to be the element in column \a x and row \a y.
1613 *
1614 * Throws an exception of type Int::OutOfLimits, if
1615 * the integers in \a n exceed the limits in Int::Limits.
1616 *
1617 * Throws an exception of type Int::ArgumentSizeMismatch, if
1618 * \f$ w\cdot h\neq|a|\f$.
1619 */
1620 GECODE_INT_EXPORT void
1621 element(Home home, IntSharedArray a,
1622 IntVar x, int w, IntVar y, int h, BoolVar z,
1623 IntPropLevel ipl=IPL_DEF);
1624 /** \brief Post domain consistent propagator for \f$ a_{x+xoff+w\cdot (y+yoff)}=z\f$
1625 *
1626 * If \a a is regarded as a two-dimensional array in row-major
1627 * order of width \a w and height \a h, then \a z is constrained
1628 * to be the element in column \a x and row \a y, offset by
1629 * xoff and yoff.
1630 *
1631 * Throws an exception of type Int::OutOfLimits, if
1632 * the integers in \a n exceed the limits in Int::Limits.
1633 *
1634 * Throws an exception of type Int::ArgumentSizeMismatch, if
1635 * \f$ w\cdot h\neq|a|\f$.
1636 */
1637 GECODE_INT_EXPORT void
1638 element(Home home, IntSharedArray a,
1639 IntVar x, int xoff, int w, IntVar y, int yoff, int h, BoolVar z,
1640 IntPropLevel ipl=IPL_DEF);
1641 /** \brief Post propagator for \f$ a_{x+w\cdot y}=z\f$
1642 *
1643 * If \a a is regarded as a two-dimensional array in row-major
1644 * order of width \a w and height \a h, then \a z is constrained
1645 * to be the element in column \a x and row \a y.
1646 *
1647 * Supports both bounds (\a ipl = IPL_BND) and
1648 * domain consistency (\a ipl = IPL_DOM, default).
1649 *
1650 * Throws an exception of type Int::OutOfLimits, if
1651 * the integers in \a n exceed the limits in Int::Limits.
1652 *
1653 * Throws an exception of type Int::ArgumentSizeMismatch, if
1654 * \f$ w\cdot h\neq|a|\f$.
1655 */
1656 GECODE_INT_EXPORT void
1657 element(Home home, const IntVarArgs& a,
1658 IntVar x, int w, IntVar y, int h, IntVar z,
1659 IntPropLevel ipl=IPL_DEF);
1660 /** \brief Post propagator for \f$ a_{x+xoff+w\cdot (y+yoff)}=z\f$
1661 *
1662 * If \a a is regarded as a two-dimensional array in row-major
1663 * order of width \a w and height \a h, then \a z is constrained
1664 * to be the element in column \a x and row \a y, offset by
1665 * xoff and yoff.
1666 *
1667 * Supports both bounds (\a ipl = IPL_BND) and
1668 * domain consistency (\a ipl = IPL_DOM, default).
1669 *
1670 * Throws an exception of type Int::OutOfLimits, if
1671 * the integers in \a n exceed the limits in Int::Limits.
1672 *
1673 * Throws an exception of type Int::ArgumentSizeMismatch, if
1674 * \f$ w\cdot h\neq|a|\f$.
1675 */
1676 GECODE_INT_EXPORT void
1677 element(Home home, const IntVarArgs& a,
1678 IntVar x, int xoff, int w, IntVar y, int yoff, int h, IntVar z,
1679 IntPropLevel ipl=IPL_DEF);
1680 /** \brief Post domain consistent propagator for \f$ a_{x+w\cdot y}=z\f$
1681 *
1682 * If \a a is regarded as a two-dimensional array in row-major
1683 * order of width \a w and height \a h, then \a z is constrained
1684 * to be the element in column \a x and row \a y.
1685 *
1686 * Throws an exception of type Int::OutOfLimits, if
1687 * the integers in \a n exceed the limits in Int::Limits.
1688 *
1689 * Throws an exception of type Int::ArgumentSizeMismatch, if
1690 * \f$ w\cdot h\neq|a|\f$.
1691 */
1692 GECODE_INT_EXPORT void
1693 element(Home home, const BoolVarArgs& a,
1694 IntVar x, int w, IntVar y, int h, BoolVar z,
1695 IntPropLevel ipl=IPL_DEF);
1696 /** \brief Post domain consistent propagator for \f$ a_{x+xoff+w\cdot (y+yoff)}=z\f$
1697 *
1698 * If \a a is regarded as a two-dimensional array in row-major
1699 * order of width \a w and height \a h, then \a z is constrained
1700 * to be the element in column \a x and row \a y, offset by
1701 * xoff and yoff.
1702 *
1703 * Throws an exception of type Int::OutOfLimits, if
1704 * the integers in \a n exceed the limits in Int::Limits.
1705 *
1706 * Throws an exception of type Int::ArgumentSizeMismatch, if
1707 * \f$ w\cdot h\neq|a|\f$.
1708 */
1709 GECODE_INT_EXPORT void
1710 element(Home home, const BoolVarArgs& a,
1711 IntVar x, int xoff, int w, IntVar y, int yoff, int h, BoolVar z,
1712 IntPropLevel ipl=IPL_DEF);
1713 //@}
1714
1715
1716 /**
1717 * \defgroup TaskModelIntDistinct Distinct constraints
1718 * \ingroup TaskModelInt
1719 */
1720
1721 //@{
1722 /** \brief Post propagator for \f$ x_i\neq x_j\f$ for all \f$0\leq i\neq j<|x|\f$
1723 *
1724 * Supports value (\a ipl = IPL_VAL, default), bounds (\a ipl = IPL_BND),
1725 * and domain consistency (\a ipl = IPL_DOM).
1726 *
1727 * Throws an exception of type Int::ArgumentSame, if \a x contains
1728 * the same unassigned variable multiply.
1729 */
1730 GECODE_INT_EXPORT void
1731 distinct(Home home, const IntVarArgs& x,
1732 IntPropLevel ipl=IPL_DEF);
1733 /** \brief Post propagator for \f$ x_i+n_i\neq x_j+n_j\f$ for all \f$0\leq i\neq j<|x|\f$
1734 *
1735 * \li Supports value (\a ipl = IPL_VAL, default), bounds (\a ipl = IPL_BND),
1736 * and domain consistency (\a ipl = IPL_DOM).
1737 * \li Throws an exception of type Int::OutOfLimits, if
1738 * the integers in \a n exceed the limits in Int::Limits
1739 * or if the sum of \a n and \a x exceed the limits.
1740 * \li Throws an exception of type Int::ArgumentSizeMismatch, if
1741 * \a x and \a n are of different size.
1742 * \li Throws an exception of type Int::ArgumentSame, if \a x contains
1743 * the same unassigned variable multiply.
1744 */
1745 GECODE_INT_EXPORT void
1746 distinct(Home home, const IntArgs& n, const IntVarArgs& x,
1747 IntPropLevel ipl=IPL_DEF);
1748 /** \brief Post propagator for \f$ b_i=1\wedge b_j=1\to x_i\neq x_j\f$ for all \f$0\leq i\neq j<|x|\f$
1749 *
1750 * \li Supports value (\a ipl = IPL_VAL, default), bounds (\a ipl = IPL_BND),
1751 * and domain consistency (\a ipl = IPL_DOM).
1752 * \li Throws an exception of type Int::OutOfLimits, if
1753 * the variable domains in \a x are too large (it must hold that
1754 * one of the values \f$(\max_{i=0,\ldots,|x|-1} \max(x_i))+|x|\f$
1755 * and \f$(\min_{i=0,\ldots,|x|-1} \min(x_i))-|x|\f$
1756 * does not exceed the limits in Int::Limits.
1757 * \li Throws an exception of type Int::ArgumentSizeMismatch, if
1758 * \a b and \a x are of different size.
1759 * \li Throws an exception of type Int::ArgumentSame, if \a x
1760 * contains the same unassigned variable multiply.
1761 */
1762 GECODE_INT_EXPORT void
1763 distinct(Home home, const BoolVarArgs& b, const IntVarArgs& x,
1764 IntPropLevel ipl=IPL_DEF);
1765 /** \brief Post propagator for \f$ x_i=c\vee x_j=c\vee x_i\neq x_j\f$ for all \f$0\leq i\neq j<|x|\f$
1766 *
1767 * \li Supports value (\a ipl = IPL_VAL, default), bounds (\a ipl = IPL_BND),
1768 * and domain consistency (\a ipl = IPL_DOM).
1769 * \li Throws an exception of type Int::OutOfLimits, if
1770 * the variable domains in \a x are too large (it must hold that
1771 * one of the values \f$(\max_{i=0,\ldots,|x|-1} \max(x_i))+|x|\f$
1772 * and \f$(\min_{i=0,\ldots,|x|-1} \min(x_i))-|x|\f$
1773 * does not exceed the limits in Int::Limits.
1774 * \li Throws an exception of type Int::ArgumentSame, if \a x
1775 * contains the same unassigned variable multiply.
1776 */
1777 GECODE_INT_EXPORT void
1778 distinct(Home home, const IntVarArgs& x, int c,
1779 IntPropLevel ipl=IPL_DEF);
1780 //@}
1781
1782
1783 /**
1784 * \defgroup TaskModelIntChannel Channel constraints
1785 * \ingroup TaskModelInt
1786 */
1787
1788 //@{
1789 /** \brief Post propagator for \f$ x_i = j\leftrightarrow y_j=i\f$ for all \f$0\leq i<|x|\f$
1790 *
1791 * \li Supports domain consistency (\a ipl = IPL_DOM) and value
1792 * propagation (all other values for \a ipl, default).
1793 * \li Throws an exception of type Int::ArgumentSizeMismatch, if
1794 * \a x and \a y are of different size.
1795 * \li Throws an exception of type Int::ArgumentSame, if \a x or
1796 * \a y contain the same unassigned variable multiply. Note that a
1797 * variable can occur in both \a x and \a y, but not more than
1798 * once in either \a x or \a y.
1799 */
1800 GECODE_INT_EXPORT void
1801 channel(Home home, const IntVarArgs& x, const IntVarArgs& y,
1802 IntPropLevel ipl=IPL_DEF);
1803
1804 /** \brief Post propagator for \f$ x_i - \mathit{xoff} = j\leftrightarrow y_j - \mathit{yoff} = i\f$ for all \f$0\leq i<|x|\f$
1805 *
1806 * \li Supports domain consistency (\a ipl = IPL_DOM) and value
1807 * propagation (all other values for \a ipl, default).
1808 * \li Throws an exception of type Int::ArgumentSizeMismatch, if
1809 * \a x and \a y are of different size.
1810 * \li Throws an exception of type Int::ArgumentSame, if \a x or
1811 * \a y contain the same unassigned variable multiply. Note that a
1812 * variable can occur in both \a x and \a y, but not more than
1813 * once in either \a x or \a y.
1814 * \li Throws an exception of type Int::OutOfLimits, if \a xoff or
1815 * \a yoff are negative.
1816 */
1817 GECODE_INT_EXPORT void
1818 channel(Home home, const IntVarArgs& x, int xoff,
1819 const IntVarArgs& y, int yoff,
1820 IntPropLevel ipl=IPL_DEF);
1821
1822 /// Post domain consistent propagator for channeling a Boolean and an integer variable \f$ x_0 = x_1\f$
1823 GECODE_INT_EXPORT void
1824 channel(Home home, BoolVar x0, IntVar x1,
1825 IntPropLevel ipl=IPL_DEF);
1826 /// Post domain consistent propagator for channeling an integer and a Boolean variable \f$ x_0 = x_1\f$
1827 void
1828 channel(Home home, IntVar x0, BoolVar x1,
1829 IntPropLevel ipl=IPL_DEF);
1830 /** \brief Post domain consistent propagator for channeling Boolean and integer variables \f$ x_i = 1\leftrightarrow y=i+o\f$
1831 *
1832 * Throws an exception of type Int::ArgumentSame, if \a x
1833 * contains the same unassigned variable multiply.
1834 */
1835 GECODE_INT_EXPORT void
1836 channel(Home home, const BoolVarArgs& x, IntVar y, int o=0,
1837 IntPropLevel ipl=IPL_DEF);
1838 //@}
1839
1840}
1841
1842#include <gecode/int/channel.hpp>
1843
1844namespace Gecode {
1845
1846 /**
1847 * \defgroup TaskModelIntSorted Sorted constraints
1848 *
1849 * All sorted constraints support bounds consistency only.
1850 *
1851 * \ingroup TaskModelInt
1852 */
1853 //@{
1854 /**
1855 * \brief Post propagator that \a y is \a x sorted in increasing order
1856 *
1857 * Might throw the following exceptions:
1858 * - Int::ArgumentSizeMismatch, if \a x and \a y differ in size.
1859 * - Int::ArgumentSame, if \a x or \a y contain
1860 * shared unassigned variables.
1861 */
1862 GECODE_INT_EXPORT void
1863 sorted(Home home, const IntVarArgs& x, const IntVarArgs& y,
1864 IntPropLevel ipl=IPL_DEF);
1865
1866 /**
1867 * \brief Post propagator that \a y is \a x sorted in increasing order
1868 *
1869 * The values in \a z describe the sorting permutation, that is
1870 * \f$\forall i\in\{0,\dots,|x|-1\}: x_i=y_{z_i} \f$.
1871 *
1872 * Might throw the following exceptions:
1873 * - Int::ArgumentSizeMismatch, if \a x and \a y differ in size.
1874 * - Int::ArgumentSame, if \a x or \a y contain
1875 * shared unassigned variables.
1876 */
1877 GECODE_INT_EXPORT void
1878 sorted(Home home, const IntVarArgs& x, const IntVarArgs& y,
1879 const IntVarArgs& z,
1880 IntPropLevel ipl=IPL_DEF);
1881 //@}
1882
1883
1884 /**
1885 * \defgroup TaskModelIntCount Counting constraints
1886 * \ingroup TaskModelInt
1887 *
1888 * \note
1889 * Domain consistency on the extended cardinality variables of
1890 * the Global Cardinality Propagator is only obtained if they are bounds
1891 * consistent, otherwise the problem of enforcing domain consistency
1892 * on the cardinality variables is NP-complete as proved by
1893 * Qumiper et. al. in
1894 * ''Improved Algorithms for the Global Cardinality Constraint''.
1895 */
1896
1897 //@{
1898 /** \brief Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=n\}\sim_{irt} m\f$
1899 *
1900 * Performs domain propagation but is not domain consistent.
1901 */
1902 GECODE_INT_EXPORT void
1903 count(Home home, const IntVarArgs& x, int n, IntRelType irt, int m,
1904 IntPropLevel ipl=IPL_DEF);
1905 /** \brief Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i\in y\}\sim_{irt} m\f$
1906 *
1907 * Performs domain propagation but is not domain consistent.
1908 */
1909 GECODE_INT_EXPORT void
1910 count(Home home, const IntVarArgs& x, const IntSet& y, IntRelType irt, int m,
1911 IntPropLevel ipl=IPL_DEF);
1912 /** \brief Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\sim_{irt} m\f$
1913 *
1914 * Performs domain propagation (\a ipl = IPL_DOM, default)
1915 * and slightly less domain propagation (all other values for \a ipl),
1916 * where \a y is not pruned. Note that in both cases propagation
1917 * is not domain consistent.
1918 */
1919 GECODE_INT_EXPORT void
1920 count(Home home, const IntVarArgs& x, IntVar y, IntRelType irt, int m,
1921 IntPropLevel ipl=IPL_DEF);
1922 /** \brief Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y_i\}\sim_{irt} m\f$
1923 *
1924 * Performs domain propagation but is not domain consistent.
1925 *
1926 * Throws an exception of type Int::ArgumentSizeMismatch, if
1927 * \a x and \a y are of different size.
1928 */
1929 GECODE_INT_EXPORT void
1930 count(Home home, const IntVarArgs& x, const IntArgs& y, IntRelType irt, int m,
1931 IntPropLevel ipl=IPL_DEF);
1932 /** \brief Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=n\}\sim_{irt} z\f$
1933 *
1934 * Performs domain propagation but is not domain consistent.
1935 */
1936 GECODE_INT_EXPORT void
1937 count(Home home, const IntVarArgs& x, int n, IntRelType irt, IntVar z,
1938 IntPropLevel ipl=IPL_DEF);
1939 /** \brief Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i\in y\}\sim_{irt} z\f$
1940 *
1941 * Performs domain propagation but is not domain consistent.
1942 */
1943 GECODE_INT_EXPORT void
1944 count(Home home, const IntVarArgs& x, const IntSet& y, IntRelType irt, IntVar z,
1945 IntPropLevel ipl=IPL_DEF);
1946 /** \brief Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\sim_{irt} z\f$
1947 *
1948 * Performs domain propagation (\a ipl = IPL_DOM, default)
1949 * and slightly less domain propagation (all other values for \a ipl),
1950 * where \a y is not pruned. Note that in both cases propagation
1951 * is not domain consistent.
1952 */
1953 GECODE_INT_EXPORT void
1954 count(Home home, const IntVarArgs& x, IntVar y, IntRelType irt, IntVar z,
1955 IntPropLevel ipl=IPL_DEF);
1956 /** \brief Post propagator for \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y_i\}\sim_{irt} z\f$
1957 *
1958 * Performs domain propagation but is not domain consistent.
1959 *
1960 * Throws an exception of type Int::ArgumentSizeMismatch, if
1961 * \a x and \a y are of different size.
1962 */
1963 GECODE_INT_EXPORT void
1964 count(Home home, const IntVarArgs& x, const IntArgs& y, IntRelType irt, IntVar z,
1965 IntPropLevel ipl=IPL_DEF);
1966
1967 /** \brief Posts a global count (cardinality) constraint
1968 *
1969 * Posts the constraint that
1970 * \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=j\}=c_j\f$ and
1971 * \f$ \bigcup_i \{x_i\} \subseteq \{0,\ldots,|c|-1\}\f$
1972 * (no other value occurs).
1973 *
1974 * Supports value (\a ipl = IPL_VAL, default), bounds (\a ipl = IPL_BND),
1975 * and domain consistency (\a ipl = IPL_DOM).
1976 *
1977 * Throws an exception of type Int::ArgumentSame, if \a x contains
1978 * the same unassigned variable multiply.
1979 */
1980 GECODE_INT_EXPORT void
1981 count(Home home, const IntVarArgs& x, const IntVarArgs& c,
1982 IntPropLevel ipl=IPL_DEF);
1983
1984 /** \brief Posts a global count (cardinality) constraint
1985 *
1986 * Posts the constraint that
1987 * \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=j\}\in c_j\f$ and
1988 * \f$ \bigcup_i \{x_i\} \subseteq \{0,\ldots,|c|-1\}\f$
1989 * (no other value occurs).
1990 *
1991 * Supports value (\a ipl = IPL_VAL, default), bounds (\a ipl = IPL_BND),
1992 * and domain consistency (\a ipl = IPL_DOM).
1993 *
1994 * Throws an exception of type Int::ArgumentSame, if \a x contains
1995 * the same unassigned variable multiply.
1996 */
1997 GECODE_INT_EXPORT void
1998 count(Home home, const IntVarArgs& x, const IntSetArgs& c,
1999 IntPropLevel ipl=IPL_DEF);
2000
2001 /** \brief Posts a global count (cardinality) constraint
2002 *
2003 * Posts the constraint that
2004 * \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=v_j\}=c_j\f$ and
2005 * \f$ \bigcup_i \{x_i\} \subseteq \bigcup_j \{v_j\}\f$
2006 * (no other value occurs).
2007 *
2008 * Supports value (\a ipl = IPL_VAL, default), bounds (\a ipl = IPL_BND),
2009 * and domain consistency (\a ipl = IPL_DOM).
2010 *
2011 * Throws an exception of type Int::ArgumentSame, if \a x contains
2012 * the same unassigned variable multiply.
2013 *
2014 * Throws an exception of type Int::ArgumentSizeMismatch, if
2015 * \a c and \a v are of different size.
2016 */
2017 GECODE_INT_EXPORT void
2018 count(Home home, const IntVarArgs& x,
2019 const IntVarArgs& c, const IntArgs& v,
2020 IntPropLevel ipl=IPL_DEF);
2021
2022 /** \brief Posts a global count (cardinality) constraint
2023 *
2024 * Posts the constraint that
2025 * \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=v_j\}\in c_j\f$ and
2026 * \f$ \bigcup_i \{x_i\} \subseteq \bigcup_j \{v_j\}\f$
2027 * (no other value occurs).
2028 *
2029 * Supports value (\a ipl = IPL_VAL, default), bounds (\a ipl = IPL_BND),
2030 * and domain consistency (\a ipl = IPL_DOM).
2031 *
2032 * Throws an exception of type Int::ArgumentSame, if \a x contains
2033 * the same unassigned variable multiply.
2034 *
2035 * Throws an exception of type Int::ArgumentSizeMismatch, if
2036 * \a c and \a v are of different size.
2037 */
2038 GECODE_INT_EXPORT void
2039 count(Home home, const IntVarArgs& x,
2040 const IntSetArgs& c, const IntArgs& v,
2041 IntPropLevel ipl=IPL_DEF);
2042
2043 /** \brief Posts a global count (cardinality) constraint
2044 *
2045 * Posts the constraint that
2046 * \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=v_j\}\in c\f$ and
2047 * \f$ \bigcup_i \{x_i\} \subseteq \bigcup_j \{v_j\}\f$
2048 * (no other value occurs).
2049 *
2050 * Supports value (\a ipl = IPL_VAL, default), bounds (\a ipl = IPL_BND),
2051 * and domain consistency (\a ipl = IPL_DOM).
2052 *
2053 * Throws an exception of type Int::ArgumentSame, if \a x contains
2054 * the same unassigned variable multiply.
2055 *
2056 * Throws an exception of type Int::ArgumentSizeMismatch, if
2057 * \a c and \a v are of different size.
2058 */
2059 GECODE_INT_EXPORT void
2060 count(Home home, const IntVarArgs& x,
2061 const IntSet& c, const IntArgs& v,
2062 IntPropLevel ipl=IPL_DEF);
2063
2064 //@}
2065
2066 /**
2067 * \defgroup TaskModelIntNValues Number of values constraints
2068 * \ingroup TaskModelInt
2069 *
2070 * The number of values constraints perform propagation
2071 * following: C. Bessiere, E. Hebrard, B. Hnich, Z. Kiziltan,
2072 * and T. Walsh, Filtering Algorithms for the NValue
2073 * Constraint, Constraints, 11(4), 271-293, 2006.
2074 */
2075
2076 //@{
2077 /** \brief Post propagator for \f$\#\{x_0,\ldots,x_{|x|-1}\}\sim_{irt} y\f$
2078 *
2079 */
2080 GECODE_INT_EXPORT void
2081 nvalues(Home home, const IntVarArgs& x, IntRelType irt, int y,
2082 IntPropLevel ipl=IPL_DEF);
2083 /** \brief Post propagator for \f$\#\{x_0,\ldots,x_{|x|-1}\}\sim_{irt} y\f$
2084 *
2085 */
2086 GECODE_INT_EXPORT void
2087 nvalues(Home home, const IntVarArgs& x, IntRelType irt, IntVar y,
2088 IntPropLevel ipl=IPL_DEF);
2089 /** \brief Post propagator for \f$\#\{x_0,\ldots,x_{|x|-1}\}\sim_{irt} y\f$
2090 *
2091 */
2092 GECODE_INT_EXPORT void
2093 nvalues(Home home, const BoolVarArgs& x, IntRelType irt, int y,
2094 IntPropLevel ipl=IPL_DEF);
2095 /** \brief Post propagator for \f$\#\{x_0,\ldots,x_{|x|-1}\}\sim_{irt} y\f$
2096 *
2097 */
2098 GECODE_INT_EXPORT void
2099 nvalues(Home home, const BoolVarArgs& x, IntRelType irt, IntVar y,
2100 IntPropLevel ipl=IPL_DEF);
2101 //@}
2102
2103 /**
2104 * \defgroup TaskModelIntSequence Sequence constraints
2105 * \ingroup TaskModelInt
2106 */
2107
2108 //@{
2109 /** \brief Post propagator for \f$\operatorname{sequence}(x,s,q,l,u)\f$
2110 *
2111 * Posts a domain consistent propagator for the constraint
2112 * \f$\bigwedge_{i=0}^{|x|-q}
2113 * \operatorname{among}(\langle x_i,\ldots,x_{i+q-1}\rangle,s,l,u)\f$
2114 * where the among constraint is defined as
2115 * \f$l\leq\#\{j\in\{i,\ldots,i+q-1\}\;|\;x_j\in s\} \leq u\f$.
2116 *
2117 * Throws the following exceptions:
2118 * - Of type Int::TooFewArguments, if \f$|x|=0\f$.
2119 * - Of type Int::ArgumentSame, if \a x contains
2120 * the same unassigned variable multiply.
2121 * - Of type Int::OutOfRange, if \f$q < 1 \vee q > |x|\f$.
2122 */
2123 GECODE_INT_EXPORT void
2124 sequence(Home home, const IntVarArgs& x, const IntSet& s,
2125 int q, int l, int u, IntPropLevel ipl=IPL_DEF);
2126
2127 /** \brief Post propagator for \f$\operatorname{sequence}(x,s,q,l,u)\f$
2128 *
2129 * Posts a domain consistent propagator for the constraint
2130 * \f$\bigwedge_{i=0}^{|x|-q}
2131 * \operatorname{among}(\langle x_i,\ldots,x_{i+q-1}\rangle,s,l,u)\f$
2132 * where the among constraint is defined as
2133 * \f$l\leq\#\{j\in\{i,\ldots,i+q-1\}\;|\;x_j\in s\} \leq u\f$.
2134 *
2135 * Throws the following exceptions:
2136 * - Of type Int::TooFewArguments, if \f$|x|=0\f$.
2137 * - Of type Int::ArgumentSame, if \a x contains
2138 * the same unassigned variable multiply.
2139 * - Of type Int::OutOfRange, if \f$q < 1 \vee q > |x|\f$.
2140 */
2141 GECODE_INT_EXPORT void
2142 sequence(Home home, const BoolVarArgs& x, const IntSet& s,
2143 int q, int l, int u, IntPropLevel ipl=IPL_DEF);
2144
2145 //@}
2146
2147 /**
2148 * \defgroup TaskModelIntExt Extensional constraints
2149 * \ingroup TaskModelInt
2150 *
2151 * Extensional constraints support different ways of how the
2152 * extensionally defined relation between the variables is defined.
2153 * Examples include specification by a %DFA or a table.
2154 *
2155 * A %DFA can be defined by a regular expression, for regular expressions
2156 * see the module MiniModel.
2157 */
2158
2159 /**
2160 * \brief Deterministic finite automaton (%DFA)
2161 *
2162 * After initialization, the start state is always zero.
2163 * The final states are contiguous ranging from the first to the
2164 * last final state.
2165 *
2166 * \ingroup TaskModelIntExt
2167 */
2168 class DFA : public SharedHandle {
2169 private:
2170 /// Implementation of DFA
2171 class DFAI;
2172 /// Test whether DFA is equal to \a d
2173 GECODE_INT_EXPORT
2174 bool equal(const DFA& d) const;
2175 public:
2176 /// Specification of a %DFA transition
2177 class Transition {
2178 public:
2179 int i_state; ///< input state
2180 int symbol; ///< symbol
2181 int o_state; ///< output state
2182 /// Default constructor
2183 Transition(void);
2184 /// Initialize members
2185 Transition(int i_state0, int symbol0, int o_state0);
2186 };
2187 /// Iterator for %DFA transitions (sorted by symbols)
2188 class Transitions {
2189 private:
2190 /// Current transition
2191 const Transition* c_trans;
2192 /// End of transitions
2193 const Transition* e_trans;
2194 public:
2195 /// Initialize to all transitions of DFA \a d
2196 Transitions(const DFA& d);
2197 /// Initialize to transitions of DFA \a d for symbol \a n
2198 Transitions(const DFA& d, int n);
2199 /// Test whether iterator still at a transition
2200 bool operator ()(void) const;
2201 /// Move iterator to next transition
2202 void operator ++(void);
2203 /// Return in-state of current transition
2204 int i_state(void) const;
2205 /// Return symbol of current transition
2206 int symbol(void) const;
2207 /// Return out-state of current transition
2208 int o_state(void) const;
2209 };
2210 /// Iterator for %DFA symbols
2211 class Symbols {
2212 private:
2213 /// Current transition
2214 const Transition* c_trans;
2215 /// End of transitions
2216 const Transition* e_trans;
2217 public:
2218 /// Initialize to symbols of DFA \a d
2219 Symbols(const DFA& d);
2220 /// Test whether iterator still at a symbol
2221 bool operator ()(void) const;
2222 /// Move iterator to next symbol
2223 void operator ++(void);
2224 /// Return current symbol
2225 int val(void) const;
2226 };
2227 /**
2228 * \brief Initialize DFA
2229 *
2230 * - Start state is given by \a s.
2231 * - %Transitions are described by \a t, where the last element
2232 * must have -1 as value for \c i_state.
2233 * - Final states are given by \a f, where the last final element
2234 * must be -1.
2235 * - Minimizes the DFA, if \a minimize is true.
2236 * - Note that the transitions must be deterministic.
2237 */
2238 GECODE_INT_EXPORT
2239 void init(int s, Transition t[], int f[], bool minimize=true);
2240 public:
2241 friend class Transitions;
2242 /// Initialize for DFA accepting the empty word
2243 DFA(void);
2244 /**
2245 * \brief Initialize DFA
2246 *
2247 * - Start state is given by \a s.
2248 * - %Transitions are described by \a t, where the last element
2249 * must have -1 as value for \c i_state.
2250 * - Final states are given by \a f, where the last final element
2251 * must be -1.
2252 * - Minimizes the DFA, if \a minimize is true.
2253 * - Note that the transitions must be deterministic.
2254 */
2255 GECODE_INT_EXPORT
2256 DFA(int s, Transition t[], int f[], bool minimize=true);
2257 /**
2258 * \brief Initialize DFA
2259 *
2260 * - Start state is given by \a s.
2261 * - %Transitions are described by \a t.
2262 * - Final states are given by \a f.
2263 * - Minimizes the DFA, if \a minimize is true.
2264 * - Note that the transitions must be deterministic.
2265 */
2266 GECODE_INT_EXPORT
2267 DFA(int s, std::initializer_list<Transition> t,
2268 std::initializer_list<int> f, bool minimize=true);
2269 /// Initialize by DFA \a d (DFA is shared)
2270 DFA(const DFA& d);
2271 /// Test whether DFA is equal to \a d
2272 GECODE_INT_EXPORT
2273 bool operator ==(const DFA& d) const;
2274 /// Test whether DFA is not equal to \a d
2275 bool operator !=(const DFA& d) const;
2276 /// Return the number of states
2277 int n_states(void) const;
2278 /// Return the number of transitions
2279 int n_transitions(void) const;
2280 /// Return the number of symbols
2281 unsigned int n_symbols(void) const;
2282 /// Return maximal degree (in-degree and out-degree) of any state
2283 unsigned int max_degree(void) const;
2284 /// Return the number of the first final state
2285 int final_fst(void) const;
2286 /// Return the number of the last final state
2287 int final_lst(void) const;
2288 /// Return smallest symbol in DFA
2289 int symbol_min(void) const;
2290 /// Return largest symbol in DFA
2291 int symbol_max(void) const;
2292 /// Return hash key
2293 std::size_t hash(void) const;
2294 };
2295
2296}
2297
2298#include <gecode/int/extensional/dfa.hpp>
2299
2300namespace Gecode {
2301
2302 /** \brief Class represeting a set of tuples.
2303 *
2304 * A TupleSet is used for storing an extensional representation of a
2305 * constraint. After a TupleSet is finalized, no more tuples may be
2306 * added to it.
2307 *
2308 * \ingroup TaskModelIntExt
2309 */
2310 class TupleSet : public SharedHandle {
2311 public:
2312 /** \brief Type of a tuple
2313 *
2314 * The arity of the tuple is left implicit.
2315 */
2316 typedef int* Tuple;
2317 /// Import bit set data type
2318 typedef Gecode::Support::BitSetData BitSetData;
2319 /// Range information
2320 class Range {
2321 public:
2322 /// Minimum value
2323 int min;
2324 /// Maximum value
2325 int max;
2326 /// Begin of supports
2327 BitSetData* s;
2328 /// Return the width
2329 unsigned int width(void) const;
2330 /// Return the supports for value \a n
2331 const BitSetData* supports(unsigned int n_words, int n) const;
2332 };
2333 protected:
2334 /// Data about values in the table
2335 class ValueData {
2336 public:
2337 /// Number of ranges
2338 unsigned int n;
2339 /// Ranges
2340 Range* r;
2341 /// Find start range for value \a n
2342 unsigned int start(int n) const;
2343 };
2344 /**
2345 * \brief Data stored for a Table
2346 *
2347 */
2348 class GECODE_VTABLE_EXPORT Data : public SharedHandle::Object {
2349 protected:
2350 /// Initial number of free tuples
2351 static const int n_initial_free = 1024;
2352 public:
2353 /// Arity
2354 int arity;
2355 /// Number of words for support
2356 unsigned int n_words;
2357 /// Number of Tuples
2358 int n_tuples;
2359 /// Number of free tuple entries of arity
2360 int n_free;
2361 /// Smallest value
2362 int min;
2363 /// Largest value
2364 int max;
2365 /// Hash key
2366 std::size_t key;
2367 /// Tuple data
2368 int* td;
2369 /// Value data
2370 ValueData* vd;
2371 /// Pointer to all ranges
2372 Range* range;
2373 /// Pointer to all support data
2374 BitSetData* support;
2375
2376 /// Return newly added tuple
2377 Tuple add(void);
2378 /// Return tuple with number \a i
2379 Tuple get(int i) const;
2380 /// Set bit \a n in bitset data \a d
2381 static void set(BitSetData* d, unsigned int n);
2382 /// Get bit \a n in bitset data \a d
2383 static bool get(const BitSetData* d, unsigned int n);
2384 /// Map tuple address to index
2385 unsigned int tuple2idx(Tuple t) const;
2386 /// Return first range for position \a i
2387 const Range* fst(int i) const;
2388 /// Return last range for position \a i
2389 const Range* lst(int i) const;
2390 /// Finalize datastructure (disallows additions of more Tuples)
2391 GECODE_INT_EXPORT
2392 void finalize(void);
2393 /// Resize tuple data
2394 GECODE_INT_EXPORT
2395 void resize(void);
2396 /// Is datastructure finalized
2397 bool finalized(void) const;
2398 /// Initialize as empty tuple set with arity \a a
2399 Data(int a);
2400 /// Delete implementation
2401 GECODE_INT_EXPORT
2402 virtual ~Data(void);
2403 };
2404
2405 /// Get data (must be initialized and finalized)
2406 Data& data(void) const;
2407 /// Get raw data (must be initialized)
2408 Data& raw(void) const;
2409 /// Add tuple \a t to tuple set
2410 GECODE_INT_EXPORT
2411 void _add(const IntArgs& t);
2412 /// Test whether tuple set is equal to \a t
2413 GECODE_INT_EXPORT
2414 bool equal(const TupleSet& t) const;
2415 public:
2416 /// \name Initialization
2417 //@{
2418 /// Construct an unitialized tuple set
2419 TupleSet(void);
2420 /// Initialize for a tuple set with arity \a a
2421 GECODE_INT_EXPORT
2422 TupleSet(int a);
2423 /// Initialize an uninitialized tuple set
2424 GECODE_INT_EXPORT
2425 void init(int a);
2426 /// Initialize by TupleSet \a t (tuple set is shared)
2427 GECODE_INT_EXPORT
2428 TupleSet(const TupleSet& t);
2429 /// Assignment operator
2430 GECODE_INT_EXPORT
2431 TupleSet& operator =(const TupleSet& t);
2432 /// Initialize with DFA \a dfa for arity \a a
2433 GECODE_INT_EXPORT
2434 TupleSet(int a, const DFA& dfa);
2435 /// Test whether tuple set has been initialized
2436 operator bool(void) const;
2437 /// Test whether tuple set is equal to \a t
2438 bool operator ==(const TupleSet& t) const;
2439 /// Test whether tuple set is different from \a t
2440 bool operator !=(const TupleSet& t) const;
2441 //@}
2442
2443 /// \name Addition and finalization
2444 //@{
2445 /// Add tuple \a t to tuple set
2446 TupleSet& add(const IntArgs& t);
2447 /// Is tuple set finalized
2448 bool finalized(void) const;
2449 /// Finalize tuple set
2450 void finalize(void);
2451 //@}
2452
2453 /// \name Tuple access
2454 //@{
2455 /// Arity of tuple set
2456 int arity(void) const;
2457 /// Number of tuples
2458 int tuples(void) const;
2459 /// Return number of required bit set words
2460 unsigned int words(void) const;
2461 /// Get tuple \a i
2462 Tuple operator [](int i) const;
2463 /// Return minimal value in all tuples
2464 int min(void) const;
2465 /// Return maximal value in all tuples
2466 int max(void) const;
2467 /// Return hash key
2468 std::size_t hash(void) const;
2469 //@}
2470
2471 /// \name Range access and iteration
2472 //@{
2473 /// Return first range for position \a i
2474 const Range* fst(int i) const;
2475 /// Return last range for position \a i
2476 const Range* lst(int i) const;
2477 /// Iterator over ranges
2478 class Ranges {
2479 protected:
2480 /// Current range
2481 const Range* c;
2482 /// Last range
2483 const Range* l;
2484 public:
2485 /// \name Constructors and initialization
2486 //@{
2487 /// Initialize for column \a i
2488 Ranges(const TupleSet& ts, int i);
2489 //@}
2490
2491 /// \name Iteration control
2492 //@{
2493 /// Test whether iterator is still at a range
2494 bool operator ()(void) const;
2495 /// Move iterator to next range (if possible)
2496 void operator ++(void);
2497 //@}
2498
2499 /// \name %Range access
2500 //@{
2501 /// Return smallest value of range
2502 int min(void) const;
2503 /// Return largest value of range
2504 int max(void) const;
2505 /// Return width of range (distance between minimum and maximum)
2506 unsigned int width(void) const;
2507 //@}
2508 };
2509 //@}
2510 };
2511
2512}
2513
2514#include <gecode/int/extensional/tuple-set.hpp>
2515
2516namespace Gecode {
2517
2518 /**
2519 * \brief Post domain consistent propagator for extensional constraint described by a DFA
2520 *
2521 * The elements of \a x must be a word of the language described by
2522 * the DFA \a d.
2523 *
2524 * Throws an exception of type Int::ArgumentSame, if \a x contains
2525 * the same unassigned variable multiply. If shared occurences of variables
2526 * are required, unshare should be used.
2527 *
2528 * \ingroup TaskModelIntExt
2529 */
2530 GECODE_INT_EXPORT void
2531 extensional(Home home, const IntVarArgs& x, DFA d,
2532 IntPropLevel ipl=IPL_DEF);
2533
2534 /**
2535 * \brief Post domain consistent propagator for extensional constraint described by a DFA
2536 *
2537 * The elements of \a x must be a word of the language described by
2538 * the DFA \a d.
2539 *
2540 * Throws an exception of type Int::ArgumentSame, if \a x contains
2541 * the same unassigned variable multiply. If shared occurences of variables
2542 * are required, unshare should be used.
2543 *
2544 * \ingroup TaskModelIntExt
2545 */
2546 GECODE_INT_EXPORT void
2547 extensional(Home home, const BoolVarArgs& x, DFA d,
2548 IntPropLevel ipl=IPL_DEF);
2549
2550 /** \brief Post propagator for \f$x\in t\f$.
2551 *
2552 * \li Supports domain consistency (\a ipl = IPL_DOM, default) only.
2553 * \li Throws an exception of type Int::ArgumentSizeMismatch, if
2554 * \a x and \a t are of different size.
2555 * \li Throws an exception of type Int::NotYetFinalized, if the tuple
2556 * set \a t has not been finalized.
2557 *
2558 * \ingroup TaskModelIntExt
2559 */
2560 void
2561 extensional(Home home, const IntVarArgs& x, const TupleSet& t,
2562 IntPropLevel ipl=IPL_DEF);
2563
2564 /** \brief Post propagator for \f$x\in t\f$ or \f$x\not\in t\f$.
2565 *
2566 * \li If \a pos is true, it posts a propagator for \f$x\in t\f$
2567 * and otherwise for \f$x\not\in t\f$.
2568 * \li Supports domain consistency (\a ipl = IPL_DOM, default) only.
2569 * \li Throws an exception of type Int::ArgumentSizeMismatch, if
2570 * \a x and \a t are of different size.
2571 * \li Throws an exception of type Int::NotYetFinalized, if the tuple
2572 * set \a t has not been finalized.
2573 *
2574 * \ingroup TaskModelIntExt
2575 */
2576 GECODE_INT_EXPORT void
2577 extensional(Home home, const IntVarArgs& x, const TupleSet& t, bool pos,
2578 IntPropLevel ipl=IPL_DEF);
2579
2580 /** \brief Post propagator for \f$(x\in t)\equiv r\f$.
2581 *
2582 * \li Supports domain consistency (\a ipl = IPL_DOM, default) only.
2583 * \li Throws an exception of type Int::ArgumentSizeMismatch, if
2584 * \a x and \a t are of different size.
2585 * \li Throws an exception of type Int::NotYetFinalized, if the tuple
2586 * set \a t has not been finalized.
2587 *
2588 * \ingroup TaskModelIntExt
2589 */
2590 void
2591 extensional(Home home, const IntVarArgs& x, const TupleSet& t, Reify r,
2592 IntPropLevel ipl=IPL_DEF);
2593
2594 /** \brief Post propagator for \f$(x\in t)\equiv r\f$ or \f$(x\not\in t)\equiv r\f$.
2595 *
2596 * \li If \a pos is true, it posts a propagator for \f$(x\in t)\equiv r\f$
2597 * and otherwise for \f$(x\not\in t)\equiv r\f$.
2598 * \li Supports domain consistency (\a ipl = IPL_DOM, default) only.
2599 * \li Throws an exception of type Int::ArgumentSizeMismatch, if
2600 * \a x and \a t are of different size.
2601 * \li Throws an exception of type Int::NotYetFinalized, if the tuple
2602 * set \a t has not been finalized.
2603 *
2604 * \ingroup TaskModelIntExt
2605 */
2606 GECODE_INT_EXPORT void
2607 extensional(Home home, const IntVarArgs& x, const TupleSet& t, bool pos,
2608 Reify r,
2609 IntPropLevel ipl=IPL_DEF);
2610
2611 /** \brief Post propagator for \f$x\in t\f$.
2612 *
2613 * \li Supports domain consistency (\a ipl = IPL_DOM, default) only.
2614 * \li Throws an exception of type Int::ArgumentSizeMismatch, if
2615 * \a x and \a t are of different size.
2616 * \li Throws an exception of type Int::NotYetFinalized, if the tuple
2617 * set \a t has not been finalized.
2618 *
2619 * \ingroup TaskModelIntExt
2620 */
2621 void
2622 extensional(Home home, const BoolVarArgs& x, const TupleSet& t,
2623 IntPropLevel ipl=IPL_DEF);
2624
2625 /** \brief Post propagator for \f$x\in t\f$ or \f$x\not\in t\f$.
2626 *
2627 * \li If \a pos is true, it posts a propagator for \f$x\in t\f$
2628 * and otherwise for \f$x\not\in t\f$.
2629 * \li Supports domain consistency (\a ipl = IPL_DOM, default) only.
2630 * \li Throws an exception of type Int::ArgumentSizeMismatch, if
2631 * \a x and \a t are of different size.
2632 * \li Throws an exception of type Int::NotYetFinalized, if the tuple
2633 * set \a t has not been finalized.
2634 *
2635 * \ingroup TaskModelIntExt
2636 */
2637 GECODE_INT_EXPORT void
2638 extensional(Home home, const BoolVarArgs& x, const TupleSet& t, bool pos,
2639 IntPropLevel ipl=IPL_DEF);
2640
2641 /** \brief Post propagator for \f$(x\in t)\equiv r\f$.
2642 *
2643 * \li Supports domain consistency (\a ipl = IPL_DOM, default) only.
2644 * \li Throws an exception of type Int::ArgumentSizeMismatch, if
2645 * \a x and \a t are of different size.
2646 * \li Throws an exception of type Int::NotYetFinalized, if the tuple
2647 * set \a t has not been finalized.
2648 *
2649 * \ingroup TaskModelIntExt
2650 */
2651 void
2652 extensional(Home home, const BoolVarArgs& x, const TupleSet& t, Reify r,
2653 IntPropLevel ipl=IPL_DEF);
2654
2655 /** \brief Post propagator for \f$(x\in t)\equiv r\f$ or \f$(x\not\in t)\equiv r\f$.
2656 *
2657 * \li If \a pos is true, it posts a propagator for \f$(x\in t)\equiv r\f$
2658 * and otherwise for \f$(x\not\in t)\equiv r\f$.
2659 * \li Supports domain consistency (\a ipl = IPL_DOM, default) only.
2660 * \li Throws an exception of type Int::ArgumentSizeMismatch, if
2661 * \a x and \a t are of different size.
2662 * \li Throws an exception of type Int::NotYetFinalized, if the tuple
2663 * set \a t has not been finalized.
2664 *
2665 * \ingroup TaskModelIntExt
2666 */
2667 GECODE_INT_EXPORT void
2668 extensional(Home home, const BoolVarArgs& x, const TupleSet& t, bool pos,
2669 Reify r,
2670 IntPropLevel ipl=IPL_DEF);
2671
2672}
2673
2674#include <gecode/int/extensional.hpp>
2675
2676namespace Gecode {
2677
2678 /**
2679 * \defgroup TaskModelIntArith Arithmetic constraints
2680 * \ingroup TaskModelInt
2681 */
2682
2683 //@{
2684 /** \brief Post propagator for \f$ \min\{x_0,x_1\}=x_2\f$
2685 *
2686 * Supports both bounds consistency (\a ipl = IPL_BND, default)
2687 * and domain consistency (\a ipl = IPL_DOM).
2688 */
2689 GECODE_INT_EXPORT void
2690 min(Home home, IntVar x0, IntVar x1, IntVar x2,
2691 IntPropLevel ipl=IPL_DEF);
2692 /** \brief Post propagator for \f$ \min x=y\f$
2693 *
2694 * Supports both bounds consistency (\a ipl = IPL_BND, default)
2695 * and domain consistency (\a ipl = IPL_DOM).
2696 *
2697 * If \a x is empty, an exception of type Int::TooFewArguments is thrown.
2698 */
2699 GECODE_INT_EXPORT void
2700 min(Home home, const IntVarArgs& x, IntVar y,
2701 IntPropLevel ipl=IPL_DEF);
2702 /** \brief Post propagator for \f$ \max\{x_0,x_1\}=x_2\f$
2703 *
2704 * Supports both bounds consistency (\a ipl = IPL_BND, default)
2705 * and domain consistency (\a ipl = IPL_DOM).
2706 */
2707 GECODE_INT_EXPORT void
2708 max(Home home, IntVar x0, IntVar x1, IntVar x2,
2709 IntPropLevel ipl=IPL_DEF);
2710 /** \brief Post propagator for \f$ \max x=y\f$
2711 *
2712 * Supports both bounds consistency (\a ipl = IPL_BND, default)
2713 * and domain consistency (\a ipl = IPL_DOM).
2714 *
2715 * If \a x is empty, an exception of type Int::TooFewArguments is thrown.
2716 */
2717 GECODE_INT_EXPORT void
2718 max(Home home, const IntVarArgs& x, IntVar y,
2719 IntPropLevel ipl=IPL_DEF);
2720
2721 /** \brief Post propagator for \f$ \operatorname{argmin}(x)=y\f$
2722 *
2723 * In case of ties, the smallest value for \a y is chosen
2724 * (provided \a tiebreak is true).
2725 *
2726 * If \a x is empty, an exception of type Int::TooFewArguments is thrown.
2727 * If \a y occurs in \a x, an exception of type Int::ArgumentSame
2728 * is thrown.
2729 */
2730 GECODE_INT_EXPORT void
2731 argmin(Home home, const IntVarArgs& x, IntVar y, bool tiebreak=true,
2732 IntPropLevel ipl=IPL_DEF);
2733 /** \brief Post propagator for \f$ \operatorname{argmin}(x)+o=y\f$
2734 *
2735 * In case of ties, the smallest value for \a y is chosen
2736 * (provided \a tiebreak is true).
2737 *
2738 * If \a x is empty, an exception of type Int::TooFewArguments is thrown.
2739 * If \a y occurs in \a x, an exception of type Int::ArgumentSame
2740 * is thrown.
2741 */
2742 GECODE_INT_EXPORT void
2743 argmin(Home home, const IntVarArgs& x, int o, IntVar y, bool tiebreak=true,
2744 IntPropLevel ipl=IPL_DEF);
2745 /** \brief Post propagator for \f$ \operatorname{argmax}(x)=y\f$
2746 *
2747 * In case of ties, the smallest value for \a y is chosen
2748 * (provided \a tiebreak is true).
2749 *
2750 * If \a x is empty, an exception of type Int::TooFewArguments is thrown.
2751 * If \a y occurs in \a x, an exception of type Int::ArgumentSame
2752 * is thrown.
2753 */
2754 GECODE_INT_EXPORT void
2755 argmax(Home home, const IntVarArgs& x, IntVar y, bool tiebreak=true,
2756 IntPropLevel ipl=IPL_DEF);
2757 /** \brief Post propagator for \f$ \operatorname{argmax}(x)+o=y\f$
2758 *
2759 * In case of ties, the smallest value for \a y is chosen
2760 * (provided \a tiebreak is true).
2761 *
2762 * If \a x is empty, an exception of type Int::TooFewArguments is thrown.
2763 * If \a y occurs in \a x, an exception of type Int::ArgumentSame
2764 * is thrown.
2765 */
2766 GECODE_INT_EXPORT void
2767 argmax(Home home, const IntVarArgs& x, int o, IntVar y, bool tiebreak=true,
2768 IntPropLevel ipl=IPL_DEF);
2769 /** \brief Post propagator for \f$ \operatorname{argmin}(x)=y\f$
2770 *
2771 * In case of ties, the smallest value for \a y is chosen
2772 * (provided \a tiebreak is true).
2773 *
2774 * If \a x is empty, an exception of type Int::TooFewArguments is thrown.
2775 * If \a y occurs in \a x, an exception of type Int::ArgumentSame
2776 * is thrown.
2777 */
2778 GECODE_INT_EXPORT void
2779 argmin(Home home, const BoolVarArgs& x, IntVar y, bool tiebreak=true,
2780 IntPropLevel ipl=IPL_DEF);
2781 /** \brief Post propagator for \f$ \operatorname{argmin}(x)-o=y\f$
2782 *
2783 * In case of ties, the smallest value for \a y is chosen
2784 * (provided \a tiebreak is true).
2785 *
2786 * If \a x is empty, an exception of type Int::TooFewArguments is thrown.
2787 * If \a y occurs in \a x, an exception of type Int::ArgumentSame
2788 * is thrown.
2789 */
2790 GECODE_INT_EXPORT void
2791 argmin(Home home, const BoolVarArgs& x, int o, IntVar y, bool tiebreak=true,
2792 IntPropLevel ipl=IPL_DEF);
2793 /** \brief Post propagator for \f$ \operatorname{argmax}(x)=y\f$
2794 *
2795 * In case of ties, the smallest value for \a y is chosen
2796 * (provided \a tiebreak is true).
2797 *
2798 * If \a x is empty, an exception of type Int::TooFewArguments is thrown.
2799 * If \a y occurs in \a x, an exception of type Int::ArgumentSame
2800 * is thrown.
2801 */
2802 GECODE_INT_EXPORT void
2803 argmax(Home home, const BoolVarArgs& x, IntVar y, bool tiebreak=true,
2804 IntPropLevel ipl=IPL_DEF);
2805 /** \brief Post propagator for \f$ \operatorname{argmax}(x)-o=y\f$
2806 *
2807 * In case of ties, the smallest value for \a y is chosen
2808 * (provided \a tiebreak is true).
2809 *
2810 * If \a x is empty, an exception of type Int::TooFewArguments is thrown.
2811 * If \a y occurs in \a x, an exception of type Int::ArgumentSame
2812 * is thrown.
2813 */
2814 GECODE_INT_EXPORT void
2815 argmax(Home home, const BoolVarArgs& x, int o, IntVar y, bool tiebreak=true,
2816 IntPropLevel ipl=IPL_DEF);
2817
2818 /** \brief Post propagator for \f$ |x_0|=x_1\f$
2819 *
2820 * Supports both bounds consistency (\a ipl = IPL_BND, default)
2821 * and domain consistency (\a ipl = IPL_DOM).
2822 */
2823 GECODE_INT_EXPORT void
2824 abs(Home home, IntVar x0, IntVar x1,
2825 IntPropLevel ipl=IPL_DEF);
2826
2827 /** \brief Post propagator for \f$x_0\cdot x_1=x_2\f$
2828 *
2829 * Supports both bounds consistency (\a ipl = IPL_BND, default)
2830 * and domain consistency (\a ipl = IPL_DOM).
2831 */
2832 GECODE_INT_EXPORT void
2833 mult(Home home, IntVar x0, IntVar x1, IntVar x2,
2834 IntPropLevel ipl=IPL_DEF);
2835
2836 /** \brief Post propagator for \f$x_0\ \mathrm{div}\ x_1=x_2 \land x_0\ \mathrm{mod}\ x_1 = x_3\f$
2837 *
2838 * Supports bounds consistency (\a ipl = IPL_BND, default).
2839 */
2840 GECODE_INT_EXPORT void
2841 divmod(Home home, IntVar x0, IntVar x1, IntVar x2, IntVar x3,
2842 IntPropLevel ipl=IPL_DEF);
2843
2844 /** \brief Post propagator for \f$x_0\ \mathrm{div}\ x_1=x_2\f$
2845 *
2846 * Supports bounds consistency (\a ipl = IPL_BND, default).
2847 */
2848 GECODE_INT_EXPORT void
2849 div(Home home, IntVar x0, IntVar x1, IntVar x2,
2850 IntPropLevel ipl=IPL_DEF);
2851
2852 /** \brief Post propagator for \f$x_0\ \mathrm{mod}\ x_1=x_2\f$
2853 *
2854 * Supports bounds consistency (\a ipl = IPL_BND, default).
2855 */
2856 GECODE_INT_EXPORT void
2857 mod(Home home, IntVar x0, IntVar x1, IntVar x2,
2858 IntPropLevel ipl=IPL_DEF);
2859
2860 /** \brief Post propagator for \f$x_0^2=x_1\f$
2861 *
2862 * Supports both bounds consistency (\a ipl = IPL_BND, default)
2863 * and domain consistency (\a ipl = IPL_DOM).
2864 */
2865 GECODE_INT_EXPORT void
2866 sqr(Home home, IntVar x0, IntVar x1,
2867 IntPropLevel ipl=IPL_DEF);
2868
2869 /** \brief Post propagator for \f$\lfloor\sqrt{x_0}\rfloor=x_1\f$
2870 *
2871 * Supports both bounds consistency (\a ipl = IPL_BND, default)
2872 * and domain consistency (\a ipl = IPL_DOM).
2873 */
2874 GECODE_INT_EXPORT void
2875 sqrt(Home home, IntVar x0, IntVar x1,
2876 IntPropLevel ipl=IPL_DEF);
2877
2878 /** \brief Post propagator for \f$x_0^n=x_1\f$
2879 *
2880 * Supports both bounds consistency (\a ipl = IPL_BND, default)
2881 * and domain consistency (\a ipl = IPL_DOM).
2882 *
2883 * Throws an exception of type Int::OutOfLimits, if \a n is
2884 * negative.
2885 */
2886 GECODE_INT_EXPORT void
2887 pow(Home home, IntVar x0, int n, IntVar x1,
2888 IntPropLevel ipl=IPL_DEF);
2889
2890 /** \brief Post propagator for \f$\lfloor\sqrt[n]{x_0}\rfloor=x_1\f$
2891 *
2892 * Supports both bounds consistency (\a ipl = IPL_BND, default)
2893 * and domain consistency (\a ipl = IPL_DOM).
2894 *
2895 * Throws an exception of type Int::OutOfLimits, if \a n is
2896 * not strictly positive.
2897 */
2898 GECODE_INT_EXPORT void
2899 nroot(Home home, IntVar x0, int n, IntVar x1,
2900 IntPropLevel ipl=IPL_DEF);
2901
2902 //@}
2903
2904 /**
2905 * \defgroup TaskModelIntLI Linear constraints over integer variables
2906 * \ingroup TaskModelInt
2907 *
2908 * All variants for linear constraints over integer variables share
2909 * the following properties:
2910 * - Bounds consistency (over the real numbers) is supported for
2911 * all constraints (actually, for disequlities always domain consistency
2912 * is used as it is cheaper). Domain consistency is supported for all
2913 * non-reified constraint. As bounds consistency for inequalities
2914 * coincides with domain consistency, the only
2915 * real variation is for linear equations. Domain consistent
2916 * linear equations have exponential complexity, so use with care!
2917 * - If the integer propagation level IPL_DEF is used as argument
2918 * (hence, default propagation) and the linear constraint is sufficiently
2919 * simple (two variables with unit coefficients), the domain
2920 * consistent propagation is used.
2921 * - Variables occurring multiply in the argument arrays are replaced
2922 * by a single occurrence: for example, \f$ax+bx\f$ becomes
2923 * \f$(a+b)x\f$.
2924 * - If in the above simplification the value for \f$(a+b)\f$ (or for
2925 * \f$a\f$ and \f$b\f$) exceeds the limits for integers as
2926 * defined in Int::Limits, an exception of type
2927 * Int::OutOfLimits is thrown.
2928 * - Assume the constraint
2929 * \f$\sum_{i=0}^{|x|-1}a_i\cdot x_i\sim_{irt} c\f$.
2930 * If \f$|c|+\sum_{i=0}^{|x|-1}a_i\cdot x_i\f$ exceeds the maximal
2931 * available precision (at least \f$2^{48}\f$), an exception of
2932 * type Int::OutOfLimits is thrown.
2933 * - In all other cases, the created propagators are accurate (that
2934 * is, they will not silently overflow during propagation).
2935 */
2936 /** \brief Post propagator for \f$\sum_{i=0}^{|x|-1}x_i\sim_{irt} c\f$
2937 * \ingroup TaskModelIntLI
2938 */
2939 GECODE_INT_EXPORT void
2940 linear(Home home, const IntVarArgs& x,
2941 IntRelType irt, int c,
2942 IntPropLevel ipl=IPL_DEF);
2943 /** \brief Post propagator for \f$\sum_{i=0}^{|x|-1}x_i\sim_{irt} y\f$
2944 * \ingroup TaskModelIntLI
2945 */
2946 GECODE_INT_EXPORT void
2947 linear(Home home, const IntVarArgs& x,
2948 IntRelType irt, IntVar y,
2949 IntPropLevel ipl=IPL_DEF);
2950 /** \brief Post propagator for \f$\left(\sum_{i=0}^{|x|-1}x_i\sim_{irt} c\right)\equiv r\f$
2951 * \ingroup TaskModelIntLI
2952 */
2953 GECODE_INT_EXPORT void
2954 linear(Home home, const IntVarArgs& x,
2955 IntRelType irt, int c, Reify r,
2956 IntPropLevel ipl=IPL_DEF);
2957 /** \brief Post propagator for \f$\left(\sum_{i=0}^{|x|-1}x_i\sim_{irt} y\right)\equiv r\f$
2958 * \ingroup TaskModelIntLI
2959 */
2960 GECODE_INT_EXPORT void
2961 linear(Home home, const IntVarArgs& x,
2962 IntRelType irt, IntVar y, Reify r,
2963 IntPropLevel ipl=IPL_DEF);
2964 /** \brief Post propagator for \f$\sum_{i=0}^{|x|-1}a_i\cdot x_i\sim_{irt} c\f$
2965 *
2966 * Throws an exception of type Int::ArgumentSizeMismatch, if
2967 * \a a and \a x are of different size.
2968 * \ingroup TaskModelIntLI
2969 */
2970 GECODE_INT_EXPORT void
2971 linear(Home home, const IntArgs& a, const IntVarArgs& x,
2972 IntRelType irt, int c,
2973 IntPropLevel ipl=IPL_DEF);
2974 /** \brief Post propagator for \f$\sum_{i=0}^{|x|-1}a_i\cdot x_i\sim_{irt} y\f$
2975 *
2976 * Throws an exception of type Int::ArgumentSizeMismatch, if
2977 * \a a and \a x are of different size.
2978 * \ingroup TaskModelIntLI
2979 */
2980 GECODE_INT_EXPORT void
2981 linear(Home home, const IntArgs& a, const IntVarArgs& x,
2982 IntRelType irt, IntVar y,
2983 IntPropLevel ipl=IPL_DEF);
2984 /** \brief Post propagator for \f$\left(\sum_{i=0}^{|x|-1}a_i\cdot x_i\sim_{irt} c\right)\equiv r\f$
2985 *
2986 * Throws an exception of type Int::ArgumentSizeMismatch, if
2987 * \a a and \a x are of different size.
2988 * \ingroup TaskModelIntLI
2989 */
2990 GECODE_INT_EXPORT void
2991 linear(Home home, const IntArgs& a, const IntVarArgs& x,
2992 IntRelType irt, int c, Reify r,
2993 IntPropLevel ipl=IPL_DEF);
2994 /** \brief Post propagator for \f$\left(\sum_{i=0}^{|x|-1}a_i\cdot x_i\sim_{irt} y\right)\equiv r\f$
2995 *
2996 * Throws an exception of type Int::ArgumentSizeMismatch, if
2997 * \a a and \a x are of different size.
2998 * \ingroup TaskModelIntLI
2999 */
3000 GECODE_INT_EXPORT void
3001 linear(Home home, const IntArgs& a, const IntVarArgs& x,
3002 IntRelType irt, IntVar y, Reify r,
3003 IntPropLevel ipl=IPL_DEF);
3004
3005
3006 /**
3007 * \defgroup TaskModelIntLB Linear constraints over Boolean variables
3008 * \ingroup TaskModelInt
3009 *
3010 * All variants for linear constraints over Boolean variables share
3011 * the following properties:
3012 * - Bounds consistency (over the real numbers) is supported for
3013 * all constraints (actually, for disequlities always domain consistency
3014 * is used as it is cheaper).
3015 * - Variables occurring multiply in the argument arrays are replaced
3016 * by a single occurrence: for example, \f$ax+bx\f$ becomes
3017 * \f$(a+b)x\f$.
3018 * - If in the above simplification the value for \f$(a+b)\f$ (or for
3019 * \f$a\f$ and \f$b\f$) exceeds the limits for integers as
3020 * defined in Int::Limits, an exception of type
3021 * Int::OutOfLimits is thrown.
3022 * - Assume the constraint
3023 * \f$\sum_{i=0}^{|x|-1}a_i\cdot x_i\sim_{irt} c\f$.
3024 * If \f$|c|+\sum_{i=0}^{|x|-1}a_i\cdot x_i\f$ exceeds the limits
3025 * for integers as defined in Int::Limits, an exception of
3026 * type Int::OutOfLimits is thrown.
3027 * - In all other cases, the created propagators are accurate (that
3028 * is, they will not silently overflow during propagation).
3029 */
3030 /** \brief Post propagator for \f$\sum_{i=0}^{|x|-1}x_i\sim_{irt} c\f$
3031 * \ingroup TaskModelIntLB
3032 */
3033 GECODE_INT_EXPORT void
3034 linear(Home home, const BoolVarArgs& x,
3035 IntRelType irt, int c,
3036 IntPropLevel ipl=IPL_DEF);
3037 /** \brief Post propagator for \f$\left(\sum_{i=0}^{|x|-1}x_i\sim_{irt} c\right)\equiv r\f$
3038 * \ingroup TaskModelIntLB
3039 */
3040 GECODE_INT_EXPORT void
3041 linear(Home home, const BoolVarArgs& x,
3042 IntRelType irt, int c, Reify r,
3043 IntPropLevel ipl=IPL_DEF);
3044 /** \brief Post propagator for \f$\sum_{i=0}^{|x|-1}x_i\sim_{irt} y\f$
3045 * \ingroup TaskModelIntLB
3046 */
3047 GECODE_INT_EXPORT void
3048 linear(Home home, const BoolVarArgs& x,
3049 IntRelType irt, IntVar y,
3050 IntPropLevel ipl=IPL_DEF);
3051 /** \brief Post propagator for \f$\left(\sum_{i=0}^{|x|-1}x_i\sim_{irt} y\right)\equiv r\f$
3052 * \ingroup TaskModelIntLB
3053 */
3054 GECODE_INT_EXPORT void
3055 linear(Home home, const BoolVarArgs& x,
3056 IntRelType irt, IntVar y, Reify r,
3057 IntPropLevel ipl=IPL_DEF);
3058 /** \brief Post propagator for \f$\sum_{i=0}^{|x|-1}a_i\cdot x_i\sim_{irt} c\f$
3059 *
3060 * Throws an exception of type Int::ArgumentSizeMismatch, if
3061 * \a a and \a x are of different size.
3062 * \ingroup TaskModelIntLB
3063 */
3064 GECODE_INT_EXPORT void
3065 linear(Home home, const IntArgs& a, const BoolVarArgs& x,
3066 IntRelType irt, int c,
3067 IntPropLevel ipl=IPL_DEF);
3068 /** \brief Post propagator for \f$\left(\sum_{i=0}^{|x|-1}a_i\cdot x_i\sim_{irt} c\right)\equiv r\f$
3069 *
3070 * Throws an exception of type Int::ArgumentSizeMismatch, if
3071 * \a a and \a x are of different size.
3072 * \ingroup TaskModelIntLB
3073 */
3074 GECODE_INT_EXPORT void
3075 linear(Home home, const IntArgs& a, const BoolVarArgs& x,
3076 IntRelType irt, int c, Reify r,
3077 IntPropLevel ipl=IPL_DEF);
3078 /** \brief Post propagator for \f$\sum_{i=0}^{|x|-1}a_i\cdot x_i\sim_{irt} y\f$
3079 *
3080 * Throws an exception of type Int::ArgumentSizeMismatch, if
3081 * \a a and \a x are of different size.
3082 * \ingroup TaskModelIntLB
3083 */
3084 GECODE_INT_EXPORT void
3085 linear(Home home, const IntArgs& a, const BoolVarArgs& x,
3086 IntRelType irt, IntVar y,
3087 IntPropLevel ipl=IPL_DEF);
3088 /** \brief Post propagator for \f$\left(\sum_{i=0}^{|x|-1}a_i\cdot x_i\sim_{irt} y\right)\equiv r\f$
3089 *
3090 * Throws an exception of type Int::ArgumentSizeMismatch, if
3091 * \a a and \a x are of different size.
3092 * \ingroup TaskModelIntLB
3093 */
3094 GECODE_INT_EXPORT void
3095 linear(Home home, const IntArgs& a, const BoolVarArgs& x,
3096 IntRelType irt, IntVar y, Reify r,
3097 IntPropLevel ipl=IPL_DEF);
3098
3099
3100 /**
3101 * \defgroup TaskModelIntBinPacking Bin packing constraints
3102 * \ingroup TaskModelInt
3103 *
3104 */
3105 /** \brief Post propagator for bin packing
3106 *
3107 * The variables in \a l are the loads for each bin, whereas the
3108 * variables in \a b define for each item into which bin it is packed.
3109 * The integer values \a s define the size of the items.
3110 *
3111 * It is propagated that for each \f$j\f$ with \f$0\leq j<|l|\f$ the
3112 * constraint \f$l_j=\sum_{0\leq i<|b|\wedge b_i=j}s_i\f$ holds and that
3113 * for each \f$i\f$ with \f$0\leq i<|b|\f$ the constraint
3114 * \f$0\leq b_i<|l|\f$ holds.
3115 *
3116 * The propagation follows: Paul Shaw. A Constraint for Bin Packing. CP 2004.
3117 *
3118 * Throws the following exceptions:
3119 * - Of type Int::ArgumentSizeMismatch if \a b and \a s are not of
3120 * the same size.
3121 * - Of type Int::ArgumentSame if \a l and \a b share unassigned variables.
3122 * - Of type Int::OutOfLimits if \a s contains a negative number.
3123 *
3124 * \ingroup TaskModelIntBinPacking
3125 */
3126 GECODE_INT_EXPORT void
3127 binpacking(Home home,
3128 const IntVarArgs& l,
3129 const IntVarArgs& b, const IntArgs& s,
3130 IntPropLevel ipl=IPL_DEF);
3131 /* \brief Post propagator for multi-dimensional bin packing
3132 *
3133 * In the following \a n refers to the number of items and \a m
3134 * refers to the number of bins.
3135 *
3136 * The multi-dimensional bin-packing constraint enforces that
3137 * all items are packed into bins
3138 * \f$b_i\in\{0,\ldots,m-1\}\f$ for \f$0\leq i<n\f$
3139 * and that the load of each bin corresponds to the items
3140 * packed into it for each dimension \f$l_{j\cdot
3141 * d + k} = \sum_{\{i\in\{0,\ldots,n-1\}|
3142 * b_{j\cdot d+k}=i}\}s_{i\cdot d+k}\f$
3143 * for \f$0\leq j<m\f$, \f$0\leq k<d\f$
3144 * Furthermore, the load variables must satisfy the capacity
3145 * constraints \f$l_{j\cdot d + k} \leq
3146 * c_k\f$ for \f$0\leq j<m\f$, \f$0\leq k<d\f$.
3147 *
3148 * The constraint is implemented by the decomposition
3149 * introduced in: Stefano Gualandi and Michele Lombardi. A
3150 * simple and effective decomposition for the multidimensional
3151 * binpacking constraint. CP 2013, pages 356--364.
3152 *
3153 * Posting the constraint returns a maximal set containing conflicting
3154 * items that require pairwise different bins.
3155 *
3156 * Note that posting the constraint has exponential complexity in the
3157 * number of items due to the Bron-Kerbosch algorithm used for finding
3158 * the maximal conflict item sets.
3159 *
3160 * Throws the following exceptions:
3161 * - Of type Int::ArgumentSizeMismatch if any of the following properties
3162 * is violated: \f$|b|=n\f$, \f$|l|=m\cdot d\f$, \f$|s|=n\cdot d\f$,
3163 * and \f$|c|=d\f$.
3164 * - Of type Int::ArgumentSame if \a l and \a b share unassigned variables.
3165 * - Of type Int::OutOfLimits if \a s or \a c contains a negative number.
3166 *
3167 * \ingroup TaskModelIntBinPacking
3168 */
3169 GECODE_INT_EXPORT IntSet
3170 binpacking(Home home, int d,
3171 const IntVarArgs& l, const IntVarArgs& b,
3172 const IntArgs& s, const IntArgs& c,
3173 IntPropLevel ipl=IPL_DEF);
3174
3175
3176 /**
3177 * \defgroup TaskModelIntGeoPacking Geometrical packing constraints
3178 * \ingroup TaskModelInt
3179 *
3180 * Constraints for modeling geometrical packing problems.
3181 */
3182 /** \brief Post propagator for rectangle packing
3183 *
3184 * Propagate that no two rectangles as described by the coordinates
3185 * \a x, and \a y, widths \a w, and heights \a h overlap.
3186 *
3187 * Throws the following exceptions:
3188 * - Of type Int::ArgumentSizeMismatch if \a x, \a w, \a y, or \a h
3189 * are not of the same size.
3190 * - Of type Int::OutOfLimits if \a w or \a h contain a negative number.
3191 *
3192 * \ingroup TaskModelIntGeoPacking
3193 */
3194 GECODE_INT_EXPORT void
3195 nooverlap(Home home,
3196 const IntVarArgs& x, const IntArgs& w,
3197 const IntVarArgs& y, const IntArgs& h,
3198 IntPropLevel ipl=IPL_DEF);
3199 /** \brief Post propagator for rectangle packing
3200 *
3201 * Propagate that no two rectangles as described by the coordinates
3202 * \a x, and \a y, widths \a w, and heights \a h overlap. The rectangles
3203 * can be optional, as described by the Boolean variables \a o.
3204 *
3205 * Throws the following exceptions:
3206 * - Of type Int::ArgumentSizeMismatch if \a x, \a w, \a y, \a h, or \a o
3207 * are not of the same size.
3208 * - Of type Int::OutOfLimits if \a w or \a h contain a negative number.
3209 *
3210 * \ingroup TaskModelIntGeoPacking
3211 */
3212 GECODE_INT_EXPORT void
3213 nooverlap(Home home,
3214 const IntVarArgs& x, const IntArgs& w,
3215 const IntVarArgs& y, const IntArgs& h,
3216 const BoolVarArgs& o,
3217 IntPropLevel ipl=IPL_DEF);
3218 /** \brief Post propagator for rectangle packing
3219 *
3220 * Propagate that no two rectangles as described by the start coordinates
3221 * \a x0 and \a y0, widths \a w and heights \a h, and end coordinates
3222 * \a x1 and \a y1 overlap.
3223 *
3224 * Note that the relations \f$x0_i+w_i=x1_i\f$ and \f$y0_i+h_i=y1_i\f$ are
3225 * not propagated (for \f$0\leq i<|x0|\f$). That is, additional constraints
3226 * must be posted to enforce that relation.
3227 *
3228 * Throws the following exceptions:
3229 * - Of type Int::ArgumentSizeMismatch if \a x0, \a x1, \a w,
3230 * \a y0, \a y1, or \a h are not of the same size.
3231 *
3232 * \ingroup TaskModelIntGeoPacking
3233 */
3234 GECODE_INT_EXPORT void
3235 nooverlap(Home home,
3236 const IntVarArgs& x0, const IntVarArgs& w, const IntVarArgs& x1,
3237 const IntVarArgs& y0, const IntVarArgs& h, const IntVarArgs& y1,
3238 IntPropLevel ipl=IPL_DEF);
3239 /** \brief Post propagator for rectangle packing
3240 *
3241 * Propagate that no two rectangles as described by the start coordinates
3242 * \a x0 and \a y0, widths \a w and heights \a h, and end coordinates
3243 * \a x1 and \a y1 overlap. The rectangles can be optional, as described
3244 * by the Boolean variables \a o.
3245 *
3246 * Note that the relations \f$x0_i+w_i=x1_i\f$ and \f$y0_i+h_i=y1_i\f$ are
3247 * not propagated (for \f$0\leq i<|x0|\f$). That is, additional constraints
3248 * must be posted to enforce that relation.
3249 *
3250 * Throws the following exceptions:
3251 * - Of type Int::ArgumentSizeMismatch if \a x0, \a x1, \a w,
3252 * \a y0, \a y1, or \a h are not of the same size.
3253 *
3254 * \ingroup TaskModelIntGeoPacking
3255 */
3256 GECODE_INT_EXPORT void
3257 nooverlap(Home home,
3258 const IntVarArgs& x0, const IntVarArgs& w, const IntVarArgs& x1,
3259 const IntVarArgs& y0, const IntVarArgs& h, const IntVarArgs& y1,
3260 const BoolVarArgs& o,
3261 IntPropLevel ipl=IPL_DEF);
3262
3263
3264 /**
3265 * \defgroup TaskModelIntScheduling Scheduling constraints
3266 * \ingroup TaskModelInt
3267 */
3268 //@{
3269
3270 /** \brief Post propagators for ordering two tasks
3271 *
3272 * Order two tasks with start times \f$s_0\f$ and \f$s_1\f$ with
3273 * processing times \f$p_0\f$ and \f$p_1\f$ according to Boolean variable
3274 * \a b (if \a b is zero \f$s_0\f$ starts before \f$s_1\f$).
3275 *
3276 * Throws an exception of Int::OutOfLimits, if the durations or
3277 * the sum of durations and start times are too large.
3278 *
3279 */
3280 GECODE_INT_EXPORT void
3281 order(Home home, IntVar s0, int p0, IntVar s1, int p1, BoolVar b,
3282 IntPropLevel ipl=IPL_DEF);
3283
3284 /**
3285 * \brief Post propagators for the cumulatives constraint
3286 *
3287 * This function creates propagators for the cumulatives constraint
3288 * presented in <em>"A new multi-resource cumulatives constraint
3289 * with negative heights"</em>, Nicolas Beldiceanu and Mats
3290 * Carlsson, Principles and Practice of Constraint Programming 2002.
3291 *
3292 * The constraint models a set of machines and a set of tasks that
3293 * should be assigned to the machines. The machines have a positive
3294 * resource limit and the tasks each have a resource usage that can
3295 * be either positive, negative, or zero. The constraint is enforced
3296 * over each point in time for a machine where there is at least one
3297 * task assigned.
3298 *
3299 * The propagator does not enforce \f$s_i+p_i=e_i\f$, this constraint
3300 * has to be posted in addition to ensure consistency of the task bounds.
3301 *
3302 * The limit for a machine is either the maximum amount available at
3303 * any given time (\a at_most = true), or else the least amount to
3304 * be used (\a at_most = false).
3305 *
3306 * \param home current space
3307 * \param m \f$ m_i \f$ is the machine assigned to task \f$ i \f$
3308 * \param s \f$ s_i \f$ is the start time assigned to task \f$ i \f$
3309 * \param p \f$ p_i \f$ is the processing time of task \f$ i \f$
3310 * \param e \f$ e_i \f$ is the end time assigned to task \f$ i \f$
3311 * \param u \f$ u_i \f$ is the amount of
3312 * resources consumed by task \f$ i \f$
3313 * \param c \f$ c_r \f$ is the capacity, the amount of resource available
3314 * for machine \f$ r \f$
3315 * \param at_most \a at_most tells if the amount of resources used
3316 * for a machine should be less than the limit (\a at_most
3317 * = true) or greater than the limit (\a at_most = false)
3318 * \param ipl Supports value-consistency only (\a ipl = IPL_VAL, default).
3319 *
3320 * \exception Int::ArgumentSizeMismatch thrown if the sizes
3321 * of the arguments representing tasks does not match.
3322 * \exception Int::OutOfLimits thrown if any numerical argument is
3323 * larger than Int::Limits::max or less than
3324 * Int::Limits::min.
3325 */
3326 GECODE_INT_EXPORT void
3327 cumulatives(Home home, const IntVarArgs& m,
3328 const IntVarArgs& s, const IntVarArgs& p,
3329 const IntVarArgs& e, const IntVarArgs& u,
3330 const IntArgs& c, bool at_most,
3331 IntPropLevel ipl=IPL_DEF);
3332 /** \brief Post propagators for the cumulatives constraint.
3333 *
3334 * \copydoc cumulatives()
3335 */
3336 GECODE_INT_EXPORT void
3337 cumulatives(Home home, const IntArgs& m,
3338 const IntVarArgs& s, const IntVarArgs& p,
3339 const IntVarArgs& e, const IntVarArgs& u,
3340 const IntArgs& c, bool at_most,
3341 IntPropLevel ipl=IPL_DEF);
3342 /** \brief Post propagators for the cumulatives constraint.
3343 *
3344 * \copydoc cumulatives()
3345 */
3346 GECODE_INT_EXPORT void
3347 cumulatives(Home home, const IntVarArgs& m,
3348 const IntVarArgs& s, const IntArgs& p,
3349 const IntVarArgs& e, const IntVarArgs& u,
3350 const IntArgs& c, bool at_most,
3351 IntPropLevel ipl=IPL_DEF);
3352 /** \brief Post propagators for the cumulatives constraint.
3353 *
3354 * \copydoc cumulatives()
3355 */
3356 GECODE_INT_EXPORT void
3357 cumulatives(Home home, const IntArgs& m,
3358 const IntVarArgs& s, const IntArgs& p,
3359 const IntVarArgs& e, const IntVarArgs& u,
3360 const IntArgs& c, bool at_most,
3361 IntPropLevel ipl=IPL_DEF);
3362 /** \brief Post propagators for the cumulatives constraint.
3363 *
3364 * \copydoc cumulatives()
3365 */
3366 GECODE_INT_EXPORT void
3367 cumulatives(Home home, const IntVarArgs& m,
3368 const IntVarArgs& s, const IntVarArgs& p,
3369 const IntVarArgs& e, const IntArgs& u,
3370 const IntArgs& c, bool at_most,
3371 IntPropLevel ipl=IPL_DEF);
3372 /** \brief Post propagators for the cumulatives constraint.
3373 *
3374 * \copydoc cumulatives()
3375 */
3376 GECODE_INT_EXPORT void
3377 cumulatives(Home home, const IntArgs& m,
3378 const IntVarArgs& s, const IntVarArgs& p,
3379 const IntVarArgs& e, const IntArgs& u,
3380 const IntArgs& c, bool at_most,
3381 IntPropLevel ipl=IPL_DEF);
3382 /** \brief Post propagators for the cumulatives constraint.
3383 *
3384 * \copydoc cumulatives()
3385 */
3386 GECODE_INT_EXPORT void
3387 cumulatives(Home home, const IntVarArgs& m,
3388 const IntVarArgs& s, const IntArgs& p,
3389 const IntVarArgs& e, const IntArgs& u,
3390 const IntArgs& c, bool at_most,
3391 IntPropLevel ipl=IPL_DEF);
3392 /** \brief Post propagators for the cumulatives constraint.
3393 *
3394 * \copydoc cumulatives()
3395 */
3396 GECODE_INT_EXPORT void
3397 cumulatives(Home home, const IntArgs& m,
3398 const IntVarArgs& s, const IntArgs& p,
3399 const IntVarArgs& e, const IntArgs& u,
3400 const IntArgs& c, bool at_most,
3401 IntPropLevel ipl=IPL_DEF);
3402
3403 /** \brief Post propagators for scheduling tasks on unary resources
3404 *
3405 * Schedule tasks with start times \a s and processing times \a p
3406 * on a unary resource. The propagator uses the algorithms from:
3407 * Petr Vilím, Global Constraints in Scheduling, PhD thesis,
3408 * Charles University, Prague, Czech Republic, 2007.
3409 *
3410 * The propagator performs propagation that depends on the integer
3411 * propagation level \a ipl as follows:
3412 * - If \a IPL_BASIC is set, the propagator performs overload checking
3413 * and time-tabling propagation.
3414 * - If \a IPL_ADVANCED is set, the propagator performs overload checking,
3415 * detectable precendence propagation, not-first-not-last propagation,
3416 * and edge finding.
3417 * - If both flags are combined (default), all the above listed propagation
3418 * is performed.
3419 *
3420 * Posting the constraint might throw the following exceptions:
3421 * - Throws an exception of type Int::ArgumentSizeMismatch, if \a s
3422 * and \a p are of different size.
3423 * - Throws an exception of type Int::ArgumentSame, if \a s contains
3424 * the same unassigned variable multiply.
3425 * - Throws an exception of type Int::OutOfLimits, if \a p contains
3426 * an integer that is negative or that could generate
3427 * an overflow.
3428 */
3429 GECODE_INT_EXPORT void
3430 unary(Home home, const IntVarArgs& s, const IntArgs& p,
3431 IntPropLevel ipl=IPL_DEF);
3432
3433 /** \brief Post propagators for scheduling optional tasks on unary resources
3434 *
3435 * Schedule optional tasks with start times \a s, processing times \a p,
3436 * and whether a task is mandatory \a m (a task is mandatory if the
3437 * Boolean variable is 1) on a unary resource. The propagator uses the
3438 * algorithms from:
3439 * Petr Vilím, Global Constraints in Scheduling, PhD thesis,
3440 * Charles University, Prague, Czech Republic, 2007.
3441 *
3442 * The propagator performs propagation that depends on the integer
3443 * propagation level \a ipl as follows:
3444 * - If \a IPL_BASIC is set, the propagator performs overload checking
3445 * and time-tabling propagation.
3446 * - If \a IPL_ADVANCED is set, the propagator performs overload checking,
3447 * detectable precendence propagation, not-first-not-last propagation,
3448 * and edge finding.
3449 * - If both flags are combined (default), all the above listed propagation
3450 * is performed.
3451 *
3452 * Posting the constraint might throw the following exceptions:
3453 * - Throws an exception of type Int::ArgumentSizeMismatch, if \a s,
3454 * \a p, or \a m are of different size.
3455 * - Throws an exception of type Int::ArgumentSame, if \a s contains
3456 * the same unassigned variable multiply.
3457 * - Throws an exception of type Int::OutOfLimits, if \a p contains
3458 * an integer that is negative or that could generate
3459 * an overflow.
3460 */
3461 GECODE_INT_EXPORT void
3462 unary(Home home, const IntVarArgs& s, const IntArgs& p,
3463 const BoolVarArgs& m, IntPropLevel ipl=IPL_DEF);
3464
3465 /** \brief Post propagators for scheduling tasks on unary resources
3466 *
3467 * Schedule tasks with flexible times \a flex and fixed times \a fix
3468 * on a unary resource. For each
3469 * task, it depends on \a t how the flexible and fix times are interpreted:
3470 * - If <code>t[i]</code> is <code>TT_FIXP</code>, then
3471 * <code>flex[i]</code> is the start time and <code>fix[i]</code> is the
3472 * processing time.
3473 * - If <code>t[i]</code> is <code>TT_FIXS</code>, then
3474 * <code>flex[i]</code> is the end time and <code>fix[i]</code> is the
3475 * start time.
3476 * - If <code>t[i]</code> is <code>TT_FIXE</code>, then
3477 * <code>flex[i]</code> is the start time and <code>fix[i]</code> is the
3478 * end time.
3479 *
3480 * The propagator uses the algorithms from:
3481 * Petr Vilím, Global Constraints in Scheduling, PhD thesis,
3482 * Charles University, Prague, Czech Republic, 2007.
3483 *
3484 * The propagator performs propagation that depends on the integer
3485 * propagation level \a ipl as follows:
3486 * - If \a IPL_BASIC is set, the propagator performs overload checking
3487 * and time-tabling propagation.
3488 * - If \a IPL_ADVANCED is set, the propagator performs overload checking,
3489 * detectable precendence propagation, not-first-not-last propagation,
3490 * and edge finding.
3491 * - If both flags are combined (default), all the above listed propagation
3492 * is performed.
3493 *
3494 * Posting the constraint might throw the following exceptions:
3495 * - Throws an exception of type Int::ArgumentSizeMismatch, if \a s
3496 * and \a p are of different size.
3497 * - Throws an exception of type Int::OutOfLimits, if \a p contains
3498 * an integer that is negative for a task with type <code>TT_FIXP</code>
3499 * or that could generate an overflow.
3500 */
3501 GECODE_INT_EXPORT void
3502 unary(Home home, const TaskTypeArgs& t,
3503 const IntVarArgs& flex, const IntArgs& fix, IntPropLevel ipl=IPL_DEF);
3504
3505 /** \brief Post propagators for scheduling optional tasks on unary resources
3506 *
3507 * Schedule optional tasks with flexible times \a flex, fixed times \a fix,
3508 * and whether a task is mandatory \a m (a task is mandatory if the
3509 * Boolean variable is 1) on a unary resource. For each
3510 * task, it depends on \a t how the flexible and fix times are interpreted:
3511 * - If <code>t[i]</code> is <code>TT_FIXP</code>, then
3512 * <code>flex[i]</code> is the start time and <code>fix[i]</code> is the
3513 * processing time.
3514 * - If <code>t[i]</code> is <code>TT_FIXS</code>, then
3515 * <code>flex[i]</code> is the end time and <code>fix[i]</code> is the
3516 * start time.
3517 * - If <code>t[i]</code> is <code>TT_FIXE</code>, then
3518 * <code>flex[i]</code> is the start time and <code>fix[i]</code> is the
3519 * end time.
3520 *
3521 * The propagator uses the
3522 * algorithms from:
3523 * Petr Vilím, Global Constraints in Scheduling, PhD thesis,
3524 * Charles University, Prague, Czech Republic, 2007.
3525 *
3526 * The propagator performs propagation that depends on the integer
3527 * propagation level \a ipl as follows:
3528 * - If \a IPL_BASIC is set, the propagator performs overload checking
3529 * and time-tabling propagation.
3530 * - If \a IPL_ADVANCED is set, the propagator performs overload checking,
3531 * detectable precendence propagation, not-first-not-last propagation,
3532 * and edge finding.
3533 * - If both flags are combined (default), all the above listed propagation
3534 * is performed.
3535 *
3536 * Posting the constraint might throw the following exceptions:
3537 * - Throws an exception of type Int::ArgumentSizeMismatch, if \a s,
3538 * \a p, or \a m are of different size.
3539 * - Throws an exception of type Int::OutOfLimits, if \a p contains
3540 * an integer that is negative for a task with type <code>TT_FIXP</code>
3541 * or that could generate an overflow.
3542 */
3543 GECODE_INT_EXPORT void
3544 unary(Home home, const TaskTypeArgs& t,
3545 const IntVarArgs& flex, const IntArgs& fix,
3546 const BoolVarArgs& m, IntPropLevel ipl=IPL_DEF);
3547
3548 /** \brief Post propagators for scheduling tasks on unary resources
3549 *
3550 * Schedule tasks with start times \a s, processing times \a p, and
3551 * end times \a e
3552 * on a unary resource. The propagator uses the algorithms from:
3553 * Petr Vilím, Global Constraints in Scheduling, PhD thesis,
3554 * Charles University, Prague, Czech Republic, 2007.
3555 *
3556 * The propagator does not enforce \f$s_i+p_i=e_i\f$, this constraint
3557 * has to be posted in addition to ensure consistency of the task bounds.
3558 *
3559 * The propagator performs propagation that depends on the integer
3560 * propagation level \a ipl as follows:
3561 * - If \a IPL_BASIC is set, the propagator performs overload checking
3562 * and time-tabling propagation.
3563 * - If \a IPL_ADVANCED is set, the propagator performs overload checking,
3564 * detectable precendence propagation, not-first-not-last propagation,
3565 * and edge finding.
3566 * - If both flags are combined (default), all the above listed propagation
3567 * is performed.
3568 *
3569 * The processing times are constrained to be non-negative.
3570 *
3571 * Throws an exception of type Int::ArgumentSizeMismatch, if \a s
3572 * and \a p are of different size.
3573 */
3574 GECODE_INT_EXPORT void
3575 unary(Home home, const IntVarArgs& s, const IntVarArgs& p,
3576 const IntVarArgs& e, IntPropLevel ipl=IPL_DEF);
3577
3578 /** \brief Post propagators for scheduling optional tasks on unary resources
3579 *
3580 * Schedule optional tasks with start times \a s, processing times \a p,
3581 * end times \a e,
3582 * and whether a task is mandatory \a m (a task is mandatory if the
3583 * Boolean variable is 1) on a unary resource. The propagator uses the
3584 * algorithms from:
3585 * Petr Vilím, Global Constraints in Scheduling, PhD thesis,
3586 * Charles University, Prague, Czech Republic, 2007.
3587 *
3588 * The propagator performs propagation that depends on the integer
3589 * propagation level \a ipl as follows:
3590 * - If \a IPL_BASIC is set, the propagator performs overload checking
3591 * and time-tabling propagation.
3592 * - If \a IPL_ADVANCED is set, the propagator performs overload checking,
3593 * detectable precendence propagation, not-first-not-last propagation,
3594 * and edge finding.
3595 * - If both flags are combined, all the above listed propagation is
3596 * performed (default).
3597 *
3598 * The propagator does not enforce \f$s_i+p_i=e_i\f$, this constraint
3599 * has to be posted in addition to ensure consistency of the task bounds.
3600 *
3601 * The processing times are constrained to be non-negative.
3602 *
3603 * Throws an exception of type Int::ArgumentSizeMismatch, if \a s,
3604 * \a p, or \a m are of different size.
3605 */
3606 GECODE_INT_EXPORT void
3607 unary(Home home, const IntVarArgs& s, const IntVarArgs& p,
3608 const IntVarArgs& e, const BoolVarArgs& m, IntPropLevel ipl=IPL_DEF);
3609
3610
3611
3612 /** \brief Post propagators for scheduling tasks on cumulative resources
3613 *
3614 * Schedule tasks with flexible times \a flex, fixed times \a fix, and
3615 * use capacity \a u on a cumulative resource with capacity \a c. For each
3616 * task, it depends on \a t how the flexible and fix times are interpreted:
3617 * - If <code>t[i]</code> is <code>TT_FIXP</code>, then
3618 * <code>flex[i]</code> is the start time and <code>fix[i]</code> is the
3619 * processing time.
3620 * - If <code>t[i]</code> is <code>TT_FIXS</code>, then
3621 * <code>flex[i]</code> is the end time and <code>fix[i]</code> is the
3622 * start time.
3623 * - If <code>t[i]</code> is <code>TT_FIXE</code>, then
3624 * <code>flex[i]</code> is the start time and <code>fix[i]</code> is the
3625 * end time.
3626 *
3627 * The propagator performs propagation that depends on the integer
3628 * propagation level \a ipl as follows:
3629 * - If \a IPL_BASIC is set, the propagator performs overload checking
3630 * and time-tabling propagation.
3631 * - If \a IPL_ADVANCED is set, the propagator performs overload checking
3632 * and edge finding.
3633 * - If both flags are combined, all the above listed propagation is
3634 * performed.
3635 *
3636 * The propagator uses algorithms taken from:
3637 *
3638 * Petr Vilím, Max Energy Filtering Algorithm for Discrete Cumulative
3639 * Resources, in W. J. van Hoeve and J. N. Hooker, editors, CPAIOR, volume
3640 * 5547 of LNCS, pages 294-308. Springer, 2009.
3641 *
3642 * and
3643 *
3644 * Petr Vilím, Edge finding filtering algorithm for discrete cumulative
3645 * resources in O(kn log n). In I. P. Gent, editor, CP, volume 5732 of LNCS,
3646 * pages 802-816. Springer, 2009.
3647 *
3648 * - Throws an exception of type Int::ArgumentSizeMismatch, if \a t, \a s
3649 * \a p, or \a u are of different size.
3650 * - Throws an exception of type Int::OutOfLimits, if \a p, \a u, or \a c
3651 * contain an integer that is not nonnegative, or that could generate
3652 * an overflow.
3653 */
3654 GECODE_INT_EXPORT void
3655 cumulative(Home home, int c, const TaskTypeArgs& t,
3656 const IntVarArgs& flex, const IntArgs& fix, const IntArgs& u,
3657 IntPropLevel ipl=IPL_DEF);
3658
3659
3660 /** \brief Post propagators for scheduling tasks on cumulative resources
3661 *
3662 * \copydoc cumulative(Home,int,const TaskTypeArgs&,const IntVarArgs&,const IntArgs&,const IntArgs&,IntPropLevel)
3663 */
3664 GECODE_INT_EXPORT void
3665 cumulative(Home home, IntVar c, const TaskTypeArgs& t,
3666 const IntVarArgs& flex, const IntArgs& fix, const IntArgs& u,
3667 IntPropLevel ipl=IPL_DEF);
3668
3669 /** \brief Post propagators for scheduling optional tasks on cumulative resources
3670 *
3671 * Schedule tasks with flexible times \a flex, fixed times \a fix,
3672 * use capacity \a u, and whether a task is mandatory \a m (a task is
3673 * mandatory if the Boolean variable is 1) on a cumulative resource with
3674 * capacity \a c. For each
3675 * task, it depends on \a t how the flexible and fix times are interpreted:
3676 * - If <code>t[i]</code> is <code>TT_FIXP</code>, then
3677 * <code>flex[i]</code> is the start time and <code>fix[i]</code> is the
3678 * processing time.
3679 * - If <code>t[i]</code> is <code>TT_FIXS</code>, then
3680 * <code>flex[i]</code> is the end time and <code>fix[i]</code> is the
3681 * start time.
3682 * - If <code>t[i]</code> is <code>TT_FIXE</code>, then
3683 * <code>flex[i]</code> is the start time and <code>fix[i]</code> is the
3684 * end time.
3685 *
3686 * The propagator performs propagation that depends on the integer
3687 * propagation level \a ipl as follows:
3688 * - If \a IPL_BASIC is set, the propagator performs overload checking
3689 * and time-tabling propagation.
3690 * - If \a IPL_ADVANCED is set, the propagator performs overload checking
3691 * and edge finding.
3692 * - If both flags are combined, all the above listed propagation is
3693 * performed.
3694 *
3695 * The propagator uses algorithms taken from:
3696 *
3697 * Petr Vilím, Max Energy Filtering Algorithm for Discrete Cumulative
3698 * Resources, in W. J. van Hoeve and J. N. Hooker, editors, CPAIOR, volume
3699 * 5547 of LNCS, pages 294-308. Springer, 2009.
3700 *
3701 * and
3702 *
3703 * Petr Vilím, Edge finding filtering algorithm for discrete cumulative
3704 * resources in O(kn log n). In I. P. Gent, editor, CP, volume 5732 of LNCS,
3705 * pages 802-816. Springer, 2009.
3706 *
3707 * - Throws an exception of type Int::ArgumentSizeMismatch, if \a t, \a s
3708 * \a p, or \a u are of different size.
3709 * - Throws an exception of type Int::OutOfLimits, if \a p, \a u, or \a c
3710 * contain an integer that is not nonnegative, or that could generate
3711 * an overflow.
3712 */
3713 GECODE_INT_EXPORT void
3714 cumulative(Home home, int c, const TaskTypeArgs& t,
3715 const IntVarArgs& flex, const IntArgs& fix, const IntArgs& u,
3716 const BoolVarArgs& m, IntPropLevel ipl=IPL_DEF);
3717
3718 /** \brief Post propagators for scheduling optional tasks on cumulative resources
3719 * \copydoc cumulative(Home,int,const TaskTypeArgs&,const IntVarArgs&,const IntArgs&,const IntArgs&,const BoolVarArgs&,IntPropLevel)
3720 */
3721 GECODE_INT_EXPORT void
3722 cumulative(Home home, IntVar c, const TaskTypeArgs& t,
3723 const IntVarArgs& flex, const IntArgs& fix, const IntArgs& u,
3724 const BoolVarArgs& m, IntPropLevel ipl=IPL_DEF);
3725
3726 /** \brief Post propagators for scheduling tasks on cumulative resources
3727 *
3728 * Schedule tasks with start times \a s, processing times \a p, and
3729 * use capacity \a u on a cumulative resource with capacity \a c.
3730 *
3731 * The propagator performs propagation that depends on the integer
3732 * propagation level \a ipl as follows:
3733 * - If \a IPL_BASIC is set, the propagator performs overload checking
3734 * and time-tabling propagation.
3735 * - If \a IPL_ADVANCED is set, the propagator performs overload checking
3736 * and edge finding.
3737 * - If both flags are combined, all the above listed propagation is
3738 * performed.
3739 *
3740 * The propagator uses algorithms taken from:
3741 *
3742 * Petr Vilím, Max Energy Filtering Algorithm for Discrete Cumulative
3743 * Resources, in W. J. van Hoeve and J. N. Hooker, editors, CPAIOR, volume
3744 * 5547 of LNCS, pages 294-308. Springer, 2009.
3745 *
3746 * and
3747 *
3748 * Petr Vilím, Edge finding filtering algorithm for discrete cumulative
3749 * resources in O(kn log n). In I. P. Gent, editor, CP, volume 5732 of LNCS,
3750 * pages 802-816. Springer, 2009.
3751 *
3752 * - Throws an exception of type Int::ArgumentSizeMismatch, if \a s
3753 * \a p, or \a u are of different size.
3754 * - Throws an exception of type Int::OutOfLimits, if \a p, \a u, or \a c
3755 * contain an integer that is not nonnegative, or that could generate
3756 * an overflow.
3757 */
3758 GECODE_INT_EXPORT void
3759 cumulative(Home home, int c, const IntVarArgs& s, const IntArgs& p,
3760 const IntArgs& u, IntPropLevel ipl=IPL_DEF);
3761
3762 /** \brief Post propagators for scheduling tasks on cumulative resources
3763 * \copydoc cumulative(Home,int,const IntVarArgs&,const IntArgs&,const IntArgs&,IntPropLevel)
3764 */
3765 GECODE_INT_EXPORT void
3766 cumulative(Home home, IntVar c, const IntVarArgs& s, const IntArgs& p,
3767 const IntArgs& u, IntPropLevel ipl=IPL_DEF);
3768
3769 /** \brief Post propagators for scheduling optional tasks on cumulative resources
3770 *
3771 * Schedule optional tasks with start times \a s, processing times \a p,
3772 * used capacity \a u, and whether a task is mandatory \a m (a task is
3773 * mandatory if the Boolean variable is 1) on a cumulative resource
3774 * with capacity \a c.
3775 *
3776 * The propagator performs propagation that depends on the integer
3777 * propagation level \a ipl as follows:
3778 * - If \a IPL_BASIC is set, the propagator performs overload checking
3779 * and time-tabling propagation.
3780 * - If \a IPL_ADVANCED is set, the propagator performs overload checking
3781 * and edge finding.
3782 * - If both flags are combined, all the above listed propagation is
3783 * performed.
3784 *
3785 * The propagator uses algorithms taken from:
3786 *
3787 * Petr Vilím, Max Energy Filtering Algorithm for Discrete Cumulative
3788 * Resources, in W. J. van Hoeve and J. N. Hooker, editors, CPAIOR, volume
3789 * 5547 of LNCS, pages 294-308. Springer, 2009.
3790 *
3791 * and
3792 *
3793 * Petr Vilím, Edge finding filtering algorithm for discrete cumulative
3794 * resources in O(kn log n). In I. P. Gent, editor, CP, volume 5732 of LNCS,
3795 * pages 802-816. Springer, 2009.
3796 *
3797 * - Throws an exception of type Int::ArgumentSizeMismatch, if \a s,
3798 * \a p, \a u, or \a m are of different size.
3799 * - Throws an exception of type Int::OutOfLimits, if \a p, \a u, or \a c
3800 * contain an integer that is not nonnegative, or that could generate
3801 * an overflow.
3802 */
3803 GECODE_INT_EXPORT void
3804 cumulative(Home home, int c, const IntVarArgs& s, const IntArgs& p,
3805 const IntArgs& u, const BoolVarArgs& m, IntPropLevel ipl=IPL_DEF);
3806
3807 /** \brief Post propagators for scheduling optional tasks on cumulative resources
3808 * \copydoc cumulative(Home,int,const IntVarArgs&,const IntArgs&,const IntArgs&,const BoolVarArgs&,IntPropLevel)
3809 */
3810 GECODE_INT_EXPORT void
3811 cumulative(Home home, IntVar c, const IntVarArgs& s, const IntArgs& p,
3812 const IntArgs& u, const BoolVarArgs& m, IntPropLevel ipl=IPL_DEF);
3813
3814 /** \brief Post propagators for scheduling tasks on cumulative resources
3815 *
3816 * Schedule tasks with start times \a s, processing times \a p,
3817 * end times \a e, and
3818 * use capacity \a u on a cumulative resource with capacity \a c.
3819 *
3820 * The propagator does not enforce \f$s_i+p_i=e_i\f$, this constraint
3821 * has to be posted in addition to ensure consistency of the task bounds.
3822 *
3823 * The propagator performs propagation that depends on the integer
3824 * propagation level \a ipl as follows:
3825 * - If \a IPL_BASIC is set, the propagator performs overload checking
3826 * and time-tabling propagation.
3827 * - If \a IPL_ADVANCED is set, the propagator performs overload checking
3828 * and edge finding.
3829 * - If both flags are combined, all the above listed propagation is
3830 * performed.
3831 *
3832 * The propagator uses algorithms taken from:
3833 *
3834 * Petr Vilím, Max Energy Filtering Algorithm for Discrete Cumulative
3835 * Resources, in W. J. van Hoeve and J. N. Hooker, editors, CPAIOR, volume
3836 * 5547 of LNCS, pages 294-308. Springer, 2009.
3837 *
3838 * and
3839 *
3840 * Petr Vilím, Edge finding filtering algorithm for discrete cumulative
3841 * resources in O(kn log n). In I. P. Gent, editor, CP, volume 5732 of LNCS,
3842 * pages 802-816. Springer, 2009.
3843 *
3844 * - Throws an exception of type Int::ArgumentSizeMismatch, if \a s
3845 * \a p, or \a u are of different size.
3846 * - Throws an exception of type Int::OutOfLimits, if \a u or \a c
3847 * contain an integer that is not nonnegative, or that could generate
3848 * an overflow.
3849 */
3850 GECODE_INT_EXPORT void
3851 cumulative(Home home, int c, const IntVarArgs& s, const IntVarArgs& p,
3852 const IntVarArgs& e, const IntArgs& u, IntPropLevel ipl=IPL_DEF);
3853
3854 /** \brief Post propagators for scheduling tasks on cumulative resources
3855 * \copydoc cumulative(Home,int,const IntVarArgs&,const IntVarArgs&,const IntVarArgs&,const IntArgs&,IntPropLevel)
3856 */
3857 GECODE_INT_EXPORT void
3858 cumulative(Home home, IntVar c, const IntVarArgs& s, const IntVarArgs& p,
3859 const IntVarArgs& e, const IntArgs& u, IntPropLevel ipl=IPL_DEF);
3860
3861 /** \brief Post propagators for scheduling optional tasks on cumulative resources
3862 *
3863 * Schedule optional tasks with start times \a s, processing times \a p,
3864 * end times \a e,
3865 * used capacity \a u, and whether a task is mandatory \a m (a task is
3866 * mandatory if the Boolean variable is 1) on a cumulative resource
3867 * with capacity \a c.
3868 *
3869 * The propagator does not enforce \f$s_i+p_i=e_i\f$, this constraint
3870 * has to be posted in addition to ensure consistency of the task bounds.
3871 *
3872 * The propagator performs propagation that depends on the integer
3873 * propagation level \a ipl as follows:
3874 * - If \a IPL_BASIC is set, the propagator performs overload checking
3875 * and time-tabling propagation.
3876 * - If \a IPL_ADVANCED is set, the propagator performs overload checking
3877 * and edge finding.
3878 * - If both flags are combined, all the above listed propagation is
3879 * performed.
3880 *
3881 * The propagator uses algorithms taken from:
3882 *
3883 * Petr Vilím, Max Energy Filtering Algorithm for Discrete Cumulative
3884 * Resources, in W. J. van Hoeve and J. N. Hooker, editors, CPAIOR, volume
3885 * 5547 of LNCS, pages 294-308. Springer, 2009.
3886 *
3887 * and
3888 *
3889 * Petr Vilím, Edge finding filtering algorithm for discrete cumulative
3890 * resources in O(kn log n). In I. P. Gent, editor, CP, volume 5732 of LNCS,
3891 * pages 802-816. Springer, 2009.
3892 *
3893 * - Throws an exception of type Int::ArgumentSizeMismatch, if \a s,
3894 * \a p, \a u, or \a m are of different size.
3895 * - Throws an exception of type Int::OutOfLimits, if \a u or \a c
3896 * contain an integer that is not nonnegative, or that could generate
3897 * an overflow.
3898 */
3899 GECODE_INT_EXPORT void
3900 cumulative(Home home, int c, const IntVarArgs& s, const IntVarArgs& p,
3901 const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
3902 IntPropLevel ipl=IPL_DEF);
3903
3904 /** \brief Post propagators for scheduling optional tasks on cumulative resources
3905 * \copydoc cumulative(Home,int,const IntVarArgs&,const IntVarArgs&,const IntVarArgs&,const IntArgs&,const BoolVarArgs&,IntPropLevel)
3906 */
3907 GECODE_INT_EXPORT void
3908 cumulative(Home home, IntVar c, const IntVarArgs& s, const IntVarArgs& p,
3909 const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
3910 IntPropLevel ipl=IPL_DEF);
3911 //@}
3912
3913
3914 /**
3915 * \defgroup TaskModelIntGraph Graph constraints
3916 * \ingroup TaskModelInt
3917 */
3918 //@{
3919 /** \brief Post propagator such that \a x forms a circuit
3920 *
3921 * \a x forms a circuit if the graph with edges \f$i\to j\f$ where
3922 * \f$x_i=j\f$ has a single cycle covering all nodes.
3923 *
3924 * Supports domain (\a ipl = IPL_DOM) and value propagation (all
3925 * other values for \a ipl), where this refers to whether value or
3926 * domain consistent distinct in enforced on \a x.
3927 *
3928 * Throws the following exceptions:
3929 * - Int::ArgumentSame, if \a x contains the same unassigned variable
3930 * multiply.
3931 * - Int::TooFewArguments, if \a x has no elements.
3932 */
3933 GECODE_INT_EXPORT void
3934 circuit(Home home, const IntVarArgs& x,
3935 IntPropLevel ipl=IPL_DEF);
3936 /** \brief Post propagator such that \a x forms a circuit
3937 *
3938 * \a x forms a circuit if the graph with edges \f$i\to j\f$ where
3939 * \f$x_{i-\text{offset}}=j\f$ has a single cycle covering all nodes.
3940 *
3941 * Supports domain (\a ipl = IPL_DOM) and value propagation (all
3942 * other values for \a ipl), where this refers to whether value or
3943 * domain consistent distinct in enforced on \a x.
3944 *
3945 * Throws the following exceptions:
3946 * - Int::ArgumentSame, if \a x contains the same unassigned variable
3947 * multiply.
3948 * - Int::TooFewArguments, if \a x has no elements.
3949 * - Int::OutOfLimits, if \a offset is negative.
3950 */
3951 GECODE_INT_EXPORT void
3952 circuit(Home home, int offset, const IntVarArgs& x,
3953 IntPropLevel ipl=IPL_DEF);
3954 /** \brief Post propagator such that \a x forms a circuit with costs \a y and \a z
3955 *
3956 * \a x forms a circuit if the graph with edges \f$i\to j\f$ where
3957 * \f$x_i=j\f$ has a single cycle covering all nodes.
3958 * The integer array
3959 * \a c gives the costs of all possible edges where \f$c_{i*|x|+j}\f$ is
3960 * the cost of the edge \f$i\to j\f$. The variable \a z is the cost of
3961 * the entire circuit. The variables \a y define the cost
3962 * of the edge in \a x: that is, if \f$x_i=j\f$ then \f$y_i=c_{i*n+j}\f$.
3963 *
3964 * Supports domain (\a ipl = IPL_DOM) and value propagation (all
3965 * other values for \a ipl), where this refers to whether value or
3966 * domain consistent distinct in enforced on \a x for circuit.
3967 *
3968 * Throws the following exceptions:
3969 * - Int::ArgumentSame, if \a x contains the same unassigned variable
3970 * multiply.
3971 * - Int::TooFewArguments, if \a x has no elements.
3972 * - Int::ArgumentSizeMismatch, if \a x and \a y do not have the same
3973 * size or if \f$|x|\times|x|\neq|c|\f$.
3974 */
3975 GECODE_INT_EXPORT void
3976 circuit(Home home,
3977 const IntArgs& c,
3978 const IntVarArgs& x, const IntVarArgs& y, IntVar z,
3979 IntPropLevel ipl=IPL_DEF);
3980 /** \brief Post propagator such that \a x forms a circuit with costs \a y and \a z
3981 *
3982 * \a x forms a circuit if the graph with edges \f$i\to j\f$ where
3983 * \f$x_{i-\text{offset}}=j\f$ has a single cycle covering all nodes.
3984 * The integer array
3985 * \a c gives the costs of all possible edges where \f$c_{i*|x|+j}\f$ is
3986 * the cost of the edge \f$i\to j\f$. The variable \a z is the cost of
3987 * the entire circuit. The variables \a y define the cost
3988 * of the edge in \a x: that is, if \f$x_i=j\f$ then \f$y_i=c_{i*n+j}\f$.
3989 *
3990 * Supports domain (\a ipl = IPL_DOM) and value propagation (all
3991 * other values for \a ipl), where this refers to whether value or
3992 * domain consistent distinct in enforced on \a x for circuit.
3993 *
3994 * Throws the following exceptions:
3995 * - Int::ArgumentSame, if \a x contains the same unassigned variable
3996 * multiply.
3997 * - Int::TooFewArguments, if \a x has no elements.
3998 * - Int::ArgumentSizeMismatch, if \a x and \a y do not have the same
3999 * size or if \f$|x|\times|x|\neq|c|\f$.
4000 * - Int::OutOfLimits, if \a offset is negative.
4001 */
4002 GECODE_INT_EXPORT void
4003 circuit(Home home,
4004 const IntArgs& c, int offset,
4005 const IntVarArgs& x, const IntVarArgs& y, IntVar z,
4006 IntPropLevel ipl=IPL_DEF);
4007 /** \brief Post propagator such that \a x forms a circuit with cost \a z
4008 *
4009 * \a x forms a circuit if the graph with edges \f$i\to j\f$ where
4010 * \f$x_i=j\f$ has a single cycle covering all nodes. The integer array
4011 * \a c gives the costs of all possible edges where \f$c_{i*|x|+j}\f$ is
4012 * the cost of the edge \f$i\to j\f$. The variable \a z is the cost of
4013 * the entire circuit.
4014 *
4015 * Supports domain (\a ipl = IPL_DOM) and value propagation (all
4016 * other values for \a ipl), where this refers to whether value or
4017 * domain consistent distinct in enforced on \a x for circuit.
4018 *
4019 * Throws the following exceptions:
4020 * - Int::ArgumentSame, if \a x contains the same unassigned variable
4021 * multiply.
4022 * - Int::TooFewArguments, if \a x has no elements.
4023 * - Int::ArgumentSizeMismatch, if \f$|x|\times|x|\neq|c|\f$.
4024 */
4025 GECODE_INT_EXPORT void
4026 circuit(Home home,
4027 const IntArgs& c,
4028 const IntVarArgs& x, IntVar z,
4029 IntPropLevel ipl=IPL_DEF);
4030 /** \brief Post propagator such that \a x forms a circuit with cost \a z
4031 *
4032 * \a x forms a circuit if the graph with edges \f$i\to j\f$ where
4033 * \f$x_{i-\text{offset}}=j\f$ has a single cycle covering all nodes.
4034 * The integer array
4035 * \a c gives the costs of all possible edges where \f$c_{i*|x|+j}\f$ is
4036 * the cost of the edge \f$i\to j\f$. The variable \a z is the cost of
4037 * the entire circuit.
4038 *
4039 * Supports domain (\a ipl = IPL_DOM) and value propagation (all
4040 * other values for \a ipl), where this refers to whether value or
4041 * domain consistent distinct in enforced on \a x for circuit.
4042 *
4043 * Throws the following exceptions:
4044 * - Int::ArgumentSame, if \a x contains the same unassigned variable
4045 * multiply.
4046 * - Int::TooFewArguments, if \a x has no elements.
4047 * - Int::ArgumentSizeMismatch, if \f$|x|\times|x|\neq|c|\f$.
4048 * - Int::OutOfLimits, if \a offset is negative.
4049 */
4050 GECODE_INT_EXPORT void
4051 circuit(Home home,
4052 const IntArgs& c, int offset,
4053 const IntVarArgs& x, IntVar z,
4054 IntPropLevel ipl=IPL_DEF);
4055 /** \brief Post propagator such that \a x forms a Hamiltonian path
4056 *
4057 * \a x forms a Hamiltonian path if the graph with edges \f$i\to j\f$
4058 * where \f$x_i=j\f$ visits all nodes exactly once. The path starts at
4059 * node \a s and the successor of the last node \a e is equal to \f$|x|\f$.
4060 *
4061 * Supports domain (\a ipl = IPL_DOM) and value propagation (all
4062 * other values for \a ipl), where this refers to whether value or
4063 * domain consistent distinct in enforced on \a x.
4064 *
4065 * Throws the following exceptions:
4066 * - Int::ArgumentSame, if \a x contains the same unassigned variable
4067 * multiply.
4068 * - Int::TooFewArguments, if \a x has no elements.
4069 */
4070 GECODE_INT_EXPORT void
4071 path(Home home, const IntVarArgs& x, IntVar s, IntVar e,
4072 IntPropLevel ipl=IPL_DEF);
4073 /** \brief Post propagator such that \a x forms a Hamiltonian path
4074 *
4075 * \a x forms a Hamiltonian path if the graph with edges \f$i\to j\f$
4076 * where \f$x_{i-\text{offset}}=j\f$ visits all nodes exactly once.
4077 * The path starts at node \a s and the successor of the last node \a e
4078 * is equal to \f$|x|+\text{offset}\f$.
4079 *
4080 * Supports domain (\a ipl = IPL_DOM) and value propagation (all
4081 * other values for \a ipl), where this refers to whether value or
4082 * domain consistent distinct in enforced on \a x.
4083 *
4084 * Throws the following exceptions:
4085 * - Int::ArgumentSame, if \a x contains the same unassigned variable
4086 * multiply.
4087 * - Int::TooFewArguments, if \a x has no elements.
4088 * - Int::OutOfLimits, if \a offset is negative.
4089 */
4090 GECODE_INT_EXPORT void
4091 path(Home home, int offset, const IntVarArgs& x, IntVar s, IntVar e,
4092 IntPropLevel ipl=IPL_DEF);
4093 /** \brief Post propagator such that \a x forms a Hamiltonian path with costs \a y and \a z
4094 *
4095 * \a x forms a Hamiltonian path if the graph with edges \f$i\to j\f$
4096 * where \f$x_i=j\f$ visits all nodes exactly once. The path starts at node
4097 * \a s and the successor of
4098 * the last node \a e is equal to \f$|x|\f$. The integer array
4099 * \a c gives the costs of all possible edges where \f$c_{i*|x|+j}\f$ is
4100 * the cost of the edge \f$i\to j\f$. The variable \a z is the cost of
4101 * the entire path. The variables \a y define the cost
4102 * of the edge in \a x: that is, if \f$x_i=j\f$ then \f$y_i=c_{i*n+j}\f$.
4103 *
4104 * Supports domain (\a ipl = IPL_DOM) and value propagation (all
4105 * other values for \a ipl), where this refers to whether value or
4106 * domain consistent distinct in enforced on \a x for circuit.
4107 *
4108 * Throws the following exceptions:
4109 * - Int::ArgumentSame, if \a x contains the same unassigned variable
4110 * multiply.
4111 * - Int::TooFewArguments, if \a x has no elements.
4112 * - Int::ArgumentSizeMismacth, if \a x and \a y do not have the same
4113 * size or if \f$|x|\times|x|\neq|c|\f$.
4114 */
4115 GECODE_INT_EXPORT void
4116 path(Home home,
4117 const IntArgs& c,
4118 const IntVarArgs& x, IntVar s, IntVar e, const IntVarArgs& y, IntVar z,
4119 IntPropLevel ipl=IPL_DEF);
4120 /** \brief Post propagator such that \a x forms a Hamiltonian path with costs \a y and \a z
4121 *
4122 * \a x forms a Hamiltonian path if the graph with edges \f$i\to j\f$
4123 * where \f$x_{i-\text{offset}}=j\f$ visits all nodes exactly once.
4124 * The path starts at node \a s and the successor of
4125 * the last node \a e is equal to \f$|x|+\text{offset}\f$.
4126 * The integer array
4127 * \a c gives the costs of all possible edges where \f$c_{i*|x|+j}\f$ is
4128 * the cost of the edge \f$i\to j\f$. The variable \a z is the cost of
4129 * the entire path. The variables \a y define the cost
4130 * of the edge in \a x: that is, if \f$x_i=j\f$ then \f$y_i=c_{i*n+j}\f$.
4131 *
4132 * Supports domain (\a ipl = IPL_DOM) and value propagation (all
4133 * other values for \a ipl), where this refers to whether value or
4134 * domain consistent distinct in enforced on \a x for circuit.
4135 *
4136 * Throws the following exceptions:
4137 * - Int::ArgumentSame, if \a x contains the same unassigned variable
4138 * multiply.
4139 * - Int::TooFewArguments, if \a x has no elements.
4140 * - Int::ArgumentSizeMismacth, if \a x and \a y do not have the same
4141 * size or if \f$|x|\times|x|\neq|c|\f$.
4142 * - Int::OutOfLimits, if \a offset is negative.
4143 */
4144 GECODE_INT_EXPORT void
4145 path(Home home,
4146 const IntArgs& c, int offset,
4147 const IntVarArgs& x, IntVar s, IntVar e, const IntVarArgs& y, IntVar z,
4148 IntPropLevel ipl=IPL_DEF);
4149 /** \brief Post propagator such that \a x forms a Hamiltonian path with cost \a z
4150 *
4151 * \a x forms a Hamiltonian path if the graph with edges \f$i\to j\f$
4152 * where \f$x_i=j\f$ visits all nodes exactly once. The path starts at node
4153 * \a s and the successor of
4154 * the last node \a e is equal to \f$|x|\f$. The integer array
4155 * \a c gives the costs of all possible edges where \f$c_{i*|x|+j}\f$ is
4156 * the cost of the edge \f$i\to j\f$. The variable \a z is the cost of
4157 * the entire path.
4158 *
4159 * Supports domain (\a ipl = IPL_DOM) and value propagation (all
4160 * other values for \a ipl), where this refers to whether value or
4161 * domain consistent distinct in enforced on \a x for circuit.
4162 *
4163 * Throws the following exceptions:
4164 * - Int::ArgumentSame, if \a x contains the same unassigned variable
4165 * multiply.
4166 * - Int::TooFewArguments, if \a x has no elements.
4167 * - Int::ArgumentSizeMismacth, if \f$|x|\times|x|\neq|c|\f$.
4168 */
4169 GECODE_INT_EXPORT void
4170 path(Home home,
4171 const IntArgs& c,
4172 const IntVarArgs& x, IntVar s, IntVar e, IntVar z,
4173 IntPropLevel ipl=IPL_DEF);
4174 /** \brief Post propagator such that \a x forms a Hamiltonian path with cost \a z
4175 *
4176 * \a x forms a Hamiltonian path if the graph with edges \f$i\to j\f$
4177 * where \f$x_{i-\text{offset}}=j\f$ visits all nodes exactly once.
4178 * The path starts at node \a s and the successor of
4179 * the last node \a e is equal to \f$|x|+\text{offset}\f$.
4180 * The integer array
4181 * \a c gives the costs of all possible edges where \f$c_{i*|x|+j}\f$ is
4182 * the cost of the edge \f$i\to j\f$. The variable \a z is the cost of
4183 * the entire circuit.
4184 *
4185 * Supports domain (\a ipl = IPL_DOM) and value propagation (all
4186 * other values for \a ipl), where this refers to whether value or
4187 * domain consistent distinct in enforced on \a x for circuit.
4188 *
4189 * Throws the following exceptions:
4190 * - Int::ArgumentSame, if \a x contains the same unassigned variable
4191 * multiply.
4192 * - Int::TooFewArguments, if \a x has no elements.
4193 * - Int::ArgumentSizeMismacth, if \f$|x|\times|x|\neq|c|\f$.
4194 * - Int::OutOfLimits, if \a offset is negative.
4195 */
4196 GECODE_INT_EXPORT void
4197 path(Home home,
4198 const IntArgs& c, int offset,
4199 const IntVarArgs& x, IntVar s, IntVar e, IntVar z,
4200 IntPropLevel ipl=IPL_DEF);
4201 //@}
4202
4203
4204
4205 /**
4206 * \defgroup TaskModelIntExec Synchronized execution
4207 * \ingroup TaskModelInt
4208 *
4209 * Synchronized execution executes a function or a static member function
4210 * when a certain event happends.
4211 */
4212 //@{
4213 /// Execute \a c when \a x becomes assigned
4214 GECODE_INT_EXPORT void
4215 wait(Home home, IntVar x, std::function<void(Space& home)> c,
4216 IntPropLevel ipl=IPL_DEF);
4217 /// Execute \a c when \a x becomes assigned
4218 GECODE_INT_EXPORT void
4219 wait(Home home, BoolVar x, std::function<void(Space& home)> c,
4220 IntPropLevel ipl=IPL_DEF);
4221 /// Execute \a c when all variables in \a x become assigned
4222 GECODE_INT_EXPORT void
4223 wait(Home home, const IntVarArgs& x, std::function<void(Space& home)> c,
4224 IntPropLevel ipl=IPL_DEF);
4225 /// Execute \a c when all variables in \a x become assigned
4226 GECODE_INT_EXPORT void
4227 wait(Home home, const BoolVarArgs& x,
4228 std::function<void(Space& home)> c,
4229 IntPropLevel ipl=IPL_DEF);
4230 /// Execute \a t (then) when \a x is assigned one, and \a e (else) otherwise
4231 GECODE_INT_EXPORT void
4232 when(Home home, BoolVar x,
4233 std::function<void(Space& home)> t,
4234 std::function<void(Space& home)> e,
4235 IntPropLevel ipl=IPL_DEF);
4236 /// Execute \a t (then) when \a x is assigned one
4237 GECODE_INT_EXPORT void
4238 when(Home home, BoolVar x,
4239 std::function<void(Space& home)> t,
4240 IntPropLevel ipl=IPL_DEF);
4241 //@}
4242
4243
4244 /**
4245 * \defgroup TaskModelIntUnshare Unsharing variables
4246 * \ingroup TaskModelInt
4247 *
4248 * Unsharing replaces multiple occurences of the same variable by
4249 * fresh yet equal (enforced through propagators for equality)
4250 * variables: after unsharing a variable appears at most once. Note
4251 * that this is only done for not yet assigned variables (as all
4252 * propagators can handle multiple occurences of the same variable
4253 * provided it is already assigned).
4254 *
4255 * Unsharing is useful for constraints that only accept variable
4256 * arrays without multiple occurences of the same variable, for
4257 * example extensional.
4258 *
4259 */
4260 //@{
4261 /**
4262 * \brief Replace multiple variable occurences in \a x by fresh variables
4263 *
4264 * Supports domain consistency (\a ipl = IPL_DOM, default) and
4265 * bounds consistency (\a ipl = IPL_BND).
4266 *
4267 */
4268 GECODE_INT_EXPORT void
4269 unshare(Home home, IntVarArgs& x,
4270 IntPropLevel ipl=IPL_DEF);
4271 /// Replace multiple variable occurences in \a x by fresh variables
4272 GECODE_INT_EXPORT void
4273 unshare(Home home, BoolVarArgs& x,
4274 IntPropLevel ipl=IPL_DEF);
4275 //@}
4276
4277}
4278
4279namespace Gecode {
4280
4281 /**
4282 * \defgroup TaskModelIntBranch Branching
4283 * \ingroup TaskModelInt
4284 */
4285
4286 /**
4287 * \brief Branch filter function type for integer variables
4288 *
4289 * The variable \a x is considered for selection and \a i refers to the
4290 * variable's position in the original array passed to the brancher.
4291 *
4292 * \ingroup TaskModelIntBranch
4293 */
4294 typedef std::function<bool(const Space& home, IntVar x, int i)>
4295 IntBranchFilter;
4296 /**
4297 * \brief Branch filter function type for Boolean variables
4298 *
4299 * The variable \a x is considered for selection and \a i refers to the
4300 * variable's position in the original array passed to the brancher.
4301 *
4302 * \ingroup TaskModelIntBranch
4303 */
4304 typedef std::function<bool(const Space& home, BoolVar x, int i)>
4305 BoolBranchFilter;
4306
4307 /**
4308 * \brief Branch merit function type for integer variables
4309 *
4310 * The function must return a merit value for the variable
4311 * \a x. The integer \a i refers to the variable's position
4312 * in the original array passed to the brancher.
4313 *
4314 * \ingroup TaskModelIntBranch
4315 */
4316 typedef std::function<double(const Space& home, IntVar x, int i)>
4317 IntBranchMerit;
4318 /**
4319 * \brief Branch merit function type for Boolean variables
4320 *
4321 * The function must return a merit value for the variable
4322 * \a x. The integer \a i refers to the variable's position
4323 * in the original array passed to the brancher.
4324 *
4325 * \ingroup TaskModelIntBranch
4326 */
4327 typedef std::function<double(const Space& home, BoolVar x, int i)>
4328 BoolBranchMerit;
4329
4330 /**
4331 * \brief Branch value function type for integer variables
4332 *
4333 * Returns a value for the variable \a x that is to be used in the
4334 * corresponding branch commit function. The integer \a i refers
4335 * to the variable's position in the original array passed to the
4336 * brancher.
4337 *
4338 * \ingroup TaskModelIntBranch
4339 */
4340 typedef std::function<int(const Space& home, IntVar x, int i)>
4341 IntBranchVal;
4342 /**
4343 * \brief Branch value function type for Boolean variables
4344 *
4345 * Returns a value for the variable \a x that is to be used in the
4346 * corresponding branch commit function. The integer \a i refers
4347 * to the variable's position in the original array passed to the
4348 * brancher.
4349 *
4350 * \ingroup TaskModelIntBranch
4351 */
4352 typedef std::function<int(const Space& home, BoolVar x, int i)>
4353 BoolBranchVal;
4354
4355 /**
4356 * \brief Branch commit function type for integer variables
4357 *
4358 * The function must post a constraint on the variable \a x which
4359 * corresponds to the alternative \a a. The integer \a i refers
4360 * to the variable's position in the original array passed to the
4361 * brancher. The value \a n is the value
4362 * computed by the corresponding branch value function.
4363 *
4364 * \ingroup TaskModelIntBranch
4365 */
4366 typedef std::function<void(Space& home, unsigned int a,
4367 IntVar x, int i, int n)>
4368 IntBranchCommit;
4369 /**
4370 * \brief Branch commit function type for Boolean variables
4371 *
4372 * The function must post a constraint on the variable \a x which
4373 * corresponds to the alternative \a a. The integer \a i refers
4374 * to the variable's position in the original array passed to the
4375 * brancher. The value \a n is the value
4376 * computed by the corresponding branch value function.
4377 *
4378 * \ingroup TaskModelIntBranch
4379 */
4380 typedef std::function<void(Space& home, unsigned int a,
4381 BoolVar x, int i, int n)>
4382 BoolBranchCommit;
4383
4384}
4385
4386#include <gecode/int/branch/traits.hpp>
4387
4388namespace Gecode {
4389
4390 /**
4391 * \brief Recording AFC information for integer variables
4392 *
4393 * \ingroup TaskModelIntBranch
4394 */
4395 class IntAFC : public AFC {
4396 public:
4397 /**
4398 * \brief Construct as not yet initialized
4399 *
4400 * The only member functions that can be used on a constructed but not
4401 * yet initialized AFC storage is init or the assignment operator.
4402 *
4403 */
4404 IntAFC(void);
4405 /// Copy constructor
4406 IntAFC(const IntAFC& a);
4407 /// Assignment operator
4408 IntAFC& operator =(const IntAFC& a);
4409 /**
4410 * \brief Initialize for integer variables \a x and decay factor \a d
4411 *
4412 * If several AFC objects are created for a space or its clones,
4413 * the AFC values are shared between spaces. If the values should
4414 * not be shared, \a share should be false.
4415 */
4416 IntAFC(Home home, const IntVarArgs& x, double d=1.0, bool share=true);
4417 /**
4418 * \brief Initialize for integer variables \a x with decay factor \a d
4419 *
4420 * This member function can only be used once and only if the
4421 * AFC storage has been constructed with the default constructor.
4422 *
4423 * If several AFC objects are created for a space or its clones,
4424 * the AFC values are shared between spaces. If the values should
4425 * not be shared, \a share should be false.
4426 */
4427 void init(Home home, const IntVarArgs& x, double d=1.0, bool share=true);
4428 };
4429
4430 /**
4431 * \brief Recording AFC information for Boolean variables
4432 *
4433 * \ingroup TaskModelIntBranch
4434 */
4435 class BoolAFC : public AFC {
4436 public:
4437 /**
4438 * \brief Construct as not yet initialized
4439 *
4440 * The only member functions that can be used on a constructed but not
4441 * yet initialized AFC storage is init or the assignment operator.
4442 *
4443 */
4444 BoolAFC(void);
4445 /// Copy constructor
4446 BoolAFC(const BoolAFC& a);
4447 /// Assignment operator
4448 BoolAFC& operator =(const BoolAFC& a);
4449 /**
4450 * \brief Initialize for Boolean variables \a x and decay factor \a d
4451 *
4452 * If several AFC objects are created for a space or its clones,
4453 * the AFC values are shared between spaces. If the values should
4454 * not be shared, \a share should be false.
4455 */
4456 BoolAFC(Home home, const BoolVarArgs& x, double d=1.0, bool share=true);
4457 /**
4458 * \brief Initialize for Boolean variables \a x with decay factor \a d
4459 *
4460 * This member function can only be used once and only if the
4461 * AFC storage has been constructed with the default constructor.
4462 *
4463 * If several AFC objects are created for a space or its clones,
4464 * the AFC values are shared between spaces. If the values should
4465 * not be shared, \a share should be false.
4466 */
4467 void init(Home home, const BoolVarArgs& x, double d=1.0, bool share=true);
4468 };
4469
4470}
4471
4472#include <gecode/int/branch/afc.hpp>
4473
4474namespace Gecode {
4475
4476 /**
4477 * \brief Recording actions for integer variables
4478 *
4479 * \ingroup TaskModelIntBranch
4480 */
4481 class IntAction : public Action {
4482 public:
4483 /**
4484 * \brief Construct as not yet initialized
4485 *
4486 * The only member functions that can be used on a constructed but not
4487 * yet initialized action storage is init or the assignment operator.
4488 *
4489 */
4490 IntAction(void);
4491 /// Copy constructor
4492 IntAction(const IntAction& a);
4493 /// Assignment operator
4494 IntAction& operator =(const IntAction& a);
4495 /**
4496 * \brief Initialize for integer variables \a x with decay factor \a d
4497 *
4498 * Counts propagation if \a p is true and failure if \a f is true.
4499 *
4500 * If the branch merit function \a bm is different from nullptr, the
4501 * action for each variable is initialized with the merit returned
4502 * by \a bm.
4503 */
4504 GECODE_INT_EXPORT
4505 IntAction(Home home, const IntVarArgs& x, double d=1.0,
4506 bool p=true, bool f=true,
4507 IntBranchMerit bm=nullptr);
4508 /**
4509 * \brief Initialize for integer variables \a x with decay factor \a d
4510 *
4511 * Counts propagation if \a p is true and failure if \a f is true.
4512 *
4513 * If the branch merit function \a bm is different from nullptr, the
4514 * action for each variable is initialized with the merit returned
4515 * by \a bm.
4516 *
4517 * This member function can only be used once and only if the
4518 * action storage has been constructed with the default constructor.
4519 *
4520 */
4521 GECODE_INT_EXPORT void
4522 init(Home home, const IntVarArgs& x, double d=1.0,
4523 bool p=true, bool f=true,
4524 IntBranchMerit bm=nullptr);
4525 };
4526
4527 /**
4528 * \brief Recording actions for Boolean variables
4529 *
4530 * \ingroup TaskModelIntBranch
4531 */
4532 class BoolAction : public Action {
4533 public:
4534 /**
4535 * \brief Construct as not yet initialized
4536 *
4537 * The only member functions that can be used on a constructed but not
4538 * yet initialized action storage is init or the assignment operator.
4539 *
4540 */
4541 BoolAction(void);
4542 /// Copy constructor
4543 BoolAction(const BoolAction& a);
4544 /// Assignment operator
4545 BoolAction& operator =(const BoolAction& a);
4546 /**
4547 * \brief Initialize for Boolean variables \a x with decay factor \a d
4548 *
4549 * Counts propagation if \a p is true and failure if \a f is true.
4550 *
4551 * If the branch merit function \a bm is different from nullptr, the
4552 * action for each variable is initialized with the merit returned
4553 * by \a bm.
4554 */
4555 GECODE_INT_EXPORT
4556 BoolAction(Home home, const BoolVarArgs& x, double d=1.0,
4557 bool p=true, bool f=true,
4558 BoolBranchMerit bm=nullptr);
4559 /**
4560 * \brief Initialize for Boolean variables \a x with decay factor \a d
4561 *
4562 * Counts propagation if \a p is true and failure if \a f is true.
4563 *
4564 * If the branch merit function \a bm is different from nullptr, the
4565 * action for each variable is initialized with the merit returned
4566 * by \a bm.
4567 *
4568 * This member function can only be used once and only if the
4569 * action storage has been constructed with the default constructor.
4570 *
4571 */
4572 GECODE_INT_EXPORT void
4573 init(Home home, const BoolVarArgs& x, double d=1.0,
4574 bool p=true, bool f=true,
4575 BoolBranchMerit bm=nullptr);
4576 };
4577
4578}
4579
4580#include <gecode/int/branch/action.hpp>
4581
4582namespace Gecode {
4583
4584 /**
4585 * \brief Recording CHB for integer variables
4586 *
4587 * \ingroup TaskModelIntBranch
4588 */
4589 class IntCHB : public CHB {
4590 public:
4591 /**
4592 * \brief Construct as not yet initialized
4593 *
4594 * The only member functions that can be used on a constructed but not
4595 * yet initialized CHB storage is init or the assignment operator.
4596 *
4597 */
4598 IntCHB(void);
4599 /// Copy constructor
4600 IntCHB(const IntCHB& chb);
4601 /// Assignment operator
4602 IntCHB& operator =(const IntCHB& chb);
4603 /**
4604 * \brief Initialize for integer variables \a x
4605 *
4606 * If the branch merit function \a bm is different from nullptr, the
4607 * action for each variable is initialized with the merit returned
4608 * by \a bm.
4609 *
4610 */
4611 GECODE_INT_EXPORT
4612 IntCHB(Home home, const IntVarArgs& x, IntBranchMerit bm=nullptr);
4613 /**
4614 * \brief Initialize for integer variables \a x
4615 *
4616 * If the branch merit function \a bm is different from nullptr, the
4617 * action for each variable is initialized with the merit returned
4618 * by \a bm.
4619 *
4620 * This member function can only be used once and only if the
4621 * action storage has been constructed with the default constructor.
4622 *
4623 */
4624 GECODE_INT_EXPORT void
4625 init(Home home, const IntVarArgs& x, IntBranchMerit bm=nullptr);
4626 };
4627
4628 /**
4629 * \brief Recording CHB for Boolean variables
4630 *
4631 * \ingroup TaskModelIntBranch
4632 */
4633 class BoolCHB : public CHB {
4634 public:
4635 /**
4636 * \brief Construct as not yet initialized
4637 *
4638 * The only member functions that can be used on a constructed but not
4639 * yet initialized action storage is init or the assignment operator.
4640 *
4641 */
4642 BoolCHB(void);
4643 /// Copy constructor
4644 BoolCHB(const BoolCHB& chb);
4645 /// Assignment operator
4646 BoolCHB& operator =(const BoolCHB& chb);
4647 /**
4648 * \brief Initialize for Boolean variables \a x
4649 *
4650 * If the branch merit function \a bm is different from nullptr, the
4651 * action for each variable is initialized with the merit returned
4652 * by \a bm.
4653 *
4654 */
4655 GECODE_INT_EXPORT
4656 BoolCHB(Home home, const BoolVarArgs& x, BoolBranchMerit bm=nullptr);
4657 /**
4658 * \brief Initialize for Boolean variables \a x
4659 *
4660 * If the branch merit function \a bm is different from nullptr, the
4661 * action for each variable is initialized with the merit returned
4662 * by \a bm.
4663 *
4664 * This member function can only be used once and only if the
4665 * action storage has been constructed with the default constructor.
4666 *
4667 */
4668 GECODE_INT_EXPORT void
4669 init(Home home, const BoolVarArgs& x, BoolBranchMerit bm=nullptr);
4670 };
4671
4672}
4673
4674#include <gecode/int/branch/chb.hpp>
4675
4676namespace Gecode {
4677
4678 /// Function type for printing branching alternatives for integer variables
4679 typedef std::function<void(const Space &home, const Brancher& b,
4680 unsigned int a,
4681 IntVar x, int i, const int& n,
4682 std::ostream& o)>
4683 IntVarValPrint;
4684
4685 /// Function type for printing branching alternatives for Boolean variables
4686 typedef std::function<void(const Space &home, const Brancher& b,
4687 unsigned int a,
4688 BoolVar x, int i, const int& n,
4689 std::ostream& o)>
4690 BoolVarValPrint;
4691
4692}
4693
4694namespace Gecode {
4695
4696 /**
4697 * \brief Which integer variable to select for branching
4698 *
4699 * \ingroup TaskModelIntBranch
4700 */
4701 class IntVarBranch : public VarBranch<IntVar> {
4702 public:
4703 /// Which variable selection
4704 enum Select {
4705 SEL_NONE = 0, ///< First unassigned
4706 SEL_RND, ///< Random (uniform, for tie breaking)
4707 SEL_MERIT_MIN, ///< With least merit
4708 SEL_MERIT_MAX, ///< With highest merit
4709 SEL_DEGREE_MIN, ///< With smallest degree
4710 SEL_DEGREE_MAX, ///< With largest degree
4711 SEL_AFC_MIN, ///< With smallest accumulated failure count
4712 SEL_AFC_MAX, ///< With largest accumulated failure count
4713 SEL_ACTION_MIN, ///< With lowest action
4714 SEL_ACTION_MAX, ///< With highest action
4715 SEL_CHB_MIN, ///< With lowest CHB Q-score
4716 SEL_CHB_MAX, ///< With highest CHB Q-score
4717 SEL_MIN_MIN, ///< With smallest min
4718 SEL_MIN_MAX, ///< With largest min
4719 SEL_MAX_MIN, ///< With smallest max
4720 SEL_MAX_MAX, ///< With largest max
4721 SEL_SIZE_MIN, ///< With smallest domain size
4722 SEL_SIZE_MAX, ///< With largest domain size
4723 SEL_DEGREE_SIZE_MIN, ///< With smallest degree divided by domain size
4724 SEL_DEGREE_SIZE_MAX, ///< With largest degree divided by domain size
4725 SEL_AFC_SIZE_MIN, ///< With smallest accumulated failure count divided by domain size
4726 SEL_AFC_SIZE_MAX, ///< With largest accumulated failure count divided by domain size
4727 SEL_ACTION_SIZE_MIN, ///< With smallest action divided by domain size
4728 SEL_ACTION_SIZE_MAX, ///< With largest action divided by domain size
4729 SEL_CHB_SIZE_MIN, ///< With smallest CHB Q-score divided by domain size
4730 SEL_CHB_SIZE_MAX, ///< With largest CHB Q-score divided by domain size
4731 /** \brief With smallest min-regret
4732 *
4733 * The min-regret of a variable is the difference between the
4734 * smallest and second-smallest value still in the domain.
4735 */
4736 SEL_REGRET_MIN_MIN,
4737 /** \brief With largest min-regret
4738 *
4739 * The min-regret of a variable is the difference between the
4740 * smallest and second-smallest value still in the domain.
4741 */
4742 SEL_REGRET_MIN_MAX,
4743 /** \brief With smallest max-regret
4744 *
4745 * The max-regret of a variable is the difference between the
4746 * largest and second-largest value still in the domain.
4747 */
4748 SEL_REGRET_MAX_MIN,
4749 /** \brief With largest max-regret
4750 *
4751 * The max-regret of a variable is the difference between the
4752 * largest and second-largest value still in the domain.
4753 */
4754 SEL_REGRET_MAX_MAX
4755 };
4756 protected:
4757 /// Which variable to select
4758 Select s;
4759 public:
4760 /// Initialize with strategy SEL_NONE
4761 IntVarBranch(void);
4762 /// Initialize with random number generator \a r
4763 IntVarBranch(Rnd r);
4764 /// Initialize with selection strategy \a s and tie-break limit function \a t
4765 IntVarBranch(Select s, BranchTbl t);
4766 /// Initialize with selection strategy \a s, decay factor \a d, and tie-break limit function \a t
4767 IntVarBranch(Select s, double d, BranchTbl t);
4768 /// Initialize with selection strategy \a s, AFC \a a, and tie-break limit function \a t
4769 IntVarBranch(Select s, IntAFC a, BranchTbl t);
4770 /// Initialize with selection strategy \a s, action \a a, and tie-break limit function \a t
4771 IntVarBranch(Select s, IntAction a, BranchTbl t);
4772 /// Initialize with selection strategy \a s, CHB \a c, and tie-break limit function \a t
4773 IntVarBranch(Select s, IntCHB c, BranchTbl t);
4774 /// Initialize with selection strategy \a s, branch merit function \a mf, and tie-break limit function \a t
4775 IntVarBranch(Select s, IntBranchMerit mf, BranchTbl t);
4776 /// Return selection strategy
4777 Select select(void) const;
4778 /// Expand AFC, action, and CHB
4779 void expand(Home home, const IntVarArgs& x);
4780 };
4781
4782 /**
4783 * \brief Which Boolean variable to select for branching
4784 *
4785 * \ingroup TaskModelIntBranch
4786 */
4787 class BoolVarBranch : public VarBranch<BoolVar> {
4788 public:
4789 /// Which variable selection
4790 enum Select {
4791 SEL_NONE = 0, ///< First unassigned
4792 SEL_RND, ///< Random (uniform, for tie breaking)
4793 SEL_MERIT_MIN, ///< With least merit
4794 SEL_MERIT_MAX, ///< With highest merit
4795 SEL_DEGREE_MIN, ///< With smallest degree
4796 SEL_DEGREE_MAX, ///< With largest degree
4797 SEL_AFC_MIN, ///< With smallest accumulated failure count
4798 SEL_AFC_MAX, ///< With largest accumulated failure count
4799 SEL_ACTION_MIN, ///< With lowest action
4800 SEL_ACTION_MAX, ///< With highest action
4801 SEL_CHB_MIN, ///< With lowest CHB
4802 SEL_CHB_MAX ///< With highest CHB
4803 };
4804 protected:
4805 /// Which variable to select
4806 Select s;
4807 public:
4808 /// Initialize with strategy SEL_NONE
4809 BoolVarBranch(void);
4810 /// Initialize with random number generator \a r
4811 BoolVarBranch(Rnd r);
4812 /// Initialize with selection strategy \a s and tie-break limit function \a t
4813 BoolVarBranch(Select s, BranchTbl t);
4814 /// Initialize with selection strategy \a s, decay factor \a d, and tie-break limit function \a t
4815 BoolVarBranch(Select s, double d, BranchTbl t);
4816 /// Initialize with selection strategy \a s, AFC \a a, and tie-break limit function \a t
4817 BoolVarBranch(Select s, BoolAFC a, BranchTbl t);
4818 /// Initialize with selection strategy \a s, action \a a, and tie-break limit function \a t
4819 BoolVarBranch(Select s, BoolAction a, BranchTbl t);
4820 /// Initialize with selection strategy \a s, CHB \a c, and tie-break limit function \a t
4821 BoolVarBranch(Select s, BoolCHB c, BranchTbl t);
4822 /// Initialize with selection strategy \a s, branch merit function \a mf, and tie-break limit function \a t
4823 BoolVarBranch(Select s, BoolBranchMerit mf, BranchTbl t);
4824 /// Return selection strategy
4825 Select select(void) const;
4826 /// Expand decay factor into AFC or action
4827 void expand(Home home, const BoolVarArgs& x);
4828 };
4829
4830 /**
4831 * \defgroup TaskModelIntBranchVar Variable selection for integer and Boolean variables
4832 * \ingroup TaskModelIntBranch
4833 */
4834 //@{
4835 /// Select first unassigned variable
4836 IntVarBranch INT_VAR_NONE(void);
4837 /// Select random variable (uniform distribution, for tie breaking)
4838 IntVarBranch INT_VAR_RND(Rnd r);
4839 /// Select variable with least merit according to branch merit function \a bm
4840 IntVarBranch INT_VAR_MERIT_MIN(IntBranchMerit bm, BranchTbl tbl=nullptr);
4841 /// Select variable with highest merit according to branch merit function \a bm
4842 IntVarBranch INT_VAR_MERIT_MAX(IntBranchMerit bm, BranchTbl tbl=nullptr);
4843 /// Select variable with smallest degree
4844 IntVarBranch INT_VAR_DEGREE_MIN(BranchTbl tbl=nullptr);
4845 /// Select variable with largest degree
4846 IntVarBranch INT_VAR_DEGREE_MAX(BranchTbl tbl=nullptr);
4847 /// Select variable with smallest accumulated failure count with decay factor \a d
4848 IntVarBranch INT_VAR_AFC_MIN(double d=1.0, BranchTbl tbl=nullptr);
4849 /// Select variable with smallest accumulated failure count
4850 IntVarBranch INT_VAR_AFC_MIN(IntAFC a, BranchTbl tbl=nullptr);
4851 /// Select variable with largest accumulated failure count with decay factor \a d
4852 IntVarBranch INT_VAR_AFC_MAX(double d=1.0, BranchTbl tbl=nullptr);
4853 /// Select variable with largest accumulated failure count
4854 IntVarBranch INT_VAR_AFC_MAX(IntAFC a, BranchTbl tbl=nullptr);
4855 /// Select variable with lowest action with decay factor \a d
4856 IntVarBranch INT_VAR_ACTION_MIN(double d=1.0, BranchTbl tbl=nullptr);
4857 /// Select variable with lowest action
4858 IntVarBranch INT_VAR_ACTION_MIN(IntAction a, BranchTbl tbl=nullptr);
4859 /// Select variable with highest action with decay factor \a d
4860 IntVarBranch INT_VAR_ACTION_MAX(double d=1.0, BranchTbl tbl=nullptr);
4861 /// Select variable with highest action
4862 IntVarBranch INT_VAR_ACTION_MAX(IntAction a, BranchTbl tbl=nullptr);
4863 /// Select variable with lowest CHB Q-score
4864 IntVarBranch INT_VAR_CHB_MIN(IntCHB c, BranchTbl tbl=nullptr);
4865 /// Select variable with lowest CHB Q-score
4866 IntVarBranch INT_VAR_CHB_MIN(BranchTbl tbl=nullptr);
4867 /// Select variable with largest CHB Q-score
4868 IntVarBranch INT_VAR_CHB_MAX(IntCHB c, BranchTbl tbl=nullptr);
4869 /// Select variable with largest CHB Q-score
4870 IntVarBranch INT_VAR_CHB_MAX(BranchTbl tbl=nullptr);
4871 /// Select variable with smallest min
4872 IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl=nullptr);
4873 /// Select variable with largest min
4874 IntVarBranch INT_VAR_MIN_MAX(BranchTbl tbl=nullptr);
4875 /// Select variable with smallest max
4876 IntVarBranch INT_VAR_MAX_MIN(BranchTbl tbl=nullptr);
4877 /// Select variable with largest max
4878 IntVarBranch INT_VAR_MAX_MAX(BranchTbl tbl=nullptr);
4879 /// Select variable with smallest domain size
4880 IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl=nullptr);
4881 /// Select variable with largest domain size
4882 IntVarBranch INT_VAR_SIZE_MAX(BranchTbl tbl=nullptr);
4883 /// Select variable with smallest degree divided by domain size
4884 IntVarBranch INT_VAR_DEGREE_SIZE_MIN(BranchTbl tbl=nullptr);
4885 /// Select variable with largest degree divided by domain size
4886 IntVarBranch INT_VAR_DEGREE_SIZE_MAX(BranchTbl tbl=nullptr);
4887 /// Select variable with smallest accumulated failure count divided by domain size with decay factor \a d
4888 IntVarBranch INT_VAR_AFC_SIZE_MIN(double d=1.0, BranchTbl tbl=nullptr);
4889 /// Select variable with smallest accumulated failure count divided by domain size
4890 IntVarBranch INT_VAR_AFC_SIZE_MIN(IntAFC a, BranchTbl tbl=nullptr);
4891 /// Select variable with largest accumulated failure count divided by domain size with decay factor \a d
4892 IntVarBranch INT_VAR_AFC_SIZE_MAX(double d=1.0, BranchTbl tbl=nullptr);
4893 /// Select variable with largest accumulated failure count divided by domain size
4894 IntVarBranch INT_VAR_AFC_SIZE_MAX(IntAFC a, BranchTbl tbl=nullptr);
4895 /// Select variable with smallest action divided by domain size with decay factor \a d
4896 IntVarBranch INT_VAR_ACTION_SIZE_MIN(double d=1.0, BranchTbl tbl=nullptr);
4897 /// Select variable with smallest action divided by domain size
4898 IntVarBranch INT_VAR_ACTION_SIZE_MIN(IntAction a, BranchTbl tbl=nullptr);
4899 /// Select variable with largest action divided by domain size with decay factor \a d
4900 IntVarBranch INT_VAR_ACTION_SIZE_MAX(double d=1.0, BranchTbl tbl=nullptr);
4901 /// Select variable with largest action divided by domain size
4902 IntVarBranch INT_VAR_ACTION_SIZE_MAX(IntAction a, BranchTbl tbl=nullptr);
4903 /// Select variable with smallest CHB Q-score divided by domain size
4904 IntVarBranch INT_VAR_CHB_SIZE_MIN(IntCHB c, BranchTbl tbl=nullptr);
4905 /// Select variable with smallest CHB Q-score divided by domain size
4906 IntVarBranch INT_VAR_CHB_SIZE_MIN(BranchTbl tbl=nullptr);
4907 /// Select variable with largest CHB Q-score divided by domain size
4908 IntVarBranch INT_VAR_CHB_SIZE_MAX(IntCHB c, BranchTbl tbl=nullptr);
4909 /// Select variable with largest CHB Q-score divided by domain size
4910 IntVarBranch INT_VAR_CHB_SIZE_MAX(BranchTbl tbl=nullptr);
4911 /** \brief Select variable with smallest min-regret
4912 *
4913 * The min-regret of a variable is the difference between the
4914 * smallest and second-smallest value still in the domain.
4915 */
4916 IntVarBranch INT_VAR_REGRET_MIN_MIN(BranchTbl tbl=nullptr);
4917 /** \brief Select variable with largest min-regret
4918 *
4919 * The min-regret of a variable is the difference between the
4920 * smallest and second-smallest value still in the domain.
4921 */
4922 IntVarBranch INT_VAR_REGRET_MIN_MAX(BranchTbl tbl=nullptr);
4923 /** \brief Select variable with smallest max-regret
4924 *
4925 * The max-regret of a variable is the difference between the
4926 * largest and second-largest value still in the domain.
4927 */
4928 IntVarBranch INT_VAR_REGRET_MAX_MIN(BranchTbl tbl=nullptr);
4929 /** \brief Select variable with largest max-regret
4930 *
4931 * The max-regret of a variable is the difference between the
4932 * largest and second-largest value still in the domain.
4933 */
4934 IntVarBranch INT_VAR_REGRET_MAX_MAX(BranchTbl tbl=nullptr);
4935
4936 /// Select first unassigned variable
4937 BoolVarBranch BOOL_VAR_NONE(void);
4938 /// Select random variable (uniform distribution, for tie breaking)
4939 BoolVarBranch BOOL_VAR_RND(Rnd r);
4940 /// Select variable with least merit according to branch merit function \a bm
4941 BoolVarBranch BOOL_VAR_MERIT_MIN(BoolBranchMerit bm, BranchTbl tbl=nullptr);
4942 /// Select variable with highest merit according to branch merit function \a bm
4943 BoolVarBranch BOOL_VAR_MERIT_MAX(BoolBranchMerit bm, BranchTbl tbl=nullptr);
4944 /// Select variable with smallest degree
4945 BoolVarBranch BOOL_VAR_DEGREE_MIN(BranchTbl tbl=nullptr);
4946 /// Select variable with largest degree
4947 BoolVarBranch BOOL_VAR_DEGREE_MAX(BranchTbl tbl=nullptr);
4948 /// Select variable with smallest accumulated failure count with decay factor \a d
4949 BoolVarBranch BOOL_VAR_AFC_MIN(double d=1.0, BranchTbl tbl=nullptr);
4950 /// Select variable with smallest accumulated failure count
4951 BoolVarBranch BOOL_VAR_AFC_MIN(BoolAFC a, BranchTbl tbl=nullptr);
4952 /// Select variable with largest accumulated failure count with decay factor \a d
4953 BoolVarBranch BOOL_VAR_AFC_MAX(double d=1.0, BranchTbl tbl=nullptr);
4954 /// Select variable with largest accumulated failure count
4955 BoolVarBranch BOOL_VAR_AFC_MAX(BoolAFC a, BranchTbl tbl=nullptr);
4956 /// Select variable with lowest action with decay factor \a d
4957 BoolVarBranch BOOL_VAR_ACTION_MIN(double d=1.0, BranchTbl tbl=nullptr);
4958 /// Select variable with lowest action
4959 BoolVarBranch BOOL_VAR_ACTION_MIN(BoolAction a, BranchTbl tbl=nullptr);
4960 /// Select variable with highest action with decay factor \a d
4961 BoolVarBranch BOOL_VAR_ACTION_MAX(double d=1.0, BranchTbl tbl=nullptr);
4962 /// Select variable with highest action
4963 BoolVarBranch BOOL_VAR_ACTION_MAX(BoolAction a, BranchTbl tbl=nullptr);
4964 /// Select variable with lowest CHB Q-score
4965 BoolVarBranch BOOL_VAR_CHB_MIN(BoolCHB c, BranchTbl tbl=nullptr);
4966 /// Select variable with lowest CHB Q-score
4967 BoolVarBranch BOOL_VAR_CHB_MIN(BranchTbl tbl=nullptr);
4968 /// Select variable with largest CHB Q-score
4969 BoolVarBranch BOOL_VAR_CHB_MAX(BoolCHB c, BranchTbl tbl=nullptr);
4970 /// Select variable with largest CHB Q-score
4971 BoolVarBranch BOOL_VAR_CHB_MAX(BranchTbl tbl=nullptr);
4972 //@}
4973
4974}
4975
4976#include <gecode/int/branch/var.hpp>
4977
4978namespace Gecode {
4979
4980 /**
4981 * \brief Which values to select for branching first
4982 *
4983 * \ingroup TaskModelIntBranch
4984 */
4985 class IntValBranch : public ValBranch<IntVar> {
4986 public:
4987 /// Which value selection
4988 enum Select {
4989 SEL_MIN, ///< Select smallest value
4990 SEL_MED, ///< Select greatest value not greater than the median
4991 SEL_MAX, ///< Select largest value
4992 SEL_RND, ///< Select random value
4993 SEL_SPLIT_MIN, ///< Select values not greater than mean of smallest and largest value
4994 SEL_SPLIT_MAX, ///< Select values greater than mean of smallest and largest value
4995 SEL_RANGE_MIN, ///< Select the smallest range of the variable domain if it has several ranges, otherwise select values not greater than mean of smallest and largest value
4996 SEL_RANGE_MAX, ///< Select the largest range of the variable domain if it has several ranges, otherwise select values greater than mean of smallest and largest value
4997 SEL_VAL_COMMIT, ///< Select value according to user-defined functions
4998 SEL_VALUES_MIN, ///< Select all values starting from smallest
4999 SEL_VALUES_MAX ///< Select all values starting from largest
5000 };
5001 protected:
5002 /// Which value to select
5003 Select s;
5004 public:
5005 /// Initialize with selection strategy \a s
5006 IntValBranch(Select s = SEL_MIN);
5007 /// Initialize with random number generator \a r
5008 IntValBranch(Rnd r);
5009 /// Initialize with value function \a f and commit function \a c
5010 IntValBranch(IntBranchVal v, IntBranchCommit c);
5011 /// Return selection strategy
5012 Select select(void) const;
5013 };
5014
5015 /**
5016 * \brief Which values to select for branching first
5017 *
5018 * \ingroup TaskModelIntBranch
5019 */
5020 class BoolValBranch : public ValBranch<BoolVar> {
5021 public:
5022 /// Which value selection
5023 enum Select {
5024 SEL_MIN, ///< Select smallest value
5025 SEL_MAX, ///< Select largest value
5026 SEL_RND, ///< Select random value
5027 SEL_VAL_COMMIT ///< Select value according to user-defined functions
5028 };
5029 protected:
5030 /// Which value to select
5031 Select s;
5032 public:
5033 /// Initialize with selection strategy \a s
5034 BoolValBranch(Select s = SEL_MIN);
5035 /// Initialize with random number generator \a r
5036 BoolValBranch(Rnd r);
5037 /// Initialize with value function \a f and commit function \a c
5038 BoolValBranch(BoolBranchVal v, BoolBranchCommit c);
5039 /// Return selection strategy
5040 Select select(void) const;
5041 };
5042
5043 /**
5044 * \defgroup TaskModelIntBranchVal Value selection for integer and Boolean variables
5045 * \ingroup TaskModelIntBranch
5046 */
5047 //@{
5048 /// Select smallest value
5049 IntValBranch INT_VAL_MIN(void);
5050 /// Select greatest value not greater than the median
5051 IntValBranch INT_VAL_MED(void);
5052 /// Select largest value
5053 IntValBranch INT_VAL_MAX(void);
5054 /// Select random value
5055 IntValBranch INT_VAL_RND(Rnd r);
5056 /// Select values not greater than mean of smallest and largest value
5057 IntValBranch INT_VAL_SPLIT_MIN(void);
5058 /// Select values greater than mean of smallest and largest value
5059 IntValBranch INT_VAL_SPLIT_MAX(void);
5060 /// Select the smallest range of the variable domain if it has several ranges, otherwise select values not greater than mean of smallest and largest value
5061 IntValBranch INT_VAL_RANGE_MIN(void);
5062 /// Select the largest range of the variable domain if it has several ranges, otherwise select values greater than mean of smallest and largest value
5063 IntValBranch INT_VAL_RANGE_MAX(void);
5064 /**
5065 * \brief Select value as defined by the value function \a v and commit function \a c
5066 * Uses a commit function as default that posts the constraints that
5067 * a variable \a x must be equal to a value \a n for the first alternative
5068 * and that \a x must be different from \a n for the second alternative.
5069 */
5070 IntValBranch INT_VAL(IntBranchVal v, IntBranchCommit c=nullptr);
5071 /// Try all values starting from smallest
5072 IntValBranch INT_VALUES_MIN(void);
5073 /// Try all values starting from largest
5074 IntValBranch INT_VALUES_MAX(void);
5075
5076 /// Select smallest value
5077 BoolValBranch BOOL_VAL_MIN(void);
5078 /// Select largest value
5079 BoolValBranch BOOL_VAL_MAX(void);
5080 /// Select random value
5081 BoolValBranch BOOL_VAL_RND(Rnd r);
5082 /**
5083 * \brief Select value as defined by the value function \a v and commit function \a c
5084 * Uses a commit function as default that posts the constraints that
5085 * a variable \a x must be equal to a value \a n for the first alternative
5086 * and that \a x must be different from \a n for the second alternative.
5087 */
5088 BoolValBranch BOOL_VAL(BoolBranchVal v, BoolBranchCommit c=nullptr);
5089 //@}
5090
5091}
5092
5093#include <gecode/int/branch/val.hpp>
5094
5095namespace Gecode {
5096
5097 /**
5098 * \brief Which values to select for assignment
5099 *
5100 * \ingroup TaskModelIntBranch
5101 */
5102 class IntAssign : public ValBranch<IntVar> {
5103 public:
5104 /// Which value selection
5105 enum Select {
5106 SEL_MIN, ///< Select smallest value
5107 SEL_MED, ///< Select greatest value not greater than the median
5108 SEL_MAX, ///< Select largest value
5109 SEL_RND, ///< Select random value
5110 SEL_VAL_COMMIT ///< Select value according to user-defined functions
5111 };
5112 protected:
5113 /// Which value to select
5114 Select s;
5115 public:
5116 /// Initialize with selection strategy \a s
5117 IntAssign(Select s = SEL_MIN);
5118 /// Initialize with random number generator \a r
5119 IntAssign(Rnd r);
5120 /// Initialize with value function \a f and commit function \a c
5121 IntAssign(IntBranchVal v, IntBranchCommit c);
5122 /// Return selection strategy
5123 Select select(void) const;
5124 };
5125
5126 /**
5127 * \brief Which values to select for assignment
5128 *
5129 * \ingroup TaskModelIntBranch
5130 */
5131 class BoolAssign : public ValBranch<BoolVar> {
5132 public:
5133 /// Which value selection
5134 enum Select {
5135 SEL_MIN, ///< Select smallest value
5136 SEL_MAX, ///< Select largest value
5137 SEL_RND, ///< Select random value
5138 SEL_VAL_COMMIT ///< Select value according to user-defined functions
5139 };
5140 protected:
5141 /// Which value to select
5142 Select s;
5143 public:
5144 /// Initialize with selection strategy \a s
5145 BoolAssign(Select s = SEL_MIN);
5146 /// Initialize with random number generator \a r
5147 BoolAssign(Rnd r);
5148 /// Initialize with value function \a f and commit function \a c
5149 BoolAssign(BoolBranchVal v, BoolBranchCommit c);
5150 /// Return selection strategy
5151 Select select(void) const;
5152 };
5153
5154 /**
5155 * \defgroup TaskModelIntBranchAssign Value selection for assigning integer variables
5156 * \ingroup TaskModelIntBranch
5157 */
5158 //@{
5159 /// Select smallest value
5160 IntAssign INT_ASSIGN_MIN(void);
5161 /// Select greatest value not greater than the median
5162 IntAssign INT_ASSIGN_MED(void);
5163 /// Select largest value
5164 IntAssign INT_ASSIGN_MAX(void);
5165 /// Select random value
5166 IntAssign INT_ASSIGN_RND(Rnd r);
5167 /**
5168 * \brief Select value as defined by the value function \a v and commit function \a c
5169 *
5170 * Uses a commit function as default that posts the constraint that
5171 * a variable \a x must be equal to the value \a n.
5172 */
5173 IntAssign INT_ASSIGN(IntBranchVal v, IntBranchCommit c=nullptr);
5174
5175 /// Select smallest value
5176 BoolAssign BOOL_ASSIGN_MIN(void);
5177 /// Select largest value
5178 BoolAssign BOOL_ASSIGN_MAX(void);
5179 /// Select random value
5180 BoolAssign BOOL_ASSIGN_RND(Rnd r);
5181 /**
5182 * \brief Select value as defined by the value function \a v and commit function \a c
5183 *
5184 * Uses a commit function as default that posts the constraint that
5185 * a variable \a x must be equal to the value \a n.
5186 */
5187 BoolAssign BOOL_ASSIGN(BoolBranchVal v, BoolBranchCommit c=nullptr);
5188 //@}
5189
5190}
5191
5192#include <gecode/int/branch/assign.hpp>
5193
5194namespace Gecode {
5195
5196 /**
5197 * \brief Branch over \a x with variable selection \a vars and value selection \a vals
5198 *
5199 * \ingroup TaskModelIntBranch
5200 */
5201 GECODE_INT_EXPORT void
5202 branch(Home home, const IntVarArgs& x,
5203 IntVarBranch vars, IntValBranch vals,
5204 IntBranchFilter bf=nullptr,
5205 IntVarValPrint vvp=nullptr);
5206 /**
5207 * \brief Branch over \a x with tie-breaking variable selection \a vars and value selection \a vals
5208 *
5209 * \ingroup TaskModelIntBranch
5210 */
5211 GECODE_INT_EXPORT void
5212 branch(Home home, const IntVarArgs& x,
5213 TieBreak<IntVarBranch> vars, IntValBranch vals,
5214 IntBranchFilter bf=nullptr,
5215 IntVarValPrint vvp=nullptr);
5216 /**
5217 * \brief Branch over \a x with value selection \a vals
5218 *
5219 * \ingroup TaskModelIntBranch
5220 */
5221 GECODE_INT_EXPORT void
5222 branch(Home home, IntVar x, IntValBranch vals,
5223 IntVarValPrint vvp=nullptr);
5224 /**
5225 * \brief Branch over \a x with variable selection \a vars and value selection \a vals
5226 *
5227 * \ingroup TaskModelIntBranch
5228 */
5229 GECODE_INT_EXPORT void
5230 branch(Home home, const BoolVarArgs& x,
5231 BoolVarBranch vars, BoolValBranch vals,
5232 BoolBranchFilter bf=nullptr,
5233 BoolVarValPrint vvp=nullptr);
5234 /**
5235 * \brief Branch over \a x with tie-breaking variable selection \a vars and value selection \a vals
5236 *
5237 * \ingroup TaskModelIntBranch
5238 */
5239 GECODE_INT_EXPORT void
5240 branch(Home home, const BoolVarArgs& x,
5241 TieBreak<BoolVarBranch> vars, BoolValBranch vals,
5242 BoolBranchFilter bf=nullptr,
5243 BoolVarValPrint vvp=nullptr);
5244 /**
5245 * \brief Branch over \a x with value selection \a vals
5246 *
5247 * \ingroup TaskModelIntBranch
5248 */
5249 GECODE_INT_EXPORT void
5250 branch(Home home, BoolVar x, BoolValBranch vals,
5251 BoolVarValPrint vvp=nullptr);
5252
5253 /**
5254 * \brief Assign all \a x with variable selection \a vars with value selection \a vals
5255 *
5256 * \ingroup TaskModelIntBranch
5257 */
5258 GECODE_INT_EXPORT void
5259 assign(Home home, const IntVarArgs& x,
5260 IntVarBranch vars, IntAssign vals,
5261 IntBranchFilter bf=nullptr,
5262 IntVarValPrint vvp=nullptr);
5263 /**
5264 * \brief Assign all \a x with tie-breaking variable selection \a vars and value selection \a vals
5265 *
5266 * \ingroup TaskModelIntBranch
5267 */
5268 GECODE_INT_EXPORT void
5269 assign(Home home, const IntVarArgs& x,
5270 TieBreak<IntVarBranch> vars, IntAssign vals,
5271 IntBranchFilter bf=nullptr,
5272 IntVarValPrint vvp=nullptr);
5273 /**
5274 * \brief Assign \a x with value selection \a vals
5275 *
5276 * \ingroup TaskModelIntBranch
5277 */
5278 GECODE_INT_EXPORT void
5279 assign(Home home, IntVar x, IntAssign vals,
5280 IntVarValPrint vvp=nullptr);
5281 /**
5282 * \brief Assign all \a x with variable selection \a vars with value selection \a vals
5283 *
5284 * \ingroup TaskModelIntBranch
5285 */
5286 GECODE_INT_EXPORT void
5287 assign(Home home, const BoolVarArgs& x,
5288 BoolVarBranch vars, BoolAssign vals,
5289 BoolBranchFilter bf=nullptr,
5290 BoolVarValPrint vvp=nullptr);
5291 /**
5292 * \brief Assign all \a x with tie-breaking variable selection \a vars and value selection \a vals
5293 *
5294 * \ingroup TaskModelIntBranch
5295 */
5296 GECODE_INT_EXPORT void
5297 assign(Home home, const BoolVarArgs& x,
5298 TieBreak<BoolVarBranch> vars, BoolAssign vals,
5299 IntBranchFilter bf=nullptr,
5300 IntVarValPrint vvp=nullptr);
5301 /**
5302 * \brief Assign \a x with value selection \a vals
5303 *
5304 * \ingroup TaskModelIntBranch
5305 */
5306 GECODE_INT_EXPORT void
5307 assign(Home home, BoolVar x, BoolAssign vals,
5308 BoolVarValPrint vvp=nullptr);
5309
5310}
5311
5312namespace Gecode {
5313
5314 /**
5315 * \brief Branch over \a x with value selection \a vals
5316 *
5317 * \ingroup TaskModelIntBranch
5318 */
5319 void
5320 branch(Home home, const IntVarArgs& x, IntValBranch vals,
5321 IntBranchFilter bf=nullptr,
5322 IntVarValPrint vvp=nullptr);
5323 /**
5324 * \brief Branch over \a x with value selection \a vals
5325 *
5326 * \ingroup TaskModelIntBranch
5327 */
5328 void
5329 branch(Home home, const BoolVarArgs& x, BoolValBranch vals,
5330 BoolBranchFilter bf=nullptr,
5331 BoolVarValPrint vvp=nullptr);
5332
5333 /**
5334 * \brief Assign all \a x with value selection \a vals
5335 *
5336 * \ingroup TaskModelIntBranch
5337 */
5338 void
5339 assign(Home home, const IntVarArgs& x, IntAssign vals,
5340 IntBranchFilter bf=nullptr,
5341 IntVarValPrint vvp=nullptr);
5342 /**
5343 * \brief Assign all \a x with value selection \a vals
5344 *
5345 * \ingroup TaskModelIntBranch
5346 */
5347 void
5348 assign(Home home, const BoolVarArgs& x, BoolAssign vals,
5349 BoolBranchFilter bf=nullptr,
5350 BoolVarValPrint vvp=nullptr);
5351
5352}
5353
5354#include <gecode/int/branch.hpp>
5355
5356namespace Gecode {
5357
5358 /** Print DFA \a d
5359 * \relates Gecode::DFA
5360 */
5361 template<class Char, class Traits>
5362 std::basic_ostream<Char,Traits>&
5363 operator <<(std::basic_ostream<Char,Traits>& os, const DFA& d);
5364
5365 /** Print TupleSet \a ts
5366 * \relates Gecode::TupleSet
5367 */
5368 template<class Char, class Traits>
5369 std::basic_ostream<Char,Traits>&
5370 operator <<(std::basic_ostream<Char,Traits>& os, const TupleSet& ts);
5371
5372}
5373
5374// LDSB-related declarations.
5375namespace Gecode {
5376
5377 namespace Int { namespace LDSB {
5378 class SymmetryObject;
5379 }}
5380
5381 /**
5382 * \brief A reference-counted pointer to a SymmetryObject
5383 *
5384 * \ingroup TaskModelIntBranch
5385 */
5386 class GECODE_INT_EXPORT SymmetryHandle {
5387 public:
5388 /// Symmetry object that this handle refers to.
5389 Int::LDSB::SymmetryObject* ref;
5390 /// Increment counter
5391 void increment(void);
5392 /// Decrement counter
5393 void decrement(void);
5394 public:
5395 /// Default constructor
5396 SymmetryHandle(void);
5397 /// Initialies with a SymmetryObject
5398 SymmetryHandle(Int::LDSB::SymmetryObject* o);
5399 /// Copy constructor
5400 SymmetryHandle(const SymmetryHandle& h);
5401 /// Assignment operator
5402 const SymmetryHandle& operator=(const SymmetryHandle& h);
5403 /// Destructor
5404 ~SymmetryHandle(void);
5405 };
5406 class Symmetries;
5407 /// Traits of %Symmetries
5408 template<>
5409 class ArrayTraits<ArgArray<SymmetryHandle> > {
5410 public:
5411 typedef Symmetries StorageType;
5412 typedef SymmetryHandle ValueType;
5413 typedef Symmetries ArgsType;
5414 };
5415
5416 /**
5417 * \defgroup TaskModelIntBranchSymm Symmetry declarations
5418 *
5419 * \ingroup TaskModelIntBranch
5420 */
5421 //@{
5422 /// Collection of symmetries
5423 class Symmetries : public ArgArray<SymmetryHandle> {};
5424 // If this is instead a typedef, strange things happen with the
5425 // overloading of the "branch" function.
5426
5427 /// Variables in \a x are interchangeable
5428 GECODE_INT_EXPORT SymmetryHandle VariableSymmetry(const IntVarArgs& x);
5429 /// Variables in \a x are interchangeable
5430 GECODE_INT_EXPORT SymmetryHandle VariableSymmetry(const BoolVarArgs& x);
5431 /// Specified variables in \a x are interchangeable
5432 GECODE_INT_EXPORT SymmetryHandle VariableSymmetry(const IntVarArgs& x,
5433 const IntArgs& indices);
5434 /// Values in \a v are interchangeable
5435 GECODE_INT_EXPORT SymmetryHandle ValueSymmetry(const IntArgs& v);
5436 /// Values in \a v are interchangeable
5437 GECODE_INT_EXPORT SymmetryHandle ValueSymmetry(const IntSet& v);
5438 /// All values in the domain of the given variable are interchangeable
5439 GECODE_INT_EXPORT SymmetryHandle ValueSymmetry(IntVar vars);
5440 /**
5441 * \brief Variable sequences in \a x of size \a ss are interchangeable
5442 *
5443 * The size of \a x must be a multiple of \a ss.
5444 */
5445 GECODE_INT_EXPORT
5446 SymmetryHandle VariableSequenceSymmetry(const IntVarArgs& x, int ss);
5447 /**
5448 * \brief Variable sequences in \a x of size \a ss are interchangeable
5449 *
5450 * The size of \a x must be a multiple of \a ss.
5451 */
5452 GECODE_INT_EXPORT
5453 SymmetryHandle VariableSequenceSymmetry(const BoolVarArgs& x, int ss);
5454 /**
5455 * \brief Value sequences in \a v of size \a ss are interchangeable
5456 *
5457 * The size of \a v must be a multiple of \a ss.
5458 */
5459 GECODE_INT_EXPORT
5460 SymmetryHandle ValueSequenceSymmetry(const IntArgs& v, int ss);
5461
5462 /// The values from \a lower to \a upper (inclusive) can be reflected
5463 GECODE_INT_EXPORT SymmetryHandle values_reflect(int lower, int upper);
5464 /// The values in the domain of \x can be reflected
5465 GECODE_INT_EXPORT SymmetryHandle values_reflect(IntVar x);
5466 //@}
5467
5468 /**
5469 * \brief Branch over \a x with variable selection \a vars and value
5470 * selection \a vals with symmetry breaking
5471 *
5472 * Throws LDSBBadValueSelection exception if \a vals is any of
5473 * SEL_SPLIT_MIN, SEL_SPLIT_MAX, SEL_RANGE_MIN, SEL_RANGE_MAX,
5474 * SEL_VALUES_MIN, and SEL_VALUES_MAX, or if \a vals is
5475 * SEL_VAL_COMMIT with a custom commit function.
5476 *
5477 * \ingroup TaskModelIntBranch
5478 */
5479 GECODE_INT_EXPORT void
5480 branch(Home home, const IntVarArgs& x,
5481 IntVarBranch vars, IntValBranch vals,
5482 const Symmetries& syms,
5483 IntBranchFilter bf=nullptr,
5484 IntVarValPrint vvp=nullptr);
5485 /**
5486 * \brief Branch over \a x with tie-breaking variable selection \a
5487 * vars and value selection \a vals with symmetry breaking
5488 *
5489 * Throws LDSBBadValueSelection exception if \a vals is any of
5490 * SEL_SPLIT_MIN, SEL_SPLIT_MAX, SEL_RANGE_MIN, SEL_RANGE_MAX,
5491 * SEL_VALUES_MIN, and SEL_VALUES_MAX, or if \a vals is
5492 * SEL_VAL_COMMIT with a custom commit function.
5493 *
5494 * \ingroup TaskModelIntBranch
5495 */
5496 GECODE_INT_EXPORT void
5497 branch(Home home, const IntVarArgs& x,
5498 TieBreak<IntVarBranch> vars, IntValBranch vals,
5499 const Symmetries& syms,
5500 IntBranchFilter bf=nullptr,
5501 IntVarValPrint vvp=nullptr);
5502 /**
5503 * \brief Branch over \a x with variable selection \a vars and value
5504 * selection \a vals with symmetry breaking
5505 *
5506 * Throws LDSBBadValueSelection exception if \a vals is any of
5507 * SEL_SPLIT_MIN, SEL_SPLIT_MAX, SEL_RANGE_MIN, SEL_RANGE_MAX,
5508 * SEL_VALUES_MIN, and SEL_VALUES_MAX, or if \a vals is
5509 * SEL_VAL_COMMIT with a custom commit function.
5510 *
5511 * \ingroup TaskModelIntBranch
5512 */
5513 GECODE_INT_EXPORT void
5514 branch(Home home, const BoolVarArgs& x,
5515 BoolVarBranch vars, BoolValBranch vals,
5516 const Symmetries& syms,
5517 BoolBranchFilter bf=nullptr,
5518 BoolVarValPrint vvp=nullptr);
5519 /**
5520 * \brief Branch over \a x with tie-breaking variable selection \a
5521 * vars and value selection \a vals with symmetry breaking
5522 *
5523 * Throws LDSBBadValueSelection exception if \a vals is any of
5524 * SEL_SPLIT_MIN, SEL_SPLIT_MAX, SEL_RANGE_MIN, SEL_RANGE_MAX,
5525 * SEL_VALUES_MIN, and SEL_VALUES_MAX, or if \a vals is
5526 * SEL_VAL_COMMIT with a custom commit function.
5527 *
5528 * \ingroup TaskModelIntBranch
5529 */
5530 GECODE_INT_EXPORT void
5531 branch(Home home, const BoolVarArgs& x,
5532 TieBreak<BoolVarBranch> vars, BoolValBranch vals,
5533 const Symmetries& syms,
5534 BoolBranchFilter bf=nullptr,
5535 BoolVarValPrint vvp=nullptr);
5536
5537#ifdef GECODE_HAS_CBS
5538
5539 /**
5540 * \brief Branch over \a x using counting-based search
5541 *
5542 * Branches on the <variable, value> pair that has the the highest solution
5543 * density across all active propagators. Computing solution density is
5544 * currently supported for the following propagators:
5545 *
5546 * - Gecode::Int::Distinct::Val
5547 * - Gecode::Int::Distinct::Bnd
5548 * - Gecode::Int::Distinct::Dom
5549 * - More to come...
5550 *
5551 * If the space does not contain any of the preceding propagators, this
5552 * brancher won't be able to make any branching choices. For more details,
5553 * please see the documentation in MPG, section ?.
5554 *
5555 * To use this brancher, Gecode needs to be compiled with --enable-cbs.
5556 *
5557 * \ingroup TaskModelIntBranch
5558 */
5559 GECODE_INT_EXPORT void
5560 cbsbranch(Home home, const IntVarArgs& x);
5561
5562
5563 /**
5564 * \brief Branch over \a x using counting-based search
5565 *
5566 * Branches on the <variable, value> pair that has the the highest solution
5567 * density across all active propagators. Computing solution density is
5568 * currently supported for the following propagators:
5569 *
5570 * - Gecode::Int::Distinct::Val
5571 * - Gecode::Int::Distinct::Bnd
5572 * - Gecode::Int::Distinct::Dom
5573 * - More to come...
5574 *
5575 * If the space does not contain any of the preceding propagators, this
5576 * brancher won't be able to make any branching choices. For more details,
5577 * please see the documentation in MPG, section ?.
5578 *
5579 * To use this brancher, Gecode needs to be compiled with --enable-cbs.
5580 *
5581 * \ingroup TaskModelIntBranch
5582 */
5583 GECODE_INT_EXPORT void
5584 cbsbranch(Home home, const BoolVarArgs& x);
5585
5586#endif
5587
5588}
5589
5590namespace Gecode {
5591
5592 /*
5593 * \brief Relaxed assignment of variables in \a x from values in \a sx
5594 *
5595 * The variables in \a x are assigned values from the assigned variables
5596 * in the solution \a sx with a relaxation probability \a p. That is,
5597 * if \f$p=0.1\f$ approximately 10% of the variables in \a x will be
5598 * assigned a value from \a sx.
5599 *
5600 * The random numbers are generated from the generator \a r. At least
5601 * one variable will not be assigned: in case the relaxation attempt
5602 * would suggest that all variables should be assigned, a single
5603 * variable will be selected randomly to remain unassigned.
5604 *
5605 * Throws an exception of type Int::ArgumentSizeMismatch, if \a x and
5606 * \a sx are of different size.
5607 *
5608 * Throws an exception of type Int::OutOfLimits, if \a p is not between
5609 * \a 0.0 and \a 1.0.
5610 *
5611 * \ingroup TaskModelInt
5612 */
5613 GECODE_INT_EXPORT void
5614 relax(Home home, const IntVarArgs& x, const IntVarArgs& sx,
5615 Rnd r, double p);
5616
5617 /*
5618 * \brief Relaxed assignment of variables in \a x from values in \a sx
5619 *
5620 * The variables in \a x are assigned values from the assigned variables
5621 * in the solution \a sx with a relaxation probability \a p. That is,
5622 * if \f$p=0.1\f$ approximately 10% of the variables in \a x will be
5623 * assigned a value from \a sx.
5624 *
5625 * The random numbers are generated from the generator \a r. At least
5626 * one variable will not be assigned: in case the relaxation attempt
5627 * would suggest that all variables should be assigned, a single
5628 * variable will be selected randomly to remain unassigned.
5629 *
5630 * Throws an exception of type Int::ArgumentSizeMismatch, if \a x and
5631 * \a sx are of different size.
5632 *
5633 * Throws an exception of type Int::OutOfLimits, if \a p is not between
5634 * \a 0.0 and \a 1.0.
5635 *
5636 * \ingroup TaskModelInt
5637 */
5638 GECODE_INT_EXPORT void
5639 relax(Home home, const BoolVarArgs& x, const BoolVarArgs& sx,
5640 Rnd r, double p);
5641
5642}
5643
5644
5645#include <gecode/int/trace/int-trace-view.hpp>
5646#include <gecode/int/trace/bool-trace-view.hpp>
5647
5648namespace Gecode {
5649
5650 /**
5651 * \defgroup TaskIntTrace Tracing for integer and Boolean variables
5652 * \ingroup TaskTrace
5653 */
5654
5655 /**
5656 * \brief Trace delta information for integer variables
5657 * \ingroup TaskIntTrace
5658 */
5659 class IntTraceDelta
5660 : public Iter::Ranges::Diff<Iter::Ranges::RangeList,
5661 Int::ViewRanges<Int::IntView> > {
5662 protected:
5663 /// Iterator over the new values
5664 Int::ViewRanges<Int::IntView> rn;
5665 /// Iterator over the old values
5666 Iter::Ranges::RangeList ro;
5667 public:
5668 /// \name Constructors and initialization
5669 //@{
5670 /// Initialize with old trace view \a o, new view \a n, and delta \a d
5671 IntTraceDelta(Int::IntTraceView o, Int::IntView n, const Delta& d);
5672 //@}
5673 };
5674
5675 /**
5676 * \brief Trace delta information for Boolean variables
5677 * \ingroup TaskIntTrace
5678 */
5679 class BoolTraceDelta {
5680 protected:
5681 /// Delta information
5682 int delta;
5683 public:
5684 /// \name Constructors and initialization
5685 //@{
5686 /// Initialize with old trace view \a o, new view \a n, and delta \a d
5687 BoolTraceDelta(Int::BoolTraceView o, Int::BoolView n, const Delta& d);
5688 //@}
5689 /// \name Iteration control
5690 //@{
5691 /// Test whether iterator is still at a range or done
5692 bool operator ()(void) const;
5693 /// Move iterator to next range (if possible)
5694 void operator ++(void);
5695 //@}
5696
5697 /// \name Range access
5698 //@{
5699 /// Return smallest value of range
5700 int min(void) const;
5701 /// Return largest value of range
5702 int max(void) const;
5703 /// Return width of range (distance between minimum and maximum)
5704 unsigned int width(void) const;
5705 //@}
5706 };
5707
5708}
5709
5710#include <gecode/int/trace/int-delta.hpp>
5711#include <gecode/int/trace/bool-delta.hpp>
5712
5713#include <gecode/int/trace/traits.hpp>
5714
5715namespace Gecode {
5716
5717 /**
5718 * \brief Tracer for integer variables
5719 * \ingroup TaskIntTrace
5720 */
5721 typedef ViewTracer<Int::IntView> IntTracer;
5722 /**
5723 * \brief Trace recorder for integer variables
5724 * \ingroup TaskIntTrace
5725 */
5726 typedef ViewTraceRecorder<Int::IntView> IntTraceRecorder;
5727
5728 /**
5729 * \brief Standard integer variable tracer
5730 * \ingroup TaskIntTrace
5731 */
5732 class GECODE_INT_EXPORT StdIntTracer : public IntTracer {
5733 protected:
5734 /// Output stream to use
5735 std::ostream& os;
5736 public:
5737 /// Initialize with output stream \a os0 and events \ e
5738 StdIntTracer(std::ostream& os0 = std::cerr);
5739 /// Print init information
5740 virtual void init(const Space& home, const IntTraceRecorder& t);
5741 /// Print prune information
5742 virtual void prune(const Space& home, const IntTraceRecorder& t,
5743 const ViewTraceInfo& vti, int i, IntTraceDelta& d);
5744 /// Print fixpoint information
5745 virtual void fix(const Space& home, const IntTraceRecorder& t);
5746 /// Print failure information
5747 virtual void fail(const Space& home, const IntTraceRecorder& t);
5748 /// Print that trace recorder is done
5749 virtual void done(const Space& home, const IntTraceRecorder& t);
5750 /// Default tracer (printing to std::cerr)
5751 static StdIntTracer def;
5752 };
5753
5754
5755 /**
5756 * \brief Tracer for Boolean variables
5757 * \ingroup TaskIntTrace
5758 */
5759 typedef ViewTracer<Int::BoolView> BoolTracer;
5760 /**
5761 * \brief Trace recorder for Boolean variables
5762 * \ingroup TaskIntTrace
5763 */
5764 typedef ViewTraceRecorder<Int::BoolView> BoolTraceRecorder;
5765
5766 /**
5767 * \brief Standard Boolean variable tracer
5768 * \ingroup TaskIntTrace
5769 */
5770 class GECODE_INT_EXPORT StdBoolTracer : public BoolTracer {
5771 protected:
5772 /// Output stream to use
5773 std::ostream& os;
5774 public:
5775 /// Initialize with output stream \a os0
5776 StdBoolTracer(std::ostream& os0 = std::cerr);
5777 /// Print init information
5778 virtual void init(const Space& home, const BoolTraceRecorder& t);
5779 /// Print prune information
5780 virtual void prune(const Space& home, const BoolTraceRecorder& t,
5781 const ViewTraceInfo& vti, int i, BoolTraceDelta& d);
5782 /// Print fixpoint information
5783 virtual void fix(const Space& home, const BoolTraceRecorder& t);
5784 /// Print failure information
5785 virtual void fail(const Space& home, const BoolTraceRecorder& t);
5786 /// Print that trace recorder is done
5787 virtual void done(const Space& home, const BoolTraceRecorder& t);
5788 /// Default tracer (printing to std::cerr)
5789 static StdBoolTracer def;
5790 };
5791
5792 /**
5793 * \brief Create a tracer for integer variables
5794 * \ingroup TaskIntTrace
5795 */
5796 GECODE_INT_EXPORT void
5797 trace(Home home, const IntVarArgs& x,
5798 TraceFilter tf,
5799 int te = (TE_INIT | TE_PRUNE | TE_FIX | TE_FAIL | TE_DONE),
5800 IntTracer& t = StdIntTracer::def);
5801 /**
5802 * \brief Create a tracer for integer variables
5803 * \ingroup TaskIntTrace
5804 */
5805 void
5806 trace(Home home, const IntVarArgs& x,
5807 int te = (TE_INIT | TE_PRUNE | TE_FIX | TE_FAIL | TE_DONE),
5808 IntTracer& t = StdIntTracer::def);
5809
5810 /**
5811 * \brief Create a tracer for Boolean Variables
5812 * \ingroup TaskIntTrace
5813 */
5814 GECODE_INT_EXPORT void
5815 trace(Home home, const BoolVarArgs& x,
5816 TraceFilter tf,
5817 int te = (TE_INIT | TE_PRUNE | TE_FIX | TE_FAIL | TE_DONE),
5818 BoolTracer& t = StdBoolTracer::def);
5819 /**
5820 * \brief Create a tracer for Boolean Variables
5821 * \ingroup TaskIntTrace
5822 */
5823 void
5824 trace(Home home, const BoolVarArgs& x,
5825 int te = (TE_INIT | TE_PRUNE | TE_FIX | TE_FAIL | TE_DONE),
5826 BoolTracer& t = StdBoolTracer::def);
5827
5828}
5829
5830#include <gecode/int/trace.hpp>
5831
5832#endif
5833
5834// IFDEF: GECODE_HAS_INT_VARS
5835// STATISTICS: int-post
5836