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 *
6 * Contributing authors:
7 * Samuel Gagnon <samuel.gagnon92@gmail.com>
8
9 * Copyright:
10 * Christian Schulte, 2012
11 * Samuel Gagnon, 2018
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_BRANCH_HH
39#define GECODE_INT_BRANCH_HH
40
41#include <gecode/int.hh>
42
43/**
44 * \namespace Gecode::Int::Branch
45 * \brief Integer branchers
46 */
47
48namespace Gecode { namespace Int { namespace Branch {
49
50 /**
51 * \defgroup FuncIntViewSel Merit-based integer view selection for branchers
52 *
53 * Contains merit-based view selection strategies on integer
54 * views that can be used together with the generic view/value
55 * brancher classes.
56 *
57 * All merit-based view selection classes require
58 * \code #include <gecode/int/branch.hh> \endcode
59 * \ingroup Other
60 */
61
62 /**
63 * \brief Merit class for mimimum of integer views
64 *
65 * Requires \code #include <gecode/int/branch.hh> \endcode
66 * \ingroup FuncIntViewSel
67 */
68 template<class View>
69 class MeritMin : public MeritBase<View,int> {
70 public:
71 using typename MeritBase<View,int>::Var;
72 /// Constructor for initialization
73 MeritMin(Space& home, const VarBranch<Var>& vb);
74 /// Constructor for cloning
75 MeritMin(Space& home, MeritMin& m);
76 /// Return minimum as merit for view \a x at position \a i
77 int operator ()(const Space& home, View x, int i);
78 };
79
80 /**
81 * \brief Merit class for maximum
82 *
83 * Requires \code #include <gecode/int/branch.hh> \endcode
84 * \ingroup FuncIntViewSel
85 */
86 template<class View>
87 class MeritMax : public MeritBase<View,int> {
88 public:
89 using typename MeritBase<View,int>::Var;
90 /// Constructor for initialization
91 MeritMax(Space& home, const VarBranch<Var>& vb);
92 /// Constructor for cloning
93 MeritMax(Space& home, MeritMax& m);
94 /// Return maximum as merit for view \a x at position \a i
95 int operator ()(const Space& home, View x, int i);
96 };
97
98 /**
99 * \brief Merit class for size
100 *
101 * Requires \code #include <gecode/int/branch.hh> \endcode
102 * \ingroup FuncIntViewSel
103 */
104 template<class View>
105 class MeritSize : public MeritBase<View,unsigned int> {
106 public:
107 using typename MeritBase<View,unsigned int>::Var;
108 /// Constructor for initialization
109 MeritSize(Space& home, const VarBranch<Var>& vb);
110 /// Constructor for cloning
111 MeritSize(Space& home, MeritSize& m);
112 /// Return size as merit for view \a x at position \a i
113 unsigned int operator ()(const Space& home, View x, int i);
114 };
115
116 /**
117 * \brief Merit class for degree over size
118 *
119 * Requires \code #include <gecode/int/branch.hh> \endcode
120 * \ingroup FuncIntViewSel
121 */
122 template<class View>
123 class MeritDegreeSize : public MeritBase<View,double> {
124 public:
125 using typename MeritBase<View,double>::Var;
126 /// Constructor for initialization
127 MeritDegreeSize(Space& home, const VarBranch<Var>& vb);
128 /// Constructor for cloning
129 MeritDegreeSize(Space& home, MeritDegreeSize& m);
130 /// Return degree over size as merit for view \a x at position \a i
131 double operator ()(const Space& home, View x, int i);
132 };
133
134 /**
135 * \brief Merit class for AFC over size
136 *
137 * Requires \code #include <gecode/int/branch.hh> \endcode
138 * \ingroup FuncIntViewSel
139 */
140 template<class View>
141 class MeritAFCSize : public MeritBase<View,double> {
142 using typename MeritBase<View,double>::Var;
143 protected:
144 /// AFC information
145 AFC afc;
146 public:
147 /// Constructor for initialization
148 MeritAFCSize(Space& home, const VarBranch<Var>& vb);
149 /// Constructor for cloning
150 MeritAFCSize(Space& home, MeritAFCSize& m);
151 /// Return AFC over size as merit for view \a x at position \a i
152 double operator ()(const Space& home, View x, int i);
153 /// Whether dispose must always be called (that is, notice is needed)
154 bool notice(void) const;
155 /// Dispose view selection
156 void dispose(Space& home);
157 };
158
159 /**
160 * \brief Merit class for action over size
161 *
162 * Requires \code #include <gecode/int/branch.hh> \endcode
163 * \ingroup FuncIntViewSel
164 */
165 template<class View>
166 class MeritActionSize : public MeritBase<View,double> {
167 using typename MeritBase<View,double>::Var;
168 protected:
169 /// Action information
170 Action action;
171 public:
172 /// Constructor for initialization
173 MeritActionSize(Space& home, const VarBranch<Var>& vb);
174 /// Constructor for cloning
175 MeritActionSize(Space& home, MeritActionSize& m);
176 /// Return action over size as merit for view \a x at position \a i
177 double operator ()(const Space& home, View x, int i);
178 /// Whether dispose must always be called (that is, notice is needed)
179 bool notice(void) const;
180 /// Dispose view selection
181 void dispose(Space& home);
182 };
183
184 /**
185 * \brief Merit class for CHB over size
186 *
187 * Requires \code #include <gecode/int/branch.hh> \endcode
188 * \ingroup FuncIntViewSel
189 */
190 template<class View>
191 class MeritCHBSize : public MeritBase<View,double> {
192 using typename MeritBase<View,double>::Var;
193 protected:
194 /// CHB information
195 CHB chb;
196 public:
197 /// Constructor for initialization
198 MeritCHBSize(Space& home, const VarBranch<Var>& vb);
199 /// Constructor for cloning
200 MeritCHBSize(Space& home, MeritCHBSize& m);
201 /// Return size over action as merit for view \a x at position \a i
202 double operator ()(const Space& home, View x, int i);
203 /// Whether dispose must always be called (that is, notice is needed)
204 bool notice(void) const;
205 /// Dispose view selection
206 void dispose(Space& home);
207 };
208
209 /**
210 * \brief Merit class for minimum regret
211 *
212 * Requires \code #include <gecode/int/branch.hh> \endcode
213 * \ingroup FuncIntViewSel
214 */
215 template<class View>
216 class MeritRegretMin : public MeritBase<View,unsigned int> {
217 public:
218 using typename MeritBase<View,unsigned int>::Var;
219 /// Constructor for initialization
220 MeritRegretMin(Space& home, const VarBranch<Var>& vb);
221 /// Constructor for cloning
222 MeritRegretMin(Space& home, MeritRegretMin& m);
223 /// Return minimum regret as merit for view \a x at position \a i
224 unsigned int operator ()(const Space& home, View x, int i);
225 };
226
227 /**
228 * \brief Merit class for maximum regret
229 *
230 * Requires \code #include <gecode/int/branch.hh> \endcode
231 * \ingroup FuncIntViewSel
232 */
233 template<class View>
234 class MeritRegretMax : public MeritBase<View,unsigned int> {
235 public:
236 using typename MeritBase<View,unsigned int>::Var;
237 /// Constructor for initialization
238 MeritRegretMax(Space& home, const VarBranch<Var>& vb);
239 /// Constructor for cloning
240 MeritRegretMax(Space& home, MeritRegretMax& m);
241 /// Return maximum regret as merit for view \a x at position \a i
242 unsigned int operator ()(const Space& home, View x, int i);
243 };
244
245}}}
246
247#include <gecode/int/branch/merit.hpp>
248
249namespace Gecode { namespace Int { namespace Branch {
250
251 /// Return view selectors for integer views
252 GECODE_INT_EXPORT
253 ViewSel<IntView>* viewsel(Space& home, const IntVarBranch& ivb);
254 /// Return view selectors for Boolean views
255 GECODE_INT_EXPORT
256 ViewSel<BoolView>* viewsel(Space& home, const BoolVarBranch& bvb);
257
258}}}
259
260namespace Gecode { namespace Int { namespace Branch {
261
262 /**
263 * \defgroup FuncIntValSel Integer value selection for brancher
264 *
265 * Contains a description of value selection strategies on integer
266 * views that can be used together with the generic view/value
267 * branchers.
268 *
269 * All value selection classes require
270 * \code #include <gecode/int/branch.hh> \endcode
271 * \ingroup Other
272 */
273
274 /**
275 * \brief Value selection class for mimimum of view
276 *
277 * Requires \code #include <gecode/int/branch.hh> \endcode
278 * \ingroup FuncIntValSel
279 */
280 template<class View>
281 class ValSelMin : public ValSel<View,int> {
282 public:
283 using typename ValSel<View,int>::Var;
284 /// Constructor for initialization
285 ValSelMin(Space& home, const ValBranch<Var>& vb);
286 /// Constructor for cloning
287 ValSelMin(Space& home, ValSelMin& vs);
288 /// Return value of view \a x at position \a i
289 int val(const Space& home, View x, int i);
290 };
291
292 /**
293 * \brief Value selection class for maximum of view
294 *
295 * Requires \code #include <gecode/int/branch.hh> \endcode
296 * \ingroup FuncIntValSel
297 */
298 template<class View>
299 class ValSelMax : public ValSel<View,int> {
300 public:
301 using typename ValSel<View,int>::Var;
302 /// Constructor for initialization
303 ValSelMax(Space& home, const ValBranch<Var>& vb);
304 /// Constructor for cloning
305 ValSelMax(Space& home, ValSelMax& vs);
306 /// Return value of view \a x at position \a i
307 int val(const Space& home, View x, int i);
308 };
309
310 /**
311 * \brief Value selection class for median of view
312 *
313 * Requires \code #include <gecode/int/branch.hh> \endcode
314 * \ingroup FuncIntValSel
315 */
316 template<class View>
317 class ValSelMed : public ValSel<View,int> {
318 public:
319 using typename ValSel<View,int>::Var;
320 /// Constructor for initialization
321 ValSelMed(Space& home, const ValBranch<Var>& vb);
322 /// Constructor for cloning
323 ValSelMed(Space& home, ValSelMed& vs);
324 /// Return value of view \a x at position i
325 int val(const Space& home, View x, int i);
326 };
327
328 /**
329 * \brief Value selection class for average of view
330 *
331 * Requires \code #include <gecode/int/branch.hh> \endcode
332 * \ingroup FuncIntValSel
333 */
334 template<class View>
335 class ValSelAvg : public ValSel<View,int> {
336 public:
337 using typename ValSel<View,int>::Var;
338 /// Constructor for initialization
339 ValSelAvg(Space& home, const ValBranch<Var>& vb);
340 /// Constructor for cloning
341 ValSelAvg(Space& home, ValSelAvg& vs);
342 /// Return value of view \a x at position \a i
343 int val(const Space& home, View x, int i);
344 };
345
346 /**
347 * \brief Value selection class for random value of view
348 *
349 * Requires \code #include <gecode/int/branch.hh> \endcode
350 * \ingroup FuncIntValSel
351 */
352 template<class View>
353 class ValSelRnd : public ValSel<View,int> {
354 using typename ValSel<View,int>::Var;
355 protected:
356 /// The used random number generator
357 Rnd r;
358 public:
359 /// Constructor for initialization
360 ValSelRnd(Space& home, const ValBranch<Var>& vb);
361 /// Constructor for cloning
362 ValSelRnd(Space& home, ValSelRnd& vs);
363 /// Return value of view \a x at position \a i
364 int val(const Space& home, View x, int i);
365 /// Whether dispose must always be called (that is, notice is needed)
366 bool notice(void) const;
367 /// Delete value selection
368 void dispose(Space& home);
369 };
370
371 /**
372 * \brief Value selection class for minimum range of integer view
373 *
374 * Requires \code #include <gecode/int/branch.hh> \endcode
375 * \ingroup FuncIntValSel
376 */
377 class ValSelRangeMin : public ValSel<IntView,int> {
378 public:
379 /// Constructor for initialization
380 ValSelRangeMin(Space& home, const ValBranch<IntVar>& vb);
381 /// Constructor for cloning
382 ValSelRangeMin(Space& home, ValSelRangeMin& vs);
383 /// Return value of integer view \a x at position \a i
384 int val(const Space& home, IntView x, int i);
385 };
386
387 /**
388 * \brief Value selection class for maximum range of integer view
389 *
390 * Requires \code #include <gecode/int/branch.hh> \endcode
391 * \ingroup FuncIntValSel
392 */
393 class ValSelRangeMax : public ValSel<IntView,int> {
394 public:
395 /// Constructor for initialization
396 ValSelRangeMax(Space& home, const ValBranch<IntVar>& vb);
397 /// Constructor for cloning
398 ValSelRangeMax(Space& home, ValSelRangeMax& vs);
399 /// Return value of integer view \a x at position \a i
400 int val(const Space& home, IntView x, int i);
401 };
402
403}}}
404
405#include <gecode/int/branch/val-sel.hpp>
406
407namespace Gecode { namespace Int { namespace Branch {
408
409 /// No-good literal for equality
410 template<class View>
411 class EqNGL : public ViewValNGL<View,int,PC_INT_VAL> {
412 using ViewValNGL<View,int,PC_INT_VAL>::x;
413 using ViewValNGL<View,int,PC_INT_VAL>::n;
414 public:
415 /// Constructor for creation
416 EqNGL(Space& home, View x, int n);
417 /// Constructor for cloning \a ngl
418 EqNGL(Space& home, EqNGL& ngl);
419 /// Test the status of the no-good literal
420 virtual NGL::Status status(const Space& home) const;
421 /// Propagate the negation of the no-good literal
422 virtual ExecStatus prune(Space& home);
423 /// Create copy
424 virtual NGL* copy(Space& home);
425 };
426
427 /// No-good literal for disequality
428 template<class View>
429 class NqNGL : public ViewValNGL<View,int,PC_INT_DOM> {
430 using ViewValNGL<View,int,PC_INT_DOM>::x;
431 using ViewValNGL<View,int,PC_INT_DOM>::n;
432 public:
433 /// Constructor for creation
434 NqNGL(Space& home, View x, int n);
435 /// Constructor for cloning \a ngl
436 NqNGL(Space& home, NqNGL& ngl);
437 /// Test the status of the no-good literal
438 virtual NGL::Status status(const Space& home) const;
439 /// Propagate the negation of the no-good literal
440 virtual ExecStatus prune(Space& home);
441 /// Create copy
442 virtual NGL* copy(Space& home);
443 };
444
445 /// No-good literal for less or equal
446 template<class View>
447 class LqNGL : public ViewValNGL<View,int,PC_INT_BND> {
448 using ViewValNGL<View,int,PC_INT_BND>::x;
449 using ViewValNGL<View,int,PC_INT_BND>::n;
450 public:
451 /// Constructor for creation
452 LqNGL(Space& home, View x, int n);
453 /// Constructor for cloning \a ngl
454 LqNGL(Space& home, LqNGL& ngl);
455 /// Test the status of the no-good literal
456 virtual NGL::Status status(const Space& home) const;
457 /// Propagate the negation of the no-good literal
458 virtual ExecStatus prune(Space& home);
459 /// Create copy
460 virtual NGL* copy(Space& home);
461 };
462
463 /// No-good literal for greater or equal
464 template<class View>
465 class GqNGL : public ViewValNGL<View,int,PC_INT_BND> {
466 using ViewValNGL<View,int,PC_INT_BND>::x;
467 using ViewValNGL<View,int,PC_INT_BND>::n;
468 public:
469 /// Constructor for creation
470 GqNGL(Space& home, View x, int n);
471 /// Constructor for cloning \a ngl
472 GqNGL(Space& home, GqNGL& ngl);
473 /// Test the status of the no-good literal
474 virtual NGL::Status status(const Space& home) const;
475 /// Propagate the negation of the no-good literal
476 virtual ExecStatus prune(Space& home);
477 /// Create copy
478 virtual NGL* copy(Space& home);
479 };
480
481}}}
482
483#include <gecode/int/branch/ngl.hpp>
484
485namespace Gecode { namespace Int { namespace Branch {
486
487 /**
488 * \defgroup FuncIntValCommit Integer value commit classes
489 *
490 * Contains the value commit classes for integer and Boolean
491 * views that can be used together with the generic view/value
492 * branchers.
493 *
494 * All value commit classes require
495 * \code #include <gecode/int/branch.hh> \endcode
496 * \ingroup Other
497 */
498
499 /**
500 * \brief Value commit class for equality
501 *
502 * Requires \code #include <gecode/int/branch.hh> \endcode
503 * \ingroup FuncIntValCommit
504 */
505 template<class View>
506 class ValCommitEq : public ValCommit<View,int> {
507 public:
508 using typename ValCommit<View,int>::Var;
509 /// Constructor for initialization
510 ValCommitEq(Space& home, const ValBranch<Var>& vb);
511 /// Constructor for cloning
512 ValCommitEq(Space& home, ValCommitEq& vc);
513 /// Commit view \a x at position \a i to value \a n for alternative \a a
514 ModEvent commit(Space& home, unsigned int a, View x, int i, int n);
515 /// Create no-good literal for alternative \a a
516 NGL* ngl(Space& home, unsigned int a, View x, int n) const;
517 /// Print on \a o the alternative \a with view \a x at position \a i and value \a n
518 void print(const Space& home, unsigned int a, View x, int i, int n,
519 std::ostream& o) const;
520 };
521
522 /**
523 * \brief Value commit class for less or equal
524 *
525 * Requires \code #include <gecode/int/branch.hh> \endcode
526 * \ingroup FuncIntValCommit
527 */
528 template<class View>
529 class ValCommitLq : public ValCommit<View,int> {
530 public:
531 using typename ValCommit<View,int>::Var;
532 /// Constructor for initialization
533 ValCommitLq(Space& home, const ValBranch<Var>& vb);
534 /// Constructor for cloning
535 ValCommitLq(Space& home, ValCommitLq& vc);
536 /// Commit view \a x at position \a i to value \a n for alternative \a a
537 ModEvent commit(Space& home, unsigned int a, View x, int i, int n);
538 /// Create no-good literal for alternative \a a
539 NGL* ngl(Space& home, unsigned int a, View x, int n) const;
540 /// Print on \a o the alternative \a with view \a x at position \a i and value \a n
541 void print(const Space& home, unsigned int a, View x, int i, int n,
542 std::ostream& o) const;
543 };
544
545 /**
546 * \brief Value commit class for greater or equal
547 *
548 * Requires \code #include <gecode/int/branch.hh> \endcode
549 * \ingroup FuncIntValCommit
550 */
551 template<class View>
552 class ValCommitGq : public ValCommit<View,int> {
553 public:
554 using typename ValCommit<View,int>::Var;
555 /// Constructor for initialization
556 ValCommitGq(Space& home, const ValBranch<Var>& vb);
557 /// Constructor for cloning
558 ValCommitGq(Space& home, ValCommitGq& vc);
559 /// Commit view \a x at position \a i to value \a n for alternative \a a
560 ModEvent commit(Space& home, unsigned int a, View x, int i, int n);
561 /// Create no-good literal for alternative \a a
562 NGL* ngl(Space& home, unsigned int a, View x, int n) const;
563 /// Print on \a o the alternative \a with view \a x at position \a i and value \a n
564 void print(const Space& home, unsigned int a, View x, int i, int n,
565 std::ostream& o) const;
566 };
567
568 /**
569 * \brief Value commit class for greater
570 *
571 * Requires \code #include <gecode/int/branch.hh> \endcode
572 * \ingroup FuncIntValCommit
573 */
574 template<class View>
575 class ValCommitGr : public ValCommit<View,int> {
576 public:
577 using typename ValCommit<View,int>::Var;
578 /// Constructor for initialization
579 ValCommitGr(Space& home, const ValBranch<Var>& vb);
580 /// Constructor for cloning
581 ValCommitGr(Space& home, ValCommitGr& vc);
582 /// Commit view \a x at position \a i to value \a n for alternative \a a
583 ModEvent commit(Space& home, unsigned int a, View x, int i, int n);
584 /// Create no-good literal for alternative \a a
585 NGL* ngl(Space& home, unsigned int a, View x, int n) const;
586 /// Print on \a o the alternative \a with view \a x at position \a i and value \a n
587 void print(const Space& home, unsigned int a, View x, int i, int n,
588 std::ostream& o) const;
589 };
590
591}}}
592
593#include <gecode/int/branch/val-commit.hpp>
594
595namespace Gecode { namespace Int { namespace Branch {
596
597 /// Return value and commit for integer views
598 GECODE_INT_EXPORT
599 ValSelCommitBase<IntView,int>*
600 valselcommit(Space& home, const IntValBranch& ivb);
601
602 /// Return value and commit for Boolean views
603 GECODE_INT_EXPORT
604 ValSelCommitBase<BoolView,int>*
605 valselcommit(Space& home, const BoolValBranch& bvb);
606
607 /// Return value and commit for integer views
608 GECODE_INT_EXPORT
609 ValSelCommitBase<IntView,int>*
610 valselcommit(Space& home, const IntAssign& ia);
611
612 /// Return value and commit for Boolean views
613 GECODE_INT_EXPORT
614 ValSelCommitBase<BoolView,int>*
615 valselcommit(Space& home, const BoolAssign& ba);
616
617}}}
618
619namespace Gecode { namespace Int { namespace Branch {
620
621 /**
622 * \brief %Brancher by view and values selection
623 *
624 */
625 template<int n, bool min, class Filter, class Print>
626 class ViewValuesBrancher : public ViewBrancher<IntView,Filter,n> {
627 protected:
628 using ViewBrancher<IntView,Filter,n>::x;
629 using ViewBrancher<IntView,Filter,n>::f;
630 /// Print function
631 Print p;
632 /// Constructor for cloning \a b
633 ViewValuesBrancher(Space& home, ViewValuesBrancher& b);
634 /// Constructor for creation
635 ViewValuesBrancher(Home home, ViewArray<IntView>& x,
636 ViewSel<IntView>* vs[n],
637 IntBranchFilter bf,
638 IntVarValPrint vvp);
639 public:
640 /// Return choice
641 virtual const Choice* choice(Space& home);
642 /// Return choice
643 virtual const Choice* choice(const Space& home, Archive& e);
644 /// Perform commit for choice \a c and alternative \a a
645 virtual ExecStatus commit(Space& home, const Choice& c, unsigned int a);
646 /// Create no-good literal for choice \a c and alternative \a a
647 virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const;
648 /**
649 * \brief Print branch for choice \a c and alternative \a a
650 *
651 * Prints an explanation of the alternative \a a of choice \a c
652 * on the stream \a o.
653 *
654 */
655 virtual void print(const Space& home, const Choice& c, unsigned int a,
656 std::ostream& o) const;
657 /// Perform cloning
658 virtual Actor* copy(Space& home);
659 /// Post function for creation
660 static void post(Home home, ViewArray<IntView>& x,
661 ViewSel<IntView>* vs[n],
662 IntBranchFilter bf,
663 IntVarValPrint vvp);
664 /// Delete brancher and return its size
665 virtual size_t dispose(Space& home);
666 };
667
668 /// Post brancher for view and values
669 template<int n, bool min>
670 void postviewvaluesbrancher(Home home, ViewArray<IntView>& x,
671 ViewSel<IntView>* vs[n],
672 IntBranchFilter bf,
673 IntVarValPrint vvp);
674
675}}}
676
677#include <gecode/int/branch/view-values.hpp>
678
679#ifdef GECODE_HAS_CBS
680
681namespace Gecode { namespace Int { namespace Branch {
682
683 /**
684 * \brief %Brancher using counting-based search
685 *
686 */
687 template<class View>
688 class CBSBrancher : public Brancher {
689 private:
690 /// Views to branch on
691 ViewArray<View> x;
692
693 /**
694 * \brief Map of variable ids to positions in \a x
695 *
696 * Once created, this mapping doesn't need to be updated. Because of this,
697 * we can share a handle of the map across all instances of CBSBrancher in
698 * all spaces.
699 */
700 class VarIdToPos : public SharedHandle {
701 protected:
702 class VarIdToPosO : public SharedHandle::Object {
703 public:
704 /// The map we want to share
705 std::unordered_map<unsigned int, unsigned int> _varIdToPos;
706 public:
707 /// Default constructur
708 VarIdToPosO(void) = default;
709 /// Delete implementation
710 virtual ~VarIdToPosO(void) = default;
711 };
712 public:
713 /// Default constructor
714 VarIdToPos(void) = default;
715 /// Allocation of the shared handle
716 void init(void);
717 /// Tests if a variable id is in the map
718 bool isIn(unsigned int var_id) const;
719 /// Returns the position of the variable id in \a x
720 int operator[](unsigned int var_id) const;
721 /// Inserts a new position for a variable id
722 void insert(unsigned int var_id, unsigned int pos);
723 } varIdToPos;
724
725 /**
726 * \brief Propagator information for counting-based search
727 *
728 * Keeps the best branching choice for each propagators (i.e. variable and
729 * value with highest solution density). We also keep \a domsum to know
730 * wether we need to recompute solution densities for the given propagator
731 * when computing a new branching choice.
732 */
733 struct PropInfo {
734 /// Sum of variable cardinalities
735 unsigned int domsum;
736 /// Variable with the highest solution density
737 unsigned int var_id;
738 /// Value with highest solution density
739 int val;
740 /// Density of the above <var_id, val> pair
741 double dens;
742 /// Flag for deleting propagator if unvisited when branching
743 bool visited;
744 };
745
746 /**
747 * \brief Map of propagator ids to PropInfo
748 *
749 * Any active propagator that:
750 *
751 * - shares a variable with \a x
752 * - has a counting algorithm (i.e. overloads solndistrib)
753 *
754 * will have an entry in this map.
755 */
756 std::unordered_map<unsigned int, PropInfo,
757 std::hash<unsigned int>,
758 std::equal_to<unsigned int>,
759 space_allocator<std::pair<const unsigned int, PropInfo>>>
760 logProp;
761
762 public:
763 /// Constructor for creation
764 CBSBrancher(Home home, ViewArray<View>& x0);
765 /// Constructor for cloning \a b
766 CBSBrancher(Space& home, CBSBrancher& b);
767 /// Post brancher
768 static void post(Home home, ViewArray<View>& x);
769 /// Copy brancher during cloning
770 virtual Actor* copy(Space& home);
771 /// Delete brancher and return its size
772 virtual size_t dispose(Space& home);
773 /// Check status of brancher, return true if alternatives left
774 virtual bool status(const Space& home) const;
775 /// Return choice
776 virtual const Choice* choice(Space& home);
777 /// Return choice
778 virtual const Choice* choice(const Space&, Archive& e);
779 /// Commit choice \a c for alternative \a a
780 virtual ExecStatus commit(Space& home, const Choice& c, unsigned int a);
781 /// Print on \a o the alternative \a with view \a x at position \a i and value \a n
782 virtual void print(const Space& home, const Choice& c, unsigned int a,
783 std::ostream& o) const;
784 private:
785 /// Returns wether a variable is in \a x or not
786 bool inbrancher(unsigned int varId) const;
787 };
788
789}}}
790
791#include <gecode/int/branch/cbs.hpp>
792
793#endif
794
795#endif
796
797// STATISTICS: int-branch