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 105 namespace 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 161 namespace 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 360 namespace 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 607 namespace 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 625 namespace 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 842 namespace 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 919 namespace 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 944 namespace 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 997 namespace 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 1844 namespace 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 2300 namespace 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 2516 namespace 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 2676 namespace 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 4279 namespace 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 4388 namespace 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 4474 namespace 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 4582 namespace 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 4676 namespace 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 4694 namespace 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 4978 namespace 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 5095 namespace 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 5194 namespace 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 5312 namespace 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 5356 namespace 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. 5375 namespace 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 5590 namespace 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 5648 namespace 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 5715 namespace 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 5837