8. Branching

This chapter discusses how branching is used for solving Gecode models. Branching defines the shape of the search tree. Exploration defines a strategy how to explore parts of the search tree and is discussed in Search.

Overview. Branching basics explains the basics of Gecode’s predefined branchings. An overview of available branchings for integer and Boolean variables is provided in Branching on integer and Boolean variables, for set variables in Branching on set variables, and for float variables in Branching on float variables. These sections belong to the basic reading material of Modeling.

Advanced topics for branchings are discussed in the remaining sections: local versus shared variable selection , random selection , user-defined variable and value selection, tie-breaking , dynamic symmetry breaking , branch filter functions , variable-value print functions , assigning variables , and executing code between branchers .

Note that the same conventions hold as in Integer and Boolean variables and constraints.

8.1. Branching basics

Gecode offers predefined variable-value branching: when calling branch() to post a branching, the third argument defines which variable is selected for branching, whereas the fourth argument defines which values are selected for branching.

For example, for an array of integer or Boolean variables x the following call to branch

branch(home, x, INT_VAR_MIN_MIN(), INT_VAL_SPLIT_MIN());

selects a variable \(y\) with the smallest minimum value (in case of ties, the first such variable in x is selected) and creates a choice with two alternatives \(y\leq n\) and \(y>n\) where

\[n=\left\lfloor\frac{\min(y)+\max(y)}{2}\right\rfloor \]

The posted brancher assigns all variables and then ceases to exist. If more branchers exist, search continues with the next brancher. Search commits a brancher to alternatives during search.

The branch() function also accepts a branch filter function and a variable-value print function as optional arguments, see Using branch filter functions and Using variable-value print functions for details.

Several branchers. A space in Gecode can have several branchers posted on behalf of a branching that are executed in order of creation. Assume that in

branch(home, x, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
...
branch(home, y, INT_VAR_SIZE_MIN(), INT_VAL_MIN());

both calls to branch() create a brancher. Search branches first on the variables x and then on the variables y. Here, it does not matter whether propagators are created in between the creation of branchers.

Branching on single variables. In addition to branching on an array of variables, Gecode also supports branching on a single variable.

For example, if x is an integer variable of type IntVar, then

branch(home, x, INT_VAL_MIN());

branches on the single variable x by first trying the smallest value of x.

Assume that x is an array of integer variables. Then the following code

for (int i=0; i<x.size(); i++)
  branch(home, x[i], INT_VAL_MIN());

is equivalent, albeit considerably less efficient, to

branch(home, x, INT_VAR_NONE(), INT_VAL_MIN());

Brancher groups. Branchers can be controlled by brancher groups, they are discussed in detail in Brancher groups.

8.2. Branching on integer and Boolean variables

Important

Do not forget to add

#include <gecode/int.hh>

to your program when you want to branch on integer and Boolean variables.

INT_VAR_NONE()

first unassigned

INT_VAR_RND(r)

randomly

INT_VAR_MERIT_MIN(m,t*)

smallest value of merit function m

INT_VAR_MERIT_MAX(m,t*)

largest value of merit function m

INT_VAR_DEGREE_MIN(t*)

smallest degree

INT_VAR_DEGREE_MAX(t*)

largest degree

INT_VAR_AFC_MIN(afc+,t*)

smallest accumulated failure count (AFC)

INT_VAR_AFC_MAX(afc+,t*)

largest accumulated failure count (AFC)

INT_VAR_ACTION_MIN(act+,t*)

lowest action

INT_VAR_ACTION_MAX(act+,t*)

highest action

INT_VAR_CHB_MIN(chb+,t*)

lowest chb Q-score

INT_VAR_CHB_MAX(chb+,t*)

highest chb Q-score

INT_VAR_MIN_MIN(t*)

smallest minimum value

INT_VAR_MIN_MAX(t*)

largest minimum value

INT_VAR_MAX_MIN(t*)

smallest maximum value

INT_VAR_MAX_MAX(t*)

largest maximum value

INT_VAR_SIZE_MIN(t*)

smallest domain size

INT_VAR_SIZE_MAX(t*)

largest domain size

INT_VAR_DEGREE_SIZE_MIN(t*)

smallest degree divided by domain size

INT_VAR_DEGREE_SIZE_MAX(t*)

largest degree by domain size

INT_VAR_AFC_SIZE_MIN(afc+,t*)

smallest AFC by domain size

INT_VAR_AFC_SIZE_MAX(afc+,t*)

largest AFC by domain size

INT_VAR_ACTION_SIZE_MIN(act+,t*)

smallest action by domain size

INT_VAR_ACTION_SIZE_MAX(act+,t*)

largest action by domain size

INT_VAR_CHB_SIZE_MIN(chb+,t*)

smallest chb by domain size

INT_VAR_CHB_SIZE_MAX(chb+,t*)

largest chb by domain size

INT_VAR_REGRET_MIN_MIN(t*)

smallest minimum-regret

INT_VAR_REGRET_MIN_MAX(t*)

largest minimum-regret

INT_VAR_REGRET_MAX_MIN(t*)

smallest maximum-regret

INT_VAR_REGRET_MAX_MAX(t*)

largest maximum-regret

Figure 8.1 Integer variable selection

Branching on integer variables. For integer variables, variable selection is defined by a value of class IntVarBranch and value selection is defined by a value of type IntValBranch. Values of these types are obtained by calling functions (possibly taking arguments) that correspond to variable and value selection strategies. For example, a call INT_VAR_SIZE_MIN() returns an object of class IntVarBranch.

For an overview of the available variable selection strategies, see Figure 8.1 (see also Variable selection for integer and Boolean variables) where \(\cdot\)* denotes an optional argument and \(\cdot\)+ is a special argument to be explained below. Here, an argument r refers to a random number generator of type Rnd. Using random number generators for branching is discussed in Random variable and value selection. An argument m refers to a user-defined merit function of type IntBranchMerit for integer variables and BoolBranchMerit for Boolean variables. User-defined merit functions are discussed in User-defined variable selection. An argument afc refers to accumulated failure count (AFC) information for integer variables (of class IntAFC). An argument act refers to action information for integer variables (of class IntAction). An argument chb refers to CHB information for integer variables (of class IntCHB). For a discussion of AFC, action, and CHB, see Local versus shared variable selection criteria. Both afc+ and act+ can also be optional arguments of type double defining a decay-factor, whereas the argument chb+ can be omitted. The optional argument t refers to a tie-breaking limit function of type BranchTbl and is discussed in Tie-breaking.

Omitting the variable selection strategy is equivalent to using INT_VAR_NONE().

INT_VAL_RND(r)

random value

INT_VAL(v,c*)

defined by value function v and commit function c

INT_VAL_MIN()

smallest value

INT_VAL_MED()

greatest value not greater than the median

INT_VAL_MAX()

largest value

INT_VAL_SPLIT_MIN()

values not greater than mean of smallest and largest value

INT_VAL_SPLIT_MAX()

values greater than mean of smallest and largest value

INT_VAL_RANGE_MIN()

values from smallest range, if domain has several ranges;

otherwise, values not greater than mean

INT_VAL_RANGE_MAX()

values from largest range, if domain has several ranges;

otherwise, values greater than mean

INT_VALUES_MIN()

all values starting from smallest

INT_VALUES_MAX()

all values starting from largest

Figure 8.2 Integer value selection

An overview of the available value selection strategies for integer variables can be found in Figure 8.2 (see also Value selection for integer and Boolean variables) where \(\cdot\)* denotes an optional argument. Here, an argument r refers to a random number generator of type Rnd which is discussed in Random variable and value selection. An argument v refers to a value selection function of type IntBranchVal. An optional argument c refers to a commit function of type IntBranchCommit. Value and commit functions are discussed in User-defined value selection.

Note that variable-value branchers are just common cases for branching based on the idea of selecting variables and values. In Gecode also arbitrary other branchers can be programmed, see Programming branchers.

Branching on Boolean variables.

BOOL_VAR_NONE()

first unassigned

BOOL_VAR_RND(r)

randomly

BOOL_VAR_MERIT_MIN(m,t*)

smallest value of merit function m

BOOL_VAR_MERIT_MAX(m,t*)

largest value of merit function m

BOOL_VAR_DEGREE_MIN(t*)

smallest degree

BOOL_VAR_DEGREE_MAX(t*)

largest degree

BOOL_VAR_AFC_MIN(afc+,t*)

smallest accumulated failure count (AFC)

BOOL_VAR_AFC_MAX(afc+,t*)

largest accumulated failure count (AFC)

BOOL_VAR_ACTION_MIN(act+,t*)

lowest action

BOOL_VAR_ACTION_MAX(act+,t*)

highest action

BOOL_VAR_CHB_MIN(chb+,t*)

lowest CHB Q-score

BOOL_VAR_CHB_MAX(chb+,t*)

highest CHB Q-score

Figure 8.3 Boolean variable selection

Similar to integer variables, variable selection for Boolean variables is defined by a value of class BoolVarBranch and value selection is defined by a value of type BoolValBranch. Values of these types are obtained by calling functions (possibly taking arguments) that correspond to variable and value selection strategies.

For an overview of the available variable selection strategies, see Figure 8.3 (see also Variable selection for integer and Boolean variables) where \(\cdot\)* denotes an optional argument and \(\cdot\)+ is a special argument to be explained below. Here, an argument r refers to a random number generator of type Rnd. An argument m refers to a user-defined merit function of type BoolBranchMerit. An argument afc refers to accumulated failure count (AFC) information for Boolean variables (of class BoolAFC). An argument act refers to action information for Boolean variables (of class BoolAction). An argument chb refers to CHB information for Boolean variables (of class BoolCHB). The optional argument t refers to a tie-breaking limit function of type BranchTbl.

Omitting the variable selection strategy is equivalent to using BOOL_VAR_NONE().

BOOL_VAL_RND(r)

random value

BOOL_VAL(v,c*)

defined by value function v and commit function c

BOOL_VAL_MIN()

smallest value

BOOL_VAL_MAX()

largest value

Figure 8.4 Boolean value selection

An overview of the available value selection strategies for Boolean variables can be found in Figure 8.4 (see also Value selection for integer and Boolean variables) where \(\cdot\)* denotes an optional argument. Here, an argument r refers to a random number generator of type Rnd. An argument v refers to a value selection function of type BoolBranchVal. An optional argument c refers to a commit function of type BoolBranchCommit.

8.3. Branching on set variables

Important

Do not forget to add

#include <gecode/set.hh>

to your program when you want to branch on set variables.

SET_VAR_NONE()

first unassigned

SET_VAR_RND(r)

randomly

SET_VAR_MERIT_MIN(m,t*)

smallest value of merit function m

SET_VAR_MERIT_MAX(m,t*)

largest value of merit function m

SET_VAR_DEGREE_MIN(t*)

smallest degree

SET_VAR_DEGREE_MAX(t*)

largest degree

SET_VAR_AFC_MIN(afc+,t*)

smallest accumulated failure count (AFC)

SET_VAR_AFC_MAX(afc+,t*)

largest accumulated failure count (AFC)

SET_VAR_ACTION_MIN(act+,t*)

lowest action

SET_VAR_ACTION_MAX(act+,t*)

highest action

SET_VAR_CHB_MIN(chb+,t*)

lowest CHB Q-score

SET_VAR_CHB_MAX(chb+,t*)

highest CHB Q-score

SET_VAR_MIN_MIN(t*)

smallest minimum unknown element

SET_VAR_MIN_MAX(t*)

largest minimum unknown element

SET_VAR_MAX_MIN(t*)

smallest maximum unknown element

SET_VAR_MAX_MAX(t*)

largest maximum unknown element

SET_VAR_SIZE_MIN(t*)

smallest unknown set

SET_VAR_SIZE_MAX(t*)

largest unknown set

SET_VAR_DEGREE_SIZE_MIN(t*)

smallest degree divided by domain size

SET_VAR_DEGREE_SIZE_MAX(t*)

largest degree divided by domain size

SET_VAR_AFC_SIZE_MIN(afc+,t*)

smallest AFC divided by domain size

SET_VAR_AFC_SIZE_MAX(afc+,t*)

largest AFC divided by domain size

SET_VAR_ACTION_SIZE_MIN(act+,t*)

smallest action divided by domain size

SET_VAR_ACTION_SIZE_MAX(act+,t*)

largest action divided by domain size

SET_VAR_CHB_SIZE_MIN(chb+,t*)

smallest CHB divided by domain size

SET_VAR_CHB_SIZE_MAX(chb+,t*)

largest CHB divided by domain size

Figure 8.5 Set variable selection

For set variables, variable selection is defined by a value of class SetVarBranch (see also Selecting set variables) and value selection is defined by a value of type SetValBranch (see also Value selection for set variables).

For an overview of the available variable selection strategies, see Figure 8.5 (see also Selecting set variables) where \(\cdot\)* denotes an optional argument and \(\cdot\)+ is a special argument to be explained below. Here, an argument r refers to a random number generator of type Rnd. Using random number generators for branching is discussed in Random variable and value selection. An argument m refers to a user-defined merit function of type SetBranchMerit. User-defined merit functions are discussed in User-defined variable selection. An argument afc refers to accumulated failure count (AFC) information for set variables (of class SetAFC). An argument act refers to action information for set variables (of class SetAction). An argument chb refers to CHB information for set variables (of class SetCHB). For a discussion of AFC, action, and CHB, see Local versus shared variable selection criteria. Both afc+ and act+ can also be optional arguments of type double defining a decay-factor. The argument ?chb?+ can be omitted. The optional argument t refers to a tie-breaking limit function of type BranchTbl and is discussed in Tie-breaking.

Omitting the variable selection strategy is equivalent to using SET_VAR_NONE().

SET_VAL_RND_INC(r)

include random element

SET_VAL_RND_EXC(r)

exclude random element

SET_VAL(v,c*)

defined by value function v and commit function c

SET_VAL_MIN_INC()

include smallest element

SET_VAL_MIN_EXC()

exclude smallest element

SET_VAL_MED_INC()

include median element (rounding downwards)

SET_VAL_MED_EXC()

exclude median element (rounding downwards)

SET_VAL_MAX_INC()

include largest element

SET_VAL_MAX_EXC()

exclude largest element

Figure 8.6 Set value selection

An overview of the available value selection strategies for set variables can be found in Figure 8.6 where \(\cdot\)* denotes an optional argument. Here, an argument r refers to a random number generator of type Rnd which is discussed in Random variable and value selection. An argument v refers to a value selection function of type SetBranchVal. An optional argument c refers to a commit function of type SetBranchCommit. Value and commit function are discussed in User-defined value selection.

8.4. Branching on float variables

Important

Do not forget to add

#include <gecode/float.hh>

to your program when you want to branch on float variables.

FLOAT_VAR_NONE()

first unassigned

FLOAT_VAR_RND(r)

randomly

FLOAT_VAR_MERIT_MIN(m,t*)

smallest value of merit function m

FLOAT_VAR_MERIT_MAX(m,t*)

largest value of merit function m

FLOAT_VAR_DEGREE_MIN(t*)

smallest degree

FLOAT_VAR_DEGREE_MAX(t*)

largest degree

FLOAT_VAR_AFC_MIN(afc+,t*)

smallest accumulated failure count (AFC)

FLOAT_VAR_AFC_MAX(afc+,t*)

largest accumulated failure count (AFC)

FLOAT_VAR_ACTION_MIN(act+,t*)

lowest action

FLOAT_VAR_ACTION_MAX(act+,t*)

highest action

FLOAT_VAR_CHB_MIN(chb+,t*)

lowest CHB Q-score

FLOAT_VAR_CHB_MAX(chb+,t*)

highest CHB Q-score

FLOAT_VAR_MIN_MIN(t*)

smallest minimum value

FLOAT_VAR_MIN_MAX(t*)

largest minimum value

FLOAT_VAR_MAX_MIN(t*)

smallest maximum value

FLOAT_VAR_MAX_MAX(t*)

largest maximum value

FLOAT_VAR_SIZE_MIN(t*)

smallest domain size

FLOAT_VAR_SIZE_MAX(t*)

largest domain size

FLOAT_VAR_DEGREE_SIZE_MIN(t*)

smallest degree divided by domain size

FLOAT_VAR_DEGREE_SIZE_MAX(t*)

largest degree divided by domain size

FLOAT_VAR_AFC_SIZE_MIN(afc+,t*)

smallest AFC divided by domain size

FLOAT_VAR_AFC_SIZE_MAX(afc+,t*)

largest AFC divided by domain size

FLOAT_VAR_ACTION_SIZE_MIN(act+,t*)

smallest action divided by domain size

FLOAT_VAR_ACTION_SIZE_MAX(act+,t*)

largest action divided by domain size

FLOAT_VAR_CHB_SIZE_MIN(chb+,t*)

smallest chb divided by domain size

FLOAT_VAR_CHB_SIZE_MAX(chb+,t*)

largest chb divided by domain size

Figure 8.7 Float variable selection

For float variables, variable selection is defined by a value of class FloatVarBranch (see also Variable selection for float variables) and value selection is defined by a value of type FloatValBranch (see also Value selection for float variables).

For an overview of the available variable selection strategies, see Figure 8.7 (see also Variable selection for float variables) where \(\cdot\)* denotes an optional argument and \(\cdot\)+ is a special argument to be explained below. Here, an argument r refers to a random number generator of type Rnd. Using random number generators for branching is discussed in Random variable and value selection. An argument m refers to a user-defined merit function of type FloatBranchMerit. User-defined merit functions are discussed in User-defined variable selection. An argument afc refers to accumulated failure count (AFC) information for float variables (of class FloatAFC). An argument act refers to action information for float variables (of class FloatAction). An argument chb refers to CHB information for float variables (of class FloatCHB). For a discussion of AFC, action, and CHB, see Local versus shared variable selection criteria. Both afc+ and act+ can also be optional arguments of type double defining a decay-factor. The argument chb+ can be ommitted. The optional argument t refers to a tie-breaking limit function of type BranchTbl and is discussed in Tie-breaking.

Omitting the variable selection strategy is equivalent to using FLOAT_VAR_NONE().

FLOAT_VAL(v,c*)

defined by value function v and commit function c

FLOAT_VAL_SPLIT_RND(r)

values not smaller or larger than mean

(smaller or larger is randomly selected)

FLOAT_VAL_SPLIT_MIN()

values not greater than mean

FLOAT_VAL_SPLIT_MAX()

values not smaller than mean

Figure 8.8 Float value selection

An overview of the available value selection strategies for float variables can be found in Figure 8.8 where \(\cdot\)* denotes an optional argument. Here, an argument r refers to a random number generator of type Rnd which is discussed in Random variable and value selection. An argument v refers to a value selection function of type FloatBranchVal. An optional argument c refers to a commit function of type FloatBranchCommit. Value and commit function are discussed in User-defined value selection.

8.5. Local versus shared variable selection criteria

The criteria used for selecting variables are either local or shared. A local variable selection criterion depends only on a brancher’s home space. A shared variable selection criterion depends not only on the brancher’s home space but also on all spaces that have been created during search sharing the same root space where the brancher had originally been posted. That entails that a shared criterion can use information that is collected during search. In terms of Hybrid recomputation, a shared variable selection criterion depends on all equivalent spaces created by cloning.

8.5.1. Local variable selection criteria

All selection criteria but those based on AFC, action, and CHB are local: they either select variables without using any information on a variable (INT_VAR_NONE()), select variables randomly (INT_VAR_RND(r), see also Random variable and value selection), or use the degree or domain of a variable for selection. The user-defined selection criteria INT_VAR_MERIT_MIN() and INT_VAR_MERIT_MAX() in addition have access to the home space and the selected variable’s position, see User-defined variable selection for details.

The degree of a variable is the number of propagators depending on the variable (useful as an approximate measure of how constrained a variables is).

The minimum-regret for integer and Boolean variables is the difference between the smallest and second smallest value in the domain of a variable (maximum-regret is analogous).

8.5.2. Selection using accumulated failure count

The accumulated failure count (AFC) of a variable is a shared selection criterion. It is defined as the sum of the AFCs of all propagators depending on the variable plus its degree (to give a good initial value if the AFCs of all propagators are still zero). The AFC of a propagator counts how often the propagator has failed during search. The AFC of a variable is also known as the weighted degree of a variable [8].

AFC in Gecode supports decay as follows. Each time a propagator fails during constraint propagation (by executing the status() function of a space, see also Propagation is explicit), the AFC of all propagators is updated:

  • If the propagator p failed, the AFC \(\mathtt{afc}(\mathtt p)\) of p is incremented by \(1\):

    \[\mathtt{afc}(\mathtt p)=\mathtt{afc}(\mathtt p)+1 \]

    For all other propagators q, the AFC \(\mathtt{afc}(\mathtt q)\) of q is updated by a decay-factor \(\mathtt{d}\) (\(0<\mathtt{d}\leq 1\)):

    \[\mathtt{afc}(\mathtt q)=\mathtt{d}\cdot\mathtt{afc}(\mathtt q) \]

  • The AFC \(\mathtt{afc}(\mathtt x)\) of a variable x is then defined as:

    \[\mathtt{afc}(\mathtt x)=\mathtt{afc}(\mathtt{p}_1)+\cdots+\mathtt{afc}(\mathtt{p}_n)\]

    where the propagators \(\mathtt{p}_i\) depend on x.

  • The AFC \(\mathtt{afc}(\mathtt p)\) of a propagator p is initialized to \(1\). That entails that the AFC of a variable x is initialized to its degree.

In order to use AFC for branching, one must create an object of class IntAFC for integer variables, an object of class BoolAFC for Boolean variables, an object of class SetAFC for set variables, or an object of class FloatAFC for float variables. The object is responsible for recording AFC information [1].

If x is an integer variable array, then

IntAFC afc(home,x,0.99);

initializes the AFC information afc for the variables in x with decay-factor \(\mathtt{d}=\mathtt{0.99}\). The decay-factor is optional and defaults to no decay (\(\mathtt{d}=1\)).

The decay-factor can be changed later, say to \(\mathtt{d}=\mathtt{0.95}\), by

afc.decay(0.95);

and afc.decay() returns the current decay-factor of afc.

A branching for integer variables using AFC information must be given an object of type IntAFC as argument:

branch(home, x, INT_VAR_AFC_MAX(afc), INT_VAL_MIN());

Here the integer variable array x must be exactly the same that has been used for creating the integer AFC object afc.

The AFC object can be omitted if one does not want to change the decay-factor later, hence it is sufficient to pass the decay-factor as argument. For example:

branch(home, x, INT_VAR_AFC_MAX(0.99), INT_VAL_MIN());

uses AFC information with a decay-factor of 0.99. Even the decay-factor can be omitted and defaults to 1 (that is, no decay).

AFC for other variable types is analogous.

For an example using a decay-factor with AFC, see More information.

8.5.3. Selection using action

The action of a variable is a shared criterion and captures how often the domain of a variable has been reduced during constraint propagation.

The action of a variable is maintained by constraint propagation as follows. Each time constraint propagation finishes (even if it finishes with failure) during search (by executing the status() function of a space, see also Propagation is explicit), the action of a variable \(\mathtt x\) is updated [37]:

  • If the variable x has not been pruned (that is, no values have been removed from the domain of x through propagation), the action \(\mathtt{action}(\mathtt x)\) of x is updated by a decay-factor \(\mathtt{d}\) (\(0<\mathtt{d}\leq 1\)):

    \[\mathtt{action}(\mathtt x)=\mathtt{d}\cdot\mathtt{action}(\mathtt x) \]

  • If the variable x has been pruned, the action \(\mathtt{action}(\mathtt x)\) of x is incremented by \(1\):

    \[\mathtt{action}(\mathtt x)=\mathtt{action}(\mathtt x)+1 \]

  • The action of a variable x is initialized to be one.

Note that in [37] action is called activity. However, as the activity of a variable during search in SAT is a well-established and different concept (see for example [14]), Gecode uses the term action instead.

In order to use action for branching, one must create an object of class IntAction for integer variables, an object of class BoolAction for Boolean variables, an object of class SetAction for set variables, or an object of class FloatAction for float variables. The object is responsible for recording action information.

If x is an integer variable array, then

IntAction act(home,x,0.99);

initializes the action information act for the variables in x with decay-factor \(\mathtt{d}=\mathtt{0.99}\). The decay-factor is optional and defaults to no decay (\(\mathtt{d}=1\)).

Note that it can be specified whether the action counter is incremented when a variable is pruned (propagation) or when a variable domain has been wiped out (failure). For example, the following creates action information that onky considers propagation:

IntAction act(home,x,0.99,true,false);

whereas the following only considers failure:

IntAction act(home,x,0.99,false,true);

By default, both are considered which corresponds to:

IntAction act(home,x,0.99,true,true);

The action of each variable in an array x can be initialized by a merit function, see User-defined variable selection. Here

IntAction act(home,x,0.99,true,true
              [](const Space& home, IntVar x, int i) {
                return 1.0;
              });

initializes the action of x[i] to 1.0.

The decay-factor can be changed later, say to \(\mathtt{d}=\mathtt{0.95}\), by

act.decay(0.95);

and act.decay() returns the current decay-factor of act.

A branching for integer variables using action information must be given an object of type IntAction as argument:

branch(home, x, INT_VAR_ACTION_MAX(act), INT_VAL_MIN());

Here the integer variable array x must be exactly the same that has been used for creating the integer action object act.

The action object can be omitted if one does not want to change the decay-factor later, hence it is sufficient to pass the decay-factor as argument. For example:

branch(home, x, INT_VAR_ACTION_MAX(0.99), INT_VAL_MIN());

uses action information with a decay-factor of 0.99. Even the decay-factor can be omitted and defaults to 1 (that is, no decay).

Action for other variable types is analogous.

8.5.4. Selection using CHB

The CHB (for conflict-history based branching) Q-score of a variable is a shared criterion and combines how often the domain of a variable has been reduced during constraint propagation with how recently the variable has been reduced during failure. CHB in Gecode is based on [29] which presents the heuristic for a SAT solver. Here, we use the term failure instead of conflict as originally in [29].

The Q-score \(\mathtt{qs}(\mathtt x)\) of a variable \(\mathtt x\) is maintained by constraint propagation as follows. For the computation of the Q-score, the following two variables are used:

  • The failure counter \(\mathtt{\#f}\) counts how often failure has been encountered. That is, each time a space is failed, \(\mathtt{\#f}\) is incremented by one and it is initialized to zero.

  • The step size \(\alpha\) is also updated when a failure occurs, it is updated by

    \[\alpha = \alpha - \mathtt{10}^{-\mathtt 6} \]

    provided \(\alpha>0.06\). If \(\alpha\leq 0.06\), its value does not change. \(\alpha\) is initialized to \(0.4\).

In addition to the Q-score for a variable, CHB also maintains the last failure \(\mathtt{lf}(\mathtt x)\) of a variable \(\mathtt x\). Each time constraint propagation finishes during search (by executing the status() function of a space, see also Propagation is explicit), the Q-score \(\mathtt{qs}(\mathtt x)\) and the last failure \(\mathtt{lf}(\mathtt x)\) of a variable \(\mathtt x\) are updated as follows:

  • If the variable x has not been pruned (that is, no values have been removed from the domain of x through propagation), the Q-score \(\mathtt{qs}(\mathtt x)\) and the last failure \(\mathtt{lf}(\mathtt x)\) do not change.

  • If the variable x has been pruned and propagation has failed, the last failure \(\mathtt{lf}(\mathtt x)\) is updated to

    \[\mathtt{lf}(\mathtt x)=\mathtt{\#f} \]

    and the Q-score is updated to

    \[\mathtt{qs}(\mathtt x)=(1-\alpha)\mathtt{qs}(\mathtt x) + \alpha r\]

    where the reward \(r\) is defined as

    \[r=\frac{1}{\mathtt{\#f}-\mathtt{lf}(\mathtt x) + 1} \]

  • If the variable x has been pruned and propagation has not failed, the last failure \(\mathtt{lf}(\mathtt x)\) remains unchanged and the Q-score is updated to

    \[\mathtt{qs}(\mathtt x)=(1-\alpha)\mathtt{qs}(\mathtt x) + \alpha r\]

    where the reward \(r\) is defined as

    \[r=\frac{0.9}{\mathtt{\#f}-\mathtt{lf}(\mathtt x) + 1} \]

  • The Q-score \(\mathtt{qs}(\mathtt x)\) of a variable x is by default initialized to be \(0.05\).

In order to use CHB Q-scores for branching, one must create an object of class IntCHB for integer variables, an object of class BoolCHB for Boolean variables, an object of class SetCHB for set variables, or an object of class FloatCHB for float variables. The object is responsible for recording CHB Q-score information.

If x is an integer variable array, then

IntCHB chb(home,x);

initializes the CHB information chb for the variables in x.

The Q-score of each variable in an array x can be initialized by a merit function, see User-defined variable selection. Here

IntCHB chb(home,x,
           [](const Space& home, IntVar x, int i) {
             return 0.0;
           });

initializes the Q-score of x[i] to 1.0.

A branching for integer variables using CHB information must be given an object of type IntCHB as argument. For example, the following brancher will select variables with largest Q-score as defined by chb first:

branch(home, x, INT_VAR_CHB_MAX(chb), INT_VAL_MIN());

Here the integer variable array x must be exactly the same that has been used for creating the integer CHB object chb.

The CHB object can be omitted if one does not want to initialize the Q-score explicitly as described above.

CHB for other variable types is analogous.

8.6. Random variable and value selection

One particular strategy for variable and value selection is by random. For integer variables, INT_VAR_RND(r) selects a random variable and INT_VAL_RND(r) selects a random value where r is a random number generator of class Rnd. For Boolean variables, BOOL_VAR_RND(r) selects a random variable and BOOL_VAL_RND(r) selects a random value. For set variables, SET_VAR_RND(r) selects a random variable and SET_VAL_RND_INC(r) and SET_VAL_RND_EXC(r) include and exclude a random value from a set variable. For float variables, FLOAT_VAR_RND(r) selects a random variable and FLOAT_VAL_SPLIT_RND(r) randomly selects the lower or upper half of the domain of a float variable.

The random number generators used for random variable and value selection follow a uniform distribution and must be initialized by a seed value. For example, a random number generator r is created and initialized with a seed value of 1 (the seed value must be an unsigned int) by

Rnd r(1U);

The seed value can be changed with the seed() function (if needed, the seed() function initializes the random number generator). For example, by

r.seed(2U);

the seed value is set to 2 (the seed() function also expects an argument of type unsigned int).

A random number generator is passed by reference to the brancher.

It is possible to use the same random number generator for both variable and value selection. For example, by

Rnd r(1U);
branch(home, x, INT_VAR_RND(r), INT_VAL_RND(r));

both the variable in x as well as its value are randomly selected using the numbers generated by r. It is of course also possible to use two separate random number generators as in:

Rnd r1(1U), r2(1U);
branch(home, x, INT_VAR_RND(r1), INT_VAL_RND(r2));

8.7. User-defined variable selection

Variables can be selected according to user-defined criteria implemented as a merit function. For integer variables, the type of the merit function is IntBranchMerit, for Boolean variables BoolBranchMerit, for set variables SetBranchMerit, and for float variables FloatBranchMerit. For integer variables, the type IntBranchMerit is defined as

  std::function<double(const Space& home, IntVar x, int i)>

where home refers to the home space, x is the integer variable for which a merit value should be computed and i refers to the position of x in the integer variable array passed as argument to the branch() function. The merit function types for Boolean, set, and float variables are analogous.

For example, the following merit function

auto m = [](const Space& home, IntVar x, int i) {
  return x.size();
}

simply returns the domain size of the integer variable x as the merit value. The merit function can be used to select a variable with either smallest or largest merit value. By

branch(home, INT_VAR_MERIT_MIN(m), INT_VAL_MIN());

a variable with least merit value according to the merit function m() is selected (that is, the first variable in the array with smallest size). A variable with maximal merit value is selected by:

branch(home, INT_VAR_MERIT_MAX(m), INT_VAL_MIN());

8.8. User-defined value selection

The value selected for branching and how the selected value is used for branching can be defined by branch value functions and branch commit functions.

Variable type

Value function type

Value type

IntVar

IntBranchVal

int

BoolVar

BoolBranchVal

int

SetVar

SetBranchVal

int

FloatVar

FloatBranchVal

FloatNumBranch

Figure 8.9 Branch value functions

A branch value function takes a constant reference to a space, a variable, and the variable’s position and returns a value, where the type of the value depends on the variable type. Figure 8.9 lists the branch value function types and the value types for the different variable types. For example, the type IntBranchVal for value functions for integer variables is defined as:

  std::function<int(const Space& home, IntVar x, int i)>

A branch commit function takes a reference to a space, the number of the alternative a (0 for the first alternative and 1 for the second alternative), a variable, the variable’s position, and a value selected by a branch value function. For example, the type IntBranchCommit for branch commit functions for integer variables is defined as:

  std::function<void(Space& home, unsigned int a,
                     IntVar x, int i, int n)>

Let us consider INT_VAL_MIN() as an example, but re-implemented by value and commit functions. The value function can be defined as:

auto v = [](const Space& home, IntVar x, int i) {
  return x.min();
}

and the commit function as:

auto c = [](Space& home, unsigned int a,
            IntVar x, int i, int n) {
  if (a == 0U) {
    rel(home, x, IRT_EQ, n);
  } else {
    rel(home, x, IRT_NQ, n);
  }
}

A branching using the value and commit function then can be posted by:

branch(home, x, INT_VAR_NONE(), INT_VAL(v,c));

The commit function is optional. If the commit function is omitted, a default commit function depending on the variable type is used. For integer variables, for example, the commit function corresponds to the commit function from the previous example. Hence, it is sufficient to post the brancher as:

branch(home, x, INT_VAR_NONE(), INT_VAL(v));

Variable type

Commit function type

Default behavior

IntVar

IntBranchCommit

\((\mathtt{x}=\mathtt{n})\vee(\mathtt{x}\neq\mathtt{n})\)

BoolVar

BoolBranchCommit

\((\mathtt{x}=\mathtt{n})\vee(\mathtt{x}\neq\mathtt{n})\)

SetVar

SetBranchCommit

\((\mathtt{n}\in\mathtt{x})\vee(\mathtt{n}\not\in\mathtt{x})\)

FloatVar

FloatBranchCommit

\((\mathtt{x}\leq\mathtt{n})\vee(\mathtt{x}\geq\mathtt{n})\)

Figure 8.10 Branch commit functions

Figure 8.10 lists the commit function types and the behavior of the default commit function for the different variable types. The variable x refers to the variable selected by the brancher and n to the value selected by the branch value function.

For examples which use value functions to implement problem-specific branching, see Black hole patience and The balanced academic curriculum problem.

8.9. Tie-breaking

The default behavior for tie-breaking during variable selection is that the first variable (that is the variable with the lowest index in the array) satisfying the selection criteria is selected. For many applications that is not sufficient.

A typical example for integer variables is to select a most constrained variable first (the variable most propagators depend on, that is, with largest degree). Then, among the most constrained variables select the variable with the smallest domain. This can be achieved by using the tiebreak() function:

branch(home, x, tiebreak(INT_VAR_DEGREE_MAX(), 
                         INT_VAR_SIZE_MIN()),
                INT_VAL_MIN());

The overloaded function tiebreak() (see Tie-breaking for variable selection) takes up to four variable selection values.

Random selection is particularly interesting for tie-breaking. For example, breaking ties by first selecting a variable with smallest domain and then selecting a random variable among those with smallest domain is obtained by:

branch(home, x, tiebreak(INT_VAR_SIZE_MIN(),
                         INT_VAR_RND(r)),
                INT_VAL_MIN());

Here, r must be a random number generator as discussed in Random variable and value selection.

Using tie-breaking limit functions. In the discussion so far only exact ties have been considered. Often it is necessary to consider several variables as ties even though some of them are not among the best variables. Which variables are considered as ties can be controlled by tie-breaking limit functions.

A tie-breaking limit function has the type BranchTbl which is defined as:

  std::function<double(const Space& home, double w, double b)>

The function takes a constant reference to a space home, the worst merit value w, and the best merit value b as arguments. The value returned by the function determines which variables are considered as ties.

Let us consider an example where we branch over four integer variables from the integer variable array x where the domains of the variables are as follows:

\[\mbox{\texttt{x[0]}}\in\{1,2,3,4\}\qquad \mbox{\texttt{x[1]}}\in\{2,3,4\}\qquad \mbox{\texttt{x[2]}}\in\{1,2,4\}\qquad \mbox{\texttt{x[3]}}\in\{1,2,3,4,5,6,7\}\]

Without a tie-breaking limit function as in (here, r is a random number generator):

branch(home, x, tiebreak(INT_VAR_SIZE_MIN(),
                         INT_VAR_RND(r)),
                INT_VAL_MIN());

the variables x[1] and x[2] (both with size as the merit value \(3.0\)) are considered as ties and random variable selection will choose one of them.

Likewise, when branching with

branch(home, x, tiebreak(INT_VAR_SIZE_MAX(),
                         INT_VAR_RND(r)),
                INT_VAL_MIN());

only variable x[3] will be considered as the single variable with the best merit value \(7.0\).

The following tie-breaking limit function

auto tbl = [](const Space& home, double w, double b) {
  return (w + b) / 2.0;
}

returns the average of the worst merit value w and the best merit value b. Using the function tbl() for tie-breaking is done by passing it as additional argument.

For example, when using tbl() with

branch(home, x, tiebreak(INT_VAR_SIZE_MIN(tbl),
                         INT_VAR_RND(r)),
                INT_VAL_MIN());

the function tbl() is called with \(\mathtt{w}=7.0\) and \(\mathtt{b}=3.0\) and returns \((7.0 + 3.0)/2.0=5.0\). Hence, the three variables x[0], x[1], and x[2] are considered for tie-breaking and random selection will make a choice among these three variables.

For example, when using tbl() with

branch(home, x, tiebreak(INT_VAR_SIZE_MAX(tbl),
                         INT_VAR_RND(r)),
                INT_VAL_MIN());

the function tbl() is called with \(\mathtt{w}=3.0\) and \(\mathtt{b}=7.0\) and returns \((3.0 + 7.0)/2.0=5.0\). Hence, only variable x[3] is considered for tie-breaking.

Note that worse and best depends on whether the variable selection tries to minimize or maximize the merit value. If a tie-breaking limit function returns a value that is worse than the worst merit value, all variables are considered for tie-breaking. If a function returns a value that is better than the best value, the returned value is ignored and the best value is considered as limit (in which case, tie-breaking works exactly the same as if not using a tie-breaking limit function at all).

8.10. Lightweight Dynamic Symmetry Breaking

Gecode supports automatic symmetry breaking with Lightweight Dynamic Symmetry Breaking (LDSB [34]). To use LDSB, you specify your problem’s symmetries as part of the branch() function.

Program 8.1 A Gecode model for Latin Squares with LDSB
class LatinSquare : public Script {
...
  LatinSquare(const SizeOptions& opt)
    : Script(opt), n(opt.size()), x(*this,n*n,0,n-1) {
    Matrix<IntVarArgs> m(x, n, n);
    for (int i=0; i<n; i++)
      distinct(*this, m.row(i));
    for (int i=0; i<n; i++)
      distinct(*this, m.col(i));
    // [latin square ldsb:symmetry breaking]
  }
  ...
};

Consider the model for the Latin Square problem in Program 8.1. A Latin Square is an \(\mathtt{n}\times\mathtt{n}\) matrix (see Matrix interface for arrays) where each cell takes a value between \(0\) and \(\mathtt n-1\) and no two values in a row or a column are the same. This is easily implemented using integer variables and distinct constraints.

The model has many solutions that are essentially the same due to symmetry. For example, the four solutions in Figure 8.11 are symmetric: from the top-left solution, we can get the top-right one by exchanging the first two rows, the bottom-left one by exchanging the second and third column, and the bottom-right one by swapping the values \(1\) and \(3\).

0

1

2

3

1

0

3

2

2

3

0

1

3

2

1

0

1

0

3

2

0

1

2

3

2

3

0

1

3

2

1

0

0

2

1

3

1

3

0

2

2

0

3

1

3

1

2

0

0

3

2

1

3

0

1

2

2

1

0

3

1

2

3

0

Figure 8.11 Symmetric solutions of the Latin Square problem

Gecode supports dynamic symmetry breaking, i.e., given a specification of the symmetries, it can avoid visiting symmetric states during the search, which can result in dramatically smaller search trees and greatly improved runtime for some problems.

Symmetries are specified by passing an object of type Symmetries to the branch() function. In the case of Latin Squares, we can easily break the value symmetry (that is, values that are interchangeable) as follows:

      Symmetries syms;
      syms << ValueSymmetry(IntArgs::create(n,0));
      // [latin square ldsb:row/column symmetry]
      branch(*this, x, INT_VAR_NONE(), INT_VAL_MIN(), syms);

Here, IntArgs::create(n,0) creates an array of integers with values \(\mathtt 0, \mathtt 1, \ldots, \mathtt{n}-1\) which specifies that all these values are symmetric, that is, interchangeable.

For the row and column symmetries, we need to declare a VariableSequenceSymmetry (see Symmetry declarations), which states that certain sequences of variables (in this case the rows and columns) are interchangeable:

      IntVarArgs rows;
      for (int r = 0; r < m.height(); r++)
        rows << m.row(r);
      syms << VariableSequenceSymmetry(rows, m.width());
      IntVarArgs cols;
      for (int c = 0; c < m.width(); c++)
        cols << m.col(c);
      syms << VariableSequenceSymmetry(cols, m.height());

Now the number of Latin squares found and the search effort required are greatly reduced. The code for the example in Program 8.1 has command line options for toggling between no symmetry breaking and LDSB.

For examples, consider Clique-based graph coloring and Steel-mill slab design problem.

8.10.1. Specifying Symmetry

LDSB supports four basic types of symmetry (see Symmetry declarations). Collections of symmetries are stored in a Symmetries object, which is passed to the branch() function. Any combination of symmetries is allowed.

  • A VariableSymmetry represents a set of variables that are interchangeable.

  • A ValueSymmetry represents a set of values that are interchangeable.

  • A VariableSequenceSymmetry represents a set of sequences of variables that are interchangeable.

  • A ValueSequenceSymmetry represents a set of sequences of values that are interchangeable.

In addition to constructing these symmetries directly, there are also some convenient functions for creating common kinds of symmetry:

  • values_reflect(), to map \(L\) to \(U\), \(L+1\) to \(U-1\) and so on, where \(L\) and \(U\) are the bounds of a variable

  • rows_interchange(), to specify that the rows of a matrix are interchangeable (see Gecode::Matrix)

  • columns_interchange(), to specify that the columns of a matrix are interchangeable (see Gecode::Matrix)

  • rows_reflect(), to specify that a matrix’s rows can be reflected (first row to last row, second row to second-last row and so on, see Gecode::Matrix)

  • columns_reflect(), to specify that a matrix’s columns can be reflected (see Gecode::Matrix)

  • diagonal_reflect(), to specify that a matrix can be reflected around its main diagonal (the matrix must be square, see Gecode::Matrix)

8.10.2. Notes

Symmetry breaking by LDSB is not guaranteed to be complete. That is, a search may still return two distinct solutions that are symmetric.

Combining LDSB with other forms of symmetry breaking — such as static ordering constraints — is not safe in general, and can cause the search to miss some solutions.

LDSB works with integer, Boolean, and set variables, and with any variable selection strategy. For integer variables, only value selection strategies that result in the variable being assigned on the left branch (such as INT_VAL_MIN(), INT_VAL_MED(), INT_VAL_MAX() or INT_VAL_RND()) are supported, other parameters throw an exception.

8.11. Using branch filter functions

By default, a variable-value branching continues to branch until all variables passed to the branching are assigned. This behavior can be changed by using a branch filter function.

A branch filter function is called during branching for each variable to be branched on. If the filter function returns true, the variable is considered for branching. Otherwise, the variable is simply ignored.

A branch filter function can be passed as the second to last (optional) argument when calling the branch() function.

The type of a branch filter function depends on the variable type. For integer variables, the type IntBranchFilter is defined as

typedef std::function<bool(const Space& home, IntVar x, int i)>
  IntBranchFilter;

That is, a branch filter function takes the home space and the position i of the variable x as argument. The position i refers to the position of the variable x in the array of variables used for posting the branching. For Boolean variables, the type is BoolBranchFilter, for set variables SetBranchFilter, and for float variables FloatBranchFilter.

Program 8.2 Model sketch for branch filter function
class Model : public Space {
protected:
  IntVarArray x;
public:
  Model(void) : ... {
    ...
    // [branch filter function sketch:post branching]
  }
  ...
  // [branch filter function sketch:define filter function]
};

Assume, for example, that we want to branch only on variables from a variable array x for branching with a domain size of at least 4. Consider the sketch of a model shown in Program 8.2.

The branch filter function can be defined as a static member function of the class Model as follows:

  static bool filter(const Space& home, IntVar y, int i) {
    return y.size() >= 4;
  }

Specifying that the branching should use the filter function is done as follows:

post branching 
    branch(home, x, ..., ..., &filter);

8.12. Using variable-value print functions

Search engines such as Gist (see Inspecting and comparing nodes) or others (see Printing information about alternatives.) use print() functions provided by branchers to display information about the alternatives that are explored during search. The information displayed for variable-value branchers can be programmed by using a variable-value print function.

A variable-value print function can be passed as the last (optional) argument when calling the branch() function.

The type of a variable-value print function depends on the variable type. For integer variables, the type IntVarValPrint is defined as

  std::function<void(const Space &home,
                     const Brancher& b, unsigned int a,
                     IntVar x, int i, const int& n,
                     std::ostream& o)>

That is, a variable-value print function takes the home space, a brancher b, the number of the alternative a, the position i of the variable x, and the integer value n as argument. The information will be printed on the standard output stream o. The position i refers to the position of the variable x in the array of variables used for posting the branching. For Boolean variables, the type is BoolVarValPrint, for set variables SetVarValPrint, and for float variables FloatVarValPrint.

For an example of how to use variable-value print functions, see Crossword puzzle.

8.13. Assigning integer, Boolean, set, and float variables

A special variant of branching is assigning variables: for a not yet assigned variable the branching creates a single alternative which assigns the variable a value. The effect of assigning is that assignment is interleaved with constraint propagation. That is, after an assignment has been done, the next assignment will be done only after the effect of the previous assignment has been propagated.

INT_ASSIGN_MIN()

smallest value

INT_ASSIGN_MED()

median value (rounding downwards)

INT_ASSIGN_MAX()

maximum value

INT_ASSIGN_RND(r)

random value

INT_ASSIGN(v, c*)

defined by value function v and commit function c

BOOL_ASSIGN_MIN()

smallest value

BOOL_ASSIGN_MAX()

maximum value

BOOL_ASSIGN_RND(r)

random value

BOOL_ASSIGN(v, c*)

defined by value function v and commit function c

SET_ASSIGN_MIN_INC()

include smallest element

SET_ASSIGN_MIN_EXC()

exclude smallest element

SET_ASSIGN_MED_INC()

include median element (rounding downwards)

SET_ASSIGN_MED_EXC()

exclude median element (rounding downwards)

SET_ASSIGN_MAX_INC()

include largest element

SET_ASSIGN_MAX_EXC()

exclude largest element

SET_ASSIGN_RND_INC(r)

include random element

SET_ASSIGN_RND_EXC(r)

exclude random element

SET_ASSIGN(v, c*)

defined by value function v and commit function c

FLOAT_ASSIGN_MIN()

median value of lower part

FLOAT_ASSIGN_MAX()

median value of upper part

FLOAT_ASSIGN_RND(r)

median value of randomly chosen part

FLOAT_ASSIGN(v, c*)

defined by value function v and commit function c

Figure 8.12 Value selection for assigning variables

For example, the next code fragment assigns all integer variables in x to their smallest possible value:

assign(home, x, INT_ASSIGN_MIN());

with the default variable selection strategy to select the next unassigned variable. All other variable selection criteria can also be used, the following is equivalent to the previous example:

assign(home, x, INT_VAR_NONE(), INT_ASSIGN_MIN());

The strategy to select the value for assignment is defined by a value of class IntAssign (see also Value selection for assigning integer variables) for integer variables, by a value of class BoolAssign (see also Value selection for assigning integer variables) for Boolean variables, by a value of class SetAssign (see also Assigning set variables) for set variables, and by a value of class FloatAssign (see also Value selection for assigning float variables) for float variables.

Figure 8.12 summarizes the value selection strategies for assigning integer, Boolean, set, and float variables. Here, an argument r refers to a random number generator of type Rnd which is discussed in Random variable and value selection. An argument v refers to a value selection function of type IntBranchVal for integer variables, BoolBranchVal for Boolean variables, SetBranchVal for set variables, and FloatBranchVal for float variables. An optional argument c refers to a commit function of type IntBranchCommit for integer variables, of type BoolBranchCommit for Boolean variables, of type SetBranchCommit for set variables, and of type FloatBranchCommit for float variables. Value and commit function can be used in the same way for assigning than for branching as described in User-defined value selection. The only difference is that the number of the alternative passed to the commit function is always zero (as there is only a single alternative).

The assign() function also accepts a branch filter function as described in Using branch filter functions as well as a variable-value print function as optional argument, see Using variable-value print functions for details, and can assign a single variable.

8.14. Executing code between branchers

A common scenario is to post some constraints only after part of the branching has been executed. This is supported in Gecode by a brancher (see Branch with a function) that executes a function (any function that is compatible with the type std::function).

Suppose the following code fragment defining a model Model:

class Model : public Space {
public:
  Model(void) : ... {
    ...
    // [exec:post branchings]
  }
  ...
  // [exec:define functions]
};

where the constructor posts two branchers

post branchings 
    branch(home, x, INT_VAR_NONE(), INT_VAL_MIN());
    branch(home, &Model::post);

The second branching takes a function pointer to the static member function Model::post which is defined as

  void more(void) {
    ...
  }
  static void post(Space& home) {
    static_cast<Model&>(home).more();
  }

As soon as the first branching is finished, the second branching is executed. This branching provides just a single alternative that calls the function Model::post with the current space as its argument. Then, the function casts the home to Model& and calls more on home. While one could post the additional constraints and/or branchings in Model::post directly, the member function Model::more is more convenient to use.