33. Advanced topics¶

This chapters presents advanced topics for programming branchers as implementations of branchings.

Overview. Assignment branchers presents a specialized brancher for assigning views rather than branching on them. How branchers support no-goods is discussed in Supporting no-goods. Variable views for branchers are discussed in Using variable views.

33.1. Assignment branchers¶

This section presents an example for a brancher that assigns all of its views rather than branches on its views. The branching

void assignmin(Home home, const IntVarArgs& x);

assigns all variables in x to their smallest possible value. That is, assignmin is equivalent to the predefined branching (see Assigning integer, Boolean, set, and float variables) used as

assign(home, x, INT_ASSIGN_MIN());

Program 33.1 A brancher for assignmin¶

...
class AssignMin : public Brancher {
...
  class PosVal : public Choice {
  public:
    int pos; int val;
    PosVal(const AssignMin& b, int p, int v)
      : Choice(b,1), pos(p), val(v) {}
    ...
  };
...
  virtual ExecStatus commit(Space& home, 
                            const Choice& c,
                            unsigned int a) {
    const PosVal& pv = static_cast<const PosVal&>(c);
    int pos=pv.pos, val=pv.val;
    return me_failed(x[pos].eq(home,val)) ? ES_FAILED : ES_OK;
  }
  ...
};

...

Download: assign-min.cpp

Program 33.1 shows the relevant parts of the brancher AssignMin. Unsurprisingly, both the status() and choice() function are identical to those shown in Program 32.2 (and hence are omitted).

The changes concern the created choice of type PosVal: the constructor now initializes a choice with a single alternative only (the second argument to the call of the constructor Choice). The commit() function is a specialized version of the commit() function defined in Program 32.2. It only needs to be capable of handling a single alternative. The same holds true for the print() function.

33.2. Supporting no-goods¶

Supporting no-goods by a brancher is straightforward: every brancher has a virtual member function ngl() (for no-good literal) that takes the same arguments as the commit() member function: a space, a choice, and the number of the alternative and returns a pointer to a no-good literal of class NGL. The ngl() function is called during no-good generation (see No-goods from restarts) and the returned no-good literal is then used by a no-good propagator that propagates the no-goods (if you are curious, the propagator is implemented by Search::NoGoodsProp).

Program 33.2 Branching for nonemin with no-good support¶

...
class EqNGL : public NGL {
protected:
  Int::IntView x; int n;
public:
  EqNGL(Space& home, Int::IntView x0, int n0)
    : NGL(home), x(x0), n(n0) {}
  EqNGL(Space& home, EqNGL& ngl)
    : NGL(home, ngl), n(ngl.n) {
    x.update(home, ngl.x);
  }
  // [none min with no-good support:status]
  // [none min with no-good support:prune]
  // [none min with no-good support:subscribe and cancel]
  // [none min with no-good support:re-scheduling]
  virtual NGL* copy(Space& home) {
    return new (home) EqNGL(home,*this);
  }
  virtual size_t dispose(Space& home) {
    (void) NGL::dispose(home);
    return sizeof(*this);
  }
};

class NoneMin : public Brancher {
...
public:
  ...
  // [none min with no-good support:no-good literal creation]
};
...

Download: none-min-with-no-good-support.cpp

By default, the ngl() function of a brancher returns NULL, which means that the brancher does not support no-goods. In order to support no-goods, a brancher must redefine the ngl() function and must define a class (or several classes) for the no-good literals to be returned. The class EqNGL implementing a no-good literal for equality and the ngl() function is shown in Program 33.2. Otherwise, the brancher is the same as the nonemin brancher shown in Program 32.2.

33.2.1. Returning no-good literals¶

The ngl() function of a brancher has the following options:

As mentioned above, it can always return NULL and hence the brancher does not support no-goods.
It returns for each alternative of a choice a no-good literal. For our NoneMin brancher this would entail that when ngl(home,c,0) is called, it returns a no-good literal implementing equality between a view and an integer that corresponds to the first alternative (for a given space home and a choice c).

For the second alternative ngl(home,c,1) a no-good literal implementing disequality should be returned. This would work, but the brancher can do better than that as is explained below.
When ngl(home,c,a) is called for an alternative where \(\mathtt{a}>0\) with a space home and a choice c and a is the last alternative (for NoneMin, \(\mathtt{a}=\mathtt{1}\)) and the last alternative is the logical negation of all other alternatives, then the ngl() function can return NULL as an optimization.

Assume that the alternatives of a choice are

\[\mathtt{l}_0\vee\ldots\vee\mathtt{l}_{\mathtt{n}-1} \]

where n is the arity of the choice and it holds that

\[(\mathtt{l}_0\vee\ldots\vee\mathtt{l}_{\mathtt{n}-2}) \Leftrightarrow \neg\mathtt{l}_{\mathtt{n}-1}\]

is true, then the ngl() function can return NULL for the last alternative (that is, for the alternative \(\mathtt{n}-1\)).

Note that this optimization implements the very same idea as discussed at the beginning of No-goods from restarts. Note also that this property is typically only true for branchers with binary choices such as in our example.

In our example, the second alternative is indeed the negation of the first alternative. Hence the following ngl() function implements no-good literal creation and only requires a single class EqNGL for no-good literals implementing equality:

no-good literal creation

  virtual NGL* ngl(Space& home, const Choice& c,
                   unsigned int a) const {
    const PosVal& pv = static_cast<const PosVal&>(c);
    int pos=pv.pos, val=pv.val;
    if (a == 0)
      return new (home) EqNGL(home, x[pos], val);
    else
      return NULL;
  }

33.2.2. Implementing no-good literals¶

No-good literals implement constraints that correspond to alternatives of choices. But instead of implementing these constraints by a propagator, they have a specialized implementation that is used by a no-good propagator. All concepts needed to implement a no-good literal are concepts that are familiar from implementing a propagator.

A no-good literal inherits from the class NGL and must implement the following constructors and functions:

Unsurprisingly, a no-good literal must implement constructors for creation and cloning and member functions copy() for copying and dispose() for disposal. They are straightforward and are shown in Program 33.2.
It must implement a status() function that checks whether the no-good literal is subsumed (the function returns NGL::SUBSUMED), failed (the function returns NGL::FAILED), or neither (the function returns NGL::NONE). The return type is NGL::Status as defined in the NGL class.

It is important to understand that the no-good propagator using no-good literals can only perform propagation if some of its no-good literals become subsumed. Hence, the test for subsumption used in status() should try to detect subsumption as early as possible.

Testing subsumption for our EqNGL no-good literal is straightforward:

status

  virtual NGL::Status status(const Space& home) const {
    if (x.assigned())
      return (x.val() == n) ? NGL::SUBSUMED : NGL::FAILED;
    else 
      return x.in(n) ? NGL::NONE : NGL::FAILED;
  }

The prune() function propagates the negation of the constraint that the no-good literal implements.

Again, the prune() function for NoneMin is straightforward:

prune

  virtual ExecStatus prune(Space& home) {
    return me_failed(x.nq(home,n)) ? ES_FAILED : ES_OK;
  }

A no-good literal must implement a subscribe() and a cancel() function that subscribe and cancel the no-good propagator to the no-good literal’s views.

As mentioned above, the earlier the status() function detects subsumption, the more constraint propagation can be expected from the no-good propagator. Hence, it is important to choose the propagation condition for subscriptions such that whenever there is a modification to the view that could result in subsumption the no-good propagator is executed.

For the EqNGL no-good literal, we choose the propagation condition for subscriptions to be Int::PC_INT_VAL (see Propagation conditions for a discussion of propagation conditions). This choice reflects the fact that subsumption can only be decided after the view x has been assigned:

  virtual void subscribe(Space& home, Propagator& p) {
    x.subscribe(home, p, Int::PC_INT_VAL);
  }
  virtual void cancel(Space& home, Propagator& p) {
    x.cancel(home, p, Int::PC_INT_VAL);
  }

A no-good literal must also implement a reschedule() function that re-schedules the no-goods propagator when it is re-enabled. The reschedule() function is straightforward, following the patterns of the subscribe() and cancel() functions:

re-scheduling

  virtual void reschedule(Space& home, Propagator& p) {
    x.reschedule(home, p, Int::PC_INT_VAL);
  }

In case a no-good literal uses members that must be deallocated when the home-space is deleted, the no-good literal’s class must redefine the virtual member functions notice() and dispose(), for example by:

virtual bool notice(void) const {
  return true;
}
virtual size_t dispose(Space& home) {
  ...
}

If notice() returns true, the no-good propagator ensures that the no-good literal’s dispose() function is called whenever the propagator’s home-space is deleted.

33.3. Using variable views¶

Variable views can also be used for reusing branchers to obtain several branchings, similar to reusing propagators for several constraints, see Views.

While in principle all different variable views introduced in Views can be used for branchers, the only meaningful variable view for branchers is the minus integer view (see Minus views).

Program 33.3 Branchings for nonemin and nonemax¶

...
template<class View>
class NoneMin : public Brancher {
...
};
void nonemin(Home home, const IntVarArgs& x) {
  ...
}
void nonemax(Home home, const IntVarArgs& x) {
  if (home.failed()) return;
  ViewArray<Int::MinusView> y(home,x.size());
  for (int i=x.size(); i--; )
    y[i]=Int::MinusView(x[i]);
  NoneMin<Int::MinusView>::post(home,y);
}

Download: none-min-and-none-max.cpp

As an example consider the branchings nonemin (see Implementing a nonemin branching) and nonemax where the latter tries to assign the maximal value of a view first. The corresponding program fragment is shown in Program 33.3. The class NoneMin is made generic with respect to the type of view it uses. Then, both nonemin and nonemax can be obtained by instantiating NoneMin with integer views or integer minus views.