Generated on Sat Jun 2 2018 07:17:44 for Gecode by doxygen 1.8.13
branch.hh
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2012
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #ifndef __GECODE_INT_BRANCH_HH__
35 #define __GECODE_INT_BRANCH_HH__
36 
37 #include <gecode/int.hh>
38 
44 namespace Gecode { namespace Int { namespace Branch {
45 
64  template<class View>
65  class MeritMin : public MeritBase<View,int> {
66  public:
67  using typename MeritBase<View,int>::Var;
69  MeritMin(Space& home, const VarBranch<Var>& vb);
71  MeritMin(Space& home, MeritMin& m);
73  int operator ()(const Space& home, View x, int i);
74  };
75 
82  template<class View>
83  class MeritMax : public MeritBase<View,int> {
84  public:
85  using typename MeritBase<View,int>::Var;
87  MeritMax(Space& home, const VarBranch<Var>& vb);
89  MeritMax(Space& home, MeritMax& m);
91  int operator ()(const Space& home, View x, int i);
92  };
93 
100  template<class View>
101  class MeritSize : public MeritBase<View,unsigned int> {
102  public:
103  using typename MeritBase<View,unsigned int>::Var;
105  MeritSize(Space& home, const VarBranch<Var>& vb);
107  MeritSize(Space& home, MeritSize& m);
109  unsigned int operator ()(const Space& home, View x, int i);
110  };
111 
118  template<class View>
119  class MeritDegreeSize : public MeritBase<View,double> {
120  public:
121  using typename MeritBase<View,double>::Var;
123  MeritDegreeSize(Space& home, const VarBranch<Var>& vb);
127  double operator ()(const Space& home, View x, int i);
128  };
129 
136  template<class View>
137  class MeritAFCSize : public MeritBase<View,double> {
138  using typename MeritBase<View,double>::Var;
139  protected:
142  public:
144  MeritAFCSize(Space& home, const VarBranch<Var>& vb);
146  MeritAFCSize(Space& home, MeritAFCSize& m);
148  double operator ()(const Space& home, View x, int i);
150  bool notice(void) const;
152  void dispose(Space& home);
153  };
154 
161  template<class View>
162  class MeritActionSize : public MeritBase<View,double> {
163  using typename MeritBase<View,double>::Var;
164  protected:
167  public:
169  MeritActionSize(Space& home, const VarBranch<Var>& vb);
173  double operator ()(const Space& home, View x, int i);
175  bool notice(void) const;
177  void dispose(Space& home);
178  };
179 
186  template<class View>
187  class MeritCHBSize : public MeritBase<View,double> {
188  using typename MeritBase<View,double>::Var;
189  protected:
192  public:
194  MeritCHBSize(Space& home, const VarBranch<Var>& vb);
196  MeritCHBSize(Space& home, MeritCHBSize& m);
198  double operator ()(const Space& home, View x, int i);
200  bool notice(void) const;
202  void dispose(Space& home);
203  };
204 
211  template<class View>
212  class MeritRegretMin : public MeritBase<View,unsigned int> {
213  public:
214  using typename MeritBase<View,unsigned int>::Var;
216  MeritRegretMin(Space& home, const VarBranch<Var>& vb);
220  unsigned int operator ()(const Space& home, View x, int i);
221  };
222 
229  template<class View>
230  class MeritRegretMax : public MeritBase<View,unsigned int> {
231  public:
232  using typename MeritBase<View,unsigned int>::Var;
234  MeritRegretMax(Space& home, const VarBranch<Var>& vb);
238  unsigned int operator ()(const Space& home, View x, int i);
239  };
240 
241 }}}
242 
244 
245 namespace Gecode { namespace Int { namespace Branch {
246 
249  ViewSel<IntView>* viewsel(Space& home, const IntVarBranch& ivb);
252  ViewSel<BoolView>* viewsel(Space& home, const BoolVarBranch& bvb);
253 
254 }}}
255 
256 namespace Gecode { namespace Int { namespace Branch {
257 
276  template<class View>
277  class ValSelMin : public ValSel<View,int> {
278  public:
279  using typename ValSel<View,int>::Var;
281  ValSelMin(Space& home, const ValBranch<Var>& vb);
283  ValSelMin(Space& home, ValSelMin& vs);
285  int val(const Space& home, View x, int i);
286  };
287 
294  template<class View>
295  class ValSelMax : public ValSel<View,int> {
296  public:
297  using typename ValSel<View,int>::Var;
299  ValSelMax(Space& home, const ValBranch<Var>& vb);
301  ValSelMax(Space& home, ValSelMax& vs);
303  int val(const Space& home, View x, int i);
304  };
305 
312  template<class View>
313  class ValSelMed : public ValSel<View,int> {
314  public:
315  using typename ValSel<View,int>::Var;
317  ValSelMed(Space& home, const ValBranch<Var>& vb);
319  ValSelMed(Space& home, ValSelMed& vs);
321  int val(const Space& home, View x, int i);
322  };
323 
330  template<class View>
331  class ValSelAvg : public ValSel<View,int> {
332  public:
333  using typename ValSel<View,int>::Var;
335  ValSelAvg(Space& home, const ValBranch<Var>& vb);
337  ValSelAvg(Space& home, ValSelAvg& vs);
339  int val(const Space& home, View x, int i);
340  };
341 
348  template<class View>
349  class ValSelRnd : public ValSel<View,int> {
350  using typename ValSel<View,int>::Var;
351  protected:
354  public:
356  ValSelRnd(Space& home, const ValBranch<Var>& vb);
358  ValSelRnd(Space& home, ValSelRnd& vs);
360  int val(const Space& home, View x, int i);
362  bool notice(void) const;
364  void dispose(Space& home);
365  };
366 
373  class ValSelRangeMin : public ValSel<IntView,int> {
374  public:
376  ValSelRangeMin(Space& home, const ValBranch<IntVar>& vb);
378  ValSelRangeMin(Space& home, ValSelRangeMin& vs);
380  int val(const Space& home, IntView x, int i);
381  };
382 
389  class ValSelRangeMax : public ValSel<IntView,int> {
390  public:
392  ValSelRangeMax(Space& home, const ValBranch<IntVar>& vb);
394  ValSelRangeMax(Space& home, ValSelRangeMax& vs);
396  int val(const Space& home, IntView x, int i);
397  };
398 
399 }}}
400 
402 
403 namespace Gecode { namespace Int { namespace Branch {
404 
406  template<class View>
407  class EqNGL : public ViewValNGL<View,int,PC_INT_VAL> {
410  public:
412  EqNGL(Space& home, View x, int n);
414  EqNGL(Space& home, EqNGL& ngl);
416  virtual NGL::Status status(const Space& home) const;
418  virtual ExecStatus prune(Space& home);
420  virtual NGL* copy(Space& home);
421  };
422 
424  template<class View>
425  class NqNGL : public ViewValNGL<View,int,PC_INT_DOM> {
428  public:
430  NqNGL(Space& home, View x, int n);
432  NqNGL(Space& home, NqNGL& ngl);
434  virtual NGL::Status status(const Space& home) const;
436  virtual ExecStatus prune(Space& home);
438  virtual NGL* copy(Space& home);
439  };
440 
442  template<class View>
443  class LqNGL : public ViewValNGL<View,int,PC_INT_BND> {
446  public:
448  LqNGL(Space& home, View x, int n);
450  LqNGL(Space& home, LqNGL& ngl);
452  virtual NGL::Status status(const Space& home) const;
454  virtual ExecStatus prune(Space& home);
456  virtual NGL* copy(Space& home);
457  };
458 
460  template<class View>
461  class GqNGL : public ViewValNGL<View,int,PC_INT_BND> {
464  public:
466  GqNGL(Space& home, View x, int n);
468  GqNGL(Space& home, GqNGL& ngl);
470  virtual NGL::Status status(const Space& home) const;
472  virtual ExecStatus prune(Space& home);
474  virtual NGL* copy(Space& home);
475  };
476 
477 }}}
478 
479 #include <gecode/int/branch/ngl.hpp>
480 
481 namespace Gecode { namespace Int { namespace Branch {
482 
501  template<class View>
502  class ValCommitEq : public ValCommit<View,int> {
503  public:
504  using typename ValCommit<View,int>::Var;
506  ValCommitEq(Space& home, const ValBranch<Var>& vb);
508  ValCommitEq(Space& home, ValCommitEq& vc);
510  ModEvent commit(Space& home, unsigned int a, View x, int i, int n);
512  NGL* ngl(Space& home, unsigned int a, View x, int n) const;
514  void print(const Space& home, unsigned int a, View x, int i, int n,
515  std::ostream& o) const;
516  };
517 
524  template<class View>
525  class ValCommitLq : public ValCommit<View,int> {
526  public:
527  using typename ValCommit<View,int>::Var;
529  ValCommitLq(Space& home, const ValBranch<Var>& vb);
531  ValCommitLq(Space& home, ValCommitLq& vc);
533  ModEvent commit(Space& home, unsigned int a, View x, int i, int n);
535  NGL* ngl(Space& home, unsigned int a, View x, int n) const;
537  void print(const Space& home, unsigned int a, View x, int i, int n,
538  std::ostream& o) const;
539  };
540 
547  template<class View>
548  class ValCommitGq : public ValCommit<View,int> {
549  public:
550  using typename ValCommit<View,int>::Var;
552  ValCommitGq(Space& home, const ValBranch<Var>& vb);
554  ValCommitGq(Space& home, ValCommitGq& vc);
556  ModEvent commit(Space& home, unsigned int a, View x, int i, int n);
558  NGL* ngl(Space& home, unsigned int a, View x, int n) const;
560  void print(const Space& home, unsigned int a, View x, int i, int n,
561  std::ostream& o) const;
562  };
563 
570  template<class View>
571  class ValCommitGr : public ValCommit<View,int> {
572  public:
573  using typename ValCommit<View,int>::Var;
575  ValCommitGr(Space& home, const ValBranch<Var>& vb);
577  ValCommitGr(Space& home, ValCommitGr& vc);
579  ModEvent commit(Space& home, unsigned int a, View x, int i, int n);
581  NGL* ngl(Space& home, unsigned int a, View x, int n) const;
583  void print(const Space& home, unsigned int a, View x, int i, int n,
584  std::ostream& o) const;
585  };
586 
587 }}}
588 
590 
591 namespace Gecode { namespace Int { namespace Branch {
592 
596  valselcommit(Space& home, const IntValBranch& ivb);
597 
601  valselcommit(Space& home, const BoolValBranch& bvb);
602 
606  valselcommit(Space& home, const IntAssign& ia);
607 
611  valselcommit(Space& home, const BoolAssign& ba);
612 
613 }}}
614 
615 namespace Gecode { namespace Int { namespace Branch {
616 
621  template<int n, bool min, class Filter, class Print>
622  class ViewValuesBrancher : public ViewBrancher<IntView,Filter,n> {
623  protected:
627  Print p;
632  ViewSel<IntView>* vs[n],
633  IntBranchFilter bf,
634  IntVarValPrint vvp);
635  public:
637  virtual const Choice* choice(Space& home);
639  virtual const Choice* choice(const Space& home, Archive& e);
641  virtual ExecStatus commit(Space& home, const Choice& c, unsigned int a);
643  virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const;
651  virtual void print(const Space& home, const Choice& c, unsigned int a,
652  std::ostream& o) const;
654  virtual Actor* copy(Space& home);
656  static void post(Home home, ViewArray<IntView>& x,
657  ViewSel<IntView>* vs[n],
658  IntBranchFilter bf,
659  IntVarValPrint vvp);
661  virtual size_t dispose(Space& home);
662  };
663 
665  template<int n, bool min>
667  ViewSel<IntView>* vs[n],
668  IntBranchFilter bf,
669  IntVarValPrint vvp);
670 
671 }}}
672 
674 
675 #endif
676 
677 // STATISTICS: int-branch
ViewSel< IntView > * viewsel(Space &home, const IntVarBranch &ivb)
Return view selectors for integer views.
Definition: view-sel.cpp:39
Action action
Action information.
Definition: branch.hh:166
No-good literal for less or equal.
Definition: branch.hh:443
Which values to select for branching first.
Definition: int.hh:4682
No-good literal for greater or equal.
Definition: branch.hh:461
Which values to select for branching first.
Definition: int.hh:4647
Which integer variable to select for branching.
Definition: int.hh:4363
Generic brancher by view selection.
Definition: view.hpp:78
Which values to select for assignment.
Definition: int.hh:4793
Rnd r
The used random number generator.
Definition: branch.hh:353
Status
The status of a no-good literal.
Definition: core.hpp:1305
int ModEvent
Type for modification events.
Definition: core.hpp:62
Merit class for CHB over size.
Definition: branch.hh:187
Base-class for merit class.
Definition: merit.hpp:46
Merit class for degree over size.
Definition: branch.hh:119
AFC afc
AFC information.
Definition: branch.hh:141
Value commit class for less or equal.
Definition: branch.hh:525
Computation spaces.
Definition: core.hpp:1701
ExecStatus prune(Space &home, ViewArray< VX > &x, ConstIntView)
Definition: rel.hpp:264
No-good literal for equality.
Definition: branch.hh:407
Base class for value selection and commit.
Brancher by view and values selection
Definition: branch.hh:622
Base-class for both propagators and branchers.
Definition: core.hpp:627
Value commit class for greater.
Definition: branch.hh:571
Value selection class for mimimum of view.
Definition: branch.hh:277
Value selection class for average of view.
Definition: branch.hh:331
Value selection class for random value of view.
Definition: branch.hh:349
Base class for value commit.
Definition: val-commit.hpp:44
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i(4, 1, 2, 3, 4)
Class for AFC (accumulated failure count) management.
Definition: afc.hpp:40
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Value selection class for minimum range of integer view.
Definition: branch.hh:373
Merit class for action over size.
Definition: branch.hh:162
Value selection class for maximum of view.
Definition: branch.hh:295
Class for CHB management.
Definition: chb.hpp:46
Merit class for mimimum of integer views.
Definition: branch.hh:65
Which Boolean variable to select for branching.
Definition: int.hh:4449
CHB chb
CHB information.
Definition: branch.hh:191
Merit class for minimum regret.
Definition: branch.hh:212
Value commit class for greater or equal.
Definition: branch.hh:548
std::function< bool(const Space &home, IntVar x, int i)> IntBranchFilter
Branch filter function type for integer variables.
Definition: int.hh:3969
Merit class for AFC over size.
Definition: branch.hh:137
ValSelCommitBase< IntView, int > * valselcommit(Space &home, const IntValBranch &ivb)
Return value and commit for integer views.
bool notice(void) const
Whether dispose must always be called (that is, notice is needed)
Definition: merit.hpp:182
No-good literal for disequality.
Definition: branch.hh:425
std::function< void(const Space &home, const Brancher &b, unsigned int a, IntVar x, int i, const int &n, std::ostream &o)> IntVarValPrint
Function type for printing branching alternatives for integer variables.
Definition: int.hh:4345
Value commit class for equality.
Definition: branch.hh:502
IntPropLevel ba(IntPropLevel ipl)
Extract basic or advanced from propagation level.
Definition: ipl.hpp:43
void print(std::basic_ostream< Char, Traits > &s, bool assigned, IL &lb, IU &ub, unsigned int cardMin, unsigned int cardMax)
Print set view.
Definition: print.hpp:63
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
Integer view for integer variables.
Definition: view.hpp:129
Value branching information.
Definition: val.hpp:41
Merit class for size.
Definition: branch.hh:101
Variable branching information.
Definition: var.hpp:55
Value selection class for median of view.
Definition: branch.hh:313
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Choice for performing commit
Definition: core.hpp:1371
Archive representation
Definition: archive.hpp:42
ExecStatus
Definition: core.hpp:471
Which values to select for assignment.
Definition: int.hh:4764
MeritMin(Space &home, const VarBranch< Var > &vb)
Constructor for initialization.
Definition: merit.hpp:39
Merit class for maximum regret.
Definition: branch.hh:230
Merit class for maximum.
Definition: branch.hh:83
Post propagator for SetVar x
Definition: set.hh:765
View-value no-good literal.
Definition: view-val.hpp:61
View View
View type.
Definition: merit.hpp:49
Gecode toplevel namespace
Class for action management.
Definition: action.hpp:42
void dispose(Space &home)
Delete view merit class.
Definition: merit.hpp:187
Random number generator.
Definition: rnd.hpp:42
#define GECODE_INT_EXPORT
Definition: int.hh:77
Value selection class for maximum range of integer view.
Definition: branch.hh:389
Home class for posting propagators
Definition: core.hpp:853
void postviewvaluesbrancher(Home home, ViewArray< IntView > &x, ViewSel< IntView > *vs[n], IntBranchFilter bf, IntVarValPrint vvp)
Post brancher for view and values.
int operator()(const Space &home, View x, int i)
Return minimum as merit for view x at position i.
Definition: merit.hpp:47
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition: filter.cpp:138
Base class for value selection.
Definition: val-sel.hpp:44
No-good literal recorded during search.
Definition: core.hpp:1299