23. Getting started

This chapter shows how to implement simple propagators for simple constraints over integer variables. It introduces the basic concepts and techniques that are necessary for any propagator.

Here, and in the following chapters, the focus is on propagators over integer and Boolean variables. Part of the concepts introduced are specific to integer and Boolean propagators, however the techniques how to program efficient propagators are largely orthogonal to the type of variables. In Propagators for set constraints and Propagators for float constraints, the corresponding concepts for set and float variables are presented.

Important

This chapter introduces concepts and techniques step-by-step, starting with a naive and inefficient first version of a propagator that then is stepwise refined. Even if you feel compelled to start programming right after you have seen the first, naive variant, you should very definitely read on until having read the entire chapter.

Overview. The first three sections set the stage for programming propagators. Constraint propagation in a nutshell sketches how propagators perform constraint propagation and is followed by an overview of some useful background reading material (Background reading). What to implement? provides an overview of what needs to be implemented for a constraint followed by the first naive implementation of a simple constraint (Implementing the less constraint). The naive implementation is improved in Improving the Less propagator by both taking advantage of some predefined abstractions in Gecode and straightforward optimizations. This is followed by a discussion of propagation conditions as a further optimization to avoid redundant propagator executions (Propagation conditions). The next section (Using propagator patterns) presents a first reasonable propagator that takes advantage of predefined patterns to cut down on programming effort. The last two sections discuss the obligations a propagator must meet (Propagator obligations) and how some of these obligations can be waived by a propagator (Waiving obligations).

23.1. Constraint propagation in a nutshell

Constraints and variables are used for modeling constraint problems. However, the only reason for actually modeling a problem is to be able to solve it with constraint propagation by removing values from variables that are in conflict with a constraint. In order to implement constraint propagation, a constraint (typically) requires a propagator (or several propagators) as its implementation.

Views versus variables. The essence of a propagator is to remove values from variables that are in conflict with the constraint the propagator implements. However, a propagator does not use variables directly as they only offer operations for accessing but not removing values. Instead, a propagator uses variable views (or just views) as they offer operations for both value access and removal.

Views and variables have a simple relationship in that they both offer interfaces to variable implementations. When a variable is created for modeling, also a variable implementation is created. The variable serves as a read-only interface to the variable implementation. A view can be initialized from a variable: the view becomes just another interface to the variable’s variable implementation. For more information on the relationship between variables, views, and variable implementations see Programming variables.

In the following we often refer to the variables of a propagator as the variable implementations that the propagator refers to through views. That is, we will often not distinguish between variables, views, and variable implementations. There is little risk of confusion as propagators always compute with views and variable implementations are never exposed for programming propagators. Much more on the relationship between variables, views, and variable implementations can be found in Programming variables.

By the domain of a variable (or a view, or a variable implementation) we refer to the set of values the variable still can take. We will often use notation such as \(\mathtt{x}\in\{1,2,5\}\) which means that the domain of x is \(\{1,2,5\}\).

Executing propagators. A propagator is implemented in Gecode as a subclass of the class Propagator where the different tasks a propagator must be able to perform are implemented as virtual member functions. Before we describe these functions and their purpose, we sketch how a propagator actually performs constraint propagation.

Figure 23.1 Scheduling and executing propagators

As mentioned above, a propagator has several views on which it performs constraint propagation according to the constraint it implements. Like variables in modeling, propagators and views (more precisely, their variable implementations) belong to a home space (or just home). When a propagator is created, it subscribes to some of its views: subscriptions control the execution of a propagator. As soon as a view changes (the only way how a view can change is that some of its values are removed), all propagators that are subscribed to the view are scheduled for execution. Actually, subscriptions offer additional control in that only certain types of value removals schedule a propagator, this is discussed in Propagation conditions. A propagator that is not scheduled, is called idle. Scheduling and execution are sketched in Figure 23.1.

Eventually, the space chooses a scheduled propagator for execution and executes it by running the propagate() member function of the propagator, provided the propagator has not been disabled (propagators can be disabled through propagator groups, see Propagator groups). That is, disabled propagators are scheduled for execution but they are not executed. The propagate() member function possibly removes values and by this might schedule more propagators for eventual execution (possibly re-scheduling the currently executing propagator itself). Besides removing values and scheduling propagators, the propagate() member function reports about propagation. The details of what can be reported by a propagator are detailed in the following sections, but a particularly important report is: the propagator reports failure as it found out that the constraint it implements is unsatisfiable with the values left for the propagator’s views (this is described by returning the value ES_FAILED). The remaining return values are discussed in Implementing the less constraint and Improving the Less propagator.

To get the entire propagation process started, some but not necessary all propagators are scheduled as soon as they are created. Which propagators are scheduled initially is discussed in detail in Propagation conditions.

Propagation is interleaved in that a space executes only one propagator at a time. The process of choosing a scheduled propagator and executing it is repeated by the space until no more propagators are available for execution. If no more propagation is possible, a space is called stable. This process implements constraint propagation and must be explicitly triggered by executing the status() member function of a space (please consult Propagation is explicit). The status() function is typically invoked by a search engine (see Programming search engines for details).

Space and propagator fixpoints. We often refer to the fact that no more propagation is possible for a space by saying that the space is at fixpoint. Likewise, we say that a propagator that cannot remove any more values is at fixpoint. The term fixpoint is intuitive when one looks at typical models for constraint propagation: propagators are modeled as functions that take variables and their values as input and output, often referred to as stores or domains. A domain that is a fixpoint means that input and output for a propagator are the same and hence the propagator did not perform any propagation.

Disabling and re-enabling propagators. As mentioned above, propagators can be disabled and re-enabled. When re-enabling a disabled propagator, the propagator might have to be re-scheduled for execution. The re-scheduling is implemented by the reschedule() member function of a propagator.

23.2. Background reading

This document does not present any formal or mathematical model of how propagation is organized and which properties propagation has. There are numerous publications that do that in more detail than is possible in this document:

• A general overview of how a constraint programming system works can be found in [48].

• Realistic models that present many ideas that have been developed in the context of Gecode can be found in [51], [49], and [60].

• A truly general model for propagation that is used in Gecode is introduced in [53]. This publication is rather specialized and the generality of the model will be only briefly discussed later (see Propagator obligations and Recomputation invariants).

It is highly recommended to read about the general setup of constraint propagation in one of these papers. For more advanced ideas, we often refer to certain sections in the above publications or to further publications. Remember, one of the advantages of Gecode is that many of its key ideas have been introduced by Gecode and are backed by academic publications.

23.3. What to implement?

Our first propagator implements the less constraint \(x<y\) for two integer variables \(x\) and \(y\).

Constraint post functions. Before discussing what a propagator must do in detail, we need to discuss how to implement the function for our less constraint that can be used for modeling. As known from Modeling, the function should have a declaration such as

void less(Space& home, IntVar x0, IntVar x1);

We call a function implementing a constraint a constraint post function. The constraint post function less() takes a space home where to post the constraint (actually, where to post the propagator implementing the constraint) and variables x0 and x1. [1] The responsibilities of a constraint post function are straightforward: it checks whether its arguments are valid (and throws an exception otherwise), checks whether the home space is failed, sets some execution information, creates variable views for the variables passed to it, and then posts an appropriate propagator. This is detailed below.

Tip 23.1 (Variables and views are passed by value).

As discussed before, variables and views are nothing but different interfaces to variable implementations. Their implementations are hence strikingly simple: they just carry a pointer to a variable implementation and their member functions just call the appropriate member functions of the variable implementation (some views might store an additional integer as well). For that reason, it is sufficient to pass variables and views simply by value rather than by reference.

◄

What a propagator must do.

Figure 23.2 Propagators, views, and variable implementations

The previous section focused on the execution of a propagator that then prunes variables. While performing propagation is typically the most involved part of a propagator, a propagator must also handle several other tasks: how to post and initialize it, how to dispose it, how to copy it during cloning for search, how to re-schedule it, and when to execute it. How propagation is organized in Gecode is sketched in Figure 23.2, this paragraph will fill in the missing details.

posting

A constraint post function typically initiates the posting of one or several propagators. Posting a propagator is organized into two steps. The first step is implemented by a propagator post function, while the second is implemented by the propagator’s constructor.

Typical tasks in a propagator post function are as follows:

• Decide whether the propagator really needs to be posted.

• Decide whether a related, simpler, and hence more efficient propagator should be posted instead.

• Enforce certain invariants the propagator might require (for example, restricting the values of variables so that the propagator becomes simpler).

• Perform some initial propagation such that variable domains become reasonably small (for a discussion why small variable domains are useful, see Small variable domains are beautiful).

• Last but definitely not least, create an instance of the propagator.

The reason why posting requires a constraint post function as well as a propagator post function is to separate concerns. We will see later that the propagator post function is typically being reused by several constraints and also for propagator rewriting, an important technique which is discussed in Reification and rewriting. The post function of a propagator is conveniently implemented as a static member function post() of the propagator’s class.

The propagator’s constructor initializes the propagator and performs another essential task: it creates subscriptions to views for the propagator. Only if a propagator subscribes to a view (together with a propagation condition which is ignored for the moment and discussed later), the propagator is scheduled for execution whenever the domain of the view changes. Subscribing also automatically schedules the propagator for execution if needed (detailed in Propagation conditions).

disposal

Gecode does not automatically garbage collect propagators. [2] Propagators must be explicitly disposed. When a propagator is disposed it must also explicitly cancel its subscriptions (the subscriptions the propagator created in the constructor).

The only exception to this rule is that subscriptions on assigned variables do not need to be canceled. In fact, as an optimization, assigned variables do not maintain subscriptions: subscribing to an assigned variable schedules the propagator and canceling a subscription on an assigned variable does nothing. Disposal must also free other resources currently used by the propagator.

Propagator disposal is implemented by a virtual member function dispose(). A propagator has no destructor, the dispose function assumes this role instead. The reason to have a dispose() function rather than a destructor is that disposal requires the home space of a propagator which is passed as an argument to the dispose() function (destructors cannot take arguments in C++).

Disposal might be triggered by the propagator itself (in fact, this is the most common case) as we will see later. It is important to understand that when the space of a propagator is deleted, its propagators are not being disposed by default. A propagator can explicitly request to be disposed when its home is deleted (see Propagator obligations). A typical case where this is needed is when the propagator has allocated memory that is not managed by the space being deleted. In Managing memory, memory management is discussed in detail.

copying

Copying for propagators works exactly as does copying for spaces: a virtual copy() member function returns a copy of a propagator during cloning and a copy constructor is in charge of copying and updating the propagator’s data structures (in particular, its views).

cost computation

Scheduling a propagator guarantees that it is executed eventually but it does not specify when. When a propagator is executed, is defined by its cost. The cheaper it is to execute the propagator, the earlier the propagator should be executed. This is based on the intuition that a cheaper propagator might either already fail a space and hence no expensive propagators must be executed, or that a cheaper propagator might perform propagation from which a more expensive propagator can take advantage.

As to be expected, every propagator must implement a virtual cost() member function. This member function is called when the propagator is scheduled. In fact, the cost() function might be called several times when certain information (so-called modification event deltas) for a propagator changes. We postpone a discussion of the details to Staging.

The cost of executing a propagator is just an approximation that helps propagation in Gecode to be fast and also to prevent pathological behavior. Propagators of same cost are executed according to a first scheduled, first executed policy (basically, scheduling is organized fairly into queues of propagators with similar cost). However, Gecode does not give hard guarantees on the order of propagator execution: the cost of a propagator should be understood as a suggestion and not a requirement.

The only exception is a cost level called record that is reserved for propagators that only record information (such as for propagators that record information about action Local versus shared variable selection criteria or for tracing Tracers for integer and Boolean variables): they will always be executed after all propagators of lower cost (these propagators are also executed on a failed space).

For the interested reader, the design of cost-based scheduling for Gecode together with its evaluation can be found in [51].

propagation

The core of a propagator is how it performs propagation by removing values from its views that are in conflict with the constraint it implements. This is implemented by a virtual member function propagate() that returns an execution status.

The execution status returned by the propagate() function must capture several important aspects:

• As mentioned before, a propagator must report whether failure occurred by returning an appropriate value for the execution status. The propagator can either find out by some propagation rules that failure must be reported. Or, when it attempts to modify view domains, the modification operation reports that it failed (a so-called domain wipe-out occurred, as all values would have been removed). Modification operations are also called tell operations.

• A propagator must report when the propagator has become subsumed (also known as entailed): that is, when the propagator can never ever again perform any propagation and should be disposed.

  The requirement to report subsumption is rather weak in that a propagator must at the very latest report subsumption if all of its views are assigned (of course, it might report subsumption earlier, as will be discussed in Improving the Less propagator). With other words, a propagator must always report subsumption but can wait until all its views are assigned (unless it reports failure, of course).

• A propagator can characterize what it actually has computed: either a fixpoint for itself or not. We ignore this aspect for the time being and return to it in Improving the Less propagator and continue this discussion in Fixpoint reasoning reconsidered.

re-scheduling

The propagator’s virtual member function reschedule() re-schedules a propagator when it is re-enabled. Typically, the member function follows how the propagator creates subscriptions and is straightforward. The reschedule() function might be more involved for propagators using advisors, this is discussed in Advisors.

Obligations of a propagator. What becomes quite clear is that a propagator has to meet certain obligations (disposing subscriptions, detecting failure, detecting subsumption, and so on). Some obligations must be met in order to comply with Gecode’s requirements of a well-behaved propagator, other obligations must be met so that a propagator becomes a faithful implementation of a constraint. Propagator obligations provides an overview of all obligations a propagator must meet.

23.4. Implementing the less constraint

Program 23.1 A constraint and propagator for less

#include <gecode/int.hh>

using namespace Gecode;

class Less : public Propagator {
protected:
  Int::IntView x0, x1;
public:
  // [less:posting]
  // [less:disposal]
  // [less:copying]
  // [less:cost computation]
  // [less:re-scheduling]
  // [less:propagation]
};

void less(Space& home, IntVar x0, IntVar x1) {
  // [less:constraint post function]
}

Download: less.cpp

Program 23.1 shows the class definition Less for our less propagator and the definition of the constraint post function. Unsurprisingly, the propagator Less uses two views for integer variables of type Int::IntView and propagates that the values for x0 must be less than the values for x1.

The Less propagator inherits from the class Propagator defined by the Gecode kernel (as any propagator must do) and stores two integer views which are defined by Gecode’s integer module. Hence, we need to include <gecode/int.hh>. Note that only the constraint post functions of the integer module are available in the Gecode namespace. All other functionality, including Int::IntView, is defined in the namespace Gecode::Int.

Constraint post function. The constraint post function is implemented as follows:

constraint post function ≡

  Int::IntView y0(x0), y1(x1);
  if (Less::post(home,y0,y1) != ES_OK)
    home.fail();

The constraint post function creates two integer variable views y0 and y1 for its integer variable arguments and calls the static propagator post function as defined by the Less class. A propagator post function also returns an execution status of type ExecStatus (see Status of constraint propagation and branching commit) where the only two values that can be returned by a propagator post function are ES_OK (posting was successful) and ES_FAILED (the post function determined even without actually posting the propagator that the constraint Less is unsatisfiable). In case ES_FAILED is returned, the constraint post function must mark the current space home as failed (by using home.fail()).

Propagator posting. The posting of the Less propagator is defined by a constructor designed for initialization and a static post function returning an execution status as follows:

posting ≡

  Less(Space& home, Int::IntView y0, Int::IntView y1) 
    : Propagator(home), x0(y0), x1(y1) {
    x0.subscribe(home,*this,Int::PC_INT_DOM);
    x1.subscribe(home,*this,Int::PC_INT_DOM);
  }
  static ExecStatus post(Space& home, 
                         Int::IntView x0, Int::IntView x1) {
    (void) new (home) Less(home,x0,x1);
    return ES_OK;
  }

The constructor initializes its integer views and creates subscriptions to both x0 and x1. Subscribing to an integer view takes the home space, the propagator as subscriber (as a reference), and a propagation condition of type PropCond. We do not look any further into propagation conditions right here (Propagation conditions does this in detail) but give two hints. First, the values for propagation conditions depend on the variable view as witnessed by the fact that the value Int::PC_INT_DOM is declared in the namespace Gecode::Int. Second, Int::PC_INT_DOM creates a subscription such that the propagator is executed whenever the domain of x0 (respectively x1) changes.

The propagator post function is entirely naive in that it always creates a Less propagator and always succeeds (and hence returns ES_OK). Note that propagators can only be created in a space. Hence, the new operator is used in a placement version with placement argument (home) which allocates memory for the Less propagator from home.

Disposal. The virtual dispose() function for the Less propagator takes a home space as argument and returns the size of the just disposed propagator (as type size_t). [3] Otherwise, the dispose() function does exactly what has been described above: it cancels the subscriptions created by the constructor used for posting:

disposal ≡

  virtual size_t dispose(Space& home) {
    x0.cancel(home,*this,Int::PC_INT_DOM);
    x1.cancel(home,*this,Int::PC_INT_DOM);
    (void) Propagator::dispose(home);
    return sizeof(*this);
  }

Note that the arguments for canceling a subscription are (and must be) exactly the same as the arguments for creating a subscription.

Copying. The virtual copy() function and the corresponding copy constructor are unsurprising in that they follow exactly the same structure as the corresponding function and constructor for spaces used for modeling:

copying ≡

  Less(Space& home, Less& p) 
    : Propagator(home,p) {
    x0.update(home,p.x0);
    x1.update(home,p.x1);
  }
  virtual Propagator* copy(Space& home) {
    return new (home) Less(home,*this);
  }

The only aspect that deserves some attention is that a propagator must be created in a home space and hence a placement new operator is used (analogous to propagator posting).

Cost computation. Cost values for propagators are defined by the class PropCost. The class PropCost defines several static member functions with which cost values can be created. For Less, the cost() function returns a cost value for a binary propagator with low cost (as we will see below, the propagate() function is really cheap to execute):

cost computation ≡

  virtual PropCost cost(const Space&, const ModEventDelta&) const {
    return PropCost::binary(PropCost::LO);
  }

Please ignore the additional argument of type ModEventDelta to cost() for now, see Modification event deltas.

static cost functions
unary	propagator with single variable view
binary	propagator with two variable views
ternary	propagator with three variable view
dynamic cost functions
linear	propagator with \(\approx\) linear complexity (or \(O(n \log n)\))
quadratic	propagator with \(\approx\) quadratic complexity
cubic	propagator with \(\approx\) cubic complexity
crazy	propagator with \(\approx\) exponential (or large polynomial) complexity

Figure 23.3 Summary of propagation cost functions

The static member functions provided by PropCost are summarized in Figure 23.3. Each function takes either the value PropCost::LO (for low cost) or PropCost::HI (for high cost). The dynamic cost functions take an additional integer (or unsigned integer) value defining how many views the propagator is computing with.

For example, a propagator with n variables and complexity \(O(\mathtt n \log \mathtt n)\) might return a cost value constructed by

PropCost::linear(PropCost::HI,n);

As mentioned before, propagation cost is nothing but an approximation of the real cost of the next execution of the propagate() function of the propagator. The only hard fact you can rely on is that a propagator with a cost value using PropCost::HI is never given preference over a propagator with a cost value using PropCost::LO.

Re-scheduling. Re-scheduling the propagator after it has been enabled again, is done by the virtual reschedule() member function as follows:

re-scheduling ≡

  virtual void reschedule(Space& home) {
    x0.reschedule(home,*this,Int::PC_INT_DOM);
    x1.reschedule(home,*this,Int::PC_INT_DOM);
  }

Re-scheduling depends, like creating and cancelling subscriptions, on the views of the propagator and the propagation conditions and follows exactly the pattern of the subscribe() and cancel() functions.

Propagation proper. Before starting with the code for propagation, we have to work out how the propagator should prune. This can be rather involved, leading to specialized pruning or filtering algorithms. For our Less propagator, the filtering rules are simple:

• All values for x0 must be less than the largest possible value of x1.

• All values for x1 must be larger than the smallest possible value of x0.

These two rules can be directly implemented as follows (again, please ignore the additional argument of type ModEventDelta to propagate() for now):

propagation ≡

  virtual ExecStatus propagate(Space& home, const ModEventDelta&)  {
    if (x0.le(home,x1.max()) == Int::ME_INT_FAILED)
      return ES_FAILED;
    if (x1.gr(home,x0.min()) == Int::ME_INT_FAILED)
      return ES_FAILED;
    if (x0.assigned() && x1.assigned())
      return home.ES_SUBSUMED(*this);
    else 
      return ES_NOFIX;
  }

The le() (for less) modification operation applied to an integer view x takes a home space and an integer value n and keeps only those values from the domain of x that are smaller than n (gr() for greater is analogous). A view modification operation returns a modification event of type ModEvent (see Generic modification events and propagation conditions and Integer modification events and propagation conditions). A modification event describes how the domain of a view has changed, in particular the value Int::ME_INT_FAILED is returned if a domain wipe-out has occurred. In that case, the propagator has found out (just by attempting to perform a view modification operation) that the constraint it implements is unsatisfiable. In this case, a propagator immediately returns with the execution status ES_FAILED. Naturally, the member functions min() and max() of an integer view x just return the smallest and largest possible value of the domain of x.

If the propagator had not reported failure by returning ES_FAILED it would be faulty: it would incorrectly claim that values for the views are solutions of the constraint it implements. Being correct with respect to the constraint a propagator implements is one of the obligations of a propagator we will discuss in Propagator obligations.

eq(home,n)	assign to value n
nq(home,n)	remove value n
le(home,n)	restrict values to be less than n
lq(home,n)	restrict values to be less or equal than n
gr(home,n)	restrict values to be greater than n
gq(home,n)	restrict values to be greater or equal than n

Figure 23.4 Value-based modification functions for integer variable views

The modification operations for integer variable views taking a single integer value n as argument are listed in Figure 23.4. Integer variable views also support modification operations that simultaneously can operate on sets of values. These operations are discussed in Domain propagation.

The second part of the propagator is concerned with deciding subsumption: if both x0 and x1 are assigned, the propagator executes the function ES_SUBSUMED(). The function ES_SUBSUMED() disposes the propagator by calling its dispose() member function and returns a value for ExecStatus that signals that the propagator is subsumed. After returning, the memory for the propagator will be reused. It is important to understand that subsumption is not an optimization but a requirement: at the very latest when all of its views are assigned, a propagator must report subsumption! The propagator is of course free to report subsumption earlier as is exploited in Improving the Less propagator.

In case the propagator is neither failed nor subsumed, it reports an execution status ES_NOFIX. Returning the value ES_NOFIX means that the propagator will be scheduled if one of its views (x0 and x1 in our example) have been modified. If none of its views have been modified, the propagator is not scheduled. This rather naive statement of what the propagator has computed is improved in Improving the Less propagator.

Tip 23.2 (Immediately return after subsumption).

As mentioned above, the function ES_SUBSUMED() disposes a propagator. To not crash Gecode, you must immediately return after calling ES_SUBSUMED(). In particular, executing view modification operations or creating subscriptions by a disposed propagator will surely crash Gecode!

◄

23.5. Improving the Less propagator

Program 23.2 A better constraint and propagator for less

...
class Less : public Propagator {
...
public:
  Less(Home home, Int::IntView y0, Int::IntView y1) 
    ...
  }
  // [less better:posting]
  ...
  // [less better:propagation]
};

// [less better:constraint post function]

Download: less-better.cpp

Program 23.2 shows an improved implementation of the Less propagator together with the corresponding constraint post function less(). The propagator features improved posting, improved propagation, and improved readability.

A recurring theme in improving propagators in this and in the next section is not about sophisticated propagation rules (admittedly, Less does not have much scope for cleverness). In contrast, all improvements will try to achieve the best of all optimizations: avoid executing the propagator in the first place!

Improving posting. As mentioned above, all functions related to posting (constructor, propagator post function, and constraint post function) should take a value of type Home rather than Space&. The improved propagator honors this without any further changes (a Space is automatically casted to a Home if needed, and vice-versa). An example of how passing a Home value is actually useful can be found in A fully reified less or equal propagator.

The improved constraint post function is as follows:

constraint post function ≡

void less(Home home, IntVar x0, IntVar x1) {
  if (home.failed()) return;
  PostInfo pi(home);
  GECODE_ES_FAIL(Less::post(home,x0,x1));
}

The constraint post function features three improvements:

• The most obvious improvement: if the home space is already failed, no propagator is posted.

• The post function creates an object of class PostInfo. When the object is created, it provides information that a post function is currently being executed and to which propagator group the post function is associated (this information is available from home, another reason why one should always use the type Home rather than Space&). This information is useful for tracing, see Groups and tracing. When the object goes out of scope, it is also recorded that the post function is done.

• The variable views are initialized implicitly. Note that the propagator post function Less::post() is called with integer variables x0 and x1 which are automatically coerced to integer views (as Int::IntView has a non-explicit constructor with argument type IntVar).

• Instead of testing whether Less::post() returns ES_FAILED, the constraint post function uses the macro GECODE_ES_FAIL for convenience (doing exactly the same as shown before). Macros for checking and failing are summarized below.

The improved post function is a little bit more sophisticated:

posting ≡

  static ExecStatus post(Home home, 
                         Int::IntView x0, Int::IntView x1) {
    if (x0 == x1)
      return ES_FAILED;
    GECODE_ME_CHECK(x0.le(home,x1.max()));
    GECODE_ME_CHECK(x1.gr(home,x0.min()));
    if (x0.max() >= x1.min())
      (void) new (home) Less(home,x0,x1);
    return ES_OK;
  }

It includes the following improvements:

• The propagator is not posted if x0 and x1 happen to refer to the very same variable implementation. In that case, of course, x0 can never be less than x1 and post() can immediately report failure.

• The propagator performs one initial round of propagation already during posting. This yields small variable domains for other propagators to be posted (see Small variable domains are beautiful).

• If all values of x0 are already less than all values of x1 (that is, x0.max() < x1.min()), then the constraint that x0 is less than x1 already holds (it is subsumed). Hence, no propagator needs to be posted.

Improving propagation.

The propagate() function is improved as follows:

propagation ≡

  virtual ExecStatus propagate(Space& home, const ModEventDelta&)  {
    GECODE_ME_CHECK(x0.le(home,x1.max()));
    GECODE_ME_CHECK(x1.gr(home,x0.min()));
    if (x0.max() < x1.min())
      return home.ES_SUBSUMED(*this);
    else 
      return ES_FIX;
  }

with the following improvements:

• The checking macro GECODE_ME_CHECK checks whether a modification operation returns failure and then returns ES_FAILED.

• The propagator tries to detect subsumption early, it does not wait until both x0 and x1 are assigned. It uses exactly the same criterion that is used for avoiding posting of the propagator in the first place.

  This is entirely legal: a propagator can report subsumption as soon as the propagator will never propagate again (or, with other words, the propagator will always be at fixpoint). The obligation is: it must report subsumption (or failure) at the very latest when all of its views are assigned. Early subsumption means fewer propagator executions.

• If the propagator is not yet subsumed it returns ES_FIX instead of ES_NOFIX. This means that the propagator tells the Gecode kernel that what it has computed happens to be a fixpoint for itself.

  This is easy enough to see for Less: executing the propagate() function twice does not perform any propagation in the second call to propagate(). After all, only after x0.min() or x1.max() change, the propagator can prune again. As neither x0.min() nor x1.max() change (the propagator might change x1.min() or x0.max() instead), the propagator should report that it has computed a fixpoint.

  The situation where returning ES_FIX instead of ES_NOFIX differs, is when the propagator actually prunes the values for x0 or x1. If the propagator returns ES_NOFIX it will be scheduled in this situation. If it returns ES_FIX it will not be scheduled. The difference between ES_FIX and ES_NOFIX is sketched in Figure 23.1. Again, not scheduling a propagator means fewer propagator executions. Avoiding execution takes a second look at fixpoint reasoning for propagators.

check macros
GECODE_ME_CHECK(me)	Checks whether me signals failure and
	returns ES_FAILED.
GECODE_ES_CHECK(es)	Checks whether es signals failure or
	subsumption and returns es.
fail macros
GECODE_ME_FAIL(me)	Checks whether me signals failure, fails home, and returns.
GECODE_ES_FAIL(es)	Checks whether es signals failure, fails home, and returns.

Figure 23.5 Check and fail macros

Check and fail macros. Check and fail macros available in Gecode are summarized in Figure 23.5. Note that a check macro can be used in a propagator post function or in a propagate() function, whereas a fail macro can only be used in a constraint post function. Note also that both fail macros assume that the identifier home refers to the current home space. For an example of how to use GECODE_ES_CHECK, see Dynamic subscriptions. For an example of how to use GECODE_ME_FAIL, see A Boolean disjunction propagator.

In fact, explicitly testing whether a modification event returned by a view modification operation is equal to Int::ME_INT_FAILED is highly discouraged. If not using GECODE_ME_CHECK, the proper way to test for failure is as in:

if (me_failed(x0.le(home,x1.max())))
  return ES_FAILED;

Note that both GECODE_ME_CHECK as well as me_failed work for all variable views and not only for integer variable views.

23.6. Propagation conditions

This section discusses modification events and propagation conditions in more detail. A modification event describes how a modification operation has changed a view. A propagation condition describes when a propagator is scheduled depending on how the views it is subscribed to are modified.

Modification events. Modification operations on integer views might return the following values for ModEvent (we assume that the view x has the domain \(\{\mathtt 0, \mathtt 2, \mathtt 3\}\)):

• Int::ME_INT_NONE: the view has not been changed. For example, both x.le(home,5) and x.nq(home,1) return Int::ME_INT_NONE.

• Int::ME_INT_FAILED: the values of a view have been wiped out. For example, both x.le(home,0) and x.eq(home,1) return Int::ME_INT_FAILED.

  Note that when a modification operation signals failure, the values of a view might change unpredictably, see also When to inspect a variable. For example, the values might entirely remain or only part of the values are removed. This also clarifies that a view (or its variable implementation) does not maintain the information that a modification operation on it failed. This also stresses that it is essential to check the modification event returned by a modification operation for failure.

• Int::ME_INT_DOM: an inner value (that is neither the smallest nor the largest value) has been removed. For example, x.nq(home,2) (\(\mathtt x\in\{\mathtt 0,\mathtt 3\}\)) returns Int::ME_INT_DOM.

• Int::ME_INT_BND: the smallest or largest value of a view has changed but the view has not been assigned. For example, both x.nq(home,0) (\(\mathtt x\in\{\mathtt 2,\mathtt 3\}\)) and x.lq(home,2) (\(\mathtt x\in\{\mathtt 0,\mathtt 2\}\)) return Int::ME_INT_BND.

• Int::ME_INT_VAL: the view has been assigned to a single value. For example, both x.le(home,2) (\(\mathtt x =\mathtt 0\)) and x.gq(home,3) (\(\mathtt x =\mathtt 3\)) return Int::ME_INT_VAL.

Program 23.3 An even better constraint and propagator for less

...
class Less : public Propagator {
...
public:
  Less(Home home, Int::IntView y0, Int::IntView y1) 
    : Propagator(home), x0(y0), x1(y1) {
    x0.subscribe(home,*this,Int::PC_INT_BND);
    x1.subscribe(home,*this,Int::PC_INT_BND);
  }
  ...
  virtual size_t dispose(Space& home) {
    x0.cancel(home,*this,Int::PC_INT_BND);
    x1.cancel(home,*this,Int::PC_INT_BND);
    (void) Propagator::dispose(home);
    return sizeof(*this);
  }
  virtual void reschedule(Space& home) {
    x0.reschedule(home,*this,Int::PC_INT_BND);
    x1.reschedule(home,*this,Int::PC_INT_BND);
  }
  ...
};

...

Download: less-even-better.cpp

Propagation conditions. The propagation condition used in subscriptions determine, based on modification events, when a propagator is scheduled. Assume that a propagator p subscribes to the integer view x with one of the following propagation conditions:

• Int::PC_INT_DOM: whenever the view x is modified (that is, for modification events Int::ME_INT_DOM, Int::ME_INT_BND, and ME_INT_VAL on x), schedule p.

• Int::PC_INT_BND: whenever the bounds of x are modified (that is, for modification events Int::ME_INT_BND and Int::ME_INT_VAL on x), schedule p.

• Int::PC_INT_VAL: whenever x becomes assigned (that is, for modification event Int::ME_INT_VAL on x), schedule p.

For our Less propagator, the right propagation condition for both views x0 and x1 is of course Int::PC_INT_BND: the propagator can only propagate if either the lower bound of x0 or the upper bound of x1 changes. Otherwise, the propagator is at fixpoint. Again, the very point of propagation conditions is to avoid executing a propagator that is known to be at fixpoint. An even better propagator for less using the proper propagation conditions is shown in Program 23.3.

The idea to avoid execution depending on how variables change is well known and typically realized through so-called events. For an evaluation, see [51]. Distinguishing between modification events and propagation conditions has been introduced by Gecode, for a discussion see [60].

The Less propagator subscribes to both of its views (that is, x0 and x1). For some propagators it is actually sufficient to only subscribe to some but not all of its views. Dynamic subscriptions discusses partial and dynamically changing subscriptions for propagators.

Scheduling when posting. As mentioned earlier, a propagator also needs to be scheduled when it is created to get the process of constraint propagation started. More precisely, a propagator p might be scheduled when it subscribes to a view x. If x is assigned, p is always scheduled regardless of the propagation condition used for subscribing. If x is not assigned, p is only scheduled if the propagation condition is different from Int::PC_INT_VAL. The same holds for the schedule() function discussed in the previous section.

Program 23.4 A propagator for disequality

...
class Disequal : public Propagator {
...
public:
  Disequal(Home home, Int::IntView y0, Int::IntView y1) 
    : Propagator(home), x0(y0), x1(y1) {
    x0.subscribe(home,*this,Int::PC_INT_VAL);
    x1.subscribe(home,*this,Int::PC_INT_VAL);
  }
  ...
  virtual ExecStatus propagate(Space& home, const ModEventDelta&) {
    if (x0.assigned())  
      GECODE_ME_CHECK(x1.nq(home,x0.val()));
    else
      GECODE_ME_CHECK(x0.nq(home,x1.val()));
    return home.ES_SUBSUMED(*this);
  }
};

...

Download: disequality.cpp

With other words: propagation conditions provide a guarantee a propagator can rely on. In particular, for the propagator condition Int::PC_INT_VAL, the guarantee is that the propagator is only executed if a view is assigned.

Consider, for example, the implementation of the propagate() method for a disequality propagator shown in Program 23.4. The propagator waits until at least x0 or x1 are assigned (due to the propagation condition PC_INT_VAL). When its propagate() method is executed, the propagator can exploit that at least one of the views x0 and x1 is assigned by testing only x0 for assignment.

Scheduling when creating subscriptions can be avoided by giving false as an optional last argument to subscribe(). This is typically used when subscriptions are created during propagation, and the propagator does not need to be scheduled.

23.7. Using propagator patterns

single view patterns
UnaryPropagator	unary propagator with view x0
BinaryPropagator	binary propagator with views x0 and x1
TernaryPropagator	ternary propagator with views x0, x1, and x2
NaryPropagator	\(n\)-ary propagator with view array x
NaryOnePropagator	\(n\)-ary propagator with view array x and view y
mixed view patterns
MixBinaryPropagator	binary propagator with views x0 and x1
MixTernaryPropagator	ternary propagator with views x0, x1, and x2
MixNaryOnePropagator	\(n\)-ary propagator with view array x and view y

Figure 23.6 Propagator patterns

Gecode’s kernel defines common propagator patterns (see Propagator patterns) which are summarized in Figure 23.6. The single view patterns are templates that require a view as first argument and a propagation condition as second argument. The mixed view patterns require for each view or view array a view argument and a propagation condition. The mixed view patterns are useful when different types of views and/or different propagation conditions for the views are needed (see Offset views for an example).

The propagator patterns accept also a value Int::PC_INT_NONE for the propagation conditions that avoid creating subscriptions at all. This comes in handy when the propagator patterns are used in situations where no subscriptions are needed, see for example General Boolean disjunction.

The patterns define a constructor for creation (that also creates subscriptions to their views with the defined propagation conditions), a constructor for cloning, a dispose() member function, a cost() member function where the cost value is always the PropCost::LO variant of the corresponding cost function (that is, PropCost::unary() for UnaryPropagator, PropCost::linear() for NaryPropagator and NaryOnePropagator, and so on), and a reschedule() function. The integer module additionally defines patterns for reified propagators which are discussed in A fully reified less or equal propagator. [4]

Program 23.5 A concise constraint and propagator for less

...
class Less : public BinaryPropagator<Int::IntView,Int::PC_INT_BND> {
public:
  Less(Home home, Int::IntView x0, Int::IntView x1) 
    : BinaryPropagator<Int::IntView,Int::PC_INT_BND>(home,x0,x1) {}
  static ExecStatus post(Home home, 
                         Int::IntView x0, Int::IntView x1) {
    if (x0 == x1)
      return ES_FAILED;
    GECODE_ME_CHECK(x0.le(home,x1.max()));
    GECODE_ME_CHECK(x1.gr(home,x0.min()));
    if (x0.max() >= x1.min())
      (void) new (home) Less(home,x0,x1);
    return ES_OK;
  }
  Less(Space& home, Less& p) 
    : BinaryPropagator<Int::IntView,Int::PC_INT_BND>(home,p) {}
  virtual Propagator* copy(Space& home) {
    return new (home) Less(home,*this);
  }
  virtual ExecStatus propagate(Space& home, const ModEventDelta&)  {
    GECODE_ME_CHECK(x0.le(home,x1.max()));
    GECODE_ME_CHECK(x1.gr(home,x0.min()));
    if (x0.max() < x1.min())
      return home.ES_SUBSUMED(*this);
    else 
      return ES_FIX;
  }
};

void less(Home home, IntVar x0, IntVar x1) {
  GECODE_POST;
  GECODE_ES_FAIL(Less::post(home,x0,x1));
}

Download: less-concise.cpp

Program 23.5 shows how to use the BinaryPropagator pattern for the less constraint. To give an impression of what needs to be implemented, the code for implementing the less constraint is shown in full. Note that one must define a propagator post function and the virtual member functions copy() and propagate(). Of course, one could also choose to overwrite the virtual member functions dispose() and cost() if needed.

Post macro. Please note that the constraint post function in Program 23.5 use the macro GECODE_POST to replace the check whether home is failed and the creation of an object of type PostInfo as discussed in Improving posting..

23.8. Propagator obligations

A propagator has to meet three different kinds of obligations: obligations towards the constraint it implements, obligations towards the amount of propagation it performs, and obligations that are Gecode specific. Some obligations can be waived by notifying the Gecode kernel that a propagator does not comply (see Waiving obligations).

Constraint implementation. A propagator must be

correct

A propagator must be correct in that it never prunes values that can appear in a solution of the constraint it implements.

checking

A propagator must be checking: at the very latest when all views are assigned, the propagator must decide whether the assignment is a solution of the constraint or not (in which case the propagator must report failure).

Amount of propagation. A propagator must be

contracting

A propagator is only allowed to remove values. The modification operations we have been discussing so-far naturally satisfy this property. For some operations that are discussed in Iterator-based modification operations extra carefulness is required.

monotonic

By default, a propagator must be monotonic: a propagator is not allowed to perform more pruning when executed for views with more values than when executed for views with less values.

Propagators are typically monotonic unless they use randomization, approximation, or something similar. For more details see below. This obligation can be waived.

subscription complete

A propagator must create sufficient subscriptions such that it is scheduled for execution when it is not at fixpoint.

fixpoint and subsumption honest

A propagator is not allowed to claim that it has computed a fixpoint or is subsumed if it is not (that is, it could still propagate).

Implementation specific obligations. A propagator must be

subsumption complete

At the very latest, a propagator must report subsumption if all views it has subscribed to are assigned.

external resource free

By default, a propagator cannot allocate memory from any other source (or any other resource) but its home space as the dispose() member function is not automatically called when the propagator’s home space is deleted. This obligation can be waived.

update complete

All views a propagator subscribes to must be updated during cloning (that is, a propagator can only subscribe to views it actually stores).

The reason for this obligation is that a space does not know its views (and variable implementations). It only gets to know them during cloning when they are explicitly updated. Having subscription information maintained by Gecode’s kernel without updating the corresponding variable implementations will leave a space after cloning in an inconsistent state (crashes are guaranteed).

cloning conservative

When a propagator is copied during cloning, it is not allowed to perform any variable modification operations nor is it allowed to change its subscriptions.

subscription correct

Any subscription to a view must eventually be canceled (typically in the dispose() member function), unless the view is assigned.

23.9. Waiving obligations

A propagator can notify its home space about some of its properties (as defined by ActorProperty, see Programming actors) that relate to some of the obligations mentioned in the previous section.

Weakly monotonic propagators. If a propagator p intends to be non-monotonic, it can notify its home space home by

home.notice(p,AP_WEAKLY);

It can revoke this notice later (it must revoke this at latest in its dispose() function) by

home.ignore(p,AP_WEAKLY);

This is typically done in the constructor of the propagator and means that the propagator intends to be only weakly monotonic: it is sufficient for the propagator to be checking and correct. For a discussion of weak monotonicity together with an example, see [53].

Currently, the information about a propagator being weakly monotonic is ignored.

Calling dispose() during space deletion. If a propagator p needs to use external resources or non-space allocated memory, it must inform its home space during posting about this fact by:

home.notice(p,AP_DISPOSE);

This will ensure that the dispose() function of the propagator p will be called when its home space is deleted.

In its dispose function the propagator p must revoke this notice by

home.ignore(p,AP_DISPOSE);

For examples, see The samedom constraint and Improving branching. In Managing memory, memory management is discussed in detail.

[1]

As we will discuss later (and as you might have noticed when modeling with Gecode, see Space& versus Home), a constraint post function takes a value of class Home instead of Space&. A value of type Home includes a reference to a space together with potentially additional information useful for posting. This aspect is discussed in Improving the Less propagator in more detail.

[2]

One of the key design principles of Gecode is: no magic! Whatever needs to be done must be done explicitly.

[3]

Following the discussion from above, the size of a disposed propagator must be returned explicitly, as propagators do not use destructors that implicitly handle size.

[4]

As reified propagators require Boolean views, reified patterns are provided by the integer module and not by the kernel. The kernel knows nothing about the different views programmed on top of it.