b-advanced.tex.in

% -*- mode: LaTeX; -*- 
\chapter{Advanced topics}
\label{chap:b:advanced}

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

\paragraph{Overview.}

\autoref{sec:b:advanced:assign} presents a specialized brancher
for assigning views rather than branching on them. How branchers
support no-goods is discussed in \autoref{sec:b:advanced:nogoods}.
Variable views for branchers are discussed in
\autoref{sec:b:advanced:views}.


\section{Assignment branchers}
\label{sec:b:advanced:assign}

This section presents an example for a brancher that assigns all
of its views rather than branches on its views.  The branching
\begin{code}
void assignmin(Home home, const IntVarArgs& x);
\end{code}
assigns all variables in \?x? to their smallest possible
value. That is, \?assignmin? is equivalent to the predefined
branching (see \autoref{sec:m:branch:assign}) used as
\begin{code}
assign(home, x, INT_ASSIGN_MIN());
\end{code}

\begin{figure}
\insertlitcode{assign min}
\caption{A brancher for \?assignmin?}
\label{fig:b:advanced:assignmin}
\end{figure}

\autoref{fig:b:advanced:assignmin} shows the relevant parts of the
brancher \?AssignMin?. Unsurprisingly, both the \?status()? and
\?choice()? function are identical to those shown in
\autoref{fig:b:started:improved} (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
\autoref{fig:b:started:improved}. It only needs to be capable of
handling a single alternative. The same holds true for the
\?print()? function.


\section{Supporting no-goods}
\label{sec:b:advanced:nogoods}

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
\gecoderef[class]{NGL}. The \?ngl()?  function is called during
no-good generation (see \autoref{sec:m:search:nogoods}) 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 \gecoderef[class]{Search::NoGoodsProp}).

\begin{figure}
\insertlitcode{none min with no-good support}
\caption{Branching for \?nonemin? with no-good support}
\label{fig:b:advanced:nogoods}
\end{figure}

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 \autoref{fig:b:advanced:nogoods}. Otherwise, the brancher is
the same as the \?nonemin? brancher shown in
\autoref{fig:b:started:improved}.

\subsection{Returning no-good literals}

The \?ngl()? function of a brancher has the following options:
\begin{itemize}
\item As mentioned above, it can always return \?NULL? and hence
  the brancher does not support no-goods.
\item 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.
\item 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 \autoref{sec:m:search:nogoods}.
  Note also that this property is typically only true for
  branchers with binary choices such as in our example.
\end{itemize}

\begin{samepage}
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:
\insertlitcode{none min with no-good support:no-good literal creation}
\end{samepage}

\subsection{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 \gecoderef[class]{NGL}
and must implement the following constructors and functions:
\begin{itemize}
\item 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
  \autoref{fig:b:advanced:nogoods}.
\item 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 \gecoderef[class]{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:
\insertsmalllitcode{none min with no-good support:status}

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

  Again, the \?prune()? function for \?NoneMin? is
  straightforward:
\insertsmalllitcode{none min with no-good support:prune}

\item 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
  \autoref{sec:p:started:propcond} for a discussion of
  propagation conditions). This choice reflects the fact that
  subsumption can only be decided after the view \?x? has been
  assigned:
\insertsmalllitcode{none min with no-good support:subscribe and cancel}
\item 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:
\insertsmalllitcode{none min with no-good support:re-scheduling}
\end{itemize}

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:
\begin{code}
virtual bool notice(void) const {
  return true;
}
virtual size_t dispose(Space& home) {
  ...
}
\end{code}
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.




\section{Using variable views}
\label{sec:b:advanced:views}

Variable views can also be used for reusing branchers to obtain
several branchings, similar to reusing propagators for several
constraints, see \autoref{chap:p:views}.

While in principle all different variable views introduced in
\autoref{chap:p:views} can be used for branchers, the only
meaningful variable view for branchers is the minus integer view
(see \autoref{sec:p:views:int:minus}).

\begin{figure}
\insertlitcode{none min and none max}
\caption{Branchings for \?nonemin? and \?nonemax?}
\label{fig:b:advanced:views}
\end{figure}

As an example consider the branchings
\?nonemin? (see \autoref{sec:b:started:nonemin}) and \?nonemax?
where the latter tries to assign the maximal value of a view
first. The corresponding program fragment is shown in
\autoref{fig:b:advanced:views}. 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.



\begin{litcode}{assign min}{schulte}
\begin{litblock}{anonymous}
#include <gecode/int.hh>

using namespace Gecode;

\end{litblock}
class AssignMin : public Brancher {
  \begin{litblock}{anonymous}
protected:
  ViewArray<Int::IntView> x;
  mutable int start;
  \end{litblock}
  class PosVal : public Choice {
  public:
    int pos; int val;
    PosVal(const AssignMin& b, int p, int v)
      : Choice(b,1), pos(p), val(v) {}
    \begin{litblock}{anonymous}
    virtual void archive(Archive& e) const {
      Choice::archive(e);
      e << pos << val;
    }
    \end{litblock}
  };
  \begin{litblock}{anonymous}
public:
  AssignMin(Home home, ViewArray<Int::IntView>& x0)
    : Brancher(home), x(x0), start(0) {}
  static void post(Home home, ViewArray<Int::IntView>& x) {
    (void) new (home) AssignMin(home,x);
  }
  virtual size_t dispose(Space& home) {
    (void) Brancher::dispose(home);
    return sizeof(*this);
  }
  AssignMin(Space& home, AssignMin& b)
    : Brancher(home,b), start(b.start) {
    x.update(home,b.x);
  }
  virtual Brancher* copy(Space& home) {
    return new (home) AssignMin(home,*this);
  }
  virtual bool status(const Space& home) const {
    for (int i=start; i<x.size(); i++)
      if (!x[i].assigned()) {
        start = i; return true;
      }
    return false;
  }
  virtual Choice* choice(Space& home) {
    return new PosVal(*this,start,x[start].min());
  }
  virtual Choice* choice(const Space&, Archive& e) {
    int pos, val;
    e >> pos >> val;
    return new PosVal(*this, pos, val);
  }
  \end{litblock}
  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;
  }
  \begin{litblock}{anonymous}
  virtual void print(const Space& home, const Choice& c,
                     unsigned int a,
                     std::ostream& o) const {
    const PosVal& pv = static_cast<const PosVal&>(c);
    int pos=pv.pos, val=pv.val;
    o << "x[" << pos << "] = " << val;
  }
  \end{litblock}
};
\begin{litblock}{anonymous}

void assignmin(Home home, const IntVarArgs& x) {
  if (home.failed()) return;
  ViewArray<Int::IntView> y(home,x);
  AssignMin::post(home,y);
}
\end{litblock}
\end{litcode}


\begin{litcode}{none min and none max}{schulte}
\begin{litblock}{anonymous}
#include <gecode/int.hh>

using namespace Gecode;

\end{litblock}
template<class View>
class NoneMin : public Brancher {
  \begin{litblock}{anonymous}
protected:
  ViewArray<View> x;
  mutable int start;
  class PosVal : public Choice {
  public:
    int pos; int val;
    PosVal(const NoneMin& b, int p, int v)
      : Choice(b,2), pos(p), val(v) {}
    virtual void archive(Archive& e) const {
      Choice::archive(e);
      e << pos << val;
    }
  };
public:
  NoneMin(Home home, ViewArray<View>& x0)
    : Brancher(home), x(x0), start(0) {}
  static void post(Home home, ViewArray<View>& x) {
    (void) new (home) NoneMin<View>(home,x);
  }
  virtual size_t dispose(Space& home) {
    (void) Brancher::dispose(home);
    return sizeof(*this);
  }
  NoneMin(Space& home, NoneMin& b)
    : Brancher(home,b), start(b.start) {
    x.update(home,b.x);
  }
  virtual Brancher* copy(Space& home) {
    return new (home) NoneMin<View>(home,*this);
  }
  virtual bool status(const Space& home) const {
    for (int i=start; i<x.size(); i++)
      if (!x[i].assigned()) {
        start = i; return true;
      }
    return false;
  }
  virtual Choice* choice(Space& home) {
    return new PosVal(*this,start,x[start].min());
  }
  virtual Choice* choice(const Space&, Archive& e) {
    int pos, val;
    e >> pos >> val;
    return new PosVal(*this, pos, val);
  }
  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;
    if (a == 0)
      return me_failed(x[pos].eq(home,val)) ? ES_FAILED : ES_OK;
    else
      return me_failed(x[pos].nq(home,val)) ? ES_FAILED : ES_OK;
  }
  virtual void print(const Space& home, const Choice& c,
                     unsigned int a,
                     std::ostream& o) const {
    const PosVal& pv = static_cast<const PosVal&>(c);
    int pos=pv.pos, val=pv.val;
    if (a == 0)
      o << "x[" << pos << "] = " << val;
    else
      o << "x[" << pos << "] != " << val;
  }
  \end{litblock}
};
void nonemin(Home home, const IntVarArgs& x) {
  \begin{litblock}{anonymous}
  if (home.failed()) return;
  ViewArray<Int::IntView> y(home,x);
  NoneMin<Int::IntView>::post(home,y);
  \end{litblock}
}
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);
}
\end{litcode}


\begin{litcode}{none min with no-good support}{schulte}
\begin{litblock}{anonymous}
#include <gecode/int.hh>

using namespace Gecode;

\end{litblock}
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);
  }
  \begin{litblock}{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;
  }
  \end{litblock}
  \begin{litblock}{prune}
  virtual ExecStatus prune(Space& home) {
    return me_failed(x.nq(home,n)) ? ES_FAILED : ES_OK;
  }
  \end{litblock}
  \begin{litblock}{subscribe and cancel}
  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);
  }
  \end{litblock}
  \begin{litblock}{re-scheduling}
  virtual void reschedule(Space& home, Propagator& p) {
    x.reschedule(home, p, Int::PC_INT_VAL);
  }
  \end{litblock}
  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 {
  \begin{litblock}{anonymous}
protected:
  ViewArray<Int::IntView> x;
  mutable int start;
  class PosVal : public Choice {
  public:
    int pos; int val;
    PosVal(const NoneMin& b, int p, int v)
      : Choice(b,2), pos(p), val(v) {}
    virtual void archive(Archive& e) const {
      Choice::archive(e);
      e << pos << val;
    }
  };
  \end{litblock}
public:
  \begin{litblock}{anonymous}
  NoneMin(Home home, ViewArray<Int::IntView>& x0)
    : Brancher(home), x(x0), start(0) {}
  static void post(Home home, ViewArray<Int::IntView>& x) {
    (void) new (home) NoneMin(home,x);
  }
  virtual size_t dispose(Space& home) {
    (void) Brancher::dispose(home);
    return sizeof(*this);
  }
  NoneMin(Space& home, NoneMin& b)
    : Brancher(home,b), start(b.start) {
    x.update(home,b.x);
  }
  virtual Brancher* copy(Space& home) {
    return new (home) NoneMin(home,*this);
  }
  virtual bool status(const Space& home) const {
    for (int i=start; i<x.size(); i++)
      if (!x[i].assigned()) {
        start = i; return true;
      }
    return false;
  }
  virtual Choice* choice(Space& home) {
    return new PosVal(*this,start,x[start].min());
  }
  virtual Choice* choice(const Space&, Archive& e) {
    int pos, val;
    e >> pos >> val;
    return new PosVal(*this, pos, val);
  }
  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;
    if (a == 0)
      return me_failed(x[pos].eq(home,val)) ? ES_FAILED : ES_OK;
    else
      return me_failed(x[pos].nq(home,val)) ? ES_FAILED : ES_OK;
  }
  virtual void print(const Space& home, const Choice& c,
                     unsigned int a,
                     std::ostream& o) const {
    const PosVal& pv = static_cast<const PosVal&>(c);
    int pos=pv.pos, val=pv.val;
    if (a == 0)
      o << "x[" << pos << "] = " << val;
    else
      o << "x[" << pos << "] != " << val;
  }
  \end{litblock}
  \begin{litblock}{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;
  }
  \end{litblock}
};
\begin{litblock}{anonymous}
void nonemin(Home home, const IntVarArgs& x) {
  if (home.failed()) return;
  ViewArray<Int::IntView> y(home,x);
  NoneMin::post(home,y);
}
\end{litblock}
\end{litcode}