28. Views

This chapter should come as a welcome diversion from the previous chapters in this part. Instead of introducing more concepts and techniques for programming propagators, it shows how to straightforwardly and efficiently reuse propagators for implementing several different constraints. In a way, the chapter tells you how to cache in on all the effort that goes into developing a propagator.

The idea is to make a propagator generic with respect to the views the propagator computes with. As we are talking C++, generic propagators will be nothing but templates where the template arguments happen to be view types. Then, by instantiating the template propagator, one can obtain implementations for several constraints from a single propagator. More on views (a concept introduced by Gecode) can be found in [54] and [52].

As it comes to importance, this chapter should be the second in this part. However, the chapter comes rather late to be able to draw on the example propagators presented in the previous chapters.

Overview. Integer variable views are discussed in Integer views and Boolean variable views are discussed in Boolean views. How integer propagators can be reused for Boolean views is presented in Integer propagators on Boolean views.

28.1. Integer views

Assume that we need an implementation for the min constraint. Of course, we could implement a Min propagator analogous to the Max propagator from Rewriting during propagation. But let us assume that we need to be lazy in that we do not have the time to implement Min (after all, there are more interesting constraints out there that we want to implement).

What we could do to implement \(\min(\mathtt{x},\mathtt{y})=\mathtt{z}\) is to introduce three new variables \(\mathtt{x}'\), \(\mathtt{y}'\), and \(\mathtt{z}'\), post three constraints such that \(\mathtt{x}=-\mathtt{x}'\), \(\mathtt{y}=-\mathtt{y}'\), and \(\mathtt{z}=-\mathtt{z}'\), and finally post a max constraint instead: \(\max(\mathtt{x}',\mathtt{y}')=\mathtt{z}'\). While the strength of propagation is uncompromised, efficiency is poor: three additional variables and three additional propagators are needed.

28.1.1. Minus views

Minus views can do exactly what we discussed above but without creating additional variables or propagators. Assume that we have an integer view \(\mathtt{x}\) that serves as an interface to a variable implementation \(v\). Then, a minus integer view \(\mathtt{m}\) for \(v\) is also an interface to \(v\), however the interface implements operations such that \(\mathtt{m}\) is an interface to \(-v\).

For example, assume that the domain of \(\mathtt{x}\) is \(\{-1,1,3,4,6\}\) (which also means that \(v\in\{-1,1,3,4,6\}\)). Then, the domain for m is \(\{-6,-4,-3,-1,1\}\). For example, m.min() returns \(-6\) (which, of course, is nothing but -x.max()) and the modification operation m.gq(home,-3) results in domains \(\mathtt{m}\in\{-3,-1,1\}\) and \(\mathtt{x}\in\{-1,1,3\}\) (which, of course, is the same as x.lq(home,-(-3)) and hence as x.lq(home,3)).

The very point of this exercise is: a minus view is just a different interface to an existing variable implementation and does not require a new variable implementation. Moreover, the operations performed by the minus view interface are optimized away at compile time.

Program 28.1 Minimum and maximum constraints implemented by a Max propagator

...
template<class View>
class Max : public TernaryPropagator<View,Int::PC_INT_BND> {
protected:
    using TernaryPropagator<View,Int::PC_INT_BND>::x0;
    using TernaryPropagator<View,Int::PC_INT_BND>::x1;
    using TernaryPropagator<View,Int::PC_INT_BND>::x2;
...
};

void min(Home home, IntVar x0, IntVar x1, IntVar x2) {
  GECODE_POST;
  Int::MinusView y0(x0), y1(x1), y2(x2);
  GECODE_ES_FAIL(Max<Int::MinusView>::post(home,y0,y1,y2));
}
void max(Home home, IntVar x0, IntVar x1, IntVar x2) {
  GECODE_POST;
  GECODE_ES_FAIL(Max<Int::IntView>::post(home,x0,x1,x2));
}

Download: min-and-max.cpp

Program 28.1 shows how to obtain both min and max constraints from the very same Max propagator using Int::IntView and Int::MinusView views. The only change needed compared to the Max propagator from Rewriting during propagation is that the propagator does not hardwire its view type. Instead, the propagator is generic by being implemented as a template over the view type View it uses. The constraint post functions then just instantiate the Max propagator with the appropriate view types.

Tip 28.1 (Using using clauses).

Note the using clauses in Program 28.1. They make x0, x1, and x2 visible for the Max propagator. This is necessary in C++ as Max inherits from a base class that itself depends on the template argument View of Max. There are other possibilities to refer to members such as x0 that also work, for example by writing this->x0 instead of just x0. We choose the variant with using clauses to keep the code of the propagator uncluttered.

◄

28.1.2. Offset views

Program 28.2 Domain equality with and without offset

...
template<class View0, class View1>
class Equal 
  : public MixBinaryPropagator<View0,Int::PC_INT_DOM,
                               View1,Int::PC_INT_DOM> {
...
};

void equal(Home home, IntVar x0, IntVar x1) {
  GECODE_POST;
  GECODE_ES_FAIL((Equal<Int::IntView,Int::IntView>
                  ::post(home,x0,x1)));
}
void equal(Home home, IntVar x0, IntVar x1, int c) {
  GECODE_POST;
  GECODE_ES_FAIL((Equal<Int::IntView,Int::OffsetView>
                  ::post(home,x0,Int::OffsetView(x1,c))));
}

Download: domain-equal-with-and-without-offset.cpp

An offset view o with offset c (an integer value) for a variable implementation \(v\) provides operations such that o behaves as \(v+\mathtt c\).

Program 28.2 shows how a domain equality constraint (see Iterator-based modification operations) and a domain equality constraint with offset (see Taking advantage of iterators) can be obtained from the same domain equality propagator Equal. Equal has two template arguments View0 and View1 for its views x0 and x1 respectively. With two view template arguments, the propagator can be instantiated with different view types for x0 and x1. Therefore, the propagator uses MixBinaryPropagator as base class as it supports different view types as well.

shared versus ==. The domain modification operations inter_r and narrow_r used in the Equal propagator from Iterator-based modification operations are used such that the operations perform a more efficient in-place update of the view domain (with an additional Boolean value false as last and optional argument). This is only legal because the range iterator passed as argument to the modification operations does not depend on the view being modified. The post function of Equal ensures this by only posting the propagator if the two views x0 and x1 are not referring to the very same variable implementation (that is, x0==x1 is false).

With arbitrary views, the situation becomes a little bit more involved. Assume that x0 is an integer view referring to the variable implementation \(v\) and that x1 is an offset integer view for the same variable implementation \(v\) and an integer value \(c\neq 0\). In this case, the views x0 and x1 share the same variable implementation \(v\) but are not the same.

The function shared() tests whether two views share the same variable implementation. Hence, the use of domain modification operations in Equal have to be modified as follows:

domain propagation ≡

    Int::ViewRanges<View0> r0(x0);
    GECODE_ME_CHECK(x1.inter_r(home,r0,shared(x0,x1)));
    Int::ViewRanges<View1> r1(x1);
    GECODE_ME_CHECK(x0.narrow_r(home,r1,shared(x0,x1)));

Now, the more efficient in-place operations are used only if x0 and x1 do not share the same variable implementation.

28.1.3. Constant and scale views

In addition to minus and offset views, Gecode offers scale views and constant views for integer variable implementations.

A scale view for a variable implementation \(v\) with an integer scale factor \(a\) where \(a>0\) implements operations for \(a\cdot v\). Scale views exist in two variants differing in the precision of multiplication: IntScaleView performs multiplication over integers, whereas LLongScaleView performs multiplication over long long integers (see Integer views and Int::ScaleView).

An integer constant view Int::ConstIntView provides an integer view interface to an integer constant c. With other words, an integer constant view for the integer c behaves as an integer view assigned to the value c.

28.2. Boolean views

Program 28.3 Disjunction and conjunction from same propagator

...
template<class View>
class OrTrue : 
  public BinaryPropagator<View,Int::PC_BOOL_VAL> {
...
};

void dis(Home home, const BoolVarArgs& x, int n) {
  ...
}

void con(Home home, const BoolVarArgs& x, int n) {
  ...
  } else {
    ViewArray<Int::NegBoolView> y(home,x.size());
    for (int i=x.size(); i--; )
      y[i]=Int::NegBoolView(x[i]);
    GECODE_ES_FAIL(OrTrue<Int::NegBoolView>::post(home,y));
  }
}

Download: or-and-and-from-or.cpp

For Boolean views, the view resembling a minus view over integers is a view for negation. For example, with Boolean negation views Int::NegBoolView both disjunction and conjunction constraints can be obtained from a propagator for disjunction (see Program 28.3).

28.3. Integer propagators on Boolean views

As has been discussed in A Boolean disjunction propagator, Boolean views feature all operations available on integer views (such as lq() or gr()) in addition to the dedicated Boolean operations (such as one() or zero()). Due to the availability of integer operations on Boolean views, integer propagators can be used to implement Boolean constraints.

Program 28.4 Less constraints for both integer and Boolean variables

...
template<class View>
class Less : public BinaryPropagator<View,Int::PC_INT_BND> {
protected:
    ...
};

void less(Home home, IntVar x0, IntVar x1) {
  GECODE_POST;
  GECODE_ES_FAIL(Less<Int::IntView>::post(home,x0,x1));
}
void less(Home home, BoolVar x0, BoolVar x1) {
  GECODE_POST;
  GECODE_ES_FAIL(Less<Int::BoolView>::post(home,x0,x1));
}

Download: less-for-integer-and-Boolean-variables.cpp

Program 28.4 shows how the propagator Less can be used to implement the less constraint for both integer and Boolean variables.

Tip 28.2 (Boolean variables are not integer variables).

The above example uses a template to obtain an implementation of a constraint on both integer and Boolean variables. This is necessary as Boolean variables are not integer variables (in the sense that BoolVar is not a subclass of IntVar). The same holds true for their views and variable implementations.

This is by design: Boolean variables are not integer variables as they have a specially optimized implementation (taking advantage of the limited possible variable domains and that only PC_BOOL_VAL as propagation condition is needed).

◄