this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 * Guido Tack <tack@gecode.org>
6 * Tias Guns <tias.guns@cs.kuleuven.be>
7 *
8 * Copyright:
9 * Christian Schulte, 2002
10 * Guido Tack, 2004
11 * Tias Guns, 2009
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.org
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining
18 * a copy of this software and associated documentation files (the
19 * "Software"), to deal in the Software without restriction, including
20 * without limitation the rights to use, copy, modify, merge, publish,
21 * distribute, sublicense, and/or sell copies of the Software, and to
22 * permit persons to whom the Software is furnished to do so, subject to
23 * the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be
26 * included in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 *
36 */
37
38#ifndef GECODE_INT_LINEAR_HH
39#define GECODE_INT_LINEAR_HH
40
41#include <gecode/int.hh>
42
43/**
44 * \namespace Gecode::Int::Linear
45 * \brief %Linear propagators
46 */
47
48namespace Gecode { namespace Int { namespace Linear {
49
50 /*
51 * Binary propagators
52 *
53 */
54
55 /**
56 * \brief Base-class for binary linear propagators
57 *
58 * The type \a Val can be either \c long long int or \c int, defining the
59 * numerical precision during propagation. The types \a A and \a B
60 * give the types of the views.
61 *
62 * The propagation condition \a pc refers to both views.
63 */
64 template<class Val, class A, class B, PropCond pc>
65 class LinBin : public Propagator {
66 protected:
67 /// View of type \a A
68 A x0;
69 /// View of type \a B
70 B x1;
71 /// Value of type \a Val
72 Val c;
73 /// Constructor for cloning \a p
74 LinBin(Space& home, LinBin& p);
75 /// Constructor for rewriting \a p during cloning
76 LinBin(Space& home, Propagator& p, A x0, B x1, Val c);
77 /// Constructor for creation
78 LinBin(Home home, A x0, B x1, Val c);
79 public:
80 /// Cost function (defined as low binary)
81 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
82 /// Schedule function
83 virtual void reschedule(Space& home);
84 /// Delete propagator and return its size
85 virtual size_t dispose(Space& home);
86 };
87
88 /**
89 * \brief Base-class for reified binary linear propagators
90 *
91 * The type \a Val can be either \c long long int or \c int, defining the
92 * numerical precision during propagation. The types \a A and \a B
93 * give the types of the views.
94 *
95 * The propagation condition \a pc refers to both views.
96 */
97 template<class Val, class A, class B, PropCond pc, class Ctrl>
98 class ReLinBin : public Propagator {
99 protected:
100 /// View of type \a A
101 A x0;
102 /// View of type \a B
103 B x1;
104 /// Value of type \a Val
105 Val c;
106 /// Control view for reification
107 Ctrl b;
108 /// Constructor for cloning \a p
109 ReLinBin(Space& home, ReLinBin& p);
110 /// Constructor for creation
111 ReLinBin(Home home, A x0, B x1, Val c, Ctrl b);
112 public:
113 /// Cost function (defined as low binary)
114 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
115 /// Schedule function
116 virtual void reschedule(Space& home);
117 /// Delete propagator and return its size
118 virtual size_t dispose(Space& home);
119 };
120
121 /**
122 * \brief %Propagator for bounds consistent binary linear equality
123 *
124 * The type \a Val can be either \c long long int or \c int, defining the
125 * numerical precision during propagation. The types \a A and \a B
126 * give the types of the views.
127 *
128 * The propagation condition \a pc refers to both views.
129 *
130 * Requires \code #include <gecode/int/linear.hh> \endcode
131 * \ingroup FuncIntProp
132 */
133 template<class Val, class A, class B>
134 class EqBin : public LinBin<Val,A,B,PC_INT_BND> {
135 protected:
136 using LinBin<Val,A,B,PC_INT_BND>::x0;
137 using LinBin<Val,A,B,PC_INT_BND>::x1;
138 using LinBin<Val,A,B,PC_INT_BND>::c;
139
140 /// Constructor for cloning \a p
141 EqBin(Space& home, EqBin& p);
142 /// Constructor for creation
143 EqBin(Home home, A x0, B x1, Val c);
144 public:
145 /// Constructor for rewriting \a p during cloning
146 EqBin(Space& home, Propagator& p, A x0, B x1, Val c);
147 /// Create copy during cloning
148 virtual Actor* copy(Space& home);
149 /// Perform propagation
150 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
151 /// Post propagator for \f$x_0+x_1 = c\f$
152 static ExecStatus post(Home home, A x0, B x1, Val c);
153 };
154
155 /**
156 * \brief %Propagator for reified bounds consistent binary linear equality
157 *
158 * The type \a Val can be either \c long long int or \c int, defining the
159 * numerical precision during propagation. The types \a A and \a B
160 * give the types of the views.
161 *
162 * The propagation condition \a pc refers to both views.
163 *
164 * Requires \code #include <gecode/int/linear.hh> \endcode
165 * \ingroup FuncIntProp
166 */
167 template<class Val, class A, class B, class Ctrl, ReifyMode rm>
168 class ReEqBin : public ReLinBin<Val,A,B,PC_INT_BND,Ctrl> {
169 protected:
170 using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::x0;
171 using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::x1;
172 using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::c;
173 using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::b;
174
175 /// Constructor for cloning \a p
176 ReEqBin(Space& home, ReEqBin& p);
177 /// Constructor for creation
178 ReEqBin(Home home,A,B,Val,Ctrl);
179 public:
180 /// Create copy during cloning
181 virtual Actor* copy(Space& home);
182 /// Perform propagation
183 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
184 /// Post propagator for \f$(x_0+x_1 = c)\equiv \operatorname{rm}(b)\f$
185 static ExecStatus post(Home home, A x0, B x1, Val c, Ctrl b);
186 };
187
188 /**
189 * \brief %Propagator for bounds consistent binary linear disequality
190 *
191 * The type \a Val can be either \c long long int or \c int, defining the
192 * numerical precision during propagation. The types \a A and \a B
193 * give the types of the views.
194 *
195 * The propagation condition \a pc refers to both views.
196 *
197 * Requires \code #include <gecode/int/linear.hh> \endcode
198 * \ingroup FuncIntProp
199 */
200 template<class Val, class A, class B>
201 class NqBin : public LinBin<Val,A,B,PC_INT_VAL> {
202 protected:
203 using LinBin<Val,A,B,PC_INT_VAL>::x0;
204 using LinBin<Val,A,B,PC_INT_VAL>::x1;
205 using LinBin<Val,A,B,PC_INT_VAL>::c;
206
207 /// Constructor for cloning \a p
208 NqBin(Space& home, NqBin& p);
209 /// Constructor for creation
210 NqBin(Home home, A x0, B x1, Val c);
211 public:
212 /// Constructor for rewriting \a p during cloning
213 NqBin(Space& home, Propagator& p, A x0, B x1, Val c);
214 /// Create copy during cloning
215 virtual Actor* copy(Space& home);
216 /// Perform propagation
217 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
218 /// Cost function (defined as low unary)
219 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
220 /// Post propagator for \f$x_0+x_1 \neq c\f$
221 static ExecStatus post(Home home, A x0, B x1, Val c);
222 };
223
224 /**
225 * \brief %Propagator for bounds consistent binary linear less or equal
226 *
227 * The type \a Val can be either \c long long int or \c int, defining the
228 * numerical precision during propagation. The types \a A and \a B
229 * give the types of the views.
230 *
231 * The propagation condition \a pc refers to both views.
232 *
233 * Requires \code #include <gecode/int/linear.hh> \endcode
234 * \ingroup FuncIntProp
235 */
236 template<class Val, class A, class B>
237 class LqBin : public LinBin<Val,A,B,PC_INT_BND> {
238 protected:
239 using LinBin<Val,A,B,PC_INT_BND>::x0;
240 using LinBin<Val,A,B,PC_INT_BND>::x1;
241 using LinBin<Val,A,B,PC_INT_BND>::c;
242
243 /// Constructor for cloning \a p
244 LqBin(Space& home, LqBin& p);
245 /// Constructor for creation
246 LqBin(Home home, A x0, B x1, Val c);
247 public:
248 /// Constructor for rewriting \a p during cloning
249 LqBin(Space& home, Propagator& p, A x0, B x1, Val c);
250 /// Create copy during cloning
251 virtual Actor* copy(Space& home);
252 /// Perform propagation
253 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
254 /// Post propagator for \f$x_0+x_1 \leq c\f$
255 static ExecStatus post(Home home, A x0, B x1, Val c);
256 };
257
258 /**
259 * \brief %Propagator for bounds consistent binary linear greater or equal
260 *
261 * The type \a Val can be either \c long long int or \c int, defining the
262 * numerical precision during propagation. The types \a A and \a B
263 * give the types of the views.
264 *
265 * The propagation condition \a pc refers to both views.
266 *
267 * Requires \code #include <gecode/int/linear.hh> \endcode
268 * \ingroup FuncIntProp
269 */
270 template<class Val, class A, class B>
271 class GqBin : public LinBin<Val,A,B,PC_INT_BND> {
272 protected:
273 using LinBin<Val,A,B,PC_INT_BND>::x0;
274 using LinBin<Val,A,B,PC_INT_BND>::x1;
275 using LinBin<Val,A,B,PC_INT_BND>::c;
276
277 /// Constructor for cloning \a p
278 GqBin(Space& home, GqBin& p);
279 /// Constructor for creation
280 GqBin(Home home, A x0, B x1, Val c);
281 public:
282 /// Constructor for rewriting \a p during cloning
283 GqBin(Space& home, Propagator& p, A x0, B x1, Val c);
284 /// Create copy during cloning
285 virtual Actor* copy(Space& home);
286 /// Perform propagation
287 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
288 /// Post propagator for \f$x_0+x_1 \geq c\f$
289 static ExecStatus post(Home home, A x0, B x1, Val c);
290 };
291
292 /**
293 * \brief %Propagator for reified bounds consistent binary linear less or equal
294 *
295 * The type \a Val can be either \c long long int or \c int, defining the
296 * numerical precision during propagation. The types \a A and \a B
297 * give the types of the views.
298 *
299 * The propagation condition \a pc refers to both views.
300 *
301 * Requires \code #include <gecode/int/linear.hh> \endcode
302 * \ingroup FuncIntProp
303 */
304 template<class Val, class A, class B, ReifyMode rm>
305 class ReLqBin : public ReLinBin<Val,A,B,PC_INT_BND,BoolView> {
306 protected:
307 using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::x0;
308 using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::x1;
309 using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::c;
310 using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::b;
311
312 /// Constructor for cloning \a p
313 ReLqBin(Space& home, ReLqBin& p);
314 /// Constructor for creation
315 ReLqBin(Home home, A x0, B x1, Val c, BoolView b);
316 public:
317 /// Create copy during cloning
318 virtual Actor* copy(Space& home);
319 /// Perform propagation
320 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
321 /// Post propagator for \f$(x_0+x_1 \leq c)\equiv \operatorname{rm}(b)\f$
322 static ExecStatus post(Home home, A x0, B x1, Val c, BoolView b);
323 };
324
325}}}
326
327#include <gecode/int/linear/int-bin.hpp>
328
329namespace Gecode { namespace Int { namespace Linear {
330
331 /*
332 * Ternary propagators
333 *
334 */
335
336 /**
337 * \brief Base-class for ternary linear propagators
338 *
339 * The type \a Val can be either \c long long int or \c int, defining the
340 * numerical precision during propagation. The types \a A, \a B,
341 * and \a C give the types of the views.
342 *
343 * The propagation condition \a pc refers to all three views.
344 */
345 template<class Val, class A, class B, class C, PropCond pc>
346 class LinTer : public Propagator {
347 protected:
348 /// View of type \a A
349 A x0;
350 /// View of type \a B
351 B x1;
352 /// View of type \a C
353 C x2;
354 /// Value of type \a Val
355 Val c;
356 /// Constructor for cloning \a p
357 LinTer(Space& home, LinTer& p);
358 /// Constructor for creation
359 LinTer(Home home, A x0, B x1, C x2, Val c);
360 /// Constructor for rewriting \a p during cloning
361 LinTer(Space& home, Propagator& p, A x0, B x1, C x2, Val c);
362 public:
363 /// Cost function (defined as low ternary)
364 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
365 /// Schedule function
366 virtual void reschedule(Space& home);
367 /// Delete propagator and return its size
368 virtual size_t dispose(Space& home);
369 };
370
371 /**
372 * \brief %Propagator for bounds consistent ternary linear equality
373 *
374 * The type \a Val can be either \c long long int or \c int, defining the
375 * numerical precision during propagation. The types \a A, \a B,
376 * and \a C give the types of the views.
377 *
378 * The propagation condition \a pc refers to all three views.
379 *
380 * Requires \code #include <gecode/int/linear.hh> \endcode
381 * \ingroup FuncIntProp
382 */
383 template<class Val, class A, class B, class C>
384 class EqTer : public LinTer<Val,A,B,C,PC_INT_BND> {
385 protected:
386 using LinTer<Val,A,B,C,PC_INT_BND>::x0;
387 using LinTer<Val,A,B,C,PC_INT_BND>::x1;
388 using LinTer<Val,A,B,C,PC_INT_BND>::x2;
389 using LinTer<Val,A,B,C,PC_INT_BND>::c;
390
391 /// Constructor for cloning \a p
392 EqTer(Space& home, EqTer& p);
393 /// Constructor for creation
394 EqTer(Home home, A x0, B x1, C x2, Val c);
395 public:
396 /// Constructor for rewriting \a p during cloning
397 EqTer(Space& home, Propagator& p, A x0, B x1, C x2, Val c);
398 /// Create copy during cloning
399 virtual Actor* copy(Space& home);
400 /// Perform propagation
401 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
402 /// Post propagator for \f$x_0+x_1+x_2 = c\f$
403 static ExecStatus post(Home home, A x0, B x1, C x2, Val c);
404 };
405
406 /**
407 * \brief %Propagator for bounds consistent ternary linear disquality
408 *
409 * The type \a Val can be either \c long long int or \c int, defining the
410 * numerical precision during propagation. The types \a A, \a B,
411 * and \a C give the types of the views.
412 *
413 * The propagation condition \a pc refers to all three views.
414 *
415 * Requires \code #include <gecode/int/linear.hh> \endcode
416 * \ingroup FuncIntProp
417 */
418 template<class Val, class A, class B, class C>
419 class NqTer : public LinTer<Val,A,B,C,PC_INT_VAL> {
420 protected:
421 using LinTer<Val,A,B,C,PC_INT_VAL>::x0;
422 using LinTer<Val,A,B,C,PC_INT_VAL>::x1;
423 using LinTer<Val,A,B,C,PC_INT_VAL>::x2;
424 using LinTer<Val,A,B,C,PC_INT_VAL>::c;
425
426 /// Constructor for cloning \a p
427 NqTer(Space& home, NqTer& p);
428 /// Constructor for creation
429 NqTer(Home home, A x0, B x1, C x2, Val c);
430 public:
431 /// Constructor for rewriting \a p during cloning
432 NqTer(Space& home, Propagator& p, A x0, B x1, C x2, Val c);
433 /// Create copy during cloning
434 virtual Actor* copy(Space& home);
435 /// Perform propagation
436 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
437 /// Post propagator for \f$x_0+x_1+x_2 \neq c\f$
438 static ExecStatus post(Home home, A x0, B x1, C x2, Val c);
439 };
440
441 /**
442 * \brief %Propagator for bounds consistent ternary linear less or equal
443 *
444 * The type \a Val can be either \c long long int or \c int, defining the
445 * numerical precision during propagation. The types \a A, \a B,
446 * and \a C give the types of the views.
447 *
448 * The propagation condition \a pc refers to all three views.
449 *
450 * Requires \code #include <gecode/int/linear.hh> \endcode
451 * \ingroup FuncIntProp
452 */
453 template<class Val, class A, class B, class C>
454 class LqTer : public LinTer<Val,A,B,C,PC_INT_BND> {
455 protected:
456 using LinTer<Val,A,B,C,PC_INT_BND>::x0;
457 using LinTer<Val,A,B,C,PC_INT_BND>::x1;
458 using LinTer<Val,A,B,C,PC_INT_BND>::x2;
459 using LinTer<Val,A,B,C,PC_INT_BND>::c;
460
461 /// Constructor for cloning \a p
462 LqTer(Space& home, LqTer& p);
463 /// Constructor for creation
464 LqTer(Home home, A x0, B x1, C x2, Val c);
465 public:
466 /// Constructor for rewriting \a p during cloning
467 LqTer(Space& home, Propagator& p, A x0, B x1, C x2, Val c);
468 /// Create copy during cloning
469 virtual Actor* copy(Space& home);
470 /// Perform propagation
471 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
472 /// Post propagator for \f$x_0+x_1+x_2 \leq c\f$
473 static ExecStatus post(Home home, A x0, B x1, C x2, Val c);
474 };
475
476}}}
477
478#include <gecode/int/linear/int-ter.hpp>
479
480namespace Gecode { namespace Int { namespace Linear {
481
482 /*
483 * n-ary propagators
484 *
485 */
486
487 /**
488 * \brief Base-class for n-ary linear propagators
489 *
490 * The type \a Val can be either \c long long int or \c int, defining the
491 * numerical precision during propagation. Positive views are of
492 * type \a P whereas negative views are of type \a N.
493 *
494 * The propagation condition \a pc refers to all views.
495 */
496 template<class Val, class P, class N, PropCond pc>
497 class Lin : public Propagator {
498 protected:
499 /// Array of positive views
500 ViewArray<P> x;
501 /// Array of negative views
502 ViewArray<N> y;
503 /// Constant value
504 Val c;
505
506 /// Constructor for cloning \a p
507 Lin(Space& home, Lin<Val,P,N,pc>& p);
508 /// Constructor for creation
509 Lin(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c);
510 public:
511 /// Cost function (defined as low linear)
512 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
513 /// Schedule function
514 virtual void reschedule(Space& home);
515 /// Delete propagator and return its size
516 virtual size_t dispose(Space& home);
517 };
518
519 /**
520 * \brief Base-class for reified n-ary linear propagators
521 *
522 * The type \a Val can be either \c long long int or \c int, defining the
523 * numerical precision during propagation. Positive views are of
524 * type \a P whereas negative views are of type \a N.
525 *
526 * The propagation condition \a pc refers to all views.
527 */
528 template<class Val, class P, class N, PropCond pc, class Ctrl>
529 class ReLin : public Lin<Val,P,N,pc> {
530 protected:
531 using Lin<Val,P,N,pc>::x;
532 using Lin<Val,P,N,pc>::y;
533 /// Control view for reification
534 Ctrl b;
535 /// Constructor for cloning \a p
536 ReLin(Space& home, ReLin& p);
537 /// Constructor for creation
538 ReLin(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b);
539 public:
540 /// Schedule function
541 virtual void reschedule(Space& home);
542 /// Delete propagator and return its size
543 virtual size_t dispose(Space& home);
544 };
545
546 /**
547 * \brief Compute bounds information for positive views
548 *
549 * \relates Lin
550 */
551 template<class Val, class View>
552 void bounds_p(ModEventDelta med, ViewArray<View>& x,
553 Val& c, Val& sl, Val& su);
554
555 /**
556 * \brief Compute bounds information for negative views
557 *
558 * \relates Lin
559 */
560 template<class Val, class View>
561 void bounds_n(ModEventDelta med, ViewArray<View>& y,
562 Val& c, Val& sl, Val& su);
563
564 /**
565 * \brief %Propagator for bounds consistent n-ary linear equality
566 *
567 * The type \a Val can be either \c long long int or \c int, defining the
568 * numerical precision during propagation. The types \a P and \a N
569 * give the types of the views.
570 *
571 * The propagation condition \a pc refers to both views.
572 *
573 * Requires \code #include <gecode/int/linear.hh> \endcode
574 * \ingroup FuncIntProp
575 */
576 template<class Val, class P, class N>
577 class Eq : public Lin<Val,P,N,PC_INT_BND> {
578 protected:
579 using Lin<Val,P,N,PC_INT_BND>::x;
580 using Lin<Val,P,N,PC_INT_BND>::y;
581 using Lin<Val,P,N,PC_INT_BND>::c;
582
583 /// Constructor for cloning \a p
584 Eq(Space& home, Eq& p);
585 public:
586 /// Constructor for creation
587 Eq(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c);
588 /// Create copy during cloning
589 virtual Actor* copy(Space& home);
590 /// Perform propagation
591 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
592 /// Post propagator for \f$\sum_{i=0}^{|x|-1}x_i-\sum_{i=0}^{|y|-1}y_i=c\f$
593 static ExecStatus
594 post(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c);
595 };
596
597 /**
598 * \brief %Propagator for domain consistent n-ary linear equality
599 *
600 * The type \a Val can be either \c long long int or \c int, defining the
601 * numerical precision during propagation. The types \a View
602 * give the type of the view.
603 *
604 * Requires \code #include <gecode/int/linear.hh> \endcode
605 * \ingroup FuncIntProp
606 */
607 template<class Val, class View>
608 class DomEq
609 : public Lin<Val,View,View,PC_INT_DOM> {
610 protected:
611 using Lin<Val,View,View,PC_INT_DOM>::x;
612 using Lin<Val,View,View,PC_INT_DOM>::y;
613 using Lin<Val,View,View,PC_INT_DOM>::c;
614
615 /// Constructor for cloning \a p
616 DomEq(Space& home, DomEq& p);
617 public:
618 /// Constructor for creation
619 DomEq(Home home, ViewArray<View>& x, ViewArray<View>& y, Val c);
620 /// Create copy during cloning
621 virtual Actor* copy(Space& home);
622 /**
623 * \brief Cost function
624 *
625 * If in stage for bounds propagation, the cost is
626 * low linear. Otherwise it is high crazy.
627 */
628 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
629 /// Perform propagation
630 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
631 /// Post propagator for \f$\sum_{i=0}^{|x|-1}x_i-\sum_{i=0}^{|y|-1}y_i=c\f$
632 static ExecStatus
633 post(Home home, ViewArray<View>& x, ViewArray<View>& y, Val c);
634 };
635
636 /**
637 * \brief %Propagator for reified bounds consistent n-ary linear equality
638 *
639 * The type \a Val can be either \c long long int or \c int, defining the
640 * numerical precision during propagation. The types \a P and \a N
641 * give the types of the views.
642 *
643 * The propagation condition \a pc refers to both views.
644 *
645 * Requires \code #include <gecode/int/linear.hh> \endcode
646 * \ingroup FuncIntProp
647 */
648 template<class Val, class P, class N, class Ctrl, ReifyMode rm>
649 class ReEq : public ReLin<Val,P,N,PC_INT_BND,Ctrl> {
650 protected:
651 using ReLin<Val,P,N,PC_INT_BND,Ctrl>::x;
652 using ReLin<Val,P,N,PC_INT_BND,Ctrl>::y;
653 using ReLin<Val,P,N,PC_INT_BND,Ctrl>::c;
654 using ReLin<Val,P,N,PC_INT_BND,Ctrl>::b;
655
656 /// Constructor for cloning \a p
657 ReEq(Space& home, ReEq& p);
658 public:
659 /// Constructor for creation
660 ReEq(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b);
661 /// Create copy during cloning
662 virtual Actor* copy(Space& home);
663 /// Perform propagation
664 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
665 /// Post propagator for \f$\left(\sum_{i=0}^{|x|-1}x_i-\sum_{i=0}^{|y|-1}y_i=c\right)\equiv \operatorname{rm}(b)\f$
666 static ExecStatus
667 post(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b);
668 };
669
670 /**
671 * \brief %Propagator for bounds consistent n-ary linear disequality
672 *
673 * The type \a Val can be either \c long long int or \c int, defining the
674 * numerical precision during propagation. The types \a P and \a N
675 * give the types of the views.
676 *
677 * The propagation condition \a pc refers to both views.
678 *
679 * Requires \code #include <gecode/int/linear.hh> \endcode
680 * \ingroup FuncIntProp
681 */
682 template<class Val, class P, class N>
683 class Nq : public Lin<Val,P,N,PC_INT_VAL> {
684 protected:
685 using Lin<Val,P,N,PC_INT_VAL>::x;
686 using Lin<Val,P,N,PC_INT_VAL>::y;
687 using Lin<Val,P,N,PC_INT_VAL>::c;
688
689 /// Constructor for cloning \a p
690 Nq(Space& home, Nq& p);
691 public:
692 /// Constructor for creation
693 Nq(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c);
694 /// Create copy during cloning
695 virtual Actor* copy(Space& home);
696 /// Perform propagation
697 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
698 /// Post propagator for \f$\sum_{i=0}^{|x|-1}x_i-\sum_{i=0}^{|y|-1}y_i\neq c\f$
699 static ExecStatus
700 post(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c);
701 };
702
703 /**
704 * \brief %Propagator for bounds consistent n-ary linear less or equal
705 *
706 * The type \a Val can be either \c long long int or \c int, defining the
707 * numerical precision during propagation. The types \a P and \a N
708 * give the types of the views.
709 *
710 * The propagation condition \a pc refers to both views.
711 *
712 * Requires \code #include <gecode/int/linear.hh> \endcode
713 * \ingroup FuncIntProp
714 */
715 template<class Val, class P, class N>
716 class Lq : public Lin<Val,P,N,PC_INT_BND> {
717 protected:
718 using Lin<Val,P,N,PC_INT_BND>::x;
719 using Lin<Val,P,N,PC_INT_BND>::y;
720 using Lin<Val,P,N,PC_INT_BND>::c;
721
722 /// Constructor for cloning \a p
723 Lq(Space& home, Lq& p);
724 public:
725 /// Constructor for creation
726 Lq(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c);
727 /// Create copy during cloning
728 virtual Actor* copy(Space& home);
729 /// Perform propagation
730 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
731 /// Post propagator for \f$\sum_{i=0}^{|x|-1}x_i-\sum_{i=0}^{|y|-1}y_i\leq c\f$
732 static ExecStatus
733 post(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c);
734 };
735
736 /**
737 * \brief %Propagator for reified bounds consistent n-ary linear less or equal
738 *
739 * The type \a Val can be either \c long long int or \c int, defining the
740 * numerical precision during propagation. The types \a P and \a N
741 * give the types of the views.
742 *
743 * The propagation condition \a pc refers to both views.
744 *
745 * Requires \code #include <gecode/int/linear.hh> \endcode
746 * \ingroup FuncIntProp
747 */
748 template<class Val, class P, class N, ReifyMode rm>
749 class ReLq : public ReLin<Val,P,N,PC_INT_BND,BoolView> {
750 protected:
751 using ReLin<Val,P,N,PC_INT_BND,BoolView>::x;
752 using ReLin<Val,P,N,PC_INT_BND,BoolView>::y;
753 using ReLin<Val,P,N,PC_INT_BND,BoolView>::c;
754 using ReLin<Val,P,N,PC_INT_BND,BoolView>::b;
755
756 /// Constructor for cloning \a p
757 ReLq(Space& home, ReLq& p);
758 public:
759 /// Constructor for creation
760 ReLq(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b);
761 /// Create copy during cloning
762 virtual Actor* copy(Space& home);
763 /// Perform propagation
764 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
765 /// Post propagator for \f$\left(\sum_{i=0}^{|x|-1}x_i-\sum_{i=0}^{|y|-1}y_i\leq c\right)\equiv \operatorname{rm}(b)\f$
766 static ExecStatus
767 post(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b);
768 };
769
770}}}
771
772#include <gecode/int/linear/int-nary.hpp>
773#include <gecode/int/linear/int-dom.hpp>
774
775namespace Gecode { namespace Int { namespace Linear {
776
777 /*
778 * Boolean linear propagators
779 *
780 */
781
782 /**
783 * \brief Baseclass for integer Boolean sum
784 *
785 */
786 template<class VX>
787 class LinBoolInt : public Propagator {
788 protected:
789 /// Council for managing single advisor
790 Council<Advisor> co;
791 /// Boolean views
792 ViewArray<VX> x;
793 /// Number of active subscriptions
794 int n_as;
795 /// Number of views that have or had subscriptions
796 int n_hs;
797 /// Righthandside
798 int c;
799 /// Normalize by removing unused views
800 void normalize(void);
801 /// Constructor for cloning \a p
802 LinBoolInt(Space& home, LinBoolInt& p);
803 /// Constructor for creation
804 LinBoolInt(Home home, ViewArray<VX>& x, int n_s, int c);
805 public:
806 /// Cost function (defined as high unary)
807 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
808 /// Delete propagator and return its size
809 virtual size_t dispose(Space& home);
810 };
811
812 /**
813 * \brief %Propagator for integer equal to Boolean sum (cardinality)
814 *
815 * Requires \code #include <gecode/int/linear.hh> \endcode
816 * \ingroup FuncIntProp
817 */
818 template<class VX>
819 class EqBoolInt : public LinBoolInt<VX> {
820 protected:
821 using LinBoolInt<VX>::co;
822 using LinBoolInt<VX>::x;
823 using LinBoolInt<VX>::n_as;
824 using LinBoolInt<VX>::n_hs;
825 using LinBoolInt<VX>::c;
826 using LinBoolInt<VX>::disabled;
827 /// Constructor for cloning \a p
828 EqBoolInt(Space& home, EqBoolInt& p);
829 /// Constructor for creation
830 EqBoolInt(Home home, ViewArray<VX>& x, int c);
831 public:
832 /// Create copy during cloning
833 virtual Actor* copy(Space& home);
834 /// Schedule function
835 virtual void reschedule(Space& home);
836 /// Give advice to propagator
837 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
838 /// Perform propagation
839 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
840 /// Post propagator for \f$\sum_{i=0}^{|x|-1}x_i = c\f$
841 static ExecStatus post(Home home, ViewArray<VX>& x, int c);
842 };
843
844 /**
845 * \brief %Propagator for integer less or equal to Boolean sum (cardinality)
846 *
847 * Requires \code #include <gecode/int/linear.hh> \endcode
848 * \ingroup FuncIntProp
849 */
850 template<class VX>
851 class GqBoolInt : public LinBoolInt<VX> {
852 protected:
853 using LinBoolInt<VX>::co;
854 using LinBoolInt<VX>::x;
855 using LinBoolInt<VX>::n_as;
856 using LinBoolInt<VX>::n_hs;
857 using LinBoolInt<VX>::c;
858 using LinBoolInt<VX>::disabled;
859 /// Constructor for cloning \a p
860 GqBoolInt(Space& home, GqBoolInt& p);
861 /// Constructor for creation
862 GqBoolInt(Home home, ViewArray<VX>& x, int c);
863 public:
864 /// Create copy during cloning
865 virtual Actor* copy(Space& home);
866 /// Schedule function
867 virtual void reschedule(Space& home);
868 /// Give advice to propagator
869 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
870 /// Perform propagation
871 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
872 /// Post propagator for \f$\sum_{i=0}^{|x|-1}x_i \geq c\f$
873 static ExecStatus post(Home home, ViewArray<VX>& x, int c);
874 };
875
876 /**
877 * \brief %Propagator for integer disequal to Boolean sum (cardinality)
878 *
879 * Requires \code #include <gecode/int/linear.hh> \endcode
880 * \ingroup FuncIntProp
881 */
882 template<class VX>
883 class NqBoolInt : public BinaryPropagator<VX,PC_INT_VAL> {
884 protected:
885 using BinaryPropagator<VX,PC_INT_VAL>::x0;
886 using BinaryPropagator<VX,PC_INT_VAL>::x1;
887 /// Views not yet subscribed to
888 ViewArray<VX> x;
889 /// Righthandside
890 int c;
891 /// Update subscription
892 bool resubscribe(Space& home, VX& y);
893 /// Constructor for posting
894 NqBoolInt(Home home, ViewArray<VX>& b, int c);
895 /// Constructor for cloning \a p
896 NqBoolInt(Space& home, NqBoolInt<VX>& p);
897 public:
898 /// Copy propagator during cloning
899 virtual Actor* copy(Space& home);
900 /// Cost function (defined as low linear)
901 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
902 /// Perform propagation
903 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
904 /// Post propagator for \f$\sum_{i=0}^{|x|-1}x_i \neq c\f$
905 static ExecStatus post(Home home, ViewArray<VX>& b, int c);
906 /// Delete propagator and return its size
907 virtual size_t dispose(Space& home);
908 };
909
910
911 /**
912 * \brief Baseclass for reified integer Boolean sum
913 *
914 */
915 template<class VX, class VB>
916 class ReLinBoolInt : public Propagator {
917 protected:
918 /// Council for single advisor
919 Council<Advisor> co;
920 /// Views
921 ViewArray<VX> x;
922 /// Number of subscriptions
923 int n_s;
924 /// Righthandside
925 int c;
926 /// Control variable
927 VB b;
928 /// Normalize by removing unused views
929 void normalize(void);
930 /// Constructor for cloning \a p
931 ReLinBoolInt(Space& home, ReLinBoolInt& p);
932 /// Constructor for creation
933 ReLinBoolInt(Home home, ViewArray<VX>& x, int c, VB b);
934 public:
935 /// Cost function (defined as high unary)
936 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
937 /// Delete propagator and return its size
938 virtual size_t dispose(Space& home);
939 };
940
941
942 /**
943 * \brief Traits for Boolean negation view
944 */
945 template<class BV>
946 class BoolNegTraits {};
947
948 /**
949 * \brief %Propagator for reified integer less or equal to Boolean sum (cardinality)
950 *
951 * Requires \code #include <gecode/int/linear.hh> \endcode
952 * \ingroup FuncIntProp
953 */
954 template<class VX, class VB, ReifyMode rm>
955 class ReGqBoolInt : public ReLinBoolInt<VX,VB> {
956 protected:
957 using ReLinBoolInt<VX,VB>::co;
958 using ReLinBoolInt<VX,VB>::x;
959 using ReLinBoolInt<VX,VB>::c;
960 using ReLinBoolInt<VX,VB>::b;
961 using ReLinBoolInt<VX,VB>::n_s;
962 using ReLinBoolInt<VX,VB>::normalize;
963 /// Constructor for cloning \a p
964 ReGqBoolInt(Space& home, ReGqBoolInt& p);
965 /// Constructor for creation
966 ReGqBoolInt(Home home, ViewArray<VX>& x, int c, VB b);
967 public:
968 /// Create copy during cloning
969 virtual Actor* copy(Space& home);
970 /// Schedule function
971 virtual void reschedule(Space& home);
972 /// Give advice to propagator
973 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
974 /// Perform propagation
975 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
976 /// Post propagator for \f$\left(\sum_{i=0}^{|x|-1}x_i \geq\right) c \equiv \operatorname{rm}(b)\f$
977 static ExecStatus post(Home home, ViewArray<VX>& x, int c, VB b);
978 };
979
980 /**
981 * \brief %Propagator for reified integer equal to Boolean sum (cardinality)
982 *
983 * Requires \code #include <gecode/int/linear.hh> \endcode
984 * \ingroup FuncIntProp
985 */
986 template<class VX, class VB, ReifyMode rm>
987 class ReEqBoolInt : public ReLinBoolInt<VX,VB> {
988 protected:
989 using ReLinBoolInt<VX,VB>::co;
990 using ReLinBoolInt<VX,VB>::x;
991 using ReLinBoolInt<VX,VB>::c;
992 using ReLinBoolInt<VX,VB>::b;
993 using ReLinBoolInt<VX,VB>::n_s;
994 using ReLinBoolInt<VX,VB>::normalize;
995 /// Constructor for cloning \a p
996 ReEqBoolInt(Space& home, ReEqBoolInt& p);
997 /// Constructor for creation
998 ReEqBoolInt(Home home, ViewArray<VX>& x, int c, VB b);
999 public:
1000 /// Create copy during cloning
1001 virtual Actor* copy(Space& home);
1002 /// Schedule function
1003 virtual void reschedule(Space& home);
1004 /// Give advice to propagator
1005 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
1006 /// Perform propagation
1007 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
1008 /// Post propagator for \f$\left(\sum_{i=0}^{|x|-1}x_i = c\right)\equiv \operatorname{rm}(b)\f$
1009 static ExecStatus post(Home home, ViewArray<VX>& x, int c, VB b);
1010 };
1011
1012}}}
1013
1014#include <gecode/int/linear/bool-int.hpp>
1015
1016namespace Gecode { namespace Int { namespace Linear {
1017
1018 /**
1019 * \brief Base-class for Boolean linear propagators
1020 *
1021 */
1022 template<class XV, class YV>
1023 class LinBoolView : public Propagator {
1024 protected:
1025 /// Boolean views
1026 ViewArray<XV> x;
1027 /// View to compare number of assigned Boolean views to
1028 YV y;
1029 /// Righthandside (constant part from Boolean views assigned to 1)
1030 int c;
1031 /// Constructor for cloning \a p
1032 LinBoolView(Space& home, LinBoolView& p);
1033 /// Constructor for creation
1034 LinBoolView(Home home, ViewArray<XV>& x, YV y, int c);
1035 public:
1036 /// Cost function (defined as low linear)
1037 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
1038 /// Schedule function
1039 virtual void reschedule(Space& home);
1040 /// Delete propagator and return its size
1041 virtual size_t dispose(Space& home);
1042 };
1043
1044
1045 /**
1046 * \brief %Propagator for equality to Boolean sum (cardinality)
1047 *
1048 * Requires \code #include <gecode/int/linear.hh> \endcode
1049 * \ingroup FuncIntProp
1050 */
1051 template<class XV, class YV>
1052 class EqBoolView : public LinBoolView<XV,YV> {
1053 protected:
1054 using LinBoolView<XV,YV>::x;
1055 using LinBoolView<XV,YV>::y;
1056 using LinBoolView<XV,YV>::c;
1057
1058 /// Constructor for cloning \a p
1059 EqBoolView(Space& home, EqBoolView& p);
1060 /// Constructor for creation
1061 EqBoolView(Home home, ViewArray<XV>& x, YV y, int c);
1062 public:
1063 /// Create copy during cloning
1064 virtual Actor* copy(Space& home);
1065 /// Perform propagation
1066 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
1067 /// Post propagator for \f$\sum_{i=0}^{|x|-1}x_i = y+c\f$
1068 static ExecStatus post(Home home, ViewArray<XV>& x, YV y, int c);
1069 };
1070
1071 /**
1072 * \brief %Propagator for disequality to Boolean sum (cardinality)
1073 *
1074 * Requires \code #include <gecode/int/linear.hh> \endcode
1075 * \ingroup FuncIntProp
1076 */
1077 template<class XV, class YV>
1078 class NqBoolView : public LinBoolView<XV,YV> {
1079 protected:
1080 using LinBoolView<XV,YV>::x;
1081 using LinBoolView<XV,YV>::y;
1082 using LinBoolView<XV,YV>::c;
1083
1084 /// Constructor for cloning \a p
1085 NqBoolView(Space& home, NqBoolView& p);
1086 /// Constructor for creation
1087 NqBoolView(Home home, ViewArray<XV>& x, YV y, int c);
1088 public:
1089 /// Create copy during cloning
1090 virtual Actor* copy(Space& home);
1091 /// Perform propagation
1092 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
1093 /// Post propagator for \f$\sum_{i=0}^{|x|-1}x_i \neq y+c\f$
1094 static ExecStatus post(Home home, ViewArray<XV>& x, YV y, int c);
1095 };
1096
1097 /**
1098 * \brief %Propagator for greater or equal to Boolean sum (cardinality)
1099 *
1100 * Requires \code #include <gecode/int/linear.hh> \endcode
1101 * \ingroup FuncIntProp
1102 */
1103 template<class XV, class YV>
1104 class GqBoolView : public LinBoolView<XV,YV> {
1105 protected:
1106 using LinBoolView<XV,YV>::x;
1107 using LinBoolView<XV,YV>::y;
1108 using LinBoolView<XV,YV>::c;
1109
1110 /// Constructor for cloning \a p
1111 GqBoolView(Space& home, GqBoolView& p);
1112 /// Constructor for creation
1113 GqBoolView(Home home, ViewArray<XV>& x, YV y, int c);
1114 public:
1115 /// Create copy during cloning
1116 virtual Actor* copy(Space& home);
1117 /// Perform propagation
1118 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
1119 /// Post propagator for \f$\sum_{i=0}^{|x|-1}x_i \geq y+c\f$
1120 static ExecStatus post(Home home, ViewArray<XV>& x, YV y, int c);
1121 };
1122
1123}}}
1124
1125#include <gecode/int/linear/bool-view.hpp>
1126
1127namespace Gecode { namespace Int { namespace Linear {
1128
1129 /// Coefficient and Boolean view
1130 class ScaleBool {
1131 public:
1132 /// Integer coefficient
1133 int a;
1134 /// Boolean view
1135 BoolView x;
1136 };
1137
1138 /// Array of scale Boolean views
1139 class ScaleBoolArray {
1140 private:
1141 /// First entry in array
1142 ScaleBool* _fst;
1143 /// One after last entry in array
1144 ScaleBool* _lst;
1145 public:
1146 /// Default constructor
1147 ScaleBoolArray(void);
1148 /// Create array with \a n elements
1149 ScaleBoolArray(Space& home, int n);
1150 /// Subscribe propagator \a p
1151 void subscribe(Space& home, Propagator& p);
1152 /// Cancel propagator \a p
1153 void cancel(Space& home, Propagator& p);
1154 /// Schedule propagator \a p
1155 void reschedule(Space& home, Propagator& p);
1156 /// Update \a sba during copying
1157 void update(Space& home, ScaleBoolArray& sba);
1158 /// Return pointer to first element
1159 ScaleBool* fst(void) const;
1160 /// Return pointer after last element
1161 ScaleBool* lst(void) const;
1162 /// Set pointer to first element
1163 void fst(ScaleBool* f);
1164 /// Set pointer after last element
1165 void lst(ScaleBool* l);
1166 /// Test whether array is empty
1167 bool empty(void) const;
1168 /// Return number of elements
1169 int size(void) const;
1170 private:
1171 /// For sorting array in decreasing order of coefficients
1172 class ScaleDec {
1173 public:
1174 bool
1175 operator ()(const ScaleBool& x, const ScaleBool& y);
1176 };
1177 public:
1178 /// Sort array in decreasing order of coefficients
1179 void sort(void);
1180 };
1181
1182
1183 /// Empty array of scale Boolean views
1184 class EmptyScaleBoolArray {
1185 public:
1186 /// Default constructor
1187 EmptyScaleBoolArray(void);
1188 /// Create array with \a n elements
1189 EmptyScaleBoolArray(Space& home, int n);
1190 /// Subscribe propagator \a p
1191 void subscribe(Space& home, Propagator& p);
1192 /// Cancel propagator \a p
1193 void cancel(Space& home, Propagator& p);
1194 /// Schedule propagator \a p
1195 void reschedule(Space& home, Propagator& p);
1196 /// Update \a sba during copying
1197 void update(Space& home, EmptyScaleBoolArray& esba);
1198 /// Return pointer to first element
1199 ScaleBool* fst(void) const;
1200 /// Return pointer after last element
1201 ScaleBool* lst(void) const;
1202 /// Set pointer to first element
1203 void fst(ScaleBool* f);
1204 /// Set pointer after last element
1205 void lst(ScaleBool* l);
1206 /// Test whether array is empty
1207 bool empty(void) const;
1208 /// Return number of elements
1209 int size(void) const;
1210 /// Sort array in decreasing order of coefficients
1211 void sort(void);
1212 };
1213
1214
1215 /**
1216 * \brief Base class for linear Boolean constraints with coefficients
1217 *
1218 */
1219 template<class SBAP, class SBAN, class VX, PropCond pcx>
1220 class LinBoolScale : public Propagator {
1221 protected:
1222 /// Positive Boolean views with coefficients on left-hand side
1223 SBAP p;
1224 /// Negative Boolean views with coefficients on left-hand side
1225 SBAN n;
1226 /// Integer view on right-hand side
1227 VX x;
1228 /// Integer constant on right-hand side
1229 int c;
1230 public:
1231 /// Constructor for creation
1232 LinBoolScale(Home home, SBAP& p, SBAN& n, VX x, int c);
1233 /// Constructor for cloning \a pr
1234 LinBoolScale(Space& home, Propagator& pr,
1235 SBAP& p, SBAN& n, VX x, int c);
1236 /// Cost function (defined as low linear)
1237 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
1238 /// Schedule function
1239 virtual void reschedule(Space& home);
1240 /// Delete propagator and return its size
1241 virtual size_t dispose(Space& home);
1242 };
1243
1244 /**
1245 * \brief %Propagator for equality to Boolean sum with coefficients
1246 *
1247 * Requires \code #include <gecode/int/linear.hh> \endcode
1248 * \ingroup FuncIntProp
1249 */
1250 template<class SBAP, class SBAN, class VX>
1251 class EqBoolScale : public LinBoolScale<SBAP,SBAN,VX,PC_INT_BND> {
1252 protected:
1253 using LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>::p;
1254 using LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>::n;
1255 using LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>::x;
1256 using LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>::c;
1257 public:
1258 /// Constructor for creation
1259 EqBoolScale(Home home, SBAP& p, SBAN& n, VX x, int c);
1260 /// Constructor for cloning \a pr
1261 EqBoolScale(Space& home, Propagator& pr,
1262 SBAP& p, SBAN& n, VX x, int c);
1263 /// Create copy during cloning
1264 virtual Actor* copy(Space& home);
1265 /// Perform propagation
1266 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
1267 /// Post propagator
1268 static ExecStatus post(Home home, SBAP& p, SBAN& n, VX x, int c);
1269 };
1270
1271 /**
1272 * \brief %Propagator for inequality to Boolean sum with coefficients
1273 *
1274 * Requires \code #include <gecode/int/linear.hh> \endcode
1275 * \ingroup FuncIntProp
1276 */
1277 template<class SBAP, class SBAN, class VX>
1278 class LqBoolScale : public LinBoolScale<SBAP,SBAN,VX,PC_INT_BND> {
1279 protected:
1280 using LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>::p;
1281 using LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>::n;
1282 using LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>::x;
1283 using LinBoolScale<SBAP,SBAN,VX,PC_INT_BND>::c;
1284 public:
1285 /// Constructor for creation
1286 LqBoolScale(Home home, SBAP& p, SBAN& n, VX x, int c);
1287 /// Constructor for cloning \a pr
1288 LqBoolScale(Space& home, Propagator& pr,
1289 SBAP& p, SBAN& n, VX x, int c);
1290 /// Create copy during cloning
1291 virtual Actor* copy(Space& home);
1292 /// Perform propagation
1293 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
1294 /// Post propagator
1295 static ExecStatus post(Home home, SBAP& p, SBAN& n, VX x, int c);
1296 };
1297
1298 /**
1299 * \brief %Propagator for disequality to Boolean sum with coefficients
1300 *
1301 * Requires \code #include <gecode/int/linear.hh> \endcode
1302 * \ingroup FuncIntProp
1303 */
1304 template<class SBAP, class SBAN, class VX>
1305 class NqBoolScale : public LinBoolScale<SBAP,SBAN,VX,PC_INT_VAL> {
1306 protected:
1307 using LinBoolScale<SBAP,SBAN,VX,PC_INT_VAL>::p;
1308 using LinBoolScale<SBAP,SBAN,VX,PC_INT_VAL>::n;
1309 using LinBoolScale<SBAP,SBAN,VX,PC_INT_VAL>::x;
1310 using LinBoolScale<SBAP,SBAN,VX,PC_INT_VAL>::c;
1311 public:
1312 /// Constructor for creation
1313 NqBoolScale(Home home, SBAP& p, SBAN& n, VX x, int c);
1314 /// Constructor for cloning \a pr
1315 NqBoolScale(Space& home, Propagator& pr,
1316 SBAP& p, SBAN& n, VX x, int c);
1317 /// Create copy during cloning
1318 virtual Actor* copy(Space& home);
1319 /// Perform propagation
1320 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
1321 /// Post propagator
1322 static ExecStatus post(Home home, SBAP& p, SBAN& n, VX x, int c);
1323 };
1324
1325}}}
1326
1327#include <gecode/int/linear/bool-scale.hpp>
1328
1329namespace Gecode { namespace Int { namespace Linear {
1330
1331 /**
1332 * \brief Class for describing linear term \f$a\cdot x\f$
1333 *
1334 */
1335 template<class View>
1336 class Term {
1337 public:
1338 /// Coefficient
1339 int a;
1340 /// View
1341 View x;
1342 /// Original position in array (for sorting into canonical order)
1343 int p;
1344 };
1345
1346 /** \brief Estimate lower and upper bounds
1347 *
1348 * Estimates the boundaries for a linear expression
1349 * \f$\sum_{i=0}^{n-1}t_i + c\f$. If the boundaries exceed
1350 * the limits as defined in Limits::Int, these boundaries
1351 * are returned.
1352 *
1353 * \param t array of linear terms
1354 * \param n size of array
1355 * \param c constant
1356 * \param l lower bound
1357 * \param u upper bound
1358 *
1359 */
1360 template<class View>
1361 void estimate(Term<View>* t, int n, int c,
1362 int& l, int& u);
1363
1364 /**
1365 * \brief Post propagator for linear constraint over integers
1366 * \param home current space
1367 * \param t array of linear terms over integers
1368 * \param n size of array
1369 * \param irt type of relation
1370 * \param c result of linear constraint
1371 *
1372 * All variants for linear constraints share the following properties:
1373 * - Variables occuring multiply in the term array are replaced
1374 * by a single occurence: for example, \f$ax+bx\f$ becomes
1375 * \f$(a+b)x\f$.
1376 * - If in the above simplification the value for \f$(a+b)\f$ (or for
1377 * \f$a\f$ and \f$b\f$) exceeds the limits for integers as
1378 * defined in Limits::Int, an exception of type
1379 * Int::NumericalOverflow is thrown.
1380 * - Assume linear terms for the constraint
1381 * \f$\sum_{i=0}^{|x|-1}a_i\cdot x_i\sim_{irt} c\f$.
1382 * If \f$|c|+\sum_{i=0}^{|x|-1}a_i\cdot x_i\f$ exceeds the limits
1383 * for long long ints as defined in Limits::Int, an exception of
1384 * type Int::NumericalOverflow is thrown.
1385 * - In all other cases, the created propagators are accurate (that
1386 * is, they will not silently overflow during propagation).
1387 *
1388 * Requires \code #include <gecode/int/linear.hh> \endcode
1389 * \ingroup FuncIntProp
1390 */
1391 GECODE_INT_EXPORT void
1392 post(Home home, Term<IntView>* t, int n, IntRelType irt, int c,
1393 IntPropLevel=IPL_DEF);
1394
1395 /**
1396 * \brief Post reified propagator for linear constraint
1397 * \param home current space
1398 * \param t array of linear terms
1399 * \param n size of array
1400 * \param irt type of relation
1401 * \param c result of linear constraint
1402 * \param r reification specification
1403 *
1404 * All variants for linear constraints share the following properties:
1405 * - Only bounds consistency is supported.
1406 * - Variables occuring multiply in the term array are replaced
1407 * by a single occurence: for example, \f$ax+bx\f$ becomes
1408 * \f$(a+b)x\f$.
1409 * - If in the above simplification the value for \f$(a+b)\f$ (or for
1410 * \f$a\f$ and \f$b\f$) exceeds the limits for integers as
1411 * defined in Limits::Int, an exception of type
1412 * Int::NumericalOverflow is thrown.
1413 * - Assume linear terms for the constraint
1414 * \f$\sum_{i=0}^{|x|-1}a_i\cdot x_i\sim_{irt} c\f$.
1415 * If \f$|c|+\sum_{i=0}^{|x|-1}a_i\cdot x_i\f$ exceeds the limits
1416 * for long long ints as defined in Limits::Int, an exception of
1417 * type Int::NumericalOverflow is thrown.
1418 * - In all other cases, the created propagators are accurate (that
1419 * is, they will not silently overflow during propagation).
1420 *
1421 * Requires \code #include <gecode/int/linear.hh> \endcode
1422 * \ingroup FuncIntProp
1423 */
1424 GECODE_INT_EXPORT void
1425 post(Home home, Term<IntView>* t, int n, IntRelType irt, int c, Reify r,
1426 IntPropLevel=IPL_DEF);
1427
1428 /**
1429 * \brief Post propagator for linear constraint over Booleans
1430 * \param home current space
1431 * \param t array of linear terms over Booleans
1432 * \param n size of array
1433 * \param irt type of relation
1434 * \param c result of linear constraint
1435 *
1436 * All variants for linear constraints share the following properties:
1437 * - Variables occuring multiply in the term array are replaced
1438 * by a single occurence: for example, \f$ax+bx\f$ becomes
1439 * \f$(a+b)x\f$.
1440 * - If in the above simplification the value for \f$(a+b)\f$ (or for
1441 * \f$a\f$ and \f$b\f$) exceeds the limits for integers as
1442 * defined in Limits::Int, an exception of type
1443 * Int::NumericalOverflow is thrown.
1444 * - Assume linear terms for the constraint
1445 * \f$\sum_{i=0}^{|x|-1}a_i\cdot x_i\sim_{irt} c\f$.
1446 * If \f$|c|+\sum_{i=0}^{|x|-1}a_i\cdot x_i\f$ exceeds the limits
1447 * for integers as defined in Limits::Int, an exception of
1448 * type Int::NumericalOverflow is thrown.
1449 * - In all other cases, the created propagators are accurate (that
1450 * is, they will not silently overflow during propagation).
1451 *
1452 * Requires \code #include <gecode/int/linear.hh> \endcode
1453 * \ingroup FuncIntProp
1454 */
1455 GECODE_INT_EXPORT void
1456 post(Home home, Term<BoolView>* t, int n, IntRelType irt, int c,
1457 IntPropLevel=IPL_DEF);
1458
1459 /**
1460 * \brief Post propagator for reified linear constraint over Booleans
1461 * \param home current space
1462 * \param t array of linear terms over Booleans
1463 * \param n size of array
1464 * \param irt type of relation
1465 * \param c result of linear constraint
1466 * \param r reification specification
1467 *
1468 * All variants for linear constraints share the following properties:
1469 * - Variables occuring multiply in the term array are replaced
1470 * by a single occurence: for example, \f$ax+bx\f$ becomes
1471 * \f$(a+b)x\f$.
1472 * - If in the above simplification the value for \f$(a+b)\f$ (or for
1473 * \f$a\f$ and \f$b\f$) exceeds the limits for integers as
1474 * defined in Limits::Int, an exception of type
1475 * Int::NumericalOverflow is thrown.
1476 * - Assume linear terms for the constraint
1477 * \f$\sum_{i=0}^{|x|-1}a_i\cdot x_i\sim_{irt} c\f$.
1478 * If \f$|c|+\sum_{i=0}^{|x|-1}a_i\cdot x_i\f$ exceeds the limits
1479 * for integers as defined in Limits::Int, an exception of
1480 * type Int::NumericalOverflow is thrown.
1481 * - In all other cases, the created propagators are accurate (that
1482 * is, they will not silently overflow during propagation).
1483 *
1484 * Requires \code #include <gecode/int/linear.hh> \endcode
1485 * \ingroup FuncIntProp
1486 */
1487 GECODE_INT_EXPORT void
1488 post(Home home, Term<BoolView>* t, int n, IntRelType irt, int c, Reify r,
1489 IntPropLevel=IPL_DEF);
1490
1491 /**
1492 * \brief Post propagator for linear constraint over Booleans
1493 * \param home current space
1494 * \param t array of linear terms over Booleans
1495 * \param n size of array
1496 * \param irt type of relation
1497 * \param y variable right hand side of linear constraint
1498 * \param c constant right hand side of linear constraint
1499 *
1500 * All variants for linear constraints share the following properties:
1501 * - Variables occuring multiply in the term array are replaced
1502 * by a single occurence: for example, \f$ax+bx\f$ becomes
1503 * \f$(a+b)x\f$.
1504 * - If in the above simplification the value for \f$(a+b)\f$ (or for
1505 * \f$a\f$ and \f$b\f$) exceeds the limits for integers as
1506 * defined in Limits::Int, an exception of type
1507 * Int::NumericalOverflow is thrown.
1508 * - Assume linear terms for the constraint
1509 * \f$\sum_{i=0}^{|x|-1}a_i\cdot x_i\sim_{irt} c\f$.
1510 * If \f$|c|+\sum_{i=0}^{|x|-1}a_i\cdot x_i\f$ exceeds the limits
1511 * for integers as defined in Limits::Int, an exception of
1512 * type Int::NumericalOverflow is thrown.
1513 * - In all other cases, the created propagators are accurate (that
1514 * is, they will not silently overflow during propagation).
1515 *
1516 * Requires \code #include <gecode/int/linear.hh> \endcode
1517 * \ingroup FuncIntProp
1518 */
1519 GECODE_INT_EXPORT void
1520 post(Home home, Term<BoolView>* t, int n, IntRelType irt, IntView y, int c=0,
1521 IntPropLevel=IPL_DEF);
1522
1523 /**
1524 * \brief Post propagator for reified linear constraint over Booleans
1525 * \param home current space
1526 * \param t array of linear terms over Booleans
1527 * \param n size of array
1528 * \param irt type of relation
1529 * \param y variable right hand side of linear constraint
1530 * \param r reification specification
1531 *
1532 * All variants for linear constraints share the following properties:
1533 * - Variables occuring multiply in the term array are replaced
1534 * by a single occurence: for example, \f$ax+bx\f$ becomes
1535 * \f$(a+b)x\f$.
1536 * - If in the above simplification the value for \f$(a+b)\f$ (or for
1537 * \f$a\f$ and \f$b\f$) exceeds the limits for integers as
1538 * defined in Limits::Int, an exception of type
1539 * Int::NumericalOverflow is thrown.
1540 * - Assume linear terms for the constraint
1541 * \f$\sum_{i=0}^{|x|-1}a_i\cdot x_i\sim_{irt} c\f$.
1542 * If \f$|c|+\sum_{i=0}^{|x|-1}a_i\cdot x_i\f$ exceeds the limits
1543 * for integers as defined in Limits::Int, an exception of
1544 * type Int::NumericalOverflow is thrown.
1545 * - In all other cases, the created propagators are accurate (that
1546 * is, they will not silently overflow during propagation).
1547 *
1548 * Requires \code #include <gecode/int/linear.hh> \endcode
1549 * \ingroup FuncIntProp
1550 */
1551 GECODE_INT_EXPORT void
1552 post(Home home, Term<BoolView>* t, int n, IntRelType irt, IntView y,
1553 Reify r, IntPropLevel=IPL_DEF);
1554
1555}}}
1556
1557#include <gecode/int/linear/post.hpp>
1558
1559#endif
1560
1561// STATISTICS: int-prop