Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
bnd.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5 *
6 * Contributing authors:
7 * Christian Schulte <schulte@gecode.org>
8 * Guido Tack <tack@gecode.org>
9 *
10 * Copyright:
11 * Patrick Pekczynski, 2004/2005
12 * Christian Schulte, 2009
13 * Guido Tack, 2009
14 *
15 * This file is part of Gecode, the generic constraint
16 * development environment:
17 * http://www.gecode.org
18 *
19 * Permission is hereby granted, free of charge, to any person obtaining
20 * a copy of this software and associated documentation files (the
21 * "Software"), to deal in the Software without restriction, including
22 * without limitation the rights to use, copy, modify, merge, publish,
23 * distribute, sublicense, and/or sell copies of the Software, and to
24 * permit persons to whom the Software is furnished to do so, subject to
25 * the following conditions:
26 *
27 * The above copyright notice and this permission notice shall be
28 * included in all copies or substantial portions of the Software.
29 *
30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 *
38 */
39
40namespace Gecode { namespace Int { namespace GCC {
41
42 template<class Card>
46 bool cf, bool nolbc) :
47 Propagator(home), x(x0), y(home, x0), k(k0),
48 card_fixed(cf), skip_lbc(nolbc) {
49 y.subscribe(home, *this, PC_INT_BND);
50 k.subscribe(home, *this, PC_INT_BND);
51 }
52
53 template<class Card>
56 Bnd(Space& home, Bnd<Card>& p)
57 : Propagator(home, p),
58 card_fixed(p.card_fixed), skip_lbc(p.skip_lbc) {
59 x.update(home, p.x);
60 y.update(home, p.y);
61 k.update(home, p.k);
62 }
63
64 template<class Card>
65 forceinline size_t
67 y.cancel(home,*this, PC_INT_BND);
68 k.cancel(home,*this, PC_INT_BND);
69 (void) Propagator::dispose(home);
70 return sizeof(*this);
71 }
72
73 template<class Card>
74 Actor*
76 return new (home) Bnd<Card>(home,*this);
77 }
78
79 template<class Card>
82 const ModEventDelta& med) const {
83 int n_k = Card::propagate ? k.size() : 0;
84 if (IntView::me(med) == ME_INT_VAL)
85 return PropCost::linear(PropCost::LO, y.size() + n_k);
86 else
87 return PropCost::quadratic(PropCost::LO, x.size() + n_k);
88 }
89
90
91 template<class Card>
92 void
94 y.reschedule(home, *this, PC_INT_BND);
95 k.reschedule(home, *this, PC_INT_BND);
96 }
97
98 template<class Card>
100 Bnd<Card>::lbc(Space& home, int& nb,
101 HallInfo hall[], Rank rank[], int mu[], int nu[]) {
102 int n = x.size();
103
104 /*
105 * Let I(S) denote the number of variables whose domain intersects
106 * the set S and C(S) the number of variables whose domain is containded
107 * in S. Let further min_cap(S) be the minimal number of variables
108 * that must be assigned to values, that is
109 * min_cap(S) is the sum over all l[i] for a value v_i that is an
110 * element of S.
111 *
112 * A failure set is a set F if
113 * I(F) < min_cap(F)
114 * An unstable set is a set U if
115 * I(U) = min_cap(U)
116 * A stable set is a set S if
117 * C(S) > min_cap(S) and S intersetcs nor
118 * any failure set nor any unstable set
119 * forall unstable and failure sets
120 *
121 * failure sets determine the satisfiability of the LBC
122 * unstable sets have to be pruned
123 * stable set do not have to be pruned
124 *
125 * hall[].ps ~ stores the unstable
126 * sets that have to be pruned
127 * hall[].s ~ stores sets that must not be pruned
128 * hall[].h ~ contains stable and unstable sets
129 * hall[].d ~ contains the difference between interval bounds, i.e.
130 * the minimal capacity of the interval
131 * hall[].t ~ contains the critical capacity pointer, pointing to the
132 * values
133 */
134
135 // LBC lower bounds
136
137 int i = 0;
138 int j = 0;
139 int w = 0;
140 int z = 0;
141 int v = 0;
142
143 //initialization of the tree structure
144 int rightmost = nb + 1; // rightmost accesible value in bounds
145 int bsize = nb + 2;
146 w = rightmost;
147
148 // test
149 // unused but uninitialized
150 hall[0].d = 0;
151 hall[0].s = 0;
152 hall[0].ps = 0;
153
154 for (i = bsize; --i; ) { // i must not be zero
155 int pred = i - 1;
156 hall[i].s = pred;
157 hall[i].ps = pred;
158 hall[i].d = lps.sumup(hall[pred].bounds, hall[i].bounds - 1);
159
160 /* Let [hall[i].bounds,hall[i-1].bounds]=:I
161 * If the capacity is zero => min_cap(I) = 0
162 * => I cannot be a failure set
163 * => I is an unstable set
164 */
165 if (hall[i].d == 0) {
166 hall[pred].h = w;
167 } else {
168 hall[w].h = pred;
169 w = pred;
170 }
171 }
172
173 w = rightmost;
174 for (i = bsize; i--; ) { // i can be zero
175 hall[i].t = i - 1;
176 if (hall[i].d == 0) {
177 hall[i].t = w;
178 } else {
179 hall[w].t = i;
180 w = i;
181 }
182 }
183
184 /*
185 * The algorithm assigns to each value v in bounds
186 * empty buckets corresponding to the minimal capacity l[i] to be
187 * filled for v. (the buckets correspond to hall[].d containing the
188 * difference between the interval bounds) Processing it
189 * searches for the smallest value v in dom(x_i) that has an
190 * empty bucket, i.e. if all buckets are filled it is guaranteed
191 * that there are at least l[i] variables that will be
192 * instantiated to v. Since the buckets are initially empty,
193 * they are considered as FAILURE SETS
194 */
195
196 for (i = 0; i < n; i++) {
197 // visit intervals in increasing max order
198 int x0 = rank[mu[i]].min;
199 int y = rank[mu[i]].max;
200 int succ = x0 + 1;
201 z = pathmax_t(hall, succ);
202 j = hall[z].t;
203
204 /*
205 * POTENTIALLY STABLE SET:
206 * z \neq succ \Leftrigharrow z>succ, i.e.
207 * min(D_{\mu(i)}) is guaranteed to occur min(K_i) times
208 * \Rightarrow [x0, min(y,z)] is potentially stable
209 */
210
211 if (z != succ) {
212 w = pathmax_ps(hall, succ);
213 v = hall[w].ps;
214 pathset_ps(hall, succ, w, w);
215 w = std::min(y, z);
216 pathset_ps(hall, hall[w].ps, v, w);
217 hall[w].ps = v;
218 }
219
220 /*
221 * STABLE SET:
222 * being stable implies being potentially stable, i.e.
223 * [hall[y].ps, hall[y].bounds-1] is the largest stable subset of
224 * [hall[j].bounds, hall[y].bounds-1].
225 */
226
227 if (hall[z].d <= lps.sumup(hall[y].bounds, hall[z].bounds - 1)) {
228 w = pathmax_s(hall, hall[y].ps);
229 pathset_s(hall, hall[y].ps, w, w);
230 // Path compression
231 v = hall[w].s;
232 pathset_s(hall, hall[y].s, v, y);
233 hall[y].s = v;
234 } else {
235 /*
236 * FAILURE SET:
237 * If the considered interval [x0,y] is neither POTENTIALLY STABLE
238 * nor STABLE there are still buckets that can be filled,
239 * therefore d can be decreased. If d equals zero the intervals
240 * minimum capacity is met and thepath can be compressed to the
241 * next value having an empty bucket.
242 * see DOMINATION in "ubc"
243 */
244 if (--hall[z].d == 0) {
245 hall[z].t = z + 1;
246 z = pathmax_t(hall, hall[z].t);
247 hall[z].t = j;
248 }
249
250 /*
251 * FINDING NEW LOWER BOUND:
252 * If the lower bound belongs to an unstable or a stable set,
253 * remind the new value we might assigned to the lower bound
254 * in case the variable doesn't belong to a stable set.
255 */
256 if (hall[x0].h > x0) {
257 hall[i].newBound = pathmax_h(hall, x0);
258 w = hall[i].newBound;
259 pathset_h(hall, x0, w, w); // path compression
260 } else {
261 // Do not shrink the variable: take old min as new min
262 hall[i].newBound = x0;
263 }
264
265 /* UNSTABLE SET
266 * If an unstable set is discovered
267 * the difference between the interval bounds is equal to the
268 * number of variables whose domain intersect the interval
269 * (see ZEROTEST in "gcc")
270 */
271 // CLEARLY THIS WAS NOT STABLE == UNSTABLE
272 if (hall[z].d == lps.sumup(hall[y].bounds, hall[z].bounds - 1)) {
273 if (hall[y].h > y)
274 /*
275 * y is not the end of the potentially stable set
276 * thus ensure that the potentially stable superset is marked
277 */
278 y = hall[y].h;
279 // Equivalent to pathmax since the path is fully compressed
280 pathset_h(hall, hall[y].h, j-1, y);
281 // mark the new unstable set [j,y]
282 hall[y].h = j-1;
283 }
284 }
285 pathset_t(hall, succ, z, z); // path compression
286 }
287
288 /* If there is a FAILURE SET left the minimum occurences of the values
289 * are not guaranteed. In order to satisfy the LBC the last value
290 * in the stable and unstable datastructure hall[].h must point to
291 * the sentinel at the beginning of bounds.
292 */
293 if (hall[nb].h != 0)
294 return ES_FAILED;
295
296 // Perform path compression over all elements in
297 // the stable interval data structure. This data
298 // structure will no longer be modified and will be
299 // accessed n or 2n times. Therefore, we can afford
300 // a linear time compression.
301 for (i = bsize; --i;)
302 if (hall[i].s > i)
303 hall[i].s = w;
304 else
305 w = i;
306
307 /*
308 * UPDATING LOWER BOUND:
309 * For all variables that are not a subset of a stable set,
310 * shrink the lower bound, i.e. forall stable sets S we have:
311 * x0 < S_min <= y <=S_max or S_min <= x0 <= S_max < y
312 * that is [x0,y] is NOT a proper subset of any stable set S
313 */
314 for (i = n; i--; ) {
315 int x0 = rank[mu[i]].min;
316 int y = rank[mu[i]].max;
317 // update only those variables that are not contained in a stable set
318 if ((hall[x0].s <= x0) || (y > hall[x0].s)) {
319 // still have to check this out, how skipping works (consider dominated indices)
320 int m = lps.skipNonNullElementsRight(hall[hall[i].newBound].bounds);
321 GECODE_ME_CHECK(x[mu[i]].gq(home, m));
322 }
323 }
324
325 // LBC narrow upper bounds
326 w = 0;
327 for (i = 0; i <= nb; i++) {
328 hall[i].d = lps.sumup(hall[i].bounds, hall[i + 1].bounds - 1);
329 if (hall[i].d == 0) {
330 hall[i].t = w;
331 } else {
332 hall[w].t = i;
333 w = i;
334 }
335 }
336 hall[w].t = i;
337
338 w = 0;
339 for (i = 1; i <= nb; i++)
340 if (hall[i - 1].d == 0) {
341 hall[i].h = w;
342 } else {
343 hall[w].h = i;
344 w = i;
345 }
346 hall[w].h = i;
347
348 for (i = n; i--; ) {
349 // visit intervals in decreasing min order
350 // i.e. minsorted from right to left
351 int x0 = rank[nu[i]].max;
352 int y = rank[nu[i]].min;
353 int pred = x0 - 1; // predecessor of x0 in the indices
354 z = pathmin_t(hall, pred);
355 j = hall[z].t;
356
357 /* If the variable is not in a discovered stable set
358 * (see above condition for STABLE SET)
359 */
360 if (hall[z].d > lps.sumup(hall[z].bounds, hall[y].bounds - 1)) {
361 // FAILURE SET
362 if (--hall[z].d == 0) {
363 hall[z].t = z - 1;
364 z = pathmin_t(hall, hall[z].t);
365 hall[z].t = j;
366 }
367 // FINDING NEW UPPER BOUND
368 if (hall[x0].h < x0) {
369 w = pathmin_h(hall, hall[x0].h);
370 hall[i].newBound = w;
371 pathset_h(hall, x0, w, w); // path compression
372 } else {
373 hall[i].newBound = x0;
374 }
375 // UNSTABLE SET
376 if (hall[z].d == lps.sumup(hall[z].bounds, hall[y].bounds - 1)) {
377 if (hall[y].h < y) {
378 y = hall[y].h;
379 }
380 int succj = j + 1;
381 // mark new unstable set [y,j]
382 pathset_h(hall, hall[y].h, succj, y);
383 hall[y].h = succj;
384 }
385 }
386 pathset_t(hall, pred, z, z);
387 }
388
389 // UPDATING UPPER BOUND
390 for (i = n; i--; ) {
391 int x0 = rank[nu[i]].min;
392 int y = rank[nu[i]].max;
393 if ((hall[x0].s <= x0) || (y > hall[x0].s)) {
394 int m = lps.skipNonNullElementsLeft(hall[hall[i].newBound].bounds - 1);
395 GECODE_ME_CHECK(x[nu[i]].lq(home, m));
396 }
397 }
398 return ES_OK;
399 }
400
401
402 template<class Card>
404 Bnd<Card>::ubc(Space& home, int& nb,
405 HallInfo hall[], Rank rank[], int mu[], int nu[]) {
406 int rightmost = nb + 1; // rightmost accesible value in bounds
407 int bsize = nb + 2; // number of unique bounds including sentinels
408
409 //Narrow lower bounds (UBC)
410
411 /*
412 * Initializing tree structure with the values from bounds
413 * and the interval capacities of neighboured values
414 * from left to right
415 */
416
417
418 hall[0].h = 0;
419 hall[0].t = 0;
420 hall[0].d = 0;
421
422 for (int i = bsize; --i; ) {
423 hall[i].h = hall[i].t = i-1;
424 hall[i].d = ups.sumup(hall[i-1].bounds, hall[i].bounds - 1);
425 }
426
427 int n = x.size();
428
429 for (int i = 0; i < n; i++) {
430 // visit intervals in increasing max order
431 int x0 = rank[mu[i]].min;
432 int succ = x0 + 1;
433 int y = rank[mu[i]].max;
434 int z = pathmax_t(hall, succ);
435 int j = hall[z].t;
436
437 /* DOMINATION:
438 * v^i_j denotes
439 * unused values in the current interval. If the difference d
440 * between to critical capacities v^i_j and v^i_z
441 * is equal to zero, j dominates z
442 *
443 * i.e. [hall[l].bounds, hall[nb+1].bounds] is not left-maximal and
444 * [hall[j].bounds, hall[l].bounds] is a Hall set iff
445 * [hall[j].bounds, hall[l].bounds] processing a variable x_i uses up a value in the interval
446 * [hall[z].bounds,hall[z+1].bounds] according to the intervals
447 * capacity. Therefore, if d = 0
448 * the considered value has already been used by processed variables
449 * m-times, where m = u[i] for value v_i. Since this value must not
450 * be reconsidered the path can be compressed
451 */
452 if (--hall[z].d == 0) {
453 hall[z].t = z + 1;
454 z = pathmax_t(hall, hall[z].t);
455 if (z >= bsize)
456 z--;
457 hall[z].t = j;
458 }
459 pathset_t(hall, succ, z, z); // path compression
460
461 /* NEGATIVE CAPACITY:
462 * A negative capacity results in a failure.Since a
463 * negative capacity signals that the number of variables
464 * whose domain is contained in the set S is larger than
465 * the maximum capacity of S => UBC is not satisfiable,
466 * i.e. there are more variables than values to instantiate them
467 */
468 if (hall[z].d < ups.sumup(hall[y].bounds, hall[z].bounds - 1))
469 return ES_FAILED;
470
471 /* UPDATING LOWER BOUND:
472 * If the lower bound min_i lies inside a Hall interval [a,b]
473 * i.e. a <= min_i <=b <= max_i
474 * min_i is set to min_i := b+1
475 */
476 if (hall[x0].h > x0) {
477 int w = pathmax_h(hall, hall[x0].h);
478 int m = hall[w].bounds;
479 GECODE_ME_CHECK(x[mu[i]].gq(home, m));
480 pathset_h(hall, x0, w, w); // path compression
481 }
482
483 /* ZEROTEST:
484 * (using the difference between capacity pointers)
485 * zero capacity => the difference between critical capacity
486 * pointers is equal to the maximum capacity of the interval,i.e.
487 * the number of variables whose domain is contained in the
488 * interval is equal to the sum over all u[i] for a value v_i that
489 * lies in the Hall-Intervall which can also be thought of as a
490 * Hall-Set
491 *
492 * ZeroTestLemma: Let k and l be succesive critical indices.
493 * v^i_k=0 => v^i_k = max_i+1-l+d
494 * <=> v^i_k = y + 1 - z + d
495 * <=> d = z-1-y
496 * if this equation holds the interval [j,z-1] is a hall intervall
497 */
498
499 if (hall[z].d == ups.sumup(hall[y].bounds, hall[z].bounds - 1)) {
500 /*
501 *mark hall interval [j,z-1]
502 * hall pointers form a path to the upper bound of the interval
503 */
504 int predj = j - 1;
505 pathset_h(hall, hall[y].h, predj, y);
506 hall[y].h = predj;
507 }
508 }
509
510 /* Narrow upper bounds (UBC)
511 * symmetric to the narrowing of the lower bounds
512 */
513 for (int i = 0; i < rightmost; i++) {
514 hall[i].h = hall[i].t = i+1;
515 hall[i].d = ups.sumup(hall[i].bounds, hall[i+1].bounds - 1);
516 }
517
518 for (int i = n; i--; ) {
519 // visit intervals in decreasing min order
520 int x0 = rank[nu[i]].max;
521 int pred = x0 - 1;
522 int y = rank[nu[i]].min;
523 int z = pathmin_t(hall, pred);
524 int j = hall[z].t;
525
526 // DOMINATION:
527 if (--hall[z].d == 0) {
528 hall[z].t = z - 1;
529 z = pathmin_t(hall, hall[z].t);
530 hall[z].t = j;
531 }
532 pathset_t(hall, pred, z, z);
533
534 // NEGATIVE CAPACITY:
535 if (hall[z].d < ups.sumup(hall[z].bounds,hall[y].bounds-1))
536 return ES_FAILED;
537
538 /* UPDATING UPPER BOUND:
539 * If the upper bound max_i lies inside a Hall interval [a,b]
540 * i.e. min_i <= a <= max_i < b
541 * max_i is set to max_i := a-1
542 */
543 if (hall[x0].h < x0) {
544 int w = pathmin_h(hall, hall[x0].h);
545 int m = hall[w].bounds - 1;
546 GECODE_ME_CHECK(x[nu[i]].lq(home, m));
547 pathset_h(hall, x0, w, w);
548 }
549
550 // ZEROTEST
551 if (hall[z].d == ups.sumup(hall[z].bounds, hall[y].bounds - 1)) {
552 //mark hall interval [y,j]
553 pathset_h(hall, hall[y].h, j+1, y);
554 hall[y].h = j+1;
555 }
556 }
557 return ES_OK;
558 }
559
560 template<class Card>
563 // Remove all values with 0 max occurrence
564 // and remove corresponding occurrence variables from k
565
566 // The number of zeroes
567 int n_z = 0;
568 for (int i=k.size(); i--;)
569 if (k[i].max() == 0)
570 n_z++;
571
572 if (n_z > 0) {
573 Region r;
574 int* z = r.alloc<int>(n_z);
575 n_z = 0;
576 int n_k = 0;
577 for (int i=0; i<k.size(); i++)
578 if (k[i].max() == 0) {
579 z[n_z++] = k[i].card();
580 } else {
581 k[n_k++] = k[i];
582 }
583 k.size(n_k);
585 for (int i=x.size(); i--;) {
586 Iter::Values::Array zi(z,n_z);
587 GECODE_ME_CHECK(x[i].minus_v(home,zi,false));
588 }
589 lps.reinit(); ups.reinit();
590 }
591 return ES_OK;
592 }
593
594 template<class Card>
597 if (IntView::me(med) == ME_INT_VAL) {
598 GECODE_ES_CHECK(prop_val<Card>(home,*this,y,k));
599 return home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_BND));
600 }
601
602 if (Card::propagate)
603 GECODE_ES_CHECK(pruneCards(home));
604
605 Region r;
606 int* count = r.alloc<int>(k.size());
607
608 for (int i = k.size(); i--; )
609 count[i] = 0;
610 bool all_assigned = true;
611 int noa = 0;
612 for (int i = x.size(); i--; ) {
613 if (x[i].assigned()) {
614 noa++;
615 int idx;
616 // reduction is essential for order on value nodes in dom
617 // hence introduce test for failed lookup
618 if (!lookupValue(k,x[i].val(),idx))
619 return ES_FAILED;
620 count[idx]++;
621 } else {
622 all_assigned = false;
623 // We only need the counts in the view case or when all
624 // x are assigned
625 if (!Card::propagate)
626 break;
627 }
628 }
629
630 if (Card::propagate) {
631 // before propagation performs inferences on cardinality variables:
632 if (noa > 0)
633 for (int i = k.size(); i--; )
634 if (!k[i].assigned()) {
635 GECODE_ME_CHECK(k[i].lq(home, x.size() - (noa - count[i])));
636 GECODE_ME_CHECK(k[i].gq(home, count[i]));
637 }
638
639 if (!card_consistent<Card>(x, k))
640 return ES_FAILED;
641
643
644 // Cardinalities may have been modified, so recompute
645 // count and all_assigned
646 for (int i = k.size(); i--; )
647 count[i] = 0;
648 all_assigned = true;
649 for (int i = x.size(); i--; ) {
650 if (x[i].assigned()) {
651 int idx;
652 // reduction is essential for order on value nodes in dom
653 // hence introduce test for failed lookup
654 if (!lookupValue(k,x[i].val(),idx))
655 return ES_FAILED;
656 count[idx]++;
657 } else {
658 // We won't need the remaining counts, they're only used when
659 // all x are assigned
660 all_assigned = false;
661 break;
662 }
663 }
664 }
665
666 if (all_assigned) {
667 for (int i = k.size(); i--; )
668 GECODE_ME_CHECK(k[i].eq(home, count[i]));
669 return home.ES_SUBSUMED(*this);
670 }
671
672 if (Card::propagate)
673 GECODE_ES_CHECK(pruneCards(home));
674
675 int n = x.size();
676
677 int* mu = r.alloc<int>(n);
678 int* nu = r.alloc<int>(n);
679
680 for (int i = n; i--; )
681 nu[i] = mu[i] = i;
682
683 // Create sorting permutation mu according to the variables upper bounds
684 MaxInc<IntView> max_inc(x);
686
687 // Create sorting permutation nu according to the variables lower bounds
688 MinInc<IntView> min_inc(x);
690
691 // Sort the cardinality bounds by index
692 MinIdx<Card> min_idx;
693 Support::quicksort<Card, MinIdx<Card> >(&k[0], k.size(), min_idx);
694
695 if (!lps) {
696 assert(!ups);
697 lps.init(home, k, false);
698 ups.init(home, k, true);
699 } else if (Card::propagate) {
700 // if there has been a change to the cardinality variables
701 // reconstruction of the partial sum structure is necessary
702 if (lps.check_update_min(k))
703 lps.init(home, k, false);
704 if (ups.check_update_max(k))
705 ups.init(home, k, true);
706 }
707
708 // assert that the minimal value of the partial sum structure for
709 // LBC is consistent with the smallest value a variable can take
710 assert(lps.minValue() <= x[nu[0]].min());
711 // assert that the maximal value of the partial sum structure for
712 // UBC is consistent with the largest value a variable can take
713
714 /*
715 * Setup rank and bounds info
716 * Since this implementation is based on the theory of Hall Intervals
717 * additional datastructures are needed in order to represent these
718 * intervals and the "partial-sum" data structure (cf."gcc/bnd-sup.hpp")
719 *
720 */
721
722 HallInfo* hall = r.alloc<HallInfo>(2 * n + 2);
723 Rank* rank = r.alloc<Rank>(n);
724
725 int nb = 0;
726 // setup bounds and rank
727 int min = x[nu[0]].min();
728 int max = x[mu[0]].max() + 1;
729 int last = lps.firstValue + 1; //equivalent to last = min -2
730 hall[0].bounds = last;
731
732 /*
733 * First the algorithm merges the arrays minsorted and maxsorted
734 * into bounds i.e. hall[].bounds contains the ordered union
735 * of the lower and upper domain bounds including two sentinels
736 * at the beginning and at the end of the set
737 * ( the upper variable bounds in this union are increased by 1 )
738 */
739
740 {
741 int i = 0;
742 int j = 0;
743 while (true) {
744 if (i < n && min < max) {
745 if (min != last) {
746 last = min;
747 hall[++nb].bounds = last;
748 }
749 rank[nu[i]].min = nb;
750 if (++i < n)
751 min = x[nu[i]].min();
752 } else {
753 if (max != last) {
754 last = max;
755 hall[++nb].bounds = last;
756 }
757 rank[mu[j]].max = nb;
758 if (++j == n)
759 break;
760 max = x[mu[j]].max() + 1;
761 }
762 }
763 }
764
765 int rightmost = nb + 1; // rightmost accesible value in bounds
766 hall[rightmost].bounds = ups.lastValue + 1 ;
767
768 if (Card::propagate) {
769 skip_lbc = true;
770 for (int i = k.size(); i--; )
771 if (k[i].min() != 0) {
772 skip_lbc = false;
773 break;
774 }
775 }
776
777 if (!card_fixed && !skip_lbc)
778 GECODE_ES_CHECK((lbc(home, nb, hall, rank, mu, nu)));
779
780 GECODE_ES_CHECK((ubc(home, nb, hall, rank, mu, nu)));
781
782 if (Card::propagate)
784
785 for (int i = k.size(); i--; )
786 count[i] = 0;
787 for (int i = x.size(); i--; )
788 if (x[i].assigned()) {
789 int idx;
790 if (!lookupValue(k,x[i].val(),idx))
791 return ES_FAILED;
792 count[idx]++;
793 } else {
794 // We won't need the remaining counts, they're only used when
795 // all x are assigned
796 return ES_NOFIX;
797 }
798
799 for (int i = k.size(); i--; )
800 GECODE_ME_CHECK(k[i].eq(home, count[i]));
801
802 return home.ES_SUBSUMED(*this);
803 }
804
805
806 template<class Card>
810 bool cardfix = true;
811 for (int i=k.size(); i--; )
812 if (!k[i].assigned()) {
813 cardfix = false; break;
814 }
815 bool nolbc = true;
816 for (int i=k.size(); i--; )
817 if (k[i].min() != 0) {
818 nolbc = false; break;
819 }
820
822
823 if (isDistinct<Card>(x,k))
824 return Distinct::Bnd<IntView>::post(home,x);
825
826 (void) new (home) Bnd<Card>(home,x,k,cardfix,nolbc);
827 return ES_OK;
828 }
829
830}}}
831
832// STATISTICS: int-prop
NodeType t
Type of node.
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
Base-class for both propagators and branchers.
Definition core.hpp:628
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3252
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1607
Home class for posting propagators
Definition core.hpp:856
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
Definition bnd.hpp:476
Bounds consistent global cardinality propagator.
Definition gcc.hh:113
Bnd(Space &home, Bnd< Card > &p)
Constructor for cloning p.
Definition bnd.hpp:56
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
Definition bnd.hpp:808
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition bnd.hpp:75
ViewArray< Card > k
Array containing either fixed cardinalities or CardViews.
Definition gcc.hh:120
ExecStatus ubc(Space &home, int &nb, HallInfo hall[], Rank rank[], int mu[], int nu[])
Upper Bounds constraint (UBC) stating Hence the ubc constraints the variables such that no value oc...
Definition bnd.hpp:404
ExecStatus pruneCards(Space &home)
Prune cardinality variables with 0 maximum occurrence.
Definition bnd.hpp:562
ViewArray< IntView > y
Views on which to perform value-propagation (subset of x)
Definition gcc.hh:118
virtual size_t dispose(Space &home)
Destructor.
Definition bnd.hpp:66
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition bnd.hpp:596
virtual void reschedule(Space &home)
Schedule function.
Definition bnd.hpp:93
ViewArray< IntView > x
Views on which to perform bounds-propagation.
Definition gcc.hh:116
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost funtion.
Definition bnd.hpp:81
ExecStatus lbc(Space &home, int &nb, HallInfo hall[], Rank rank[], int mu[], int nu[])
Lower Bounds constraint (LBC) stating Hence the lbc constraints the variables such that every value...
Definition bnd.hpp:100
Container class provding information about the Hall structure of the problem variables.
Definition bnd-sup.hpp:456
int t
Critical capacity pointer t represents a predecessor function where denotes the predecessor of i in ...
Definition bnd-sup.hpp:465
int newBound
Bound update.
Definition bnd-sup.hpp:493
int h
Hall set pointer.
Definition bnd-sup.hpp:482
int bounds
Represents the union of all lower and upper domain bounds.
Definition bnd-sup.hpp:459
int s
Stable Set pointer.
Definition bnd-sup.hpp:484
int ps
Potentially Stable Set pointer.
Definition bnd-sup.hpp:486
int d
Difference between critical capacities.
Definition bnd-sup.hpp:473
Compares two indices i, j of two views according to the ascending order of the views upper bounds.
Definition bnd-sup.hpp:176
Compares two cardinality views according to the index.
Definition bnd-sup.hpp:221
Compares two indices i, j of two views according to the ascending order of the views lower bounds.
Definition bnd-sup.hpp:199
Maps domain bounds to their position in hall[].bounds.
Definition bnd-sup.hpp:154
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition int.hpp:66
Value iterator for array of integers
Propagation cost.
Definition core.hpp:486
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition core.hpp:4787
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:4796
Base-class for propagators.
Definition core.hpp:1064
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1742
static ModEvent me(const ModEventDelta &med)
Definition view.hpp:552
View arrays.
Definition array.hpp:253
void update(Space &home, ViewArray< View > &a)
Update array to be a clone of array a.
Definition array.hpp:1328
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition array.hpp:1341
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1156
bool card_consistent(ViewArray< IntView > &x, ViewArray< Card > &k)
Consistency check, whether the cardinality values are feasible.
Definition bnd-sup.hpp:139
ExecStatus prop_card(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k)
Bounds consistency check for cardinality variables.
Definition bnd-sup.hpp:74
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition core.hpp:3576
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
int pathmin_h(const HallInfo hall[], int i)
Path minimum for hall pointer structure.
Definition bnd-sup.hpp:549
int pathmax_t(const HallInfo hall[], int i)
Path maximum for capacity pointer structure.
Definition bnd-sup.hpp:579
void pathset_ps(HallInfo hall[], int start, int end, int to)
Path compression for potentially stable set structure.
Definition bnd-sup.hpp:507
bool isDistinct(ViewArray< IntView > &x, ViewArray< Card > &k)
Check if GCC is equivalent to distinct.
Definition post.hpp:138
int pathmax_s(const HallInfo hall[], int i)
Path maximum for stable set pointer structure.
Definition bnd-sup.hpp:587
void pathset_t(HallInfo hall[], int start, int end, int to)
Path compression for capacity pointer structure.
Definition bnd-sup.hpp:523
ExecStatus prop_val(Space &home, Propagator &p, ViewArray< IntView > &x, ViewArray< Card > &k)
Definition val.hpp:92
int pathmin_t(const HallInfo hall[], int i)
Path minimum for capacity pointer structure.
Definition bnd-sup.hpp:556
void pathset_h(HallInfo hall[], int start, int end, int to)
Path compression for hall pointer structure.
Definition bnd-sup.hpp:531
void pathset_s(HallInfo hall[], int start, int end, int to)
Path compression for stable set structure.
Definition bnd-sup.hpp:515
bool lookupValue(T &a, int v, int &i)
Return index of v in array a.
Definition view.hpp:45
int pathmax_h(const HallInfo hall[], int i)
Path maximum for hall pointer structure.
Definition bnd-sup.hpp:572
ExecStatus postSideConstraints(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post side constraints for the GCC.
Definition post.hpp:60
int pathmax_ps(const HallInfo hall[], int i)
Path maximum for potentially stable set pointer structure.
Definition bnd-sup.hpp:594
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
Definition var-type.hpp:65
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:91
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition var-type.hpp:56
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode toplevel namespace
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition set.hh:767
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
Definition set.hh:767
#define forceinline
Definition config.hpp:187