s-recomputation.tex.in

% -*- mode: LaTeX; -*- 
\chapter{Recomputation}
\label{chap:s:re}

This chapter demonstrates recomputation as the most essential
technique for efficient search in Gecode. It is highly
recommended to read \autoref{sec:m:search:re} before reading this
chapter.

\paragraph{Overview.}

The simplest possible search engine based on recomputation, where
all spaces needed for search are recomputed from the root of the
search tree, is discussed in \autoref{sec:s:re:full}. Important
invariants for recomputation and how they must be taken into
account by search engines using recomputation are discussed in
\autoref{sec:s:re:invariants}. How best solution search is
combined with recomputation is discussed in
\autoref{sec:s:re:bab}. The following three sections present
important optimizations for search engines using recomputation:
\autoref{sec:s:re:lao} shows how last alternative optimization
can avoid \?commit()? operations during recomputation;
\autoref{sec:s:re:hybrid} shows how hybrid recomputation that
stores additional spaces can be used to speed up search;
\autoref{sec:s:re:adaptive} shows adaptive recomputation that
helps speeding up search in case of failures.

\begin{important}
  All sections in this chapter make the simplifying assumption
  that choices are binary, dealing with non binary choices is
  similar to \autoref{sec:s:started:dfs}. The search engine in
  \autoref{chap:s:engine} combines all recomputation techniques
  of this chapter for the general case.
\end{important}




\section{Full recomputation}
\label{sec:s:re:full}

This section demonstrates search based on full recomputation.
While full recomputation is unrealistic, the search engine
presented here helps in understanding the ideas behind
recomputation. In particular, the search engine serves as an
example for important invariants for recomputation that are
discussed in \autoref{sec:s:re:invariants}.

\paragraph{Search engine.}

\begin{figure}
\insertlitcode{dfs using full recomputation}
\caption{Depth-first search using full recomputation}
\label{fig:s:re:full}
\end{figure}

\mbox{}\autoref{fig:s:re:full} shows the outline for the search
engine that implements depth-first search with full
recomputation. The function \?dfs()? that takes a single space
\?s? as its argument is called by the user, the function \?dfs()?
that takes three arguments implements exploration with full
recomputation.

The basic idea of the search engine is to always keep a single
space \?r? as the \emph{root} space of the search tree to be
explored. Exploration maintains a current space and a path
consisting of edges that defines which node in the search tree is
currently being explored. Exploration is governed by the
invariant that the current space can always be recomputed from
the path of edges maintained by the search engine.

Initially, when the user calls the \?dfs()? function taking a
single argument, the root space \?r? is computed as a clone of
the space \?s? passed as argument. As only stable and non-failed
spaces can be cloned (see \autoref{sec:s:started:space}), the
\?status()? function is used to find out whether propagation on
\?s? results in failure. If not, the root space \?r? is created
as a clone of \?s? and the search engine \?dfs()? is called with
\?s? as the current space, \?r? as the root space, and \?NULL? as
the current path from the current space to the root space.

\paragraph{Edges for recomputation.}

\begin{figure}
\insertlitcode{dfs using full recomputation:edge class}
\caption{\?Edge? class for depth-first search using full recomputation}
\label{fig:s:re:full:edge}
\end{figure}

\mbox{}\autoref{fig:s:re:full:edge} shows the class \?Edge?
implementing an edge of a path to be used for recomputation. The
class stores a pointer \?p? to the predecessor edge, a choice
\?ch?, and the number of the alternative \?a? that corresponds to
the edge. Edges are organized from the current node (space) of
the search tree upwards to the root: the last edge of a path
connects to the root of the search tree and has \?NULL? as its
predecessor \?p?. Note that we restrict our attention in this
chapter to binary choices only.

Initialization by the \?Edge?'s constructor takes the current
space of the search engine \?s? and the predecessor edge \?e? and
initializes the edge with the choice for \?s? and the first
alternative. Deleting an edge also deletes the stored choice \?ch?.

An edge provides a \?next()? function that redirects the edge to
the next alternative: 
\insertlitcode{dfs using full recomputation:next alternative}

\begin{samepage}
The \?commit()? function of an edge commits a space \?s? to the
alternative that corresponds to the edge:
\insertlitcode{dfs using full recomputation:committing a space}
\end{samepage}
The function returns the space just for convenience as can be
seen below.

Finally, recomputing a space corresponding to an entire path of
edges is implemented by the \?recompute()? function. The function
takes the root space \?r? as argument and is implemented as follows:
\insertlitcode{dfs using full recomputation:recomputing a space}

First, the function traverses the path of edges upwards until the
root of the path is reached. Then it creates a clone of the root
space \?r? and performs the \?commit()? operations for each edge
on the path.

\paragraph{Exploring alternatives.}

The central invariant that the current path of edges \?p? must
always correspond to the current space is essential for how the
search engine implementing full recomputation explores the search
tree.

Before exploring the first alternative recursively, a new edge is
created for the first alternative, the current space \?s? is
committed to the first alternative, and exploration continues
recursively:
\insertlitcode{dfs using full recomputation:explore first alternative}
Note that all resource management for handling edges is done
automatically: as soon as the edge \?e? goes out of scope, it is
automatically deleted (and hence also the choice for the edge is
deleted). 

Again, exploration of the second alternative maintains the
central invariant: the edge is redirected to the next alternative
and then a space corresponding to the path of edges is
recomputed:
\insertlitcode{dfs using full recomputation:explore second alternative}

\paragraph{Cost of recomputation.} 

It is important to notice the following facts about the cost
of recomputation, where we compare the search engine using full
recomputation to the search engine without recomputation in
\autoref{sec:s:started:dfsbin}:
\begin{itemize}
\item While the number of \?commit()? operations on spaces
  drastically increases for full recomputation, the number of
  \?status()? operations executed remains exactly the same.
  
  However, execution of \?status()? during recomputation is more
  expensive as more constraint propagation needs to be done: full
  recomputation always starts from the root space where only
  little constraint propagation has been performed.
\item The number of \?clone()? operations executed by full
  recomputation is never larger than the number of \?clone()?
  operations without recomputation. 
  
  Typically, the number of \?clone()? operations is much smaller:
  recomputation is \emph{optimistic} in the sense that a clone is
  created and recomputation is performed only if a node is
  required for exploration. A search engine without recomputation
  is \emph{pessimistic} in that it always creates a clone
  \emph{before} continuing exploration to be able to backtrack to
  a space that might be required for further exploration.
  
  \autoref{sec:s:re:hybrid} presents hybrid recomputation as a
  technique that makes recomputation less optimistic in that it
  creates more clones before continuing exploration.
  \autoref{sec:s:re:adaptive} presents adaptive recomputation
  that makes recomputation even less optimistic in cases where it
  is likely that exploration can benefit from additional clones.
\end{itemize}

A detailed evaluation of recomputation in Gecode and a comparison
to other techniques for implementing search can be found in
\cite{ReischukSchulteEa:CP:2009}. An evaluation of different
recomputation techniques (although in a different setup) can
be found in \cite{Schulte:ICLP:99} and
\cite[Chapter~7]{Schulte:LNAI:2002}.


\section{Recomputation invariants}
\label{sec:s:re:invariants}

This section discusses two important invariants that govern
recomputation. The first invariant is that recomputation can only
use compatible choices for commit operations: the notion of
choice compatibility has been sketched in
\autoref{sec:s:started:space} and is detailed in
\autoref{sec:s:re:compatible}. The second invariant is concerned
with the fact that recomputation is not always deterministic.
However, \autoref{sec:s:re:wmp} explains why
recomputation still works even though it is not deterministic.

\subsection{Choice compatibility}
\label{sec:s:re:compatible}

\autoref{sec:s:started:space} introduced the notion that a space
\?s? is compatible with a choice \?ch? (that is, \?ch? can be
used for a \?commit()? operation on \?s?). For recomputation, a
more general notion of compatibility is needed: during
recomputation, a search engine performs \?commit()? operations
using choices that have been computed earlier on a path in the
search tree.

\begin{figure}
\centering
\psset{xunit=0.03,yunit=0.03,runit=0.03}
\begin{pspicture}(0,10)(220,152)
\DefineNode{64}{143}{n1u}
\DefineNode{64}{133}{n1c}
\DefineNode{48}{105}{n2u}
\DefineNode{48}{95}{n2c}
\DefineNode{32}{67}{n3u}
\DefineNode{32}{57}{n3c}
\DefineNode{16}{27}{n4u}
\DefineNode{16}{19}{n4c}
\DefineNode{48}{27}{n5u}
\DefineNode{48}{19}{n5c}
\DefineLink{n1c}{n2u}
\DefineLink{n2c}{n3u}
\DefineLink{n3c}{n4u}
%\DefineFatLink{n3c}{n5u}
   \RootNodeI{64}{133}{1}
  \ChoiceNodeI{48}{95}{2}
 \ChoiceNodeI{32}{57}{3}
\FailedNode{16}{19}
%\GuessNode{48}{19}
\DefineNode{120}{133}{root}
\DefineNode{120}{114}{ch1}
\DefineNode{120}{76}{ch2}
\DefineNode{120}{38}{ch3}
\DefineNode{64}{114}{n1}
\DefineNode{64}{76}{n2}
\DefineNode{64}{38}{n3}
\rput(120,133){\makebox(0,0)[l]{root space $\mathtt r$}}
\rput(120,114){\makebox(0,0)[l]{choice $\mathtt{ch0}$}}
\rput(120,76){\makebox(0,0)[l]{choice $\mathtt{ch1}$}}
\rput(120,38){\makebox(0,0)[l]{choice $\mathtt{ch2}$}}
\ncline[nodesep=15]{->}{root}{n1c}
\ncline[nodesep=15]{->}{ch1}{n1}
\ncline[nodesep=15]{->}{ch2}{n2}
\ncline[nodesep=15]{->}{ch3}{n3}
\end{pspicture}
\qquad\qquad
\begin{pspicture}(0,10)(220,152)
\DefineNode{64}{143}{n1u}
\DefineNode{64}{133}{n1c}
\DefineNode{48}{105}{n2u}
\DefineNode{48}{95}{n2c}
\DefineNode{32}{67}{n3u}
\DefineNode{32}{57}{n3c}
\DefineNode{16}{27}{n4u}
\DefineNode{16}{19}{n4c}
\DefineNode{48}{27}{n5u}
\DefineNode{48}{19}{n5c}
\DefineLink{n1c}{n2u}
\DefineLink{n2c}{n3u}
\DefineLink{n3c}{n4u}
\DefineLink{n3c}{n5u}
   \RootNodeI{64}{133}{1}
  \ChoiceNodeI{48}{95}{2}
 \ChoiceNodeI{32}{57}{3}
\FailedNode{16}{19}
\ChoiceNodeI{48}{19}{4}
\DefineNode{120}{133}{root}
\DefineNode{120}{114}{ch1}
\DefineNode{120}{76}{ch2}
\DefineNode{120}{38}{ch3}
\DefineNode{64}{114}{n1}
\DefineNode{64}{76}{n2}
\DefineNode{64}{38}{n3}
\rput(120,133){\makebox(0,0)[l]{root space $\mathtt r$}}
\rput(120,114){\makebox(0,0)[l]{choice $\mathtt{ch0}$}}
\rput(120,76){\makebox(0,0)[l]{choice $\mathtt{ch1}$}}
\rput(120,38){\makebox(0,0)[l]{choice $\mathtt{ch2}$}}
\ncline[nodesep=15]{->}{root}{n1c}
\ncline[nodesep=15]{->}{ch1}{n1}
\ncline[nodesep=15]{->}{ch2}{n2}
\ncline[nodesep=15]{->}{ch3}{n3}
\end{pspicture}
\caption{Example situations during recomputation}
\label{fig:s:re:ex}
\end{figure}

Consider the situation sketched in the left part of
\autoref{fig:s:re:ex} with a root space \?r? and choices \?ch0?,
\?ch1?, and \?ch2? as stored on the path of edges for
recomputation. That is, all choices have been computed by the
\?choice()? function from a clone of the root space \?r? where in
between the calls to \?choice()? other operations on the space
have been performed. For example, the search engine implementing
full recomputation from \autoref{sec:s:re:full} has executed the
\?status()? and \?commit()? functions several times in order to
compute the choices.

Suppose that \?s? is a clone of \?r? (computed by
\?s=r->clone()?). Then all choices are compatible with \?s?. Now
suppose that \?t? is a clone of \?s?. Then all choices are still
compatible with \?t?. Hence, if a choice \?ch? has been created
for a space \?r? all spaces that are related by cloning to \?r?
are compatible with \?ch?. Compatibility continues to hold even if
other operations (such as \?commit()? operations for other
choices, computing the status of a space, or the creation of new
variables, propagators, and branchers) are performed on a space
that is clone-related. The only exception is the \?choice()?
function of a space.

Suppose that recomputation proceeds by recomputing the space \?s?
for node~\?4?  as shown in the right part of \autoref{fig:s:re:ex}.
Assume that \?s?  requires branching. Hence, a search engine is
executing \?s->choice()?. After executing the \?choice()?
function, all previous choices \?ch0?, \?ch1?, and \?ch2? are not
any longer compatible with \?s?.

\paragraph{Order of \?commit()? operations.}

The choices \?ch0?, \?ch1?, and \?ch2? do not have to be used for
\?commit()? in the same order in which they have been created.
However, it is more efficient to use them in the order \?ch0?,
\?ch1?, and \?ch2?.  The difference is that if a space has $n$
branchers and the choices correspond to different branchers, then
a \?commit()?  operation uses $O(1)$ time to find the
corresponding brancher for a choice if the choices are used in
order. If they are not used in order, a \?commit()?  operation
uses $O(n)$ time to find the corresponding brancher. Having said
all that,
$n$ is typically just one or two.


\subsection{Recomputation is not deterministic}
\label{sec:s:re:wmp}

Assume that a search engine has recorded a path from a node in the
search tree and that the space \?s? corresponds to that node in the
tree. Then, when a space \?t? for that node is recomputed, the
two spaces \?s? and \?t? might actually differ: the amount of
propagation performed by \?s? and \?t? can be different.

The difference in propagation is due to the fact that Gecode
supports propagators that are weakly monotonic but not
necessarily monotonic. In summary, a weakly monotonic propagator
can perform more or less propagation (that is, prune more values
from variables domains or prune fewer values from variable
domains) but is still correct and complete, see also
\autoref{par:p:started:wmp}.

As weakly monotonic constraint propagation is still correct and
complete, also recomputation is
correct in the following sense: All solutions that are found by
search starting from space \?s? are also found by search starting
from space \?t?. However, search might find the solutions in
different order when starting from either \?s? or \?t?.

Consider the special case that \?s? is failed. The recomputed
space \?t? might not necessarily be failed. That is, \?s?
performed more constraint propagation than \?t?. However,
additional search from \?t? will never find any solution. The
same is also true with the roles of \?s? and \?t? exchanged: even
though \?s? is not failed, the recomputed space \?t? can be
failed.

For search engines using recomputation this typically does not
pose any problems. In most cases, a search engine does not attempt
to recompute a space that it assumes to be non-failed. Consider
the depth-first search engine using full recomputation from
\autoref{sec:s:re:full}. There, the spaces that are recomputed
correspond to nodes in the search tree not yet explored. In
other words, when recomputing spaces that have been explored
previously, a search engine cannot make the assumption that the space
is not failed just because the space explored previously has not
been failed.

An exception is adaptive recomputation to be discussed in
\autoref{sec:s:re:adaptive} as an optimization for recomputation.
Adaptive recomputation recomputes previously explored spaces to
speed up further search.

For a detailed discussion of weakly monotonic propagation
together with the consequences for search including
recomputation, please consult~\cite{SchulteTack:CP:2009}.


\section{Branch-and-bound search}
\label{sec:s:re:bab}

The first idea to combine recomputation with best solution search
is to take the engine for best solution search without
recomputation (see \autoref{sec:s:started:bab}) and add
recomputation to it along the lines of \autoref{sec:s:re:full}. A
search engine implementing this approach would work roughly as
follows: recompute a space and, if needed, add the constraints to
the space such that the space can only lead to a better solution.

A tighter integration of recomputation and best solution search
is in fact much better: instead of adding the constraints for
a better solution to the space that is recomputed, add it to the space
from which recomputation starts (with full recomputation: the
root space). The advantage is that if adding the constraints to
the space from which recomputation starts already leads to
failure, the entire subtree starting from that space can be
discarded (with full recomputation: search is done).

\begin{figure}
\insertlitcode{bab using full recomputation}
\caption{Branch-and-bound search using full recomputation}
\label{fig:s:re:bab}
\end{figure}

\autoref{fig:s:re:bab} sketches branch-and-bound best solution
search using full recomputation. The search engine takes the
current space \?s?, the root space \?r?, the so-far best solution
\?b?, and the predecessor edge \?p? as arguments. Note that both
the root space \?r? and the so-far best solution \?b? are passed
by reference as they change during exploration.

When the search engine finds a new solution \?s?, it replaces the
so-far best solution \?b? by \?s? and updates the root space by
adding the constraints that \?r? must yield better solutions than
\?b? as follows:
\insertlitcode{bab using full recomputation:solved}
The root space then must be checked for failure. If the root
space is failed, it is deleted and the pointer to the root space becomes
\?NULL?. Otherwise, the root space becomes a clone of the newly
computed space to save memory (as mentioned earlier, it is better
to store a pristine clone of a space than a space on which
propagation has been performed).

Exploring the second alternative of a choice checks whether
the root space is already failed:
\insertlitcode{bab using full recomputation:explore second alternative}



\section{Last alternative optimization}
\label{sec:s:re:lao}

This section presents an important optimization for recomputation
that helps to avoid many commit operations during
recomputation. Even though the optimization is discussed in the
context of full recomputation, it is applicable to all situations
in which recomputation is used.

\begin{figure}
\centering
\psset{xunit=0.03,yunit=0.03,runit=0.03}
\begin{pspicture}(0,10)(206,152)
\DefineNode{128.0}{143.0}{n1u}
\DefineNode{128.0}{133.0}{n1c}
 \DefineNode{192.0}{105.0}{n12u}
 \DefineNode{192.0}{95.0}{n12c}
  \DefineNode{224.0}{67.0}{n122u}
  \DefineNode{224.0}{57.0}{n122c}
   \DefineNode{240.0}{29.0}{n1222u}
   \DefineNode{240.0}{19.0}{n1222c}
   \DefineNode{208.0}{29.0}{n1221u}
   \DefineNode{208.0}{19.0}{n1221c}
  \DefineNode{160.0}{67.0}{n121u}
  \DefineNode{160.0}{57.0}{n121c}
   \DefineNode{176.0}{29.0}{n1212u}
   \DefineNode{176.0}{19.0}{n1212c}
   \DefineNode{144.0}{29.0}{n1211u}
   \DefineNode{144.0}{19.0}{n1211c}
 \DefineNode{64.0}{105.0}{n11u}
 \DefineNode{64.0}{95.0}{n11c}
  \DefineNode{96.0}{67.0}{n112u}
  \DefineNode{96.0}{57.0}{n112c}
   \DefineNode{112.0}{29.0}{n1122u}
   \DefineNode{112.0}{19.0}{n1122c}
   \DefineLink{n112c}{n1122u}
   \DefineNode{80.0}{29.0}{n1121u}
   \DefineNode{80.0}{19.0}{n1121c}
   \DefineLink{n112c}{n1121u}
  \DefineLink{n11c}{n112u}
  \DefineNode{32.0}{67.0}{n111u}
  \DefineNode{32.0}{57.0}{n111c}
   \DefineNode{48.0}{29.0}{n1112u}
   \DefineNode{48.0}{19.0}{n1112c}
   \DefineLink{n111c}{n1112u}
   \DefineNode{16.0}{29.0}{n1111u}
   \DefineNode{16.0}{19.0}{n1111c}
   \DefineLink{n111c}{n1111u}
  \DefineLink{n11c}{n111u}
 \DefineLink{n1c}{n11u}
\RootNode{128.0}{133.0}
 \ChoiceNode{64.0}{95.0}
  \ChoiceNode{96.0}{57.0}
   \FailedNode{112.0}{19.0}
   \FailedNode{80.0}{19.0}
  \ChoiceNode{32.0}{57.0}
   \FailedNode{48.0}{19.0}
   \FailedNode{16.0}{19.0}
\DefineNode{166}{76}{before}
\end{pspicture}\qquad
\begin{pspicture}(0,10)(236,152)
\DefineNode{128.0}{143.0}{n1u}
\DefineNode{128.0}{133.0}{n1c}
 \DefineNode{192.0}{105.0}{n12u}
 \DefineNode{192.0}{95.0}{n12c}
  \DefineNode{224.0}{67.0}{n122u}
  \DefineNode{224.0}{57.0}{n122c}
   \DefineNode{240.0}{29.0}{n1222u}
   \DefineNode{240.0}{19.0}{n1222c}
   \DefineNode{208.0}{29.0}{n1221u}
   \DefineNode{208.0}{19.0}{n1221c}
  \DefineNode{160.0}{67.0}{n121u}
  \DefineNode{160.0}{57.0}{n121c}
   \DefineNode{176.0}{29.0}{n1212u}
   \DefineNode{176.0}{19.0}{n1212c}
   \DefineNode{144.0}{29.0}{n1211u}
   \DefineNode{144.0}{19.0}{n1211c}
 \DefineLinkA{n1c}{n12u}
 \DefineNode{64.0}{105.0}{n11u}
 \DefineNode{64.0}{95.0}{n11c}
  \DefineNode{96.0}{67.0}{n112u}
  \DefineNode{96.0}{57.0}{n112c}
   \DefineNode{112.0}{29.0}{n1122u}
   \DefineNode{112.0}{19.0}{n1122c}
   \DefineLink{n112c}{n1122u}
   \DefineNode{80.0}{29.0}{n1121u}
   \DefineNode{80.0}{19.0}{n1121c}
   \DefineLink{n112c}{n1121u}
  \DefineLink{n11c}{n112u}
  \DefineNode{32.0}{67.0}{n111u}
  \DefineNode{32.0}{57.0}{n111c}
   \DefineNode{48.0}{29.0}{n1112u}
   \DefineNode{48.0}{19.0}{n1112c}
   \DefineLink{n111c}{n1112u}
   \DefineNode{16.0}{29.0}{n1111u}
   \DefineNode{16.0}{19.0}{n1111c}
   \DefineLink{n111c}{n1111u}
  \DefineLink{n11c}{n111u}
 \DefineLink{n1c}{n11u}
\GoneNode{128.0}{133.0}
 \RootNode{192.0}{95.0}
 \ChoiceNode{64.0}{95.0}
  \ChoiceNode{96.0}{57.0}
   \FailedNode{112.0}{19.0}
   \FailedNode{80.0}{19.0}
  \ChoiceNode{32.0}{57.0}
   \FailedNode{48.0}{19.0}
   \FailedNode{16.0}{19.0}
\DefineNode{0}{76}{after}
\end{pspicture}
\ncline[linewidth=3pt]{->}{before}{after}\Aput{LAO}
\caption{Last alternative optimization (LAO)}
\label{fig:s:re:lao:ex}
\end{figure}

Consider a situation during search as shown in the left part of
\autoref{fig:s:re:lao:ex}. There, the entire left subtree
emanating from the root node (colored in orange) has been
explored. When exploration continues for the right subtree, each
time a node is recomputed, a clone of the root node is made
immediately followed by a commit operation for the second
alternative. Hence it is much better to compute a new root node
for the entire right subtree and perform the corresponding commit
operation just once. This optimization is referred to as
\emph{last alternative optimization
  (LAO)}~\cite[Chapter~7]{Schulte:LNAI:2002}.
\autoref{fig:s:re:lao:ex} shows the new root of the search tree
after performing LAO. Note that no space needs to be stored for
the previous root node as it will never be used again for
recomputation.

\begin{figure}
\insertlitcode{dfs using full recomputation and lao}
\caption{Depth-first search using full recomputation and LAO}
\label{fig:s:re:lao}
\end{figure}

\autoref{fig:s:re:lao} shows a search engine implementing
left-most depth-first search using full recomputation and LAO.
Only very few aspects have changed compared to the engine for
full recomputation without LAO from \autoref{sec:s:re:full}. An
important change is that the root space is now passed by
reference: this is necessary as the root space changes during
exploration.

The \?Edge? class is extended by a function \?la()? that tests
whether an edge happens to be a last alternative:
\insertlitcode{dfs using full recomputation and lao:test for last alternative}

The actual optimization is performed just before exploring the
second alternative: 
\insertlitcode{dfs using full recomputation and lao:perform lao}

The space \?t? serves as a temporary reference. After performing
the \?commit()? operation on \?t? for the second alternative, it
is tested whether the new root node is already failed. 
The new root space becomes the clone of \?t?: this is
important as a clone typically requires less memory than a space
on which constraint propagation has been performed (see
\autoref{sec:s:started:dfsbin}).


\section{Hybrid recomputation}
\label{sec:s:re:hybrid}

Exploration based on copying alone or based on full recomputation
is unrealistic. As already described in
\autoref{sec:m:search:re}, Gecode's search engines use hybrid
recomputation: they create a clone now and then to limit the
amount of recomputation.

\begin{window}[0,r,{
\psset{unit=0.015}
\begin{pspicture}(0,10)(256,152)
\DefineNode{128.0}{143.0}{n1u}
\DefineNode{128.0}{133.0}{n1c}
 \DefineNode{192.0}{105.0}{n12u}
 \DefineNode{192.0}{95.0}{n12c}
  \DefineNode{224.0}{67.0}{n122u}
  \DefineNode{224.0}{57.0}{n122c}
   \DefineNode{240.0}{29.0}{n1222u}
   \DefineNode{240.0}{19.0}{n1222c}
   \DefineLink{n122c}{n1222u}
   \DefineNode{208.0}{29.0}{n1221u}
   \DefineNode{208.0}{19.0}{n1221c}
   \DefineLink{n122c}{n1221u}
  \DefineLink{n12c}{n122u}
  \DefineNode{160.0}{67.0}{n121u}
  \DefineNode{160.0}{57.0}{n121c}
   \DefineNode{176.0}{29.0}{n1212u}
   \DefineNode{176.0}{19.0}{n1212c}
   \DefineLink{n121c}{n1212u}
   \DefineNode{144.0}{29.0}{n1211u}
   \DefineNode{144.0}{19.0}{n1211c}
   \DefineLink{n121c}{n1211u}
  \DefineLink{n12c}{n121u}
 \DefineLink{n1c}{n12u}
 \DefineNode{64.0}{105.0}{n11u}
 \DefineNode{64.0}{95.0}{n11c}
  \DefineNode{96.0}{67.0}{n112u}
  \DefineNode{96.0}{57.0}{n112c}
   \DefineNode{112.0}{29.0}{n1122u}
   \DefineNode{112.0}{19.0}{n1122c}
   \DefineLink{n112c}{n1122u}
   \DefineNode{80.0}{29.0}{n1121u}
   \DefineNode{80.0}{19.0}{n1121c}
   \DefineLink{n112c}{n1121u}
  \DefineLink{n11c}{n112u}
  \DefineNode{32.0}{67.0}{n111u}
  \DefineNode{32.0}{57.0}{n111c}
   \DefineNode{48.0}{29.0}{n1112u}
   \DefineNode{48.0}{19.0}{n1112c}
   \DefineLink{n111c}{n1112u}
   \DefineNode{16.0}{29.0}{n1111u}
   \DefineNode{16.0}{19.0}{n1111c}
   \DefineLink{n111c}{n1111u}
  \DefineLink{n11c}{n111u}
 \DefineLink{n1c}{n11u}
\RootNode{128.0}{133.0}
 \ChoiceNode{192.0}{95.0}
  \RootNode{224.0}{57.0}
   \ChoiceNode{240.0}{19.0}
   \ChoiceNode{208.0}{19.0}
  \RootNode{160.0}{57.0}
   \ChoiceNode{176.0}{19.0}
   \ChoiceNode{144.0}{19.0}
 \ChoiceNode{64.0}{95.0}
  \RootNode{96.0}{57.0}
   \ChoiceNode{112.0}{19.0}
   \ChoiceNode{80.0}{19.0}
  \RootNode{32.0}{57.0}
   \ChoiceNode{48.0}{19.0}
   \ChoiceNode{16.0}{19.0}
\end{pspicture}},{}]
This section describes hybrid recomputation where the amount of
recomputation is limited by the \emph{commit distance} $c_d$:
during recomputation at most $c_d$ \?commit()?  operations are
executed. Hybrid
recomputation with commit distance $c_d=2$ where orange nodes are
nodes that store a clone is sketched to the right.
\end{window}

\begin{figure}
\insertlitcode{dfs using hybrid recomputation}
\caption{Depth-first search using hybrid recomputation}
\label{fig:s:re:hybrid}
\end{figure}

The additional clones are stored in a field \?c? in the \?Edge?
class shown in \autoref{fig:s:re:hybrid}. Initially, the field
\?c? does not store a clone. The intuition is that the clone \?c?
(if not \?NULL?) is a clone that corresponds to the node to which
the edge leads (please remember that edges lead upwards to the root
of the search tree).

\begin{samepage}
The function \?clone()? stores a clone of a space \?s? in an
edge:
\insertlitcode{dfs using hybrid recomputation:create clone}
\end{samepage}

Recomputation as performed by the \?recompute()? function now
continues to search the path of edges until an edge that stores a
clone is found:
\insertlitcode{dfs using hybrid recomputation:perform recomputation}
It must be guaranteed that there is always at least one edge in a
path
that stores a clone, otherwise recomputation would crash (see below).

The function \?dfs()? that implements exploration takes the
additional argument \?d? (for \?d?istance) which defines how many
\?commit()? operations would be needed to recompute the current
space. If \?d? reaches the limit \?c_d? (for simplicity, \?c_d?
is a constant as defined in \autoref{fig:s:re:hybrid}), a new
clone must be stored in the current edge. Hence, the code for branching starts by
checking whether a clone must be stored for the current
edge~\?e?:
\insertlitcode{dfs using hybrid recomputation:store clone if needed}

The initial call to the function \?dfs()? that implements
exploration takes \?c_d? as value for \?d?. By this, it is
guaranteed that the first edge stores a clone (that is, a clone
that corresponds to the root node of the search tree).

Exploring the alternatives is as before, the only change is that
the incremented distance \?d+1? is passed as additional argument:
\insertlitcode{dfs using hybrid recomputation:explore first alternative}

\begin{window}[0,r,{
\psset{unit=0.015}
\begin{pspicture}(0,10)(256,152)
\DefineNode{128.0}{143.0}{n1u}
\DefineNode{128.0}{133.0}{n1c}
 \DefineNode{192.0}{105.0}{n12u}
 \DefineNode{192.0}{95.0}{n12c}
  \DefineNode{224.0}{67.0}{n122u}
  \DefineNode{224.0}{57.0}{n122c}
   \DefineNode{240.0}{29.0}{n1222u}
   \DefineNode{240.0}{19.0}{n1222c}
   \DefineLinkA{n122c}{n1222u}
   \DefineNode{208.0}{29.0}{n1221u}
   \DefineNode{208.0}{19.0}{n1221c}
   \DefineLink{n122c}{n1221u}
  \DefineLinkA{n12c}{n122u}
  \DefineNode{160.0}{67.0}{n121u}
  \DefineNode{160.0}{57.0}{n121c}
   \DefineNode{176.0}{29.0}{n1212u}
   \DefineNode{176.0}{19.0}{n1212c}
   \DefineLink{n121c}{n1212u}
   \DefineNode{144.0}{29.0}{n1211u}
   \DefineNode{144.0}{19.0}{n1211c}
   \DefineLink{n121c}{n1211u}
  \DefineLink{n12c}{n121u}
 \DefineLinkA{n1c}{n12u}
 \DefineNode{64.0}{105.0}{n11u}
 \DefineNode{64.0}{95.0}{n11c}
  \DefineNode{96.0}{67.0}{n112u}
  \DefineNode{96.0}{57.0}{n112c}
   \DefineNode{112.0}{29.0}{n1122u}
   \DefineNode{112.0}{19.0}{n1122c}
   \DefineLinkA{n112c}{n1122u}
   \DefineNode{80.0}{29.0}{n1121u}
   \DefineNode{80.0}{19.0}{n1121c}
   \DefineLink{n112c}{n1121u}
  \DefineLink{n11c}{n112u}
  \DefineNode{32.0}{67.0}{n111u}
  \DefineNode{32.0}{57.0}{n111c}
   \DefineNode{48.0}{29.0}{n1112u}
   \DefineNode{48.0}{19.0}{n1112c}
   \DefineLinkA{n111c}{n1112u}
   \DefineNode{16.0}{29.0}{n1111u}
   \DefineNode{16.0}{19.0}{n1111c}
   \DefineLink{n111c}{n1111u}
  \DefineLink{n11c}{n111u}
 \DefineLink{n1c}{n11u}
\GoneNode{128.0}{133.0}
 \GoneNode{192.0}{95.0}
  \GoneNode{224.0}{57.0}
   \RootNode{240.0}{19.0}
   \ChoiceNode{208.0}{19.0}
  \ChoiceNode{160.0}{57.0}
   \RootNode{176.0}{19.0}
   \RootNode{144.0}{19.0}
 \ChoiceNode{64.0}{95.0}
  \GoneNode{96.0}{57.0}
   \RootNode{112.0}{19.0}
   \ChoiceNode{80.0}{19.0}
  \GoneNode{32.0}{57.0}
   \RootNode{48.0}{19.0}
   \ChoiceNode{16.0}{19.0}
\end{pspicture}},{}] 
LAO as described for full recomputation (\autoref{sec:s:re:lao})
can be added analogously to hybrid recomputation. Therefore we do
not present hybrid recomputation with LAO. However, how LAO
performs with hybrid recomputation is sketched to the right: gray
nodes correspond to nodes where a clone had been stored, while
orange nodes correspond to nodes where a clone has been moved due
to LAO.
\end{window}


\section{Adaptive recomputation}
\label{sec:s:re:adaptive}

Consider the situation when a search engine using recomputation
encounters a failed space during exploration. Then it is quite
likely that as exploration continues, more failed spaces are found
during search. This is due to the fact that some decision made
during branching (that is, some alternative) has lead to failure.
It is quite likely that the wrong decision from which search
must recover is somewhere on the path to the root node. 

That means that search now must explore the entire subtree
starting from the wrong decision. In this situation it would be
advantageous if additional clones were available for exploring
the entire subtree. With other words, after encountering
failure, search should become more pessimistic by
investing into the creation of additional clones to speed up
further exploration.

\emph{Adaptive recomputation}~\cite[Chapter~7]{Schulte:LNAI:2002}
optimizes recomputation in the case of failures: an additional
clone is created during recomputation. The idea is that on a path
of length $n$ without any clone, an additional clone is placed in
the middle of that path. This additional clone then speeds up
further recomputation (which is likely to occur as has been
argued above).

Adaptive recomputation is controlled by a parameter called
\emph{adaptive distance} $a_d$: only if $n\geq a_d$ an
additional clone is created. This avoids creating an excessive
amount of clones.

\begin{figure}
\insertlitcode{dfs using adaptive recomputation}
\caption{Depth-first search using adaptive recomputation}
\label{fig:s:re:adaptive}
\end{figure}

Adaptive recomputation is sketched in
\autoref{fig:s:re:adaptive}. The only change compared to hybrid
recomputation (see \autoref{sec:s:re:hybrid}) is the
implementation of \?recompute()?. The argument \?n? is the length
of the path to the next clone. When a clone is found, \?d?  is
set to $\lfloor \frac{\mathtt n}{2}\rfloor$ provided that
$\mathtt{n}\geq\mathtt{a\_d}$. Otherwise \?d? is set to \?n? (its
old value) which also prevents that an additional clone is
created. For the edge that is
\?d? \?commit()? operations away from the current space, a new
clone is stored on the path, provided that the space \?s? is not failed.

The space \?s? can be failed as has been discussed in
\autoref{sec:s:re:wmp}. The search engine here takes a rather
simplistic approach to this situation: it just does not store a
clone. A real-life engine would take more benefit from the
information that a space on the path is actually failed: it would
immediately discard the entire path below the failed space, see
\autoref{chap:s:engine}.

Another optimization that a real-life search engine would employ is
to not place a clone in a position where it could be moved by last
alternative optimization, see again \autoref{chap:s:engine}.





\begin{litcode}{dfs using full recomputation}{schulte}
\begin{litblock}{anonymous}
#include <gecode/kernel.hh>

using namespace Gecode;

\end{litblock}
\begin{litblock}{edge class}
class Edge {
protected:
  Edge* p;
  const Choice* ch;
  unsigned int a;
public:
  Edge(Space* s, Edge* e)
    : p(e), ch(s->choice()), a(0) {}
  \begin{litblock}{next alternative}
  void next(void) {
    a++;
  }
  \end{litblock}
  \begin{litblock}{committing a space}
  Space* commit(Space* s) const {
    s->commit(*ch,a); return s;
  }
  \end{litblock}
  \begin{litblock}{recomputing a space}
  Space* recompute(Space* r) const {
    return commit((p == NULL) ? r->clone() : p->recompute(r));
  }
  \end{litblock}
  ~Edge(void) {
    delete ch;
  }
};
\end{litblock}

Space* dfs(Space* s, Space* r, Edge* p) {
  switch (s->status()) {
  \begin{litblock}{anonymous}
  case SS_FAILED:
    delete s; return NULL;
  case SS_SOLVED:
    (void) s->choice(); return s;
  \end{litblock}
  case SS_BRANCH:
    { 
      \begin{litblock}{explore first alternative}
      Edge e(s,p);
      if (Space* t = dfs(e.commit(s),r,&e))
        return t;
      \end{litblock}
      \begin{litblock}{explore second alternative}
      e.next();
      return dfs(e.recompute(r),r,&e);
      \end{litblock}
    }
  }
}

Space* dfs(Space* s) {
  if (s->status() == SS_FAILED) {
    delete s; return NULL;
  }
  Space* r = s->clone();
  Space* t = dfs(s,r,NULL);
  delete r;
  return t;
}
\end{litcode}


\begin{litcode}{dfs using full recomputation and lao}{schulte}
\begin{litblock}{anonymous}
#include <gecode/kernel.hh>

using namespace Gecode;

\end{litblock}
class Edge {
  \begin{litblock}{anonymous}
protected:
  Edge* p;
  const Choice* ch;
  unsigned int a;
public:
  Edge(Space* s, Edge* e)
    : p(e), ch(s->choice()), a(0) {}
  void next(void) {
    a++;
  }
  \end{litblock}
  \begin{litblock}{test for last alternative}
  bool la(void) const {
    return (p == NULL) && (a == 1);
  }
  \end{litblock}
  \begin{litblock}{anonymous}
  Space* commit(Space* s) const {
    s->commit(*ch,a); return s;
  }
  Space* recompute(Space* r) const {
    return commit((p == NULL) ? r->clone() : p->recompute(r));
  }
  ~Edge(void) {
    delete ch;
  }
  \end{litblock}
};

Space* dfs(Space* s, Space*& r, Edge* p) {
  switch (s->status()) {
  \begin{litblock}{anonymous}
  case SS_FAILED:
    delete s; return NULL;
  case SS_SOLVED:
    (void) s->choice(); return s;
  \end{litblock}
  case SS_BRANCH:
    { 
      Edge e(s,p);
      if (Space* t = dfs(e.commit(s),r,&e))
        return t;
      e.next();
      \begin{litblock}{perform lao}
      if (e.la()) {
        Space* t = r;
        if (e.commit(t)->status() == SS_FAILED)
          return NULL;
        r = t->clone();
        return dfs(t,r,NULL);
      }
      \end{litblock}
      return dfs(e.recompute(r),r,&e);
    }
  }
}
\begin{litblock}{anonymous}
Space* dfs(Space* s) {
  if (s->status() == SS_FAILED) {
    delete s; return NULL;
  }
  Space* r = s->clone();
  Space* t = dfs(s,r,NULL);
  delete r;
  return t;
}
\end{litblock}
\end{litcode}

\begin{litcode}{dfs using hybrid recomputation}{schulte}
\begin{litblock}{anonymous}
#include <gecode/kernel.hh>

using namespace Gecode;

\end{litblock}
const unsigned int c_d = 5;

class Edge {
protected:
  \begin{litblock}{anonymous}
  Edge* p;
  const Choice* ch;
  unsigned int a;
  \end{litblock}
  Space* c;
public:
  Edge(Space* s, Edge* e)
    : p(e), ch(s->choice()), a(0), c(NULL) {}
  \begin{litblock}{anonymous}
  void next(void) {
    a++;
  }
  Space* commit(Space* s) const {
    s->commit(*ch,a); return s;
  }
  \end{litblock}
  \begin{litblock}{create clone}
  void clone(Space* s) {
    c = s->clone();
  }
  \end{litblock}
  \begin{litblock}{perform recomputation}
  Space* recompute(void) const {
    return commit((c != NULL) ? c->clone() : p->recompute());
  }
  \end{litblock}
  \begin{litblock}{anonymous}
  ~Edge(void) {
    delete c; delete ch;
  }
  \end{litblock}
};

Space* dfs(Space* s, Edge* p, unsigned int d) {
  switch (s->status()) {
  \begin{litblock}{anonymous}
  case SS_FAILED:
    delete s; return NULL;
  case SS_SOLVED:
    (void) s->choice(); return s;
  \end{litblock}
  case SS_BRANCH:
    {
      \begin{litblock}{store clone if needed}
      Edge e(s,p);
      if (d >= c_d) {
        e.clone(s); d=0;
      }
      \end{litblock}
      \begin{litblock}{explore first alternative}
      if (Space* t = dfs(e.commit(s),&e,d+1))
        return t;
      \end{litblock}
      \begin{litblock}{anonymous}
      e.next();
      return dfs(e.recompute(),&e,d+1);
      \end{litblock}
    }
  }
}

Space* dfs(Space* s) {
  return dfs(s,NULL,c_d);
}
\end{litcode}

\begin{litcode}{dfs using adaptive recomputation}{schulte}
\begin{litblock}{anonymous}
#include <gecode/kernel.hh>

using namespace Gecode;

\end{litblock}
const unsigned int c_d = 5;
const unsigned int a_d = 2;

class Edge {
protected:
  \begin{litblock}{anonymous}
  Edge* p;
  const Choice* ch;
  unsigned int a;
  Space* c;
public:
  Edge(Space* s, Edge* e)
    : p(e), ch(s->choice()), a(0), c(NULL) {}
  void next(void) {
    a++;
  }
  Space* commit(Space* s) const {
    s->commit(*ch,a); return s;
  }
  void clone(Space* s) {
    c = s->clone();
  }
  \end{litblock}
  Space* recompute(unsigned int n, unsigned int& d) {
    if (c != NULL) {
      d = (n >= a_d) ? n/2 : n;
      return commit(c->clone());
    } else {
      Space* s = p->recompute(n+1,d);
      if ((d == n) && (s->status() != SS_FAILED))
        clone(s);
      return commit(s);
    }
  }
  Space* recompute(unsigned int& d) {
    return recompute(1,d);
  }
  \begin{litblock}{anonymous}
  ~Edge(void) {
    delete c; delete ch;
  }
  \end{litblock}
};
\begin{litblock}{anonymous}

Space* dfs(Space* s, Edge* p, unsigned int d) {
  switch (s->status()) {
  case SS_FAILED:
    delete s; return NULL;
  case SS_SOLVED:
    (void) s->choice(); return s;
  case SS_BRANCH:
    {
      Edge e(s,p);
      if (d >= c_d) {
        e.clone(s); d=0;
      }
      if (Space* t = dfs(e.commit(s),&e,d+1))
        return t;
      e.next();
      return dfs(e.recompute(d),&e,d+1);
    }
  }
}

Space* dfs(Space* s) {
  return dfs(s,NULL,c_d);
}
\end{litblock}
\end{litcode}


\begin{litcode}{bab using full recomputation}{schulte}
\begin{litblock}{anonymous}
#include <gecode/kernel.hh>

using namespace Gecode;

class Edge {
protected:
  Edge* p;
  const Choice* ch;
  unsigned int a;
public:
  Edge(Space* s, Edge* e)
    : p(e), ch(s->choice()), a(0) {}
  void next(void) {
    a++;
  }
  Space* commit(Space* s) const {
    s->commit(*ch,a); return s;
  }
  Space* recompute(Space* r) const {
    return commit((p == NULL) ? r->clone() : p->recompute(r));
  }
  ~Edge(void) {
    delete ch;
  }
};

\end{litblock}
void bab(Space* s, Space*& r, Space*& b, Edge* p) {
  switch (s->status()) {
  \begin{litblock}{anonymous}
  case SS_FAILED:
    delete s; break;
  \end{litblock}
  case SS_SOLVED:
    \begin{litblock}{solved}
    delete b; 
    (void) s->choice(); b = s->clone(); delete s;
    r->constrain(*b);
    if (r->status() == SS_FAILED) {
      delete r; r = NULL;
    } else {
      Space* c = r->clone(); delete r; r = c;
    }
    break;
    \end{litblock}
  case SS_BRANCH:
    {
      \begin{litblock}{anonymous}
      Edge e(s,p);
      bab(e.commit(s),r,b,&e);
      e.next();
      \end{litblock}
      \begin{litblock}{explore second alternative}
      if (r != NULL)
        bab(e.recompute(r),r,b,&e);
      \end{litblock}
    }
  }
}

Space* bab(Space* s) {
  \begin{litblock}{anonymous}
  if (s->status() == SS_FAILED) {
    delete s; return NULL;
  }
  \end{litblock}
  Space* r = s->clone();
  Space* b = NULL;
  bab(s,r,b,NULL);
  \begin{litblock}{anonymous}
  (void) b->choice();
  delete r;
  return b;
  \end{litblock}
}
\end{litcode}