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 * Matthias Balzer <matthias.balzer@itwm.fraunhofer.de> 7 * Mikael Lagerkvist <lagerkvist@gecode.org> 8 * Vincent Barichard <Vincent.Barichard@univ-angers.fr> 9 * 10 * Copyright: 11 * Christian Schulte, 2004 12 * Fraunhofer ITWM, 2017 13 * Guido Tack, 2004 14 * Mikael Lagerkvist, 2005 15 * Vincent Barichard, 2012 16 * 17 * This file is part of Gecode, the generic constraint 18 * development environment: 19 * http://www.gecode.org 20 * 21 * Permission is hereby granted, free of charge, to any person obtaining 22 * a copy of this software and associated documentation files (the 23 * "Software"), to deal in the Software without restriction, including 24 * without limitation the rights to use, copy, modify, merge, publish, 25 * distribute, sublicense, and/or sell copies of the Software, and to 26 * permit persons to whom the Software is furnished to do so, subject to 27 * the following conditions: 28 * 29 * The above copyright notice and this permission notice shall be 30 * included in all copies or substantial portions of the Software. 31 * 32 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 33 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 34 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 35 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 36 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 37 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 38 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 39 * 40 */ 41 42 #ifndef GECODE_MINIMODEL_HH 43 #define GECODE_MINIMODEL_HH 44 45 #include <gecode/kernel.hh> 46 #include <gecode/int.hh> 47 #ifdef GECODE_HAS_SET_VARS 48 #include <gecode/set.hh> 49 #endif 50 #ifdef GECODE_HAS_FLOAT_VARS 51 #include <gecode/float.hh> 52 #endif 53 54 #include <iostream> 55 56 /* 57 * Support for DLLs under Windows 58 * 59 */ 60 61 #if !defined(GECODE_STATIC_LIBS) && \ 62 (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER)) 63 64 #ifdef GECODE_BUILD_MINIMODEL 65 #define GECODE_MINIMODEL_EXPORT __declspec( dllexport ) 66 #else 67 #define GECODE_MINIMODEL_EXPORT __declspec( dllimport ) 68 #endif 69 70 #else 71 72 #ifdef GECODE_GCC_HAS_CLASS_VISIBILITY 73 74 #define GECODE_MINIMODEL_EXPORT __attribute__ ((visibility("default"))) 75 76 #else 77 78 #define GECODE_MINIMODEL_EXPORT 79 80 #endif 81 #endif 82 83 // Configure auto-linking 84 #ifndef GECODE_BUILD_MINIMODEL 85 #define GECODE_LIBRARY_NAME "MiniModel" 86 #include <gecode/support/auto-link.hpp> 87 #endif 88 89 namespace Gecode { 90 91 /// Minimalistic modeling support 92 namespace MiniModel {} 93 94 } 95 96 #include <gecode/minimodel/exception.hpp> 97 98 namespace Gecode { 99 100 /// Class for specifying integer propagation levels used by minimodel 101 class IntPropLevels { 102 protected: 103 IntPropLevel _linear2 : IPL_BITS_; ///< For binary linear 104 IntPropLevel _linear : IPL_BITS_; ///< For n-ary linear 105 IntPropLevel _abs : IPL_BITS_; ///< For absolute value 106 IntPropLevel _max2 : IPL_BITS_; ///< For binary maximum 107 IntPropLevel _max : IPL_BITS_; ///< For n-ary maximum 108 IntPropLevel _min2 : IPL_BITS_; ///< For binary minimum 109 IntPropLevel _min : IPL_BITS_; ///< For minimum 110 IntPropLevel _mult : IPL_BITS_; ///< For multiplication 111 IntPropLevel _div : IPL_BITS_; ///< For division 112 IntPropLevel _mod : IPL_BITS_; ///< For modulo 113 IntPropLevel _sqr : IPL_BITS_; ///< For square 114 IntPropLevel _sqrt : IPL_BITS_; ///< For square root 115 IntPropLevel _pow : IPL_BITS_; ///< For power 116 IntPropLevel _nroot : IPL_BITS_; ///< For root 117 IntPropLevel _element : IPL_BITS_; ///< For element 118 IntPropLevel _ite : IPL_BITS_; ///< For if-then-else 119 public: 120 /// Initialize with default propagation level 121 IntPropLevels(IntPropLevel ipl=IPL_DEF); 122 123 /// Return integer propagation level for binary linear constraints 124 IntPropLevel linear2(void) const; 125 /// Set integer propagation level for binary linear constraints 126 IntPropLevels& linear2(IntPropLevel ipl); 127 /// Return integer propagation level for non-binary linear constraints 128 IntPropLevel linear(void) const; 129 /// Set integer propagation level for non-binary linear constraints 130 IntPropLevels& linear(IntPropLevel ipl); 131 132 /// Return integer propagation level for absolute value constraints 133 IntPropLevel abs(void) const; 134 /// Set integer propagation level for absolute value constraints 135 IntPropLevels& abs(IntPropLevel ipl); 136 137 /// Return integer propagation level for binary maximum constraints 138 IntPropLevel max2(void) const; 139 /// Set integer propagation level for binary maximum constraints 140 IntPropLevels& max2(IntPropLevel ipl); 141 /// Return integer propagation level for non-binary maximum constraints 142 IntPropLevel max(void) const; 143 /// Set integer propagation level for non-binary maximum constraints 144 IntPropLevels& max(IntPropLevel ipl); 145 /// Return integer propagation level for binary minimum constraints 146 IntPropLevel min2(void) const; 147 /// Set integer propagation level for binary minimum constraints 148 IntPropLevels& min2(IntPropLevel ipl); 149 /// Return integer propagation level for non-binary minimum constraints 150 IntPropLevel min(void) const; 151 /// Set integer propagation level for non-binary minimum constraints 152 IntPropLevels& min(IntPropLevel ipl); 153 154 /// Return integer propagation level for multiplication constraints 155 IntPropLevel mult(void) const; 156 /// Set integer propagation level for multiplication constraints 157 IntPropLevels& mult(IntPropLevel ipl); 158 /// Return integer propagation level for division constraints 159 IntPropLevel div(void) const; 160 /// Set integer propagation level for division constraints 161 IntPropLevels& div(IntPropLevel ipl); 162 /// Return integer propagation level for modulo constraints 163 IntPropLevel mod(void) const; 164 /// Set integer propagation level for modulo constraints 165 IntPropLevels& mod(IntPropLevel ipl); 166 167 /// Return integer propagation level for square constraints 168 IntPropLevel sqr(void) const; 169 /// Set integer propagation level for square constraints 170 IntPropLevels& sqr(IntPropLevel ipl); 171 /// Return integer propagation level for square root constraints 172 IntPropLevel sqrt(void) const; 173 /// Set integer propagation level for square root constraints 174 IntPropLevels& sqrt(IntPropLevel ipl); 175 176 /// Return integer propagation level for power constraints 177 IntPropLevel pow(void) const; 178 /// Set integer propagation level for power constraints 179 IntPropLevels& pow(IntPropLevel ipl); 180 /// Return integer propagation level for root constraints 181 IntPropLevel nroot(void) const; 182 /// Set integer propagation level for root constraints 183 IntPropLevels& nroot(IntPropLevel ipl); 184 185 /// Return integer propagation level for element constraints 186 IntPropLevel element(void) const; 187 /// Set integer propagation level for element constraints 188 IntPropLevels& element(IntPropLevel ipl); 189 190 /// Return integer propagation level for if-then-else constraints 191 IntPropLevel ite(void) const; 192 /// Set integer propagation level for if-then-else constraints 193 IntPropLevels& ite(IntPropLevel ipl); 194 195 /// Default propagation levels for all constraints 196 GECODE_MINIMODEL_EXPORT 197 static const IntPropLevels def; 198 }; 199 200 } 201 202 #include <gecode/minimodel/ipl.hpp> 203 204 namespace Gecode { 205 206 class LinIntRel; 207 #ifdef GECODE_HAS_SET_VARS 208 class SetExpr; 209 #endif 210 #ifdef GECODE_HAS_FLOAT_VARS 211 class LinFloatExpr; 212 #endif 213 214 /// Base class for non-linear expressions over integer variables 215 class NonLinIntExpr { 216 public: 217 /// Return variable constrained to be equal to the expression 218 virtual IntVar post(Home home, IntVar* ret, 219 const IntPropLevels& ipls) const = 0; 220 /// Post expression to be in relation \a irt with \a c 221 virtual void post(Home home, IntRelType irt, int c, 222 const IntPropLevels& ipls) const = 0; 223 /// Post reified expression to be in relation \a irt with \a c 224 virtual void post(Home home, IntRelType irt, int c, 225 BoolVar b, const IntPropLevels& ipls) const = 0; 226 /// Destructor 227 virtual ~NonLinIntExpr(void); 228 /// Return fresh variable if \a x is null, \a x otherwise 229 static IntVar result(Home home, IntVar* x); 230 /// Constrain \a x to be equal to \a y if \a x is not null 231 static IntVar result(Home home, IntVar* x, IntVar y); 232 /// Memory management 233 void* operator new(size_t s); 234 /// Memory management 235 void operator delete(void* p, size_t s); 236 }; 237 238 } 239 240 #include <gecode/minimodel/int-expr.hpp> 241 242 namespace Gecode { 243 244 /// Linear expressions over integer variables 245 class LinIntExpr { 246 friend class LinIntRel; 247 #ifdef GECODE_HAS_SET_VARS 248 friend class SetExpr; 249 #endif 250 #ifdef GECODE_HAS_FLOAT_VARS 251 friend class LinFloatExpr; 252 #endif 253 public: 254 /// Type of linear expression 255 enum NodeType { 256 NT_CONST, ///< Integer constant 257 NT_VAR_INT, ///< Linear term with integer variable 258 NT_VAR_BOOL, ///< Linear term with Boolean variable 259 NT_NONLIN, ///< Non-linear expression 260 NT_SUM_INT, ///< Sum of integer variables 261 NT_SUM_BOOL, ///< Sum of Boolean variables 262 NT_ADD, ///< Addition of linear terms 263 NT_SUB, ///< Subtraction of linear terms 264 NT_MUL ///< Multiplication by coefficient 265 }; 266 private: 267 /// Nodes for linear expressions 268 class Node; 269 /// The actual node 270 Node* n; 271 public: 272 /// Default constructor 273 GECODE_MINIMODEL_EXPORT 274 LinIntExpr(void); 275 /// Create expression for constant \a c 276 GECODE_MINIMODEL_EXPORT 277 LinIntExpr(int c); 278 /// Create expression 279 GECODE_MINIMODEL_EXPORT 280 LinIntExpr(const IntVar& x, int a=1); 281 /// Create expression 282 GECODE_MINIMODEL_EXPORT 283 LinIntExpr(const BoolVar& x, int a=1); 284 /// Create sum expression 285 GECODE_MINIMODEL_EXPORT 286 explicit LinIntExpr(const IntVarArgs& x); 287 /// Create sum expression 288 GECODE_MINIMODEL_EXPORT 289 LinIntExpr(const IntArgs& a, const IntVarArgs& x); 290 /// Create sum expression 291 GECODE_MINIMODEL_EXPORT 292 explicit LinIntExpr(const BoolVarArgs& x); 293 /// Create sum expression 294 GECODE_MINIMODEL_EXPORT 295 LinIntExpr(const IntArgs& a, const BoolVarArgs& x); 296 /// Copy constructor 297 GECODE_MINIMODEL_EXPORT 298 LinIntExpr(const LinIntExpr& e); 299 /// Create expression for type and subexpressions 300 GECODE_MINIMODEL_EXPORT 301 LinIntExpr(const LinIntExpr& e0, NodeType t, const LinIntExpr& e1); 302 /// Create expression for type and subexpression 303 GECODE_MINIMODEL_EXPORT 304 LinIntExpr(const LinIntExpr& e0, NodeType t, int c); 305 /// Create expression for multiplication 306 GECODE_MINIMODEL_EXPORT 307 LinIntExpr(int a, const LinIntExpr& e); 308 /// Create non-linear expression 309 GECODE_MINIMODEL_EXPORT 310 explicit LinIntExpr(NonLinIntExpr* e); 311 /// Assignment operator 312 GECODE_MINIMODEL_EXPORT 313 const LinIntExpr& operator =(const LinIntExpr& e); 314 /// Post propagator 315 GECODE_MINIMODEL_EXPORT 316 void post(Home home, IntRelType irt, const IntPropLevels& ipls) const; 317 /// Post reified propagator 318 GECODE_MINIMODEL_EXPORT 319 void post(Home home, IntRelType irt, const BoolVar& b, 320 const IntPropLevels& ipls) const; 321 /// Post propagator and return variable for value 322 GECODE_MINIMODEL_EXPORT 323 IntVar post(Home home, const IntPropLevels& ipls) const; 324 /// Return non-linear expression inside, or null if not non-linear 325 GECODE_MINIMODEL_EXPORT 326 NonLinIntExpr* nle(void) const; 327 /// Destructor 328 GECODE_MINIMODEL_EXPORT 329 ~LinIntExpr(void); 330 }; 331 332 class BoolExpr; 333 334 /// Linear relations over integer variables 335 class LinIntRel { 336 friend class BoolExpr; 337 private: 338 /// Linear expression describing the entire relation 339 LinIntExpr e; 340 /// Which relation 341 IntRelType irt; 342 /// Negate relation type 343 static IntRelType neg(IntRelType irt); 344 /// Default constructor 345 LinIntRel(void); 346 public: 347 /// Create linear relation for expressions \a l and \a r 348 LinIntRel(const LinIntExpr& l, IntRelType irt, const LinIntExpr& r); 349 /// Create linear relation for expression \a l and integer \a r 350 LinIntRel(const LinIntExpr& l, IntRelType irt, int r); 351 /// Create linear relation for integer \a l and expression \a r 352 LinIntRel(int l, IntRelType irt, const LinIntExpr& r); 353 /// Post propagator for relation (if \a t is false for negated relation) 354 void post(Home home, bool t, const IntPropLevels& ipls) const; 355 /// Post reified propagator for relation (if \a t is false for negated relation) 356 void post(Home home, const BoolVar& b, bool t, const IntPropLevels& ipls) const; 357 }; 358 359 /** 360 * \defgroup TaskModelMiniModelLin Linear expressions and relations 361 * 362 * Linear expressions can be freely composed of sums and differences of 363 * integer variables (Gecode::IntVar) or Boolean variables 364 * (Gecode::BoolVar) possibly with integer coefficients and integer 365 * constants. 366 * 367 * Note that both integer and Boolean variables are automatically 368 * available as linear expressions. 369 * 370 * Linear relations are obtained from linear expressions with the normal 371 * relation operators. 372 * 373 * \ingroup TaskModelMiniModel 374 */ 375 376 //@{ 377 /// Construct linear expression as sum of integer variable and integer 378 GECODE_MINIMODEL_EXPORT LinIntExpr 379 operator +(int, const IntVar&); 380 /// Construct linear expression as sum of Boolean variable and integer 381 GECODE_MINIMODEL_EXPORT LinIntExpr 382 operator +(int, const BoolVar&); 383 /// Construct linear expression as sum of linear expression and integer 384 GECODE_MINIMODEL_EXPORT LinIntExpr 385 operator +(int, const LinIntExpr&); 386 /// Construct linear expression as sum of integer variable and integer 387 GECODE_MINIMODEL_EXPORT LinIntExpr 388 operator +(const IntVar&, int); 389 /// Construct linear expression as sum of Boolean variable and integer 390 GECODE_MINIMODEL_EXPORT LinIntExpr 391 operator +(const BoolVar&, int); 392 /// Construct linear expression as sum of linear expression and integer 393 GECODE_MINIMODEL_EXPORT LinIntExpr 394 operator +(const LinIntExpr&, int); 395 /// Construct linear expression as sum of integer variables 396 GECODE_MINIMODEL_EXPORT LinIntExpr 397 operator +(const IntVar&, const IntVar&); 398 /// Construct linear expression as sum of integer and Boolean variable 399 GECODE_MINIMODEL_EXPORT LinIntExpr 400 operator +(const IntVar&, const BoolVar&); 401 /// Construct linear expression as sum of Boolean and integer variable 402 GECODE_MINIMODEL_EXPORT LinIntExpr 403 operator +(const BoolVar&, const IntVar&); 404 /// Construct linear expression as sum of Boolean variables 405 GECODE_MINIMODEL_EXPORT LinIntExpr 406 operator +(const BoolVar&, const BoolVar&); 407 /// Construct linear expression as sum of integer variable and linear expression 408 GECODE_MINIMODEL_EXPORT LinIntExpr 409 operator +(const IntVar&, const LinIntExpr&); 410 /// Construct linear expression as sum of Boolean variable and linear expression 411 GECODE_MINIMODEL_EXPORT LinIntExpr 412 operator +(const BoolVar&, const LinIntExpr&); 413 /// Construct linear expression as sum of linear expression and integer variable 414 GECODE_MINIMODEL_EXPORT LinIntExpr 415 operator +(const LinIntExpr&, const IntVar&); 416 /// Construct linear expression as sum of linear expression and Boolean variable 417 GECODE_MINIMODEL_EXPORT LinIntExpr 418 operator +(const LinIntExpr&, const BoolVar&); 419 /// Construct linear expression as sum of linear expressions 420 GECODE_MINIMODEL_EXPORT LinIntExpr 421 operator +(const LinIntExpr&, const LinIntExpr&); 422 423 /// Construct linear expression as sum of integer variable and integer 424 GECODE_MINIMODEL_EXPORT LinIntExpr 425 operator -(int, const IntVar&); 426 /// Construct linear expression as sum of Boolean variable and integer 427 GECODE_MINIMODEL_EXPORT LinIntExpr 428 operator -(int, const BoolVar&); 429 /// Construct linear expression as sum of integer and linear expression 430 GECODE_MINIMODEL_EXPORT LinIntExpr 431 operator -(int, const LinIntExpr&); 432 /// Construct linear expression as sum of integer variable and integer 433 GECODE_MINIMODEL_EXPORT LinIntExpr 434 operator -(const IntVar&, int); 435 /// Construct linear expression as sum of Boolean variable and integer 436 GECODE_MINIMODEL_EXPORT LinIntExpr 437 operator -(const BoolVar&, int); 438 /// Construct linear expression as sum of linear expression and integer 439 GECODE_MINIMODEL_EXPORT LinIntExpr 440 operator -(const LinIntExpr&, int); 441 /// Construct linear expression as sum of integer variables 442 GECODE_MINIMODEL_EXPORT LinIntExpr 443 operator -(const IntVar&, const IntVar&); 444 /// Construct linear expression as sum of integer and Boolean variable 445 GECODE_MINIMODEL_EXPORT LinIntExpr 446 operator -(const IntVar&, const BoolVar&); 447 /// Construct linear expression as sum of Boolean and integer variable 448 GECODE_MINIMODEL_EXPORT LinIntExpr 449 operator -(const BoolVar&, const IntVar&); 450 /// Construct linear expression as sum of Boolean variables 451 GECODE_MINIMODEL_EXPORT LinIntExpr 452 operator -(const BoolVar&, const BoolVar&); 453 /// Construct linear expression as sum of integer variable and linear expression 454 GECODE_MINIMODEL_EXPORT LinIntExpr 455 operator -(const IntVar&, const LinIntExpr&); 456 /// Construct linear expression as sum of Boolean variable and linear expression 457 GECODE_MINIMODEL_EXPORT LinIntExpr 458 operator -(const BoolVar&, const LinIntExpr&); 459 /// Construct linear expression as sum of linear expression and integer variable 460 GECODE_MINIMODEL_EXPORT LinIntExpr 461 operator -(const LinIntExpr&, const IntVar&); 462 /// Construct linear expression as sum of linear expression and Boolean variable 463 GECODE_MINIMODEL_EXPORT LinIntExpr 464 operator -(const LinIntExpr&, const BoolVar&); 465 /// Construct linear expression as sum of linear expressions 466 GECODE_MINIMODEL_EXPORT LinIntExpr 467 operator -(const LinIntExpr&, const LinIntExpr&); 468 469 /// Construct linear expression as negative of integer variable 470 GECODE_MINIMODEL_EXPORT LinIntExpr 471 operator -(const IntVar&); 472 /// Construct linear expression as negative of Boolean variable 473 GECODE_MINIMODEL_EXPORT LinIntExpr 474 operator -(const BoolVar&); 475 /// Construct linear expression as negative of linear expression 476 GECODE_MINIMODEL_EXPORT LinIntExpr 477 operator -(const LinIntExpr&); 478 479 /// Construct linear expression as product of integer coefficient and integer variable 480 GECODE_MINIMODEL_EXPORT LinIntExpr 481 operator *(int, const IntVar&); 482 /// Construct linear expression as product of integer coefficient and Boolean variable 483 GECODE_MINIMODEL_EXPORT LinIntExpr 484 operator *(int, const BoolVar&); 485 /// Construct linear expression as product of integer coefficient and integer variable 486 GECODE_MINIMODEL_EXPORT LinIntExpr 487 operator *(const IntVar&, int); 488 /// Construct linear expression as product of integer coefficient and Boolean variable 489 GECODE_MINIMODEL_EXPORT LinIntExpr 490 operator *(const BoolVar&, int); 491 /// Construct linear expression as product of integer coefficient and linear expression 492 GECODE_MINIMODEL_EXPORT LinIntExpr 493 operator *(const LinIntExpr&, int); 494 /// Construct linear expression as product of integer coefficient and linear expression 495 GECODE_MINIMODEL_EXPORT LinIntExpr 496 operator *(int, const LinIntExpr&); 497 498 /// Construct linear expression as sum of integer variables 499 GECODE_MINIMODEL_EXPORT LinIntExpr 500 sum(const IntVarArgs& x); 501 /// Construct linear expression as sum of integer variables with coefficients 502 GECODE_MINIMODEL_EXPORT LinIntExpr 503 sum(const IntArgs& a, const IntVarArgs& x); 504 /// Construct linear expression as sum of Boolean variables 505 GECODE_MINIMODEL_EXPORT LinIntExpr 506 sum(const BoolVarArgs& x); 507 /// Construct linear expression as sum of Boolean variables with coefficients 508 GECODE_MINIMODEL_EXPORT LinIntExpr 509 sum(const IntArgs& a, const BoolVarArgs& x); 510 /// Construct linear expression as sum of \ref IntArgs 511 GECODE_MINIMODEL_EXPORT LinIntExpr 512 sum(const IntArgs& args); 513 514 /// Construct linear equality relation 515 GECODE_MINIMODEL_EXPORT LinIntRel 516 operator ==(int l, const IntVar& r); 517 /// Construct linear equality relation 518 GECODE_MINIMODEL_EXPORT LinIntRel 519 operator ==(int l, const BoolVar& r); 520 /// Construct linear equality relation 521 GECODE_MINIMODEL_EXPORT LinIntRel 522 operator ==(int l, const LinIntExpr& r); 523 /// Construct linear equality relation 524 GECODE_MINIMODEL_EXPORT LinIntRel 525 operator ==(const IntVar& l, int r); 526 /// Construct linear equality relation 527 GECODE_MINIMODEL_EXPORT LinIntRel 528 operator ==(const BoolVar& l, int r); 529 /// Construct linear equality relation 530 GECODE_MINIMODEL_EXPORT LinIntRel 531 operator ==(const LinIntExpr& l, int r); 532 /// Construct linear equality relation 533 GECODE_MINIMODEL_EXPORT LinIntRel 534 operator ==(const IntVar& l, const IntVar& r); 535 /// Construct linear equality relation 536 GECODE_MINIMODEL_EXPORT LinIntRel 537 operator ==(const IntVar& l, const BoolVar& r); 538 /// Construct linear equality relation 539 GECODE_MINIMODEL_EXPORT LinIntRel 540 operator ==(const BoolVar& l, const IntVar& r); 541 /// Construct linear equality relation 542 GECODE_MINIMODEL_EXPORT LinIntRel 543 operator ==(const BoolVar& l, const BoolVar& r); 544 /// Construct linear equality relation 545 GECODE_MINIMODEL_EXPORT LinIntRel 546 operator ==(const IntVar& l, const LinIntExpr& r); 547 /// Construct linear equality relation 548 GECODE_MINIMODEL_EXPORT LinIntRel 549 operator ==(const BoolVar& l, const LinIntExpr& r); 550 /// Construct linear equality relation 551 GECODE_MINIMODEL_EXPORT LinIntRel 552 operator ==(const LinIntExpr& l, const IntVar& r); 553 /// Construct linear equality relation 554 GECODE_MINIMODEL_EXPORT LinIntRel 555 operator ==(const LinIntExpr& l, const BoolVar& r); 556 /// Construct linear equality relation 557 GECODE_MINIMODEL_EXPORT LinIntRel 558 operator ==(const LinIntExpr& l, const LinIntExpr& r); 559 560 /// Construct linear disequality relation 561 GECODE_MINIMODEL_EXPORT LinIntRel 562 operator !=(int l, const IntVar& r); 563 /// Construct linear disequality relation 564 GECODE_MINIMODEL_EXPORT LinIntRel 565 operator !=(int l, const BoolVar& r); 566 /// Construct linear disequality relation 567 GECODE_MINIMODEL_EXPORT LinIntRel 568 operator !=(int l, const LinIntExpr& r); 569 /// Construct linear disequality relation 570 GECODE_MINIMODEL_EXPORT LinIntRel 571 operator !=(const IntVar& l, int r); 572 /// Construct linear disequality relation 573 GECODE_MINIMODEL_EXPORT LinIntRel 574 operator !=(const BoolVar& l, int r); 575 /// Construct linear disequality relation 576 GECODE_MINIMODEL_EXPORT LinIntRel 577 operator !=(const LinIntExpr& l, int r); 578 /// Construct linear disequality relation 579 GECODE_MINIMODEL_EXPORT LinIntRel 580 operator !=(const IntVar& l, const IntVar& r); 581 /// Construct linear disequality relation 582 GECODE_MINIMODEL_EXPORT LinIntRel 583 operator !=(const IntVar& l, const BoolVar& r); 584 /// Construct linear disequality relation 585 GECODE_MINIMODEL_EXPORT LinIntRel 586 operator !=(const BoolVar& l, const IntVar& r); 587 /// Construct linear disequality relation 588 GECODE_MINIMODEL_EXPORT LinIntRel 589 operator !=(const BoolVar& l, const BoolVar& r); 590 /// Construct linear disequality relation 591 GECODE_MINIMODEL_EXPORT LinIntRel 592 operator !=(const IntVar& l, const LinIntExpr& r); 593 /// Construct linear disequality relation 594 GECODE_MINIMODEL_EXPORT LinIntRel 595 operator !=(const BoolVar& l, const LinIntExpr& r); 596 /// Construct linear disequality relation 597 GECODE_MINIMODEL_EXPORT LinIntRel 598 operator !=(const LinIntExpr& l, const IntVar& r); 599 /// Construct linear disequality relation 600 GECODE_MINIMODEL_EXPORT LinIntRel 601 operator !=(const LinIntExpr& l, const BoolVar& r); 602 /// Construct linear disequality relation 603 GECODE_MINIMODEL_EXPORT LinIntRel 604 operator !=(const LinIntExpr& l, const LinIntExpr& r); 605 606 /// Construct linear inequality relation 607 GECODE_MINIMODEL_EXPORT LinIntRel 608 operator <(int l, const IntVar& r); 609 /// Construct linear inequality relation 610 GECODE_MINIMODEL_EXPORT LinIntRel 611 operator <(int l, const BoolVar& r); 612 /// Construct linear inequality relation 613 GECODE_MINIMODEL_EXPORT LinIntRel 614 operator <(int l, const LinIntExpr& r); 615 /// Construct linear inequality relation 616 GECODE_MINIMODEL_EXPORT LinIntRel 617 operator <(const IntVar& l, int r); 618 /// Construct linear inequality relation 619 GECODE_MINIMODEL_EXPORT LinIntRel 620 operator <(const BoolVar& l, int r); 621 /// Construct linear inequality relation 622 GECODE_MINIMODEL_EXPORT LinIntRel 623 operator <(const LinIntExpr& l, int r); 624 /// Construct linear inequality relation 625 GECODE_MINIMODEL_EXPORT LinIntRel 626 operator <(const IntVar& l, const IntVar& r); 627 /// Construct linear inequality relation 628 GECODE_MINIMODEL_EXPORT LinIntRel 629 operator <(const IntVar& l, const BoolVar& r); 630 /// Construct linear inequality relation 631 GECODE_MINIMODEL_EXPORT LinIntRel 632 operator <(const BoolVar& l, const IntVar& r); 633 /// Construct linear inequality relation 634 GECODE_MINIMODEL_EXPORT LinIntRel 635 operator <(const BoolVar& l, const BoolVar& r); 636 /// Construct linear inequality relation 637 GECODE_MINIMODEL_EXPORT LinIntRel 638 operator <(const IntVar& l, const LinIntExpr& r); 639 /// Construct linear inequality relation 640 GECODE_MINIMODEL_EXPORT LinIntRel 641 operator <(const BoolVar& l, const LinIntExpr& r); 642 /// Construct linear inequality relation 643 GECODE_MINIMODEL_EXPORT LinIntRel 644 operator <(const LinIntExpr& l, const IntVar& r); 645 /// Construct linear inequality relation 646 GECODE_MINIMODEL_EXPORT LinIntRel 647 operator <(const LinIntExpr& l, const BoolVar& r); 648 /// Construct linear inequality relation 649 GECODE_MINIMODEL_EXPORT LinIntRel 650 operator <(const LinIntExpr& l, const LinIntExpr& r); 651 652 /// Construct linear inequality relation 653 GECODE_MINIMODEL_EXPORT LinIntRel 654 operator <=(int l, const IntVar& r); 655 /// Construct linear inequality relation 656 GECODE_MINIMODEL_EXPORT LinIntRel 657 operator <=(int l, const BoolVar& r); 658 /// Construct linear inequality relation 659 GECODE_MINIMODEL_EXPORT LinIntRel 660 operator <=(int l, const LinIntExpr& r); 661 /// Construct linear inequality relation 662 GECODE_MINIMODEL_EXPORT LinIntRel 663 operator <=(const IntVar& l, int r); 664 /// Construct linear inequality relation 665 GECODE_MINIMODEL_EXPORT LinIntRel 666 operator <=(const BoolVar& l, int r); 667 /// Construct linear inequality relation 668 GECODE_MINIMODEL_EXPORT LinIntRel 669 operator <=(const LinIntExpr& l, int r); 670 /// Construct linear inequality relation 671 GECODE_MINIMODEL_EXPORT LinIntRel 672 operator <=(const IntVar& l, const IntVar& r); 673 /// Construct linear inequality relation 674 GECODE_MINIMODEL_EXPORT LinIntRel 675 operator <=(const IntVar& l, const BoolVar& r); 676 /// Construct linear inequality relation 677 GECODE_MINIMODEL_EXPORT LinIntRel 678 operator <=(const BoolVar& l, const IntVar& r); 679 /// Construct linear inequality relation 680 GECODE_MINIMODEL_EXPORT LinIntRel 681 operator <=(const BoolVar& l, const BoolVar& r); 682 /// Construct linear inequality relation 683 GECODE_MINIMODEL_EXPORT LinIntRel 684 operator <=(const IntVar& l, const LinIntExpr& r); 685 /// Construct linear inequality relation 686 GECODE_MINIMODEL_EXPORT LinIntRel 687 operator <=(const BoolVar& l, const LinIntExpr& r); 688 /// Construct linear inequality relation 689 GECODE_MINIMODEL_EXPORT LinIntRel 690 operator <=(const LinIntExpr& l, const IntVar& r); 691 /// Construct linear inequality relation 692 GECODE_MINIMODEL_EXPORT LinIntRel 693 operator <=(const LinIntExpr& l, const BoolVar& r); 694 /// Construct linear inequality relation 695 GECODE_MINIMODEL_EXPORT LinIntRel 696 operator <=(const LinIntExpr& l, const LinIntExpr& r); 697 698 /// Construct linear inequality relation 699 GECODE_MINIMODEL_EXPORT LinIntRel 700 operator >(int l, const IntVar& r); 701 /// Construct linear inequality relation 702 GECODE_MINIMODEL_EXPORT LinIntRel 703 operator >(int l, const BoolVar& r); 704 /// Construct linear inequality relation 705 GECODE_MINIMODEL_EXPORT LinIntRel 706 operator >(int l, const LinIntExpr& r); 707 /// Construct linear inequality relation 708 GECODE_MINIMODEL_EXPORT LinIntRel 709 operator >(const IntVar& l, int r); 710 /// Construct linear inequality relation 711 GECODE_MINIMODEL_EXPORT LinIntRel 712 operator >(const BoolVar& l, int r); 713 /// Construct linear inequality relation 714 GECODE_MINIMODEL_EXPORT LinIntRel 715 operator >(const LinIntExpr& l, int r); 716 /// Construct linear inequality relation 717 GECODE_MINIMODEL_EXPORT LinIntRel 718 operator >(const IntVar& l, const IntVar& r); 719 /// Construct linear inequality relation 720 GECODE_MINIMODEL_EXPORT LinIntRel 721 operator >(const IntVar& l, const BoolVar& r); 722 /// Construct linear inequality relation 723 GECODE_MINIMODEL_EXPORT LinIntRel 724 operator >(const BoolVar& l, const IntVar& r); 725 /// Construct linear inequality relation 726 GECODE_MINIMODEL_EXPORT LinIntRel 727 operator >(const BoolVar& l, const BoolVar& r); 728 /// Construct linear inequality relation 729 GECODE_MINIMODEL_EXPORT LinIntRel 730 operator >(const IntVar& l, const LinIntExpr& r); 731 /// Construct linear inequality relation 732 GECODE_MINIMODEL_EXPORT LinIntRel 733 operator >(const BoolVar& l, const LinIntExpr& r); 734 /// Construct linear inequality relation 735 GECODE_MINIMODEL_EXPORT LinIntRel 736 operator >(const LinIntExpr& l, const IntVar& r); 737 /// Construct linear inequality relation 738 GECODE_MINIMODEL_EXPORT LinIntRel 739 operator >(const LinIntExpr& l, const BoolVar& r); 740 /// Construct linear inequality relation 741 GECODE_MINIMODEL_EXPORT LinIntRel 742 operator >(const LinIntExpr& l, const LinIntExpr& r); 743 744 /// Construct linear inequality relation 745 GECODE_MINIMODEL_EXPORT LinIntRel 746 operator >=(int l, const IntVar& r); 747 /// Construct linear inequality relation 748 GECODE_MINIMODEL_EXPORT LinIntRel 749 operator >=(int l, const BoolVar& r); 750 /// Construct linear inequality relation 751 GECODE_MINIMODEL_EXPORT LinIntRel 752 operator >=(int l, const LinIntExpr& r); 753 /// Construct linear inequality relation 754 GECODE_MINIMODEL_EXPORT LinIntRel 755 operator >=(const IntVar& l, int r); 756 /// Construct linear inequality relation 757 GECODE_MINIMODEL_EXPORT LinIntRel 758 operator >=(const BoolVar& l, int r); 759 /// Construct linear inequality relation 760 GECODE_MINIMODEL_EXPORT LinIntRel 761 operator >=(const LinIntExpr& l, int r); 762 /// Construct linear inequality relation 763 GECODE_MINIMODEL_EXPORT LinIntRel 764 operator >=(const IntVar& l, const IntVar& r); 765 /// Construct linear inequality relation 766 GECODE_MINIMODEL_EXPORT LinIntRel 767 operator >=(const IntVar& l, const BoolVar& r); 768 /// Construct linear inequality relation 769 GECODE_MINIMODEL_EXPORT LinIntRel 770 operator >=(const BoolVar& l, const IntVar& r); 771 /// Construct linear inequality relation 772 GECODE_MINIMODEL_EXPORT LinIntRel 773 operator >=(const BoolVar& l, const BoolVar& r); 774 /// Construct linear inequality relation 775 GECODE_MINIMODEL_EXPORT LinIntRel 776 operator >=(const IntVar& l, const LinIntExpr& r); 777 /// Construct linear inequality relation 778 GECODE_MINIMODEL_EXPORT LinIntRel 779 operator >=(const BoolVar& l, const LinIntExpr& r); 780 /// Construct linear inequality relation 781 GECODE_MINIMODEL_EXPORT LinIntRel 782 operator >=(const LinIntExpr& l, const IntVar& r); 783 /// Construct linear inequality relation 784 GECODE_MINIMODEL_EXPORT LinIntRel 785 operator >=(const LinIntExpr& l, const BoolVar& r); 786 /// Construct linear inequality relation 787 GECODE_MINIMODEL_EXPORT LinIntRel 788 operator >=(const LinIntExpr& l, const LinIntExpr& r); 789 //@} 790 791 #ifdef GECODE_HAS_FLOAT_VARS 792 793 /// Base class for non-linear float expressions 794 class NonLinFloatExpr { 795 public: 796 /// Return variable constrained to be equal to the expression 797 virtual FloatVar post(Home home, FloatVar* ret) const = 0; 798 /// Post expression to be in relation \a frt with \a c 799 virtual void post(Home home, FloatRelType frt, FloatVal c) const = 0; 800 /// Post reified expression to be in relation \a frt with \a c 801 virtual void post(Home home, FloatRelType frt, FloatVal c, 802 BoolVar b) const = 0; 803 /// Destructor 804 virtual ~NonLinFloatExpr(void); 805 /// Return fresh variable if \a x is null, \a x otherwise 806 static FloatVar result(Home home, FloatVar* x); 807 /// Constrain \a x to be equal to \a y if \a x is not null 808 static FloatVar result(Home home, FloatVar* x, FloatVar y); 809 /// Memory management 810 void* operator new(size_t s); 811 /// Memory management 812 void operator delete(void* p, size_t s); 813 }; 814 815 } 816 817 #include <gecode/minimodel/float-expr.hpp> 818 819 namespace Gecode { 820 821 /// %Float expressions 822 class LinFloatExpr { 823 friend class LinFloatRel; 824 public: 825 /// Type of linear expression 826 enum NodeType { 827 NT_CONST, ///< Float value constant 828 NT_VAR, ///< Linear term with variable 829 NT_NONLIN, ///< Non-linear expression 830 NT_SUM, ///< Sum of float variables 831 NT_ADD, ///< Addition of linear terms 832 NT_SUB, ///< Subtraction of linear terms 833 NT_MUL ///< Multiplication by coefficient 834 }; 835 private: 836 /// Nodes for linear expressions 837 class Node; 838 Node* n; 839 public: 840 /// Default constructor 841 GECODE_MINIMODEL_EXPORT 842 LinFloatExpr(void); 843 /// Create expression for constant \a c 844 GECODE_MINIMODEL_EXPORT 845 LinFloatExpr(const FloatVal& c); 846 /// Create expression 847 GECODE_MINIMODEL_EXPORT 848 LinFloatExpr(const FloatVar& x); 849 /// Create expression 850 GECODE_MINIMODEL_EXPORT 851 LinFloatExpr(const FloatVar& x, FloatVal a); 852 /// Create sum expression 853 GECODE_MINIMODEL_EXPORT 854 explicit LinFloatExpr(const FloatVarArgs& x); 855 /// Create sum expression 856 GECODE_MINIMODEL_EXPORT 857 LinFloatExpr(const FloatValArgs& a, const FloatVarArgs& x); 858 /// Copy constructor 859 GECODE_MINIMODEL_EXPORT 860 LinFloatExpr(const LinFloatExpr& e); 861 /// Create expression for type and subexpressions 862 GECODE_MINIMODEL_EXPORT 863 LinFloatExpr(const LinFloatExpr& e0, NodeType t, const LinFloatExpr& e1); 864 /// Create expression for type and subexpression 865 GECODE_MINIMODEL_EXPORT 866 LinFloatExpr(const LinFloatExpr& e0, NodeType t, const FloatVal& c); 867 /// Create expression for multiplication 868 GECODE_MINIMODEL_EXPORT 869 LinFloatExpr(FloatVal a, const LinFloatExpr& e); 870 /// Create non-linear expression 871 GECODE_MINIMODEL_EXPORT 872 explicit LinFloatExpr(NonLinFloatExpr* e); 873 /// Assignment operator 874 GECODE_MINIMODEL_EXPORT 875 const LinFloatExpr& operator =(const LinFloatExpr& e); 876 /// Post propagator 877 GECODE_MINIMODEL_EXPORT 878 void post(Home home, FloatRelType frt) const; 879 /// Post reified propagator 880 GECODE_MINIMODEL_EXPORT 881 void post(Home home, FloatRelType frt, const BoolVar& b) const; 882 /// Post propagator and return variable for value 883 GECODE_MINIMODEL_EXPORT 884 FloatVar post(Home home) const; 885 /// Return non-linear expression inside, or null if not non-linear 886 GECODE_MINIMODEL_EXPORT 887 NonLinFloatExpr* nlfe(void) const; 888 /// Destructor 889 GECODE_MINIMODEL_EXPORT 890 ~LinFloatExpr(void); 891 }; 892 893 class BoolExpr; 894 895 /// Linear relations 896 class LinFloatRel { 897 friend class BoolExpr; 898 private: 899 /// Linear float expression describing the entire relation 900 LinFloatExpr e; 901 /// Which relation 902 FloatRelType frt; 903 /// Negate relation type 904 static FloatRelType neg(FloatRelType frt); 905 /// Default constructor 906 LinFloatRel(void); 907 public: 908 /// Create linear float relation for expressions \a l and \a r 909 LinFloatRel(const LinFloatExpr& l, FloatRelType frt, const LinFloatExpr& r); 910 /// Create linear float relation for expression \a l and FloatVal \a r 911 LinFloatRel(const LinFloatExpr& l, FloatRelType frt, FloatVal r); 912 /// Create linear float relation for FloatVal \a l and expression \a r 913 LinFloatRel(FloatVal l, FloatRelType frt, const LinFloatExpr& r); 914 /// Post propagator for relation (if \a t is false for negated relation) 915 void post(Home home, bool t) const; 916 /// Post reified propagator for relation (if \a t is false for negated relation) 917 void post(Home home, const BoolVar& b, bool t) const; 918 }; 919 920 /** 921 * \defgroup TaskModelMiniModelFloat Linear float expressions and relations 922 * 923 * Linear float expressions can be freely composed of sums and differences of 924 * float variables (Gecode::FloatVar) with float coefficients and float 925 * constants. 926 * 927 * Linear float relations are obtained from linear float expressions with the normal 928 * relation operators. 929 * 930 * \ingroup TaskModelMiniModel 931 */ 932 //@{ 933 /// Construct linear float expression as sum of float variable and float 934 GECODE_MINIMODEL_EXPORT LinFloatExpr 935 operator +(const FloatVal&, const FloatVar&); 936 /// Construct linear float expression as sum of linear float expression and float 937 GECODE_MINIMODEL_EXPORT LinFloatExpr 938 operator +(const FloatVal&, const LinFloatExpr&); 939 /// Construct linear float expression as sum of float variable and float 940 GECODE_MINIMODEL_EXPORT LinFloatExpr 941 operator +(const FloatVar&, const FloatVal&); 942 /// Construct linear float expression as sum of linear float expression and float 943 GECODE_MINIMODEL_EXPORT LinFloatExpr 944 operator +(const LinFloatExpr&, const FloatVal&); 945 /// Construct linear float expression as sum of float variables 946 GECODE_MINIMODEL_EXPORT LinFloatExpr 947 operator +(const FloatVar&, const FloatVar&); 948 /// Construct linear float expression as sum of float variable and linear float expression 949 GECODE_MINIMODEL_EXPORT LinFloatExpr 950 operator +(const FloatVar&, const LinFloatExpr&); 951 /// Construct linear float expression as sum of linear float expression and float variable 952 GECODE_MINIMODEL_EXPORT LinFloatExpr 953 operator +(const LinFloatExpr&, const FloatVar&); 954 /// Construct linear float expression as sum of linear float expressions 955 GECODE_MINIMODEL_EXPORT LinFloatExpr 956 operator +(const LinFloatExpr&, const LinFloatExpr&); 957 958 /// Construct linear float expression as sum of float variable and float 959 GECODE_MINIMODEL_EXPORT LinFloatExpr 960 operator -(const FloatVal&, const FloatVar&); 961 /// Construct linear float expression as sum of float and linear float expression 962 GECODE_MINIMODEL_EXPORT LinFloatExpr 963 operator -(const FloatVal&, const LinFloatExpr&); 964 /// Construct linear float expression as sum of float variable and float 965 GECODE_MINIMODEL_EXPORT LinFloatExpr 966 operator -(const FloatVar&, const FloatVal&); 967 /// Construct linear float expression as sum of linear float expression and float 968 GECODE_MINIMODEL_EXPORT LinFloatExpr 969 operator -(const LinFloatExpr&, const FloatVal&); 970 /// Construct linear float expression as sum of float variables 971 GECODE_MINIMODEL_EXPORT LinFloatExpr 972 operator -(const FloatVar&, const FloatVar&); 973 /// Construct linear float expression as sum of float variable and linear float expression 974 GECODE_MINIMODEL_EXPORT LinFloatExpr 975 operator -(const FloatVar&, const LinFloatExpr&); 976 /// Construct linear float expression as sum of linear float expression and float variable 977 GECODE_MINIMODEL_EXPORT LinFloatExpr 978 operator -(const LinFloatExpr&, const FloatVar&); 979 /// Construct linear float expression as sum of linear float expressions 980 GECODE_MINIMODEL_EXPORT LinFloatExpr 981 operator -(const LinFloatExpr&, const LinFloatExpr&); 982 983 /// Construct linear float expression as negative of float variable 984 GECODE_MINIMODEL_EXPORT LinFloatExpr 985 operator -(const FloatVar&); 986 /// Construct linear float expression as negative of linear float expression 987 GECODE_MINIMODEL_EXPORT LinFloatExpr 988 operator -(const LinFloatExpr&); 989 990 /// Construct linear float expression as product of float coefficient and float variable 991 GECODE_MINIMODEL_EXPORT LinFloatExpr 992 operator *(const FloatVal&, const FloatVar&); 993 /// Construct linear float expression as product of float coefficient and float variable 994 GECODE_MINIMODEL_EXPORT LinFloatExpr 995 operator *(const FloatVar&, const FloatVal&); 996 /// Construct linear float expression as product of float coefficient and linear float expression 997 GECODE_MINIMODEL_EXPORT LinFloatExpr 998 operator *(const LinFloatExpr&, const FloatVal&); 999 /// Construct linear float expression as product of float coefficient and linear float expression 1000 GECODE_MINIMODEL_EXPORT LinFloatExpr 1001 operator *(const FloatVal&, const LinFloatExpr&); 1002 1003 /// Construct linear float expression as sum of float variables 1004 GECODE_MINIMODEL_EXPORT LinFloatExpr 1005 sum(const FloatVarArgs& x); 1006 /// Construct linear float expression as sum of float variables with coefficients 1007 GECODE_MINIMODEL_EXPORT LinFloatExpr 1008 sum(const FloatValArgs& a, const FloatVarArgs& x); 1009 1010 /// Construct linear float equality relation 1011 GECODE_MINIMODEL_EXPORT LinFloatRel 1012 operator ==(const FloatVal& l, const FloatVar& r); 1013 /// Construct linear float equality relation 1014 GECODE_MINIMODEL_EXPORT LinFloatRel 1015 operator ==(const FloatVal& l, const LinFloatExpr& r); 1016 /// Construct linear float equality relation 1017 GECODE_MINIMODEL_EXPORT LinFloatRel 1018 operator ==(const FloatVar& l, const FloatVal& r); 1019 /// Construct linear float equality relation 1020 GECODE_MINIMODEL_EXPORT LinFloatRel 1021 operator ==(const LinFloatExpr& l, const FloatVal& r); 1022 /// Construct linear float equality relation 1023 GECODE_MINIMODEL_EXPORT LinFloatRel 1024 operator ==(const FloatVar& l, const FloatVar& r); 1025 /// Construct linear float equality relation 1026 GECODE_MINIMODEL_EXPORT LinFloatRel 1027 operator ==(const FloatVar& l, const LinFloatExpr& r); 1028 /// Construct linear float equality relation 1029 GECODE_MINIMODEL_EXPORT LinFloatRel 1030 operator ==(const LinFloatExpr& l, const FloatVar& r); 1031 /// Construct linear float equality relation 1032 GECODE_MINIMODEL_EXPORT LinFloatRel 1033 operator ==(const LinFloatExpr& l, const LinFloatExpr& r); 1034 1035 /// Construct linear float disequality relation 1036 GECODE_MINIMODEL_EXPORT LinFloatRel 1037 operator !=(const FloatVal& l, const FloatVar& r); 1038 /// Construct linear float disequality relation 1039 GECODE_MINIMODEL_EXPORT LinFloatRel 1040 operator !=(const FloatVal& l, const LinFloatExpr& r); 1041 /// Construct linear float disequality relation 1042 GECODE_MINIMODEL_EXPORT LinFloatRel 1043 operator !=(const FloatVar& l, const FloatVal& r); 1044 /// Construct linear float disequality relation 1045 GECODE_MINIMODEL_EXPORT LinFloatRel 1046 operator !=(const LinFloatExpr& l, const FloatVal& r); 1047 /// Construct linear float disequality relation 1048 GECODE_MINIMODEL_EXPORT LinFloatRel 1049 operator !=(const FloatVar& l, const FloatVar& r); 1050 /// Construct linear float disequality relation 1051 GECODE_MINIMODEL_EXPORT LinFloatRel 1052 operator !=(const FloatVar& l, const LinFloatExpr& r); 1053 /// Construct linear float disequality relation 1054 GECODE_MINIMODEL_EXPORT LinFloatRel 1055 operator !=(const LinFloatExpr& l, const FloatVar& r); 1056 /// Construct linear float disequality relation 1057 GECODE_MINIMODEL_EXPORT LinFloatRel 1058 operator !=(const LinFloatExpr& l, const LinFloatExpr& r); 1059 1060 /// Construct linear float inequality relation 1061 GECODE_MINIMODEL_EXPORT LinFloatRel 1062 operator <(const FloatVal& l, const FloatVar& r); 1063 /// Construct linear float inequality relation 1064 GECODE_MINIMODEL_EXPORT LinFloatRel 1065 operator <(const FloatVal& l, const LinFloatExpr& r); 1066 /// Construct linear float inequality relation 1067 GECODE_MINIMODEL_EXPORT LinFloatRel 1068 operator <(const FloatVar& l, const FloatVal& r); 1069 /// Construct linear float inequality relation 1070 GECODE_MINIMODEL_EXPORT LinFloatRel 1071 operator <(const LinFloatExpr& l, const FloatVal& r); 1072 /// Construct linear float inequality relation 1073 GECODE_MINIMODEL_EXPORT LinFloatRel 1074 operator <(const FloatVar& l, const FloatVar& r); 1075 /// Construct linear float inequality relation 1076 GECODE_MINIMODEL_EXPORT LinFloatRel 1077 operator <(const FloatVar& l, const LinFloatExpr& r); 1078 /// Construct linear float inequality relation 1079 GECODE_MINIMODEL_EXPORT LinFloatRel 1080 operator <(const LinFloatExpr& l, const FloatVar& r); 1081 /// Construct linear float inequality relation 1082 GECODE_MINIMODEL_EXPORT LinFloatRel 1083 operator <(const LinFloatExpr& l, const LinFloatExpr& r); 1084 1085 /// Construct linear float inequality relation 1086 GECODE_MINIMODEL_EXPORT LinFloatRel 1087 operator <=(const FloatVal& l, const FloatVar& r); 1088 /// Construct linear float inequality relation 1089 GECODE_MINIMODEL_EXPORT LinFloatRel 1090 operator <=(const FloatVal& l, const LinFloatExpr& r); 1091 /// Construct linear float inequality relation 1092 GECODE_MINIMODEL_EXPORT LinFloatRel 1093 operator <=(const FloatVar& l, const FloatVal& r); 1094 /// Construct linear float inequality relation 1095 GECODE_MINIMODEL_EXPORT LinFloatRel 1096 operator <=(const LinFloatExpr& l, const FloatVal& r); 1097 /// Construct linear float inequality relation 1098 GECODE_MINIMODEL_EXPORT LinFloatRel 1099 operator <=(const FloatVar& l, const FloatVar& r); 1100 /// Construct linear float inequality relation 1101 GECODE_MINIMODEL_EXPORT LinFloatRel 1102 operator <=(const FloatVar& l, const LinFloatExpr& r); 1103 /// Construct linear float inequality relation 1104 GECODE_MINIMODEL_EXPORT LinFloatRel 1105 operator <=(const LinFloatExpr& l, const FloatVar& r); 1106 /// Construct linear float inequality relation 1107 GECODE_MINIMODEL_EXPORT LinFloatRel 1108 operator <=(const LinFloatExpr& l, const LinFloatExpr& r); 1109 1110 /// Construct linear float inequality relation 1111 GECODE_MINIMODEL_EXPORT LinFloatRel 1112 operator >(const FloatVal& l, const FloatVar& r); 1113 /// Construct linear float inequality relation 1114 GECODE_MINIMODEL_EXPORT LinFloatRel 1115 operator >(const FloatVal& l, const LinFloatExpr& r); 1116 /// Construct linear float inequality relation 1117 GECODE_MINIMODEL_EXPORT LinFloatRel 1118 operator >(const FloatVar& l, const FloatVal& r); 1119 /// Construct linear float inequality relation 1120 GECODE_MINIMODEL_EXPORT LinFloatRel 1121 operator >(const LinFloatExpr& l, const FloatVal& r); 1122 /// Construct linear float inequality relation 1123 GECODE_MINIMODEL_EXPORT LinFloatRel 1124 operator >(const FloatVar& l, const FloatVar& r); 1125 /// Construct linear float inequality relation 1126 GECODE_MINIMODEL_EXPORT LinFloatRel 1127 operator >(const FloatVar& l, const LinFloatExpr& r); 1128 /// Construct linear float inequality relation 1129 GECODE_MINIMODEL_EXPORT LinFloatRel 1130 operator >(const LinFloatExpr& l, const FloatVar& r); 1131 /// Construct linear float inequality relation 1132 GECODE_MINIMODEL_EXPORT LinFloatRel 1133 operator >(const LinFloatExpr& l, const LinFloatExpr& r); 1134 1135 /// Construct linear float inequality relation 1136 GECODE_MINIMODEL_EXPORT LinFloatRel 1137 operator >=(const FloatVal& l, const FloatVar& r); 1138 /// Construct linear float inequality relation 1139 GECODE_MINIMODEL_EXPORT LinFloatRel 1140 operator >=(const FloatVal& l, const LinFloatExpr& r); 1141 /// Construct linear float inequality relation 1142 GECODE_MINIMODEL_EXPORT LinFloatRel 1143 operator >=(const FloatVar& l, const FloatVal& r); 1144 /// Construct linear float inequality relation 1145 GECODE_MINIMODEL_EXPORT LinFloatRel 1146 operator >=(const LinFloatExpr& l, const FloatVal& r); 1147 /// Construct linear float inequality relation 1148 GECODE_MINIMODEL_EXPORT LinFloatRel 1149 operator >=(const FloatVar& l, const FloatVar& r); 1150 /// Construct linear float inequality relation 1151 GECODE_MINIMODEL_EXPORT LinFloatRel 1152 operator >=(const FloatVar& l, const LinFloatExpr& r); 1153 /// Construct linear float inequality relation 1154 GECODE_MINIMODEL_EXPORT LinFloatRel 1155 operator >=(const LinFloatExpr& l, const FloatVar& r); 1156 /// Construct linear float inequality relation 1157 GECODE_MINIMODEL_EXPORT LinFloatRel 1158 operator >=(const LinFloatExpr& l, const LinFloatExpr& r); 1159 //@} 1160 #endif 1161 1162 #ifdef GECODE_HAS_SET_VARS 1163 /// %Set expressions 1164 class SetExpr { 1165 public: 1166 /// Type of set expression 1167 enum NodeType { 1168 NT_VAR, ///< Variable 1169 NT_CONST, ///< Constant 1170 NT_LEXP, ///< Linear expression 1171 NT_CMPL, ///< Complement 1172 NT_INTER, ///< Intersection 1173 NT_UNION, ///< Union 1174 NT_DUNION ///< Disjoint union 1175 }; 1176 /// %Node for set expression 1177 class Node; 1178 private: 1179 /// Pointer to node for expression 1180 Node* n; 1181 public: 1182 /// Default constructor 1183 SetExpr(void); 1184 /// Copy constructor 1185 GECODE_MINIMODEL_EXPORT 1186 SetExpr(const SetExpr& e); 1187 /// Construct expression for type and subexpresssions 1188 GECODE_MINIMODEL_EXPORT 1189 SetExpr(const SetExpr& l, NodeType t, const SetExpr& r); 1190 /// Construct expression for variable 1191 GECODE_MINIMODEL_EXPORT 1192 SetExpr(const SetVar& x); 1193 /// Construct expression for integer variable 1194 GECODE_MINIMODEL_EXPORT 1195 explicit SetExpr(const LinIntExpr& x); 1196 /// Construct expression for constant 1197 GECODE_MINIMODEL_EXPORT 1198 SetExpr(const IntSet& s); 1199 /// Construct expression for negation 1200 GECODE_MINIMODEL_EXPORT 1201 SetExpr(const SetExpr& e, NodeType t); 1202 /// Post propagators for expression 1203 GECODE_MINIMODEL_EXPORT 1204 SetVar post(Home home) const; 1205 /// Post propagators for relation 1206 GECODE_MINIMODEL_EXPORT 1207 void post(Home home, SetRelType srt, const SetExpr& e) const; 1208 /// Post propagators for reified relation 1209 GECODE_MINIMODEL_EXPORT 1210 void post(Home home, BoolVar b, bool t, 1211 SetRelType srt, const SetExpr& e) const; 1212 /// Assignment operator 1213 GECODE_MINIMODEL_EXPORT 1214 const SetExpr& operator =(const SetExpr& e); 1215 /// Destructor 1216 GECODE_MINIMODEL_EXPORT 1217 ~SetExpr(void); 1218 }; 1219 1220 /// Comparison relation (for two-sided comparisons) 1221 class SetCmpRel { 1222 public: 1223 /// Left side of relation 1224 SetExpr l; 1225 /// Right side of relation 1226 SetExpr r; 1227 /// Which relation 1228 SetRelType srt; 1229 /// Constructor 1230 SetCmpRel(const SetExpr& l, SetRelType srt, const SetExpr& r); 1231 }; 1232 1233 /// %Set relations 1234 class SetRel { 1235 private: 1236 /// Expression 1237 SetExpr _e0; 1238 /// Relation 1239 SetRelType _srt; 1240 /// Expression 1241 SetExpr _e1; 1242 public: 1243 /// Default constructor 1244 SetRel(void); 1245 /// Constructor 1246 SetRel(const SetExpr& e0, SetRelType srt, const SetExpr& e1); 1247 /// Constructor 1248 SetRel(const SetCmpRel& r); 1249 /// Post propagators for relation (or negated relation if \a t is false) 1250 void post(Home home, bool t) const; 1251 /// Post propagators for reified relation (or negated relation if \a t is false) 1252 void post(Home home, BoolVar b, bool t) const; 1253 }; 1254 1255 /** 1256 * \defgroup TaskModelMiniModelSet Set expressions and relations 1257 * 1258 * Set expressions and relations can be freely composed of variables 1259 * with the usual connectives. 1260 * 1261 * \ingroup TaskModelMiniModel 1262 */ 1263 1264 //@{ 1265 /// Singleton expression 1266 GECODE_MINIMODEL_EXPORT SetExpr 1267 singleton(const LinIntExpr&); 1268 /// Complement expression 1269 GECODE_MINIMODEL_EXPORT SetExpr 1270 operator -(const SetExpr&); 1271 /// Intersection of set expressions 1272 GECODE_MINIMODEL_EXPORT SetExpr 1273 operator &(const SetExpr&, const SetExpr&); 1274 /// Union of set expressions 1275 GECODE_MINIMODEL_EXPORT SetExpr 1276 operator |(const SetExpr&, const SetExpr&); 1277 /// Disjoint union of set expressions 1278 GECODE_MINIMODEL_EXPORT SetExpr 1279 operator +(const SetExpr&, const SetExpr&); 1280 /// Difference of set expressions 1281 GECODE_MINIMODEL_EXPORT SetExpr 1282 operator -(const SetExpr&, const SetExpr&); 1283 1284 /// Intersection of set variables 1285 GECODE_MINIMODEL_EXPORT SetExpr 1286 inter(const SetVarArgs&); 1287 /// Union of set variables 1288 GECODE_MINIMODEL_EXPORT SetExpr 1289 setunion(const SetVarArgs&); 1290 /// Disjoint union of set variables 1291 GECODE_MINIMODEL_EXPORT SetExpr 1292 setdunion(const SetVarArgs&); 1293 1294 /// Cardinality of set expression 1295 GECODE_MINIMODEL_EXPORT LinIntExpr 1296 cardinality(const SetExpr&); 1297 /// Minimum element of set expression 1298 GECODE_MINIMODEL_EXPORT LinIntExpr 1299 min(const SetExpr&); 1300 /// Minimum element of set expression 1301 GECODE_MINIMODEL_EXPORT LinIntExpr 1302 max(const SetExpr&); 1303 1304 /// Equality of set expressions 1305 GECODE_MINIMODEL_EXPORT SetRel 1306 operator ==(const SetExpr&, const SetExpr&); 1307 /// Disequality of set expressions 1308 GECODE_MINIMODEL_EXPORT SetRel 1309 operator !=(const SetExpr&, const SetExpr&); 1310 /// Subset of set expressions 1311 GECODE_MINIMODEL_EXPORT SetCmpRel 1312 operator <=(const SetExpr&, const SetExpr&); 1313 /// Subset of set expressions 1314 GECODE_MINIMODEL_EXPORT BoolExpr 1315 operator <=(const SetCmpRel&, const SetExpr&); 1316 /// Superset of set expressions 1317 GECODE_MINIMODEL_EXPORT SetCmpRel 1318 operator >=(const SetExpr&, const SetExpr&); 1319 /// Superset of set expressions 1320 GECODE_MINIMODEL_EXPORT BoolExpr 1321 operator >=(const SetCmpRel&, const SetExpr&); 1322 /// Disjointness of set expressions 1323 GECODE_MINIMODEL_EXPORT SetRel 1324 operator ||(const SetExpr&, const SetExpr&); 1325 //@} 1326 #endif 1327 1328 /// Boolean expressions 1329 class BoolExpr { 1330 public: 1331 /// Type of Boolean expression 1332 enum NodeType { 1333 NT_VAR, ///< Variable 1334 NT_NOT, ///< Negation 1335 NT_AND, ///< Conjunction 1336 NT_OR, ///< Disjunction 1337 NT_EQV, ///< Equivalence 1338 NT_RLIN, ///< Reified linear relation 1339 NT_RLINFLOAT, ///< Reified linear relation 1340 NT_RSET, ///< Reified set relation 1341 NT_MISC ///< Other Boolean expression 1342 }; 1343 /// Miscealloneous Boolean expressions 1344 class GECODE_VTABLE_EXPORT Misc : public HeapAllocated { 1345 public: 1346 /// Default constructor 1347 Misc(void); 1348 /** Constrain \a b to be equivalent to the expression 1349 * (negated if \a neg) with propagation level 1350 * \a ipl. 1351 */ 1352 virtual void post(Home home, BoolVar b, bool neg, 1353 const IntPropLevels& ipls) = 0; 1354 /// Destructor 1355 virtual GECODE_MINIMODEL_EXPORT ~Misc(void); 1356 }; 1357 /// %Node for Boolean expression 1358 class Node; 1359 private: 1360 /// Pointer to node for expression 1361 Node* n; 1362 public: 1363 /// Default constructor 1364 GECODE_MINIMODEL_EXPORT 1365 BoolExpr(void); 1366 /// Copy constructor 1367 GECODE_MINIMODEL_EXPORT 1368 BoolExpr(const BoolExpr& e); 1369 /// Construct expression for type and subexpresssions 1370 GECODE_MINIMODEL_EXPORT 1371 BoolExpr(const BoolExpr& l, NodeType t, const BoolExpr& r); 1372 /// Construct expression for variable 1373 GECODE_MINIMODEL_EXPORT 1374 BoolExpr(const BoolVar& x); 1375 /// Construct expression for negation 1376 GECODE_MINIMODEL_EXPORT 1377 BoolExpr(const BoolExpr& e, NodeType t); 1378 /// Construct expression for reified linear relation 1379 GECODE_MINIMODEL_EXPORT 1380 BoolExpr(const LinIntRel& rl); 1381 #ifdef GECODE_HAS_FLOAT_VARS 1382 /// Construct expression for reified float relation 1383 GECODE_MINIMODEL_EXPORT 1384 BoolExpr(const LinFloatRel& rfl); 1385 #endif 1386 #ifdef GECODE_HAS_SET_VARS 1387 /// Construct expression for reified set relation 1388 GECODE_MINIMODEL_EXPORT 1389 BoolExpr(const SetRel& rs); 1390 /// Construct expression for reified set relation 1391 GECODE_MINIMODEL_EXPORT 1392 BoolExpr(const SetCmpRel& rs); 1393 #endif 1394 /// Construct expression for miscellaneous Boolean expression 1395 GECODE_MINIMODEL_EXPORT 1396 explicit BoolExpr(Misc* m); 1397 /// Post propagators for expression 1398 GECODE_MINIMODEL_EXPORT 1399 BoolVar expr(Home home, const IntPropLevels& ipls) const; 1400 /// Post propagators for relation 1401 GECODE_MINIMODEL_EXPORT 1402 void rel(Home home, const IntPropLevels& ipls) const; 1403 /// Assignment operator 1404 GECODE_MINIMODEL_EXPORT 1405 const BoolExpr& operator =(const BoolExpr& e); 1406 /// Destructor 1407 GECODE_MINIMODEL_EXPORT 1408 ~BoolExpr(void); 1409 }; 1410 1411 /** 1412 * \defgroup TaskModelMiniModelBool Boolean expressions 1413 * 1414 * Boolean expressions can be freely composed of variables with 1415 * the usual connectives and reified linear expressions. 1416 * 1417 * \ingroup TaskModelMiniModel 1418 */ 1419 1420 //@{ 1421 /// Negated Boolean expression 1422 GECODE_MINIMODEL_EXPORT BoolExpr 1423 operator !(const BoolExpr&); 1424 /// Conjunction of Boolean expressions 1425 GECODE_MINIMODEL_EXPORT BoolExpr 1426 operator &&(const BoolExpr&, const BoolExpr&); 1427 /// Disjunction of Boolean expressions 1428 GECODE_MINIMODEL_EXPORT BoolExpr 1429 operator ||(const BoolExpr&, const BoolExpr&); 1430 /// Exclusive-or of Boolean expressions 1431 GECODE_MINIMODEL_EXPORT BoolExpr 1432 operator ^(const BoolExpr&, const BoolExpr&); 1433 1434 /// Non-equivalence of Boolean expressions 1435 GECODE_MINIMODEL_EXPORT BoolExpr 1436 operator !=(const BoolExpr&, const BoolExpr&); 1437 /// Equivalence of Boolean expressions 1438 GECODE_MINIMODEL_EXPORT BoolExpr 1439 operator ==(const BoolExpr&, const BoolExpr&); 1440 /// Implication of Boolean expressions 1441 GECODE_MINIMODEL_EXPORT BoolExpr 1442 operator >>(const BoolExpr&, const BoolExpr&); 1443 /// Reverse implication of Boolean expressions 1444 GECODE_MINIMODEL_EXPORT BoolExpr 1445 operator <<(const BoolExpr&, const BoolExpr&); 1446 1447 //@} 1448 1449 /** 1450 * \defgroup TaskModelMiniModelReified Reified expressions 1451 * 1452 * \ingroup TaskModelMiniModel 1453 */ 1454 1455 //@{ 1456 /// \brief Return expression for \f$ x=n\f$ 1457 GECODE_MINIMODEL_EXPORT BoolExpr 1458 dom(const IntVar& x, int n); 1459 /// \brief Return expression for \f$ l\leq x \leq m\f$ 1460 GECODE_MINIMODEL_EXPORT BoolExpr 1461 dom(const IntVar& x, int l, int m); 1462 /// \brief Return expression for \f$ x \in s\f$ 1463 GECODE_MINIMODEL_EXPORT BoolExpr 1464 dom(const IntVar& x, const IntSet& s); 1465 1466 #ifdef GECODE_HAS_SET_VARS 1467 /// \brief Return expression for \f$ x \sim_{rt} \{i\}\f$ 1468 GECODE_MINIMODEL_EXPORT BoolExpr 1469 dom(const SetVar& x, SetRelType rt, int i); 1470 /// \brief Return expression for \f$ x \sim_{rt} \{i,\dots,j\}\f$ 1471 GECODE_MINIMODEL_EXPORT BoolExpr 1472 dom(const SetVar& x, SetRelType rt, int i, int j); 1473 /// \brief Return expression for \f$ x \sim_{rt} s\f$ 1474 GECODE_MINIMODEL_EXPORT BoolExpr 1475 dom(const SetVar& x, SetRelType rt, const IntSet& s); 1476 #endif 1477 1478 #ifdef GECODE_HAS_FLOAT_VARS 1479 /// \brief Return expression for \f$ x=n\f$ 1480 GECODE_MINIMODEL_EXPORT BoolExpr 1481 dom(const FloatVar& x, const FloatVal& n); 1482 /// \brief Return expression for \f$ l\leq x \leq u\f$ 1483 GECODE_MINIMODEL_EXPORT BoolExpr 1484 dom(const FloatVar& x, FloatNum l, FloatNum u); 1485 #endif 1486 //@} 1487 1488 /** 1489 * \defgroup TaskModelMiniModelMixed Mixed integer and set expressions 1490 * 1491 * \ingroup TaskModelMiniModel 1492 */ 1493 1494 //@{ 1495 #ifdef GECODE_HAS_SET_VARS 1496 /// \brief Return expression for \f$|s|\geq 1 \land \forall i\in s:\ i=x\f$ 1497 GECODE_MINIMODEL_EXPORT BoolExpr 1498 operator ==(const SetExpr& s, const LinIntExpr& x); 1499 /// \brief Return expression for \f$|s|\geq 1 \land \forall i\in s:\ x=i\f$ 1500 GECODE_MINIMODEL_EXPORT BoolExpr 1501 operator ==(const LinIntExpr& x, const SetExpr& s); 1502 /// Prevent comparison with IntSet 1503 BoolExpr 1504 operator ==(const LinIntExpr&, IntSet) = delete; 1505 /// Prevent comparison with IntSet 1506 BoolExpr 1507 operator ==(IntSet, const LinIntExpr&) = delete; 1508 1509 /// \brief Return expression for \f$|s|\geq 1 \land \forall i\in s:\ i\neq x\f$ 1510 GECODE_MINIMODEL_EXPORT BoolExpr 1511 operator !=(const SetExpr& s, const LinIntExpr& x); 1512 /// \brief Return expression for \f$|s|\geq 1 \land \forall i\in s:\ x\neq i\f$ 1513 GECODE_MINIMODEL_EXPORT BoolExpr 1514 operator !=(const LinIntExpr& x, const SetExpr& s); 1515 /// Prevent comparison with IntSet 1516 BoolExpr 1517 operator !=(const LinIntExpr&, IntSet) = delete; 1518 /// Prevent comparison with IntSet 1519 BoolExpr 1520 operator !=(IntSet, const LinIntExpr&) = delete; 1521 1522 /// \brief Return expression for \f$|s|\geq 6 \land \forall i\in s:\ i\leq x\f$ 1523 GECODE_MINIMODEL_EXPORT BoolExpr 1524 operator <=(const SetExpr& s, const LinIntExpr& x); 1525 /// \brief Return expression for \f$|s|\geq 1 \land \forall i\in s:\ x\leq i\f$ 1526 GECODE_MINIMODEL_EXPORT BoolExpr 1527 operator <=(const LinIntExpr& x, const SetExpr& s); 1528 /// Prevent comparison with IntSet 1529 BoolExpr 1530 operator <=(const LinIntExpr&, IntSet) = delete; 1531 /// Prevent comparison with IntSet 1532 BoolExpr 1533 operator <=(IntSet, const LinIntExpr&) = delete; 1534 1535 /// \brief Return expression for \f$|s|\geq 1 \land \forall i\in s:\ i<x\f$ 1536 GECODE_MINIMODEL_EXPORT BoolExpr 1537 operator <(const SetExpr& s, const LinIntExpr& x); 1538 /// \brief Return expression for \f$|s|\geq 1 \land \forall i\in s:\ x<i\f$ 1539 GECODE_MINIMODEL_EXPORT BoolExpr 1540 operator <(const LinIntExpr& x, const SetExpr& s); 1541 /// Prevent comparison with IntSet 1542 BoolExpr 1543 operator <(const LinIntExpr&, IntSet) = delete; 1544 /// Prevent comparison with IntSet 1545 BoolExpr 1546 operator <(IntSet, const LinIntExpr&) = delete; 1547 1548 /// \brief Return expression for \f$|s|\geq 1 \land \forall i\in s:\ i\geq x\f$ 1549 GECODE_MINIMODEL_EXPORT BoolExpr 1550 operator >=(const SetExpr& s, const LinIntExpr& x); 1551 /// \brief Return expression for \f$|s|\geq 1 \land \forall i\in s:\ x\geq i\f$ 1552 GECODE_MINIMODEL_EXPORT BoolExpr 1553 operator >=(const LinIntExpr& x, const SetExpr& s); 1554 /// Prevent comparison with IntSet 1555 BoolExpr 1556 operator >=(const LinIntExpr&, IntSet) = delete; 1557 /// Prevent comparison with IntSet 1558 BoolExpr 1559 operator >=(IntSet, const LinIntExpr&) = delete; 1560 1561 /// \brief Return expression for \f$|s|\geq 1 \land \forall i\in s:\ i>x\f$ 1562 GECODE_MINIMODEL_EXPORT BoolExpr 1563 operator >(const SetExpr& s, const LinIntExpr& x); 1564 /// \brief Return expression for \f$|s|\geq 1 \land \forall i\in s:\ x>i\f$ 1565 GECODE_MINIMODEL_EXPORT BoolExpr 1566 operator >(const LinIntExpr& x, const SetExpr& s); 1567 /// Prevent comparison with IntSet 1568 BoolExpr 1569 operator >(const LinIntExpr&, IntSet) = delete; 1570 /// Prevent comparison with IntSet 1571 BoolExpr 1572 operator >(IntSet, const LinIntExpr&) = delete; 1573 #endif 1574 //@} 1575 1576 /** 1577 * \defgroup TaskModelMiniModelPost Posting of expressions and relations 1578 * 1579 * \ingroup TaskModelMiniModel 1580 */ 1581 //@{ 1582 /// Post linear expression and return its value 1583 GECODE_MINIMODEL_EXPORT IntVar 1584 expr(Home home, const LinIntExpr& e, 1585 const IntPropLevels& ipls=IntPropLevels::def); 1586 #ifdef GECODE_HAS_FLOAT_VARS 1587 /// Post float expression and return its value 1588 GECODE_MINIMODEL_EXPORT FloatVar 1589 expr(Home home, const LinFloatExpr& e); 1590 #endif 1591 #ifdef GECODE_HAS_SET_VARS 1592 /// Post set expression and return its value 1593 GECODE_MINIMODEL_EXPORT SetVar 1594 expr(Home home, const SetExpr& e); 1595 #endif 1596 /// Post Boolean expression and return its value 1597 GECODE_MINIMODEL_EXPORT BoolVar 1598 expr(Home home, const BoolExpr& e, 1599 const IntPropLevels& ipls=IntPropLevels::def); 1600 /// Post Boolean relation 1601 GECODE_MINIMODEL_EXPORT void 1602 rel(Home home, const BoolExpr& e, 1603 const IntPropLevels& ipls=IntPropLevels::def); 1604 //@} 1605 1606 } 1607 1608 #include <gecode/minimodel/int-rel.hpp> 1609 #include <gecode/minimodel/float-rel.hpp> 1610 #include <gecode/minimodel/bool-expr.hpp> 1611 #include <gecode/minimodel/set-expr.hpp> 1612 #include <gecode/minimodel/set-rel.hpp> 1613 1614 namespace Gecode { 1615 1616 namespace MiniModel { 1617 class ExpInfo; 1618 } 1619 1620 /** 1621 * \brief Regular expressions over integer values 1622 * 1623 * \ingroup TaskModelMiniModel 1624 */ 1625 class GECODE_MINIMODEL_EXPORT REG { 1626 friend class MiniModel::ExpInfo; 1627 private: 1628 /// Implementation of the actual expression tree 1629 class Exp; 1630 /// The expression tree 1631 Exp* e; 1632 /// Initialize with given expression tree \a 1633 REG(Exp* e); 1634 /// Return string representatinon of expression tree 1635 std::string toString(void) const; 1636 public: 1637 /// Initialize as empty sequence (epsilon) 1638 REG(void); 1639 /// Initialize as single integer \a s 1640 REG(int s); 1641 /** 1642 * \brief Initialize as alternative of integers 1643 * 1644 * Throws an exception of type MiniModel::TooFewArguments if \a x 1645 * is empty. 1646 */ 1647 REG(const IntArgs& x); 1648 1649 /// Initialize from regular expression \a r 1650 REG(const REG& r); 1651 /// Assign to regular expression \a r 1652 const REG& operator =(const REG& r); 1653 1654 /// Return expression for: this expression followed by \a r 1655 REG operator +(const REG& r); 1656 /// This expression is followed by \a r 1657 REG& operator +=(const REG& r); 1658 /// Return expression for: this expression or \a r 1659 REG operator |(const REG& r); 1660 /// This expression or \a r 1661 REG& operator |=(const REG& r); 1662 /// Return expression for: this expression arbitrarily often (Kleene star) 1663 REG operator *(void); 1664 /// Return expression for: this expression at least once 1665 REG operator +(void); 1666 /// Return expression for: this expression at least \a n and at most \a m times 1667 REG operator ()(unsigned int n, unsigned int m); 1668 /// Return expression for: this expression at least \a n times 1669 REG operator ()(unsigned int n); 1670 /// Print expression 1671 template<class Char, class Traits> 1672 std::basic_ostream<Char,Traits>& 1673 print(std::basic_ostream<Char,Traits>& os) const; 1674 /// Return DFA for regular expression 1675 operator DFA(void); 1676 /// Destructor 1677 ~REG(void); 1678 }; 1679 1680 /** \relates Gecode::REG 1681 * Print regular expression \a r 1682 */ 1683 template<class Char, class Traits> 1684 std::basic_ostream<Char,Traits>& 1685 operator <<(std::basic_ostream<Char,Traits>& os, const REG& r); 1686 1687 } 1688 1689 #include <gecode/minimodel/reg.hpp> 1690 1691 namespace Gecode { 1692 1693 /** 1694 * \defgroup TaskModelMiniModelArith Arithmetic functions 1695 * 1696 * \ingroup TaskModelMiniModel 1697 */ 1698 //@{ 1699 /// \brief Return expression for \f$x\cdot y\f$ 1700 GECODE_MINIMODEL_EXPORT LinIntExpr 1701 operator *(const LinIntExpr& x, const LinIntExpr& y); 1702 /// \brief Return expression for \f$x\ \mathrm{div}\ y\f$ 1703 GECODE_MINIMODEL_EXPORT LinIntExpr 1704 operator /(const LinIntExpr& x, const LinIntExpr& y); 1705 /// \brief Return expression for \f$x\ \mathrm{mod}\ y\f$ 1706 GECODE_MINIMODEL_EXPORT LinIntExpr 1707 operator %(const LinIntExpr& x, const LinIntExpr& y); 1708 /// \brief Return expression for \f$|e|\f$ 1709 GECODE_MINIMODEL_EXPORT LinIntExpr 1710 abs(const LinIntExpr& e); 1711 /// \brief Return expression for \f$\min(x,y)\f$ 1712 GECODE_MINIMODEL_EXPORT LinIntExpr 1713 min(const LinIntExpr& x, const LinIntExpr& y); 1714 /// \brief Return expression for \f$\min(x)\f$ 1715 GECODE_MINIMODEL_EXPORT LinIntExpr 1716 min(const IntVarArgs& x); 1717 /// \brief Return expression for \f$\max(x,y)\f$ 1718 GECODE_MINIMODEL_EXPORT LinIntExpr 1719 max(const LinIntExpr& x, const LinIntExpr& y); 1720 /// \brief Return expression for \f$\max(x)\f$ 1721 GECODE_MINIMODEL_EXPORT LinIntExpr 1722 max(const IntVarArgs& x); 1723 /// \brief Return expression for \f$x^2\f$ 1724 GECODE_MINIMODEL_EXPORT LinIntExpr 1725 sqr(const LinIntExpr& x); 1726 /// \brief Return expression for \f$\lfloor\sqrt{x}\rfloor\f$ 1727 GECODE_MINIMODEL_EXPORT LinIntExpr 1728 sqrt(const LinIntExpr& x); 1729 /// \brief Return expression for \f$x^n\f$ 1730 GECODE_MINIMODEL_EXPORT LinIntExpr 1731 pow(const LinIntExpr& x, int n); 1732 /// \brief Return expression for \f$\lfloor\sqrt[n]{x}\rfloor\f$ 1733 GECODE_MINIMODEL_EXPORT LinIntExpr 1734 nroot(const LinIntExpr& x, int n); 1735 /// \brief Return expression for \f$x[y]\f$ 1736 GECODE_MINIMODEL_EXPORT LinIntExpr 1737 element(const IntVarArgs& x, const LinIntExpr& y); 1738 /// \brief Return expression for \f$x[y]\f$ 1739 GECODE_MINIMODEL_EXPORT BoolExpr 1740 element(const BoolVarArgs& x, const LinIntExpr& y); 1741 /// \brief Return expression for \f$x[y]\f$ 1742 GECODE_MINIMODEL_EXPORT LinIntExpr 1743 element(const IntArgs& x, const LinIntExpr& y); 1744 /// \brief Return expression for if-then-else \f$b?x:y\f$ 1745 GECODE_MINIMODEL_EXPORT LinIntExpr 1746 ite(const BoolExpr& b, const LinIntExpr& x, const LinIntExpr& y); 1747 //@} 1748 1749 #ifdef GECODE_HAS_FLOAT_VARS 1750 /// \brief Return expression as product of float variables 1751 GECODE_MINIMODEL_EXPORT LinFloatExpr 1752 operator *(const FloatVar&, const FloatVar&); 1753 /// \brief Return expression as product of float variable and linear float expression 1754 GECODE_MINIMODEL_EXPORT LinFloatExpr 1755 operator *(const FloatVar&, const LinFloatExpr&); 1756 /// \brief Return expression as product of linear float expression and float variable 1757 GECODE_MINIMODEL_EXPORT LinFloatExpr 1758 operator *(const LinFloatExpr&, const FloatVar&); 1759 /// \brief Return expression for \f$|e|\f$ 1760 GECODE_MINIMODEL_EXPORT LinFloatExpr 1761 abs(const LinFloatExpr& e); 1762 /// \brief Return expression for \f$\min(x,y)\f$ 1763 GECODE_MINIMODEL_EXPORT LinFloatExpr 1764 min(const LinFloatExpr& x, const LinFloatExpr& y); 1765 /// \brief Return expression for \f$\min(x)\f$ 1766 GECODE_MINIMODEL_EXPORT LinFloatExpr 1767 min(const FloatVarArgs& x); 1768 /// \brief Return expression for \f$\max(x,y)\f$ 1769 GECODE_MINIMODEL_EXPORT LinFloatExpr 1770 max(const LinFloatExpr& x, const LinFloatExpr& y); 1771 /// \brief Return expression for \f$\max(x)\f$ 1772 GECODE_MINIMODEL_EXPORT LinFloatExpr 1773 max(const FloatVarArgs& x); 1774 /// \brief Return expression for \f$x\cdot y\f$ 1775 GECODE_MINIMODEL_EXPORT LinFloatExpr 1776 operator *(const LinFloatExpr& x, const LinFloatExpr& y); 1777 /// \brief Return expression for \f$x/y\f$ 1778 GECODE_MINIMODEL_EXPORT LinFloatExpr 1779 operator /(const LinFloatExpr& x, const LinFloatExpr& y); 1780 /// \brief Return expression for \f$x^2\f$ 1781 GECODE_MINIMODEL_EXPORT LinFloatExpr 1782 sqr(const LinFloatExpr& x); 1783 /// \brief Return expression for \f$\sqrt{x}\f$ 1784 GECODE_MINIMODEL_EXPORT LinFloatExpr 1785 sqrt(const LinFloatExpr& x); 1786 /// \brief Return expression for \f$x^n\f$ 1787 GECODE_MINIMODEL_EXPORT LinFloatExpr 1788 pow(const LinFloatExpr& x, int n); 1789 /// \brief Return expression for \f$x^{1/n}\f$ 1790 GECODE_MINIMODEL_EXPORT LinFloatExpr 1791 nroot(const LinFloatExpr& x, int n); 1792 //@} 1793 1794 #ifdef GECODE_HAS_MPFR 1795 /** 1796 * \defgroup TaskModelMiniModelTrans Transcendental functions 1797 * 1798 * \ingroup TaskModelMiniModel 1799 */ 1800 //@{ 1801 /// \brief Return expression for \f$ \mathrm{exp}(x)\f$ 1802 GECODE_MINIMODEL_EXPORT LinFloatExpr 1803 exp(const LinFloatExpr& x); 1804 /// \brief Return expression for \f$ \mathrm{log}(x)\f$ 1805 GECODE_MINIMODEL_EXPORT LinFloatExpr 1806 log(const LinFloatExpr& x); 1807 //@} 1808 1809 /** 1810 * \defgroup TaskModelMiniModelTrigo Trigonometric functions 1811 * 1812 * \ingroup TaskModelMiniModel 1813 */ 1814 //@{ 1815 /// \brief Return expression for \f$ \mathrm{asin}(x)\f$ 1816 GECODE_MINIMODEL_EXPORT LinFloatExpr 1817 asin(const LinFloatExpr& x); 1818 /// \brief Return expression for \f$ \mathrm{sin}(x)\f$ 1819 GECODE_MINIMODEL_EXPORT LinFloatExpr 1820 sin(const LinFloatExpr& x); 1821 /// \brief Return expression for \f$ \mathrm{acos}(x)\f$ 1822 GECODE_MINIMODEL_EXPORT LinFloatExpr 1823 acos(const LinFloatExpr& x); 1824 /// \brief Return expression for \f$ \mathrm{cos}(x)\f$ 1825 GECODE_MINIMODEL_EXPORT LinFloatExpr 1826 cos(const LinFloatExpr& x); 1827 /// \brief Return expression for \f$ \mathrm{atan}(x)\f$ 1828 GECODE_MINIMODEL_EXPORT LinFloatExpr 1829 atan(const LinFloatExpr& x); 1830 /// \brief Return expression for \f$ \mathrm{tan}(x)\f$ 1831 GECODE_MINIMODEL_EXPORT LinFloatExpr 1832 tan(const LinFloatExpr& x); 1833 //@} 1834 #endif 1835 #endif 1836 1837 } 1838 1839 namespace Gecode { 1840 1841 /** 1842 * \defgroup TaskModelMiniModelChannel Channel functions 1843 * 1844 * \ingroup TaskModelMiniModel 1845 */ 1846 //@{ 1847 /// Return Boolean variable equal to \f$x\f$ 1848 BoolVar 1849 channel(Home home, IntVar x, IntPropLevel ipl=IPL_DEF); 1850 /// Return integer variable equal to \f$b\f$ 1851 IntVar 1852 channel(Home home, BoolVar b, IntPropLevel ipl=IPL_DEF); 1853 #ifdef GECODE_HAS_FLOAT_VARS 1854 /// Return integer variable equal to \f$f\f$ 1855 IntVar 1856 channel(Home home, FloatVar f); 1857 #endif 1858 #ifdef GECODE_HAS_SET_VARS 1859 /// Return set variable equal to \f$\{x_0,\dots,x_{n-1}\}\f$ 1860 SetVar 1861 channel(Home home, const IntVarArgs& x, IntPropLevel ipl=IPL_DEF); 1862 #endif 1863 //@} 1864 1865 } 1866 1867 #include <gecode/minimodel/channel.hpp> 1868 1869 namespace Gecode { 1870 1871 /** 1872 * \defgroup TaskModelMiniModelIntAlias Aliases for integer constraints 1873 * 1874 * Contains definitions of common constraints which have different 1875 * names in Gecode. 1876 * 1877 * \ingroup TaskModelMiniModel 1878 */ 1879 1880 //@{ 1881 /** \brief Post constraint \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=n\}\leq m\f$ 1882 * 1883 * Supports domain consistent propagation only. 1884 */ 1885 void 1886 atmost(Home home, const IntVarArgs& x, int n, int m, 1887 IntPropLevel ipl=IPL_DEF); 1888 /** \brief Post constraint \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\leq m\f$ 1889 * 1890 * Supports domain consistent propagation only. 1891 */ 1892 void 1893 atmost(Home home, const IntVarArgs& x, IntVar y, int m, 1894 IntPropLevel ipl=IPL_DEF); 1895 /** \brief Post constraint \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y_i\}\leq m\f$ 1896 * 1897 * Supports domain consistent propagation only. 1898 * 1899 * Throws an exception of type Int::ArgumentSizeMismatch, if 1900 * \a x and \a y are of different size. 1901 */ 1902 void 1903 atmost(Home home, const IntVarArgs& x, const IntArgs& y, int m, 1904 IntPropLevel ipl=IPL_DEF); 1905 /** \brief Post constraint \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=n\}\leq z\f$ 1906 * 1907 * Supports domain consistent propagation only. 1908 */ 1909 void 1910 atmost(Home home, const IntVarArgs& x, int n, IntVar z, 1911 IntPropLevel ipl=IPL_DEF); 1912 /** \brief Post constraint \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\leq z\f$ 1913 * 1914 * Supports domain consistent propagation only. 1915 */ 1916 void 1917 atmost(Home home, const IntVarArgs& x, IntVar y, IntVar z, 1918 IntPropLevel ipl=IPL_DEF); 1919 /** \brief Post constraint \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y_i\}\leq z\f$ 1920 * 1921 * Supports domain consistent propagation only. 1922 * 1923 * Throws an exception of type Int::ArgumentSizeMismatch, if 1924 * \a x and \a y are of different size. 1925 */ 1926 void 1927 atmost(Home home, const IntVarArgs& x, const IntArgs& y, IntVar z, 1928 IntPropLevel ipl=IPL_DEF); 1929 1930 /** \brief Post constraint \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=n\}\geq m\f$ 1931 * 1932 * Supports domain consistent propagation only. 1933 */ 1934 void 1935 atleast(Home home, const IntVarArgs& x, int n, int m, 1936 IntPropLevel ipl=IPL_DEF); 1937 /** \brief Post constraint \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\geq m\f$ 1938 * 1939 * Supports domain consistent propagation only. 1940 */ 1941 void 1942 atleast(Home home, const IntVarArgs& x, IntVar y, int m, 1943 IntPropLevel ipl=IPL_DEF); 1944 /** \brief Post constraint \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y_i\}\geq m\f$ 1945 * 1946 * Supports domain consistent propagation only. 1947 * 1948 * Throws an exception of type Int::ArgumentSizeMismatch, if 1949 * \a x and \a y are of different size. 1950 */ 1951 void 1952 atleast(Home home, const IntVarArgs& x, const IntArgs& y, int m, 1953 IntPropLevel ipl=IPL_DEF); 1954 /** \brief Post constraint \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=n\}\geq z\f$ 1955 * 1956 * Supports domain consistent propagation only. 1957 */ 1958 void 1959 atleast(Home home, const IntVarArgs& x, int n, IntVar z, 1960 IntPropLevel ipl=IPL_DEF); 1961 /** \brief Post constraint \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\geq z\f$ 1962 * 1963 * Supports domain consistent propagation only. 1964 */ 1965 void 1966 atleast(Home home, const IntVarArgs& x, IntVar y, IntVar z, 1967 IntPropLevel ipl=IPL_DEF); 1968 /** \brief Post constraint \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y_i\}\geq z\f$ 1969 * 1970 * Supports domain consistent propagation only. 1971 * 1972 * Throws an exception of type Int::ArgumentSizeMismatch, if 1973 * \a x and \a y are of different size. 1974 */ 1975 void 1976 atleast(Home home, const IntVarArgs& x, const IntArgs& y, IntVar z, 1977 IntPropLevel ipl=IPL_DEF); 1978 1979 /** \brief Post constraint \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=n\}=m\f$ 1980 * 1981 * Supports domain consistent propagation only. 1982 */ 1983 void 1984 exactly(Home home, const IntVarArgs& x, int n, int m, 1985 IntPropLevel ipl=IPL_DEF); 1986 /** \brief Post constraint \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}=m\f$ 1987 * 1988 * Supports domain consistent propagation only. 1989 */ 1990 void 1991 exactly(Home home, const IntVarArgs& x, IntVar y, int m, 1992 IntPropLevel ipl=IPL_DEF); 1993 /** \brief Post constraint \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y_i\}=m\f$ 1994 * 1995 * Supports domain consistent propagation only. 1996 * 1997 * Throws an exception of type Int::ArgumentSizeMismatch, if 1998 * \a x and \a y are of different size. 1999 */ 2000 void 2001 exactly(Home home, const IntVarArgs& x, const IntArgs& y, int m, 2002 IntPropLevel ipl=IPL_DEF); 2003 /** \brief Post constraint \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=n\}=z\f$ 2004 * 2005 * Supports domain consistent propagation only. 2006 */ 2007 void 2008 exactly(Home home, const IntVarArgs& x, int n, IntVar z, 2009 IntPropLevel ipl=IPL_DEF); 2010 /** \brief Post constraint \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}=z\f$ 2011 * 2012 * Supports domain consistent propagation only. 2013 */ 2014 void 2015 exactly(Home home, const IntVarArgs& x, IntVar y, IntVar z, 2016 IntPropLevel ipl=IPL_DEF); 2017 /** \brief Post constraint \f$\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y_i\}=z\f$ 2018 * 2019 * Supports domain consistent propagation only. 2020 * 2021 * Throws an exception of type Int::ArgumentSizeMismatch, if 2022 * \a x and \a y are of different size. 2023 */ 2024 void 2025 exactly(Home home, const IntVarArgs& x, const IntArgs& y, IntVar z, 2026 IntPropLevel ipl=IPL_DEF); 2027 2028 /** \brief Post lexical order between \a x and \a y. 2029 */ 2030 void 2031 lex(Home home, const IntVarArgs& x, IntRelType r, const IntVarArgs& y, 2032 IntPropLevel ipl=IPL_DEF); 2033 /** \brief Post lexical order between \a x and \a y. 2034 */ 2035 void 2036 lex(Home home, const BoolVarArgs& x, IntRelType r, const BoolVarArgs& y, 2037 IntPropLevel ipl=IPL_DEF); 2038 2039 /** \brief Post constraint \f$\{x_0,\dots,x_{n-1}\}=y\f$ 2040 */ 2041 void 2042 values(Home home, const IntVarArgs& x, IntSet y, 2043 IntPropLevel ipl=IPL_DEF); 2044 //@} 2045 2046 #ifdef GECODE_HAS_SET_VARS 2047 /** 2048 * \defgroup TaskModelMiniModelSetAlias Aliases for set constraints 2049 * 2050 * Contains definitions of common constraints which have different 2051 * names in Gecode. 2052 * 2053 * \ingroup TaskModelMiniModel 2054 */ 2055 2056 //@{ 2057 /** \brief Post constraint \f$\{x_0,\dots,x_{n-1}\}=y\f$ 2058 * 2059 * In addition to constraining \a y to the union of the \a x, this 2060 * also posts an nvalue constraint for additional cardinality propagation. 2061 */ 2062 void 2063 channel(Home home, const IntVarArgs& x, SetVar y); 2064 2065 /** \brief Post constraint \f$\bigcup_{i\in y}\{x_i\}=z\f$ 2066 */ 2067 void 2068 range(Home home, const IntVarArgs& x, SetVar y, SetVar z); 2069 2070 /** \brief Post constraint \f$\bigcup_{i\in z}\{j\ |\ x_j=i\}=z\f$ 2071 * 2072 * Note that this creates one temporary set variable for each element 2073 * in the upper bound of \a z, so make sure that the bound is tight. 2074 */ 2075 void 2076 roots(Home home, const IntVarArgs& x, SetVar y, SetVar z); 2077 //@} 2078 2079 #endif 2080 2081 } 2082 2083 #include <gecode/minimodel/aliases.hpp> 2084 2085 namespace Gecode { 2086 2087 template<class> class Matrix; 2088 2089 /** \brief A slice of a matrix. 2090 * 2091 * This class represents a slice of the matrix. It is used to get 2092 * context-dependent behaviour. The slice will be automatically 2093 * converted to an ArgsType Args-array or to a Matrix<ArgsType> 2094 * depending on the context where it is used. 2095 */ 2096 template<class A> 2097 class Slice { 2098 public: 2099 /// The type of the Args-array type for ValueType values 2100 typedef typename ArrayTraits<A>::ArgsType ArgsType; 2101 private: 2102 ArgsType _r; ///< The elements of the slice 2103 int _fc, ///< From column 2104 _tc, ///< To column 2105 _fr, ///< From row 2106 _tr; ///< To row 2107 public: 2108 /// Construct slice 2109 Slice(const Matrix<A>& a, int fc, int tc, int fr, int tr); 2110 /** \brief Reverses the contents of the slice, and returns a 2111 * reference to it. 2112 */ 2113 Slice& reverse(void); 2114 /// Cast to array type 2115 operator ArgsType(void); 2116 /// Cast to matrix type 2117 operator Matrix<ArgsType>(void); 2118 2119 /// Cast to array type 2120 operator const ArgsType(void) const; 2121 /// Cast to matrix type 2122 operator const Matrix<ArgsType>(void) const; 2123 }; 2124 2125 /// Concatenate \a x and \a y 2126 template<class A> 2127 typename Slice<A>::ArgsType 2128 operator+(const Slice<A>& x, const Slice<A>& y); 2129 2130 /// Concatenate \a x and \a y 2131 template<class A> 2132 typename Slice<A>::ArgsType 2133 operator+(const Slice<A>& x, const typename ArrayTraits<A>::ArgsType& y); 2134 2135 /// Concatenate \a x and \a y 2136 template<class A> 2137 typename Slice<A>::ArgsType 2138 operator+(const typename ArrayTraits<A>::ArgsType& x, const Slice<A>& y); 2139 2140 /// Concatenate \a x and \a y 2141 template<class A> 2142 typename Slice<A>::ArgsType 2143 operator+(const Slice<A>& x, const typename ArrayTraits<A>::ValueType& y); 2144 2145 /// Concatenate \a x and \a y 2146 template<class A> 2147 typename Slice<A>::ArgsType 2148 operator+(const typename ArrayTraits<A>::ValueType& x, const Slice<A>& y); 2149 2150 /** \brief Matrix-interface for arrays 2151 * 2152 * This class allows for wrapping some array and accessing it as a 2153 * matrix. 2154 * 2155 * \note This is a light-weight wrapper, and is not intended for 2156 * storing variables directly instead of in an array. 2157 * 2158 * \ingroup TaskModelMiniModel 2159 */ 2160 template<class A> 2161 class Matrix { 2162 public: 2163 /// The type of elements of this array 2164 typedef typename ArrayTraits<A>::ValueType ValueType; 2165 /// The type of the Args-array type for ValueType values 2166 typedef typename ArrayTraits<A>::ArgsType ArgsType; 2167 2168 private: 2169 /// The type of storage for this array 2170 typedef typename ArrayTraits<A>::StorageType StorageType; 2171 StorageType _a; ///< The array wrapped 2172 int _w; ///< The width of the matrix 2173 int _h; ///< The height of the matrix 2174 2175 public: 2176 /** \brief Basic constructor 2177 * 2178 * Constructs a Matrix from the array \a a, using \a w and \a h as 2179 * the width and height of the matrix. 2180 * 2181 * The elements in the wrapped array \a a are accessed in 2182 * row-major order. 2183 * 2184 * \exception MiniModel::ArgumentSizeMismatch Raised if the 2185 * parameters \a w and \a h doesn't match the size 2186 * of the array \a a. 2187 */ 2188 Matrix(A a, int w, int h); 2189 2190 /** \brief Basic constructor 2191 * 2192 * Constructs a square Matrix from the array \a a, using \a n as 2193 * the length of the sides. 2194 * 2195 * The elements in the wrapped array \a a are accessed in 2196 * row-major order. 2197 * 2198 * \exception MiniModel::ArgumentSizeMismatch Raised if the 2199 * parameter \a n doesn't match the size 2200 * of the array \a a. 2201 */ 2202 Matrix(A a, int n); 2203 2204 /// Return the width of the matrix 2205 int width(void) const; 2206 /// Return the height of the matrix 2207 int height(void) const; 2208 /// Return an Args-array of the contents of the matrix 2209 ArgsType const get_array(void) const; 2210 2211 /** \brief Access element (\a c, \a r) of the matrix 2212 * 2213 * \exception MiniModel::ArgumentOutOfRange Raised if \a c or \a r 2214 * are out of range. 2215 */ 2216 ValueType& operator ()(int c, int r); 2217 2218 /** \brief Access element (\a c, \a r) of the matrix 2219 * 2220 * \exception MiniModel::ArgumentOutOfRange Raised if \a c or \a r 2221 * are out of range. 2222 */ 2223 const ValueType& operator ()(int c, int r) const; 2224 2225 /** \brief Access slice of the matrix 2226 * 2227 * This function allows accessing a slice of the matrix, located at 2228 * columns \f$[fc,tc)\f$ and rows \f$[fr,tr)\f$. The result of this 2229 * function is an object that can be converted into either a 2230 * Matrix<ArgsType> or into ArgsType. 2231 * 2232 * For further information, see Slice. 2233 */ 2234 Slice<A> slice(int fc, int tc, int fr, int tr) const; 2235 2236 /// Access row \a r. 2237 Slice<A> row(int r) const; 2238 2239 /// Access column \a c. 2240 Slice<A> col(int c) const; 2241 }; 2242 2243 /** \relates Gecode::Matrix 2244 * Print matrix \a m 2245 */ 2246 template<class Char, class Traits, class A> 2247 std::basic_ostream<Char,Traits>& 2248 operator <<(std::basic_ostream<Char,Traits>& os, const Matrix<A>& m); 2249 2250 /** \relates Gecode::Matrix 2251 * Print slice \a s 2252 */ 2253 template<class Char, class Traits, class A> 2254 std::basic_ostream<Char,Traits>& 2255 operator <<(std::basic_ostream<Char,Traits>& os, const Slice<A>& s); 2256 2257 /** \brief Element constraint for matrix 2258 * 2259 * Here, \a x and \a y are the coordinates and \a z is the value 2260 * at position \a m(x,y). 2261 * \relates Gecode::Matrix 2262 */ 2263 void element(Home home, const Matrix<IntArgs>& m, IntVar x, IntVar y, 2264 IntVar z, IntPropLevel ipl=IPL_DEF); 2265 /** \brief Element constraint for matrix 2266 * 2267 * Here, \a x and \a y are the coordinates and \a z is the value 2268 * at position \a m(x,y). 2269 * \relates Gecode::Matrix 2270 */ 2271 void element(Home home, const Matrix<IntArgs>& m, IntVar x, IntVar y, 2272 BoolVar z, IntPropLevel ipl=IPL_DEF); 2273 /** \brief Element constraint for matrix 2274 * 2275 * Here, \a x and \a y are the coordinates and \a z is the value 2276 * at position \a m(x,y). 2277 * \relates Gecode::Matrix 2278 */ 2279 void element(Home home, const Matrix<IntVarArgs>& m, IntVar x, IntVar y, 2280 IntVar z, IntPropLevel ipl=IPL_DEF); 2281 /** \brief Element constraint for matrix 2282 * 2283 * Here, \a x and \a y are the coordinates and \a z is the value 2284 * at position \a m(x,y). 2285 * \relates Gecode::Matrix 2286 */ 2287 void element(Home home, const Matrix<BoolVarArgs>& m, IntVar x, IntVar y, 2288 BoolVar z, IntPropLevel ipln=IPL_DEF); 2289 #ifdef GECODE_HAS_SET_VARS 2290 /** \brief Element constraint for matrix 2291 * 2292 * Here, \a x and \a y are the coordinates and \a z is the value 2293 * at position \a m(x,y). 2294 * \relates Gecode::Matrix 2295 */ 2296 void element(Home home, const Matrix<IntSetArgs>& m, IntVar x, IntVar y, 2297 SetVar z); 2298 /** \brief Element constraint for matrix 2299 * 2300 * Here, \a x and \a y are the coordinates and \a z is the value 2301 * at position \a m(x,y). 2302 * \relates Gecode::Matrix 2303 */ 2304 void element(Home home, const Matrix<SetVarArgs>& m, IntVar x, IntVar y, 2305 SetVar z); 2306 #endif 2307 2308 /** \brief Interchangeable rows symmetry specification. 2309 * \relates Gecode::Matrix 2310 */ 2311 template<class A> 2312 SymmetryHandle rows_interchange(const Matrix<A>& m); 2313 /** \brief Interchangeable columns symmetry specification. 2314 * \relates Gecode::Matrix 2315 */ 2316 template<class A> 2317 SymmetryHandle columns_interchange(const Matrix<A>& m); 2318 /** \brief Reflect rows symmetry specification. 2319 * \relates Gecode::Matrix 2320 */ 2321 template<class A> 2322 SymmetryHandle rows_reflect(const Matrix<A>& m); 2323 /** \brief Reflect columns symmetry specification. 2324 * \relates Gecode::Matrix 2325 */ 2326 template<class A> 2327 SymmetryHandle columns_reflect(const Matrix<A>& m); 2328 /** \brief Reflect around main diagonal symmetry specification. 2329 * 2330 * The matrix \m must be square. 2331 * \relates Gecode::Matrix 2332 */ 2333 template<class A> 2334 SymmetryHandle diagonal_reflect(const Matrix<A>& m); 2335 } 2336 2337 #include <gecode/minimodel/matrix.hpp> 2338 #include <gecode/minimodel/ldsb.hpp> 2339 2340 /** 2341 * \addtogroup TaskModelMiniModelLin 2342 * @{ 2343 */ 2344 namespace Gecode { 2345 2346 /// Construct linear expression as sum of \ref IntArgs \ref Slice elements 2347 GECODE_MINIMODEL_EXPORT LinIntExpr 2348 sum(const Slice<IntArgs>& slice); 2349 /// Construct linear expression as sum of \ref IntArgs \ref Matrix elements 2350 GECODE_MINIMODEL_EXPORT LinIntExpr 2351 sum(const Matrix<IntArgs>& matrix); 2352 2353 } 2354 /** @}*/ 2355 2356 namespace Gecode { 2357 2358 /** 2359 * \defgroup TaskModelMiniModelOptimize Support for cost-based optimization 2360 * 2361 * Provides for minimizing or maximizing the cost value as defined by 2362 * a cost-member function of a space. 2363 * 2364 * \ingroup TaskModelMiniModel 2365 */ 2366 2367 /** 2368 * \brief Class for minimizing integer cost 2369 * \ingroup TaskModelMiniModelOptimize 2370 */ 2371 class GECODE_VTABLE_EXPORT IntMinimizeSpace : public Space { 2372 public: 2373 /// Default constructor 2374 IntMinimizeSpace(void); 2375 /// Constructor for cloning 2376 IntMinimizeSpace(IntMinimizeSpace& s); 2377 /// Member function constraining according to decreasing cost 2378 GECODE_MINIMODEL_EXPORT 2379 virtual void constrain(const Space& best); 2380 /// Return variable with current cost 2381 virtual IntVar cost(void) const = 0; 2382 }; 2383 2384 /** 2385 * \brief Class for maximizing integer cost 2386 * \ingroup TaskModelMiniModelOptimize 2387 */ 2388 class GECODE_VTABLE_EXPORT IntMaximizeSpace : public Space { 2389 public: 2390 /// Default constructor 2391 IntMaximizeSpace(void); 2392 /// Constructor for cloning 2393 IntMaximizeSpace(IntMaximizeSpace& s); 2394 /// Member function constraining according to increasing cost 2395 GECODE_MINIMODEL_EXPORT 2396 virtual void constrain(const Space& best); 2397 /// Return variable with current cost 2398 virtual IntVar cost(void) const = 0; 2399 }; 2400 2401 /** 2402 * \brief Class for lexicographically minimizing integer costs 2403 * \ingroup TaskModelMiniModelOptimize 2404 */ 2405 class GECODE_VTABLE_EXPORT IntLexMinimizeSpace : public Space { 2406 public: 2407 /// Default constructor 2408 IntLexMinimizeSpace(void); 2409 /// Constructor for cloning 2410 IntLexMinimizeSpace(IntLexMinimizeSpace& s); 2411 /// Member function constraining according to decreasing costs 2412 GECODE_MINIMODEL_EXPORT 2413 virtual void constrain(const Space& best); 2414 /// Return variables with current costs 2415 virtual IntVarArgs cost(void) const = 0; 2416 }; 2417 2418 /** 2419 * \brief Class for lexicographically maximizing integer costs 2420 * \ingroup TaskModelMiniModelOptimize 2421 */ 2422 class GECODE_VTABLE_EXPORT IntLexMaximizeSpace : public Space { 2423 public: 2424 /// Default constructor 2425 IntLexMaximizeSpace(void); 2426 /// Constructor for cloning 2427 IntLexMaximizeSpace(IntLexMaximizeSpace& s); 2428 /// Member function constraining according to increasing costs 2429 GECODE_MINIMODEL_EXPORT 2430 virtual void constrain(const Space& best); 2431 /// Return variables with current costs 2432 virtual IntVarArgs cost(void) const = 0; 2433 }; 2434 2435 #ifdef GECODE_HAS_FLOAT_VARS 2436 2437 /** 2438 * \brief Class for minimizing float cost 2439 * 2440 * The class supports using a step value \a step that will make sure 2441 * that better solutions must be better by at least the value of 2442 * \a step. 2443 * 2444 * \ingroup TaskModelMiniModelOptimize 2445 */ 2446 class GECODE_VTABLE_EXPORT FloatMinimizeSpace : public Space { 2447 protected: 2448 /// Step by which a next solution has to have lower cost 2449 FloatNum step; 2450 public: 2451 /// Constructor with step \a s 2452 FloatMinimizeSpace(FloatNum s=0.0); 2453 /// Constructor for cloning 2454 FloatMinimizeSpace(FloatMinimizeSpace& s); 2455 /// Member function constraining according to cost 2456 GECODE_MINIMODEL_EXPORT 2457 virtual void constrain(const Space& best); 2458 /// Return variable with current cost 2459 virtual FloatVar cost(void) const = 0; 2460 }; 2461 2462 /** 2463 * \brief Class for maximizing float cost 2464 * 2465 * The class supports using a step value \a step that will make sure 2466 * that better solutions must be better by at least the value of 2467 * \a step. 2468 * 2469 * \ingroup TaskModelMiniModelOptimize 2470 */ 2471 class GECODE_VTABLE_EXPORT FloatMaximizeSpace : public Space { 2472 protected: 2473 /// Step by which a next solution has to have lower cost 2474 FloatNum step; 2475 public: 2476 /// Constructor with step \a s 2477 FloatMaximizeSpace(FloatNum s=0.0); 2478 /// Constructor for cloning 2479 FloatMaximizeSpace(FloatMaximizeSpace& s); 2480 /// Member function constraining according to cost 2481 GECODE_MINIMODEL_EXPORT 2482 virtual void constrain(const Space& best); 2483 /// Return variable with current cost 2484 virtual FloatVar cost(void) const = 0; 2485 }; 2486 2487 #endif 2488 2489 } 2490 2491 #include <gecode/minimodel/optimize.hpp> 2492 2493 #endif 2494 2495 // IFDEF: GECODE_HAS_INT_VARS 2496 // STATISTICS: minimodel-any 2497 2498