m-search.tex.in

% -*- mode: LaTeX; -*- 
\chapter{Search}
\label{chap:m:search}

This chapter discusses how \emph{exploration} for search is used
for solving Gecode models. Exploration defines a strategy how to
explore parts of the search tree and how to possibly modify the
tree's shape during exploration (for example, during
branch-and-bound best solution search by adding new constraints).
This chapter restricts itself to simple search engines to find
solutions, Gist as an interactive and graphical search engine is
discussed in \autoref{chap:m:gist}.

\paragraph{Overview.}

\autoref{sec:m:search:re} explains how search in Gecode makes use
of hybrid recomputation and why it is efficient. Even though this
section does not belong to the basic reading material, you are
highly encouraged to read it. 

\autoref{sec:m:search:parallel} explains how parallel search can
be used in Gecode and what can be expected of parallel search in
principle.  How search engines can be used is explained in
\autoref{sec:m:search:simple}.  Restart-based search is discussed
in \autoref{sec:m:search:restart} and portfolio-based search is
discussed in \autoref{sec:m:search:portfolio}. This is followed
by a discussion in \autoref{sec:m:search:nogoods} how no-goods
from restarts can be used. \autoref{sec:m:search:trace} describes
how the execution of search engines can be traced and
\autoref{sec:m:search:cpprofiler} how the CPProfiler can be used
for tracing during search.

\begin{convention}
  Note that the same conventions hold as in \autoref{chap:m:int}.
\end{convention}

\section{Hybrid recomputation}
\label{sec:m:search:re}

A central requirement for search is that it can return to
previous states: as spaces constitute nodes of the search tree, a
previous state is nothing but a space. Returning to a previous
space might be necessary because an alternative suggested by a
branching did not lead to a solution, or even if a solution has
been found more solutions might be requested.  As propagation and
branching change spaces, provisions must be taken that search can
actually return to a previous space, or an equivalent version of
that space.

Two space are \emph{equivalent} if propagation and branching and
hence search behave exactly the same on both spaces. Equivalent
spaces can be different, for example, they contain different yet
equivalent propagators, or are allocated at a different memory
area.

Gecode employs a hybrid of two techniques for restoring spaces:
\emph{recomputation} and \emph{cloning}.  

If you want to know how search engines can be programmed in
Gecode, please consult \autoref{part:s}.

\subsection{Cloning}

Cloning creates a clone of a space (this is supported by the
virtual \?copy?  member function as discussed in
\autoref{chap:m:started}). A clone and the original space are of
course equivalent. Restoration with cloning is straightforward:
before following a particular alternative during search, a clone
of the space is made and used later if necessary.

\subsection{Recomputation}
\label{sec:m:search:recomp}

Recomputation remembers what has happened during branching:
rather than storing an entire clone of a space just enough
information to redo the effect of a brancher is stored. The
information stored is called a \emph{choice} in
Gecode.  Redoing the effect is called to \emph{commit} a space:
given a space and a choice committing re-executes
the brancher as described by the choice and the
alternative to be explored (for example, left or right).

Consider the following part of a model, which constrains both
the sum and the product of \?x[0]? and \?x[1]? to be equal to
\?x[2]?:
\begin{code}
IntVarArray x(home, 3, 1, 6);
rel(home, x[0] + x[1] == x[2]);
mult(home, x[0], x[1], x[2]);
branch(home, x, INT_VAR_NONE(), INT_VAL_MIN());
\end{code}

\begin{figure}
\newcommand{\domINC}[2]{\{\mathtt{#1},\ldots,\mathtt{#2}\}}
\begin{center}
\begin{tabular}{c@{\qquad\qquad}c}
\begin{tabular}[c]{c}
\psset{xunit=0.04,yunit=0.04,runit=0.04}
\begin{pspicture}(96,152)(0,0)
\DefineNode{32}{143}{n1u}
\DefineNode{32}{133}{n1c}
 \DefineNode{48}{105}{n12u}
 \DefineNode{48}{95}{n12c}
  \DefineNode{64}{67}{n122u}
  \DefineNode{64}{57}{n122c}
   \DefineNode{80}{27}{n1222u}
   \DefineNode{80}{19}{n1222c}
   \DefineLink{n122c}{n1222u}
   \HiddenLinkL{n122c}{n1222c}{\footnotesize\quad$\mathtt{x[0]} \neq \mathtt 3$}
   \DefineNode{48}{27}{n1221u}
   \DefineNode{48}{19}{n1221c}
   \DefineLink{n122c}{n1221u}
   \HiddenLinkR{n122c}{n1221c}{\footnotesize$\mathtt{x[0]} = \mathtt 3$\quad}
  \DefineLink{n12c}{n122u}
  \HiddenLinkL{n12c}{n122c}{\footnotesize\quad$\mathtt{x[0]} \neq \mathtt 2$}
  \DefineNode{32}{67}{n121u}
  \DefineNode{32}{57}{n121c}
  \DefineLink{n12c}{n121u}
  \HiddenLinkR{n12c}{n121c}{\footnotesize$\mathtt{x[0]} = \mathtt 2$\quad}
 \DefineLink{n1c}{n12u}
 \HiddenLinkL{n1c}{n12c}{\footnotesize\quad$\mathtt{x[0]} \neq \mathtt 1$}
 \DefineNode{16}{103}{n11u}
 \DefineNode{16}{95}{n11c}
 \DefineLink{n1c}{n11u}
 \HiddenLinkR{n1c}{n11c}{\footnotesize$\mathtt{x[0]} = \mathtt 1$\quad}
\ChoiceNodeI{32}{133}{1}
 \ChoiceNodeI{48}{95}{3}
  \ChoiceNodeI{64}{57}{5}
   \FailedNodeI{80}{19}{7}
   \FailedNodeI{48}{19}{6}
  \SolvedNodeI{32}{57}{4}
 \FailedNodeI{16}{95}{2}
\end{pspicture}
\end{tabular}
&
\begin{tabular}[c]{|c||c|c|c|}
\hline
\textbf{node} & $\mathtt{x[0]}$ & $\mathtt{x[1]}$ & $\mathtt{x[2]}$ 
\\\hline\hline
1 & $\domINC{1}{5}$ & $\domINC{1}{5}$ & $\domINC{2}{6}$ 
\\\hline
3 & $\domINC{2}{5}$ & $\domINC{1}{3}$ & $\domINC{3}{6}$
\\\hline
4 & $\mathtt 2$             & $\mathtt 2$             & $\mathtt 4$
\\\hline
5 & $\domINC{3}{5}$ & $\domINC{1}{2}$ & $\domINC{4}{6}$
\\\hline
\end{tabular}
\end{tabular}
\end{center}

\caption{Example search tree}
\label{fig:m:search:tree}
\end{figure}

The corresponding search tree is shown in
\autoref{fig:m:search:tree}. A red box corresponds to a failed
node, a green diamond to a solution, and a blue circle to a
choice node (a node that has a not-yet finished brancher left).
An example choice for node~3 is
$\left(\mathtt{x[0]} = \mathtt 2\right) \vee \left(\mathtt{x[0]}
  \neq \mathtt 2\right)$ where the left alternative (or the
$0$-th alternative) is $\mathtt{x[0]} = \mathtt 2$ and the right
alternative ($1$-st alternative) is $\mathtt{x[0]} \neq \mathtt
2$.  Committing a space for node~3 to the $1$-st alternative
posts the constraint $\mathtt{x[0]} \neq \mathtt 2$.
     
More precisely, a choice does not store the actual
variables but the position among the variables of the brancher
(storing \?0? rather than \?x[0]?). By that, a choice can be used with an equivalent yet different space.
This is essential as the space used during recomputation will be
different from the space for which the choice has
been created.

\tip{Search is indeterministic}{
\label{tip:m:search:wmp}%
Gecode has been carefully designed to support non-monotonic
propagators: they are essential for example for randomized or
approximation propagation algorithms. A propagator in Gecode must
be \emph{weakly} monotonic: essentially, a propagator must be
correct but it does not need to always prune exactly the same
way. A consequence of this is that search is indeterministic: it
might be that two different searches find solutions in a
different order (possibly returning a different first solution)
or that the number of explored nodes is different. However,
search is always sound and complete: it never misses any
solution, it does not duplicate solutions, nor does it report
non-solutions as solutions.

If you want to know more about weakly monotonic propagators and
their interaction with search, we recommend to
consult~\cite{SchulteTack:CP:2009}.
}

\subsection{Hybrid recomputation}

The hybrid of recomputation and cloning works as follows. For
each new choice node, a choice is stored. Then,
every now and then search also stores a clone of a space (say,
every eight steps). Now, restoring a space at a certain position
in the search tree traverses the path in the tree upwards until a
clone $c$ is found on the path. Then recomputation creates a
clone $c'$ of $c$ (in certain cases, recomputation might use $c$
directly as an optimization). Then all choices on
the path are committed on $c'$ yielding an equivalent space.

\begin{figure}
\begin{center}
\psset{xunit=0.04,yunit=0.04,runit=0.04}
\begin{pspicture}(240,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}
   \ChoiceNodeI{64}{133}{1}
  \UChoiceNodeI{48}{95}{2}
 \UChoiceNodeI{32}{57}{3}
\FailedNodeI{16}{19}{4}
\GuessNode{48}{19}
\DefineNode{120}{133}{t1}
\DefineNode{120}{95}{t2}
\DefineNode{120}{57}{t3}
\DefineNode{120}{19}{t4}
\rput(120,133){\makebox(0,0)[l]{space $\mathtt c$ and choice
    $\mathtt{ch1}$}}
\rput(120,95){\makebox(0,0)[l]{choice $\mathtt{ch2}$}}
\rput(120,57){\makebox(0,0)[l]{choice $\mathtt{ch3}$}}
\ncline[nodesep=15]{->}{t1}{n1c}
\ncline[nodesep=15]{->}{t2}{n2c}
\ncline[nodesep=15]{->}{t3}{n3c}
\end{pspicture}
\end{center}

\caption{Hybrid recomputation}
\label{fig:m:search:hybrid}
\end{figure}

\begin{samepage}
To recompute the node \texttt{?} for the example shown in
\autoref{fig:m:search:hybrid}, the following operations are
executed:
\begin{code}
Space* s = c->clone();
s->commit(ch1, 0);
s->commit(ch2, 0);
s->commit(ch3, 1);
\end{code}
\end{samepage}

\subsection{Why recomputation is almost for free}

An absolutely fundamental property of the above hybrid is that an
equivalent space is computed without performing any constraint
propagation! Remember: committing just reposts constraints but
does not perform constraint propagation.

Reconsider the example from \autoref{fig:m:search:hybrid}.
Search has just failed at node~4 and must compute a space for
node \texttt{?}.

Suppose that only cloning but no recomputation is used. Then, a
clone of the space for node~3 is created (from the clone that is
stored in node~3) and that clone is committed to the first
alternative of $\mathtt{d3}$ (this corresponds to the slightly
thicker edge in \autoref{fig:m:search:hybrid}).  After that,
constraint propagation is performed (by executing the \?status()?
function of a space, see also \autoref{tip:m:started:status}) to
find out if and how search must continue. That is: there is one
\?clone?  operation, one \?commit? operation, and one \?status?
operation to perform constraint propagation.

With hybrid recomputation, one \?clone? operation, three
\?commit? operations, and one \?status? operation to perform
constraint propagation are needed (as shown above). The good news
is that \?commit? operations are very cheap (most often, just
modifying a single variable or posting a constraint). What is
essential is that in both cases only a \emph{single} \?status?
operation is executed. Hence, the cost for constraint propagation
during hybrid recomputation turns out to be not much higher than
the cost without recomputation.

For hybrid recomputation, some additional propagation might have
to be done compared to cloning. As it turns out, the additional
cost is rather small. This is due to the fact that constraint
propagation executes all propagators that might be able to remove
values for variables until no more propagation is possible (a
fixpoint for the propagators is computed). Due to the
approximative nature of ``might be able to remove values'' the
additional propagation tends to show only a very small increase
in runtime.


\subsection{Adaptive recomputation}

Consider the case that a search engine finds a failed node. That
means that some brancher has made an erroneous decision and now
search has to recover from that decision. It is quite likely that
not only the last decision is wrong but that the decision that
lead to failure is somewhere higher up in the search tree. With
other words, it is quite likely that search following a
depth-first left-most strategy must explore an entire failed
subtree to recover from the erroneous decision.  In that case it
would be better for hybrid recomputation if there was a clone
close to the failed node rather than far away.

To optimize recomputation in this example scenario, Gecode uses
\emph{adaptive recomputation}: if a node must be recomputed,
adaptive recomputation creates an additional clone in the middle
of the recomputation path. A clone created during adaptive
recomputation is likely to be a good investment.  Most likely, an
entire failed subtree will be explored. Hence, the clone will be
reused several times for reducing the amount of constraint
propagation during recomputation.

More information about search based on recomputation (although
not using choices) can be found in~\cite{Schulte:LNAI:2002}.
Search using choices has been inspired by batch
recomputation~\cite{components} and decomposition-based
search~\cite{DecoSearch}. For an empirical evaluation of
different techniques for search,
see~\cite{ReischukSchulteEa:CP:2009}. 

\subsection{Controlling recomputation}

Hybrid and adaptive recomputation can be easily controlled by two
integers $c_d$ (\emph{commit distance})
and $a_d$ (\emph{adaptive distance}).  The value for $c_d$ controls how
many clones are created during exploration: a search engine
creates clones during exploration to ensure that recomputation
executes at most $c_d$ commit operations. The value for $a_d$
controls adaptive recomputation: only if the clone for
recomputation is more than $a_d$ commit operations away from the
node to be recomputed, adaptive recomputation is used. 

Values for $c_d$ and $a_d$ are used to configure the behavior of
search engines using hybrid and adaptive recomputation, see more
in the next Section.

The number of commit operations as distance measure is
approximately the same as the length of a path in the search
tree. It is only an approximation as search engines use
additional techniques to avoid some unused clone and commit
operations.

\tip{Values for $c_d$ and $a_d$}{ 
  If $c_d=1$, recomputation is never used (you might not want
  to try that for any other reason but curiosity; it takes too
  much memory to be useful). Likewise, to switch off cloning, you
  can use a value for $c_d$ that is larger than the expected
  depth of the search tree. If $a_d\geq c_d$, adaptive
  recomputation is never used.
}


\section{Parallel search}
\label{sec:m:search:parallel}

Parallel search has but one motivation: try to make search more
efficient by employing several threads (or workers) to explore
different parts of the search tree in parallel.

Gecode uses a standard work-stealing architecture for parallel
search: initially, all work (the entire search tree to be
explored) is given to a single worker for exploration, making the
worker busy. All other workers are initially idle, and try to
steal work from a busy worker.  Stealing work means that part of
the search tree is given from a busy worker to an idle worker
such that the idle worker can become busy itself. If a busy
worker becomes idle, it tries to steal new work from a busy
worker.

As work-stealing is indeterministic (depending on how threads are
scheduled, machine load, and other factors), the work that is
stolen varies over different runs for the very same problem: an
idle worker could potentially steal different subtrees from
different busy workers. As different subtrees contain different
solutions, it is indeterministic which solution is found first.

When using parallel search one needs to take the following facts
into account (note that some facts are not particular to
parallel search, check \autoref{tip:m:search:wmp}: they are just
more likely to occur):
\begin{itemize}
\item The order in which solutions are found might be different
  compared to the order in which sequential search finds
  solutions. Likewise, the order in which solutions are found
  might differ from one parallel search to the next. This is just
  a direct consequence of the indeterministic nature of parallel
  search.
\item Naturally, the amount of search needed to find a first
  solution might differ both from sequential search and among
  different parallel searches. Note that this might actually lead
  to super-linear speedup (for $n$ workers, the time to find a
  first solution is less than $1/n$ the time of sequential
  search) or also to real slowdown.
\item For best solution search, the number of solutions until a
  best solution is found as well as the solutions found are
  indeterministic. First, any better solution is legal (it does
  not matter which one) and different runs will sometimes be
  lucky (or not so lucky) to find a good solution rather quickly.
  Second, as a better solution prunes the remaining search space
  the size of the search space depends crucially on how quickly
  good solutions are found.
\item As a corollary to the above items, the deviation in runtime
  and number of nodes explored for parallel search can be quite
  high for different runs of the same problem.
\item Parallel search needs more memory. As a rule of thumb, the
  amount of memory needed scales linearly with the number of
  workers used.
\item For parallel search to deliver some speedup, the search
  tree must be sufficiently large. Otherwise, not all threads
  might be able to find work and idle threads might slow down
  busy threads by the overhead of unsuccessful work-stealing.
\item From all the facts listed, it should be clear that for
  depth-first left-most search for just a single solution it is
  notoriously difficult to obtain consistent speedup. If the
  heuristic is very good (there are almost no failures), sequential
  left-most depth-first search is optimal in exploring the single
  path to the first solution. Hence, all additional work will be
  wasted and the work-stealing overhead might slow down the
  otherwise optimal search.
\end{itemize}

\tip{Be optimistic about parallel search}{%
  After reading the above list of facts you might have come to
  the conclusion that parallel search is not worth it as it does
  not exploit the parallelism of your computer very well. Well,
  why not turn the argument upside down: your machine will almost
  for sure have more than a single processing unit and maybe
  quite some. With sequential search, all units but one will be
  idle anyway.
  
  The point of parallel search is to make search go faster.  It
  is not to perfectly utilize your parallel hardware.  Parallel
  search makes good use (and very often excellent use for large
  problems with large search trees) of the additional processing
  power your computer has anyway.

\begin{figure}
\begin{cmd}
GolombRuler
        m[12] = {0, 1, 3, 7, 12, 20, 30, 44, 65, 80, 96, 122}
        m[12] = {0, 1, 3, 7, 12, 20, 30, 44, 65, 90, 105, 121}
        m[12] = {0, 1, 3, 7, 12, 20, 30, 45, 61, 82, 96, 118}
        ... (additional solutions omitted)
        m[12] = {0, 2, 6, 24, 29, 40, 43, 55, 68, 75, 76, 85}

Initial
        propagators: 58
        branchers:   1

Summary
        runtime:      14.866 (14866.000 ms)
        solutions:    17
        propagations: 519555681
        nodes:        3836351
        failures:     1918148
        restarts:     0
        no-goods:     0
        peak depth:   26
\end{cmd}
\caption{Output for Golomb rulers with eight workers}
\label{fig:m:search:out:8}
\end{figure}


\begin{samepage}
  For example, on my machine with eight cores and using Gecode 4.2.0, running
  \gecoderef[example]{golomb-ruler} for size $12$ as follows
\begin{cmd}
golomb-ruler.exe -threads 8 12
\end{cmd}
\end{samepage}
  prints something like shown in \autoref{fig:m:search:out:8}.

\begin{figure}
\begin{cmd}
GolombRuler
        m[12] = {0, 1, 3, 7, 12, 20, 30, 44, 65, 80, 96, 122}
        m[12] = {0, 1, 3, 7, 12, 20, 30, 44, 65, 90, 105, 121}
        m[12] = {0, 1, 3, 7, 12, 20, 30, 45, 61, 82, 96, 118}
        ... (additional solutions omitted)
        m[12] = {0, 2, 6, 24, 29, 40, 43, 55, 68, 75, 76, 85}

Initial
        propagators: 58
        branchers:   1

Summary
        runtime:      1:47.316 (107316.000 ms)
        solutions:    16
        propagations: 692676452
        nodes:        5313357
        failures:     2656663
        restarts:     0
        no-goods:     0
        peak depth:   24
\end{cmd}
\caption{Output for Golomb rulers with one worker}
\label{fig:m:search:out:1}
\end{figure}

Compared to sequential search where one gets something like shown
in \autoref{fig:m:search:out:1} one gets a speedup of $7.2$.  }

Parallel search is controlled by the number of threads (or
workers) used for search. If a single worker is requested,
sequential search is used. The number of threads to be used for
search is controlled by the search options passed to a search
engine, see the following section for details.

Gecode also provides parallel portfolio search which is discussed
in \autoref{sec:m:search:portfolio}.

\tip{Do not optimize by branching alone}{%
\label{tip:m:search:parbab}%
\begin{samepage}
  A common modeling technique for optimization problems that does
  not work for parallel search is the following. Suppose, one has
  a variable \?c? for the cost of a problem and one wants to
  minimize the cost. Then, one could use the following code
  fragment
\begin{code}
branch(home, c, INT_VAL_MIN());
\end{code}
which will try the values for \?c? in increasing order.
\end{samepage}

With sequential search, searching for the first solution with a
standard depth-first left-most search engine will deliver a
best solution, that is, a solution with least cost for \?c?.

With parallel search, the first solution found might of course
not be a best one. Hence, instead of using plain left-most
depth-first search, one should use best solution search with a
proper constrain function that guarantees that \?c? will be
minimized. This will as always guarantee that the last solution
found is the best.

For an example, see the naive model for the bin packing case
study in \autoref{sec:c:bpp:naive} where a branching first
branches on the number of required bins.
}



\section{Search engines}
\label{sec:m:search:simple}

\begin{important}
Do not forget to add
\begin{code}
#include <gecode/search.hh>
\end{code}
to your program when you want to use search engines.
\end{important}

\begin{figure}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
\multicolumn{1}{|c|}{member} & 
\multicolumn{1}{c|}{type} & 
\multicolumn{1}{c|}{meaning} \\
\hline\hline
\?propagate? & \?unsigned long int? & propagators executed\\
\hline
\?fail? & \?unsigned long int? & failed nodes explored\\
\?node? & \?unsigned long int? & nodes explored\\
\?restart? & \?unsigned long int? & restarts performed\\
\?nogood? & \?unsigned long int? & no-goods generated\\
\hline
\?depth? & \?unsigned long int? & maximal depth of explored tree\\
\hline
\end{tabular}
\end{center}
\caption[Search statistics]{Search statistics (partial)}
\label{fig:m:search:statistics}
\end{figure}

All search engines in Gecode are parametric (are templates) with
respect to a subclass \?T? of \gecoderef[class]{Space} (for
example, \?SendMoreMoney? in \autoref{sec:m:started:first}).
Moreover, all search engines share the same interface:
\begin{itemize}
\item The search engine is initialized by a constructor taking a
  pointer to an instance of the space subclass \?T? as argument.
  By default, the search engine takes a clone of the space
  passed. 
  
  This behavior can be changed, as can be other aspects of a
  search engine, see \autoref{sec:m:search:options}.
\item A next solution can be requested by a \?next()? member
  function. If no more solutions exist, \?next()? returns
  \?NULL?. Otherwise, the engine returns a solution which again
  is an instance of \?T?. The client of the search engine is
  responsible for deleting solutions.
\item A search engine can be asked for statistics information by
  the \?statistics()? member function. The function returns an
  object of type \gecoderef[class]{Search::Statistics}. The
  statistics information provided is partially summarized in
  \autoref{fig:m:search:statistics} (see
  \autoref{sec:m:search:restart} for the meaning of \?restart?
  and \autoref{sec:m:search:nogoods} for the meaning of \?nogood?).
\item A search engine can be queried by \?stopped()? whether the
  search engine has been stopped by a \emph{stop object}. Stop
  objects are discussed in \autoref{sec:m:search:stop}.
\item The destructor deletes all resources used by the search
  engine.
\end{itemize}

Note that search engines use pointers to objects rather than
references to objects. The reason is that some pointers might be
\?NULL?-pointers (for example, if \?next()? fails to find a
solution) and that users of search engines have to think about
deleting solutions computed by search engines.

\begin{figure}
\begin{center}
\begin{tabular}{|l|l|l|c|c|}
\hline
\multicolumn{1}{|c|}{engine} & 
\multicolumn{1}{c|}{shortcut} & 
\multicolumn{1}{c|}{exploration} & 
best solution &
parallel \\
\hline\hline
\gecoderef[class]{DFS} & \?dfs? & depth-first left-most & & \YES\\
\gecoderef[class]{LDS} & \?lds? & limited discrepancy~\cite{HarveyGinsberg:95} &&\\
\hline
\gecoderef[class]{BAB} & \?bab? & branch-and-bound & \YES & \YES\\
\hline
\end{tabular}
\end{center}
\caption{Available search engines}
\label{fig:m:search:engine}
\end{figure}

For each search engine there also exists a convenient shortcut
function (of the same name but entirely in lowercase letters)
that returns either the first solution or, in the case of best
solution search, the last (and hence best) solution. The
available search engines are summarized in
\autoref{fig:m:search:engine}. 

\?BAB? continues search when a solution is found by adding a
constraint (through the \?constrain()? function as discussed in
\autoref{sec:m:started:search-best}) to search for a better
solution to all remaining nodes of the search tree. 

Note that the version of Gecode (\GecodeVersion) this document
corresponds to does not support parallel search for \?LDS?.


\subsection{Search options}
\label{sec:m:search:options}

All search engines can take a default option value of type 
\gecoderef[class]{Search::Options} when being created. The
options are summarized in \autoref{fig:m:search:options}.
The default values for the options are defined in the namespace
\gecoderef[namespace]{Search::Config}. 

\begin{figure}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
\multicolumn{1}{|c|}{member} & 
\multicolumn{1}{c|}{type} & 
\multicolumn{1}{c|}{meaning} \\
\hline\hline
\?threads? & \?double? & number of parallel threads to use\\
\hline
\?c_d? & \?unsigned int? & commit recomputation distance\\
\?a_d? & \?unsigned int? & adaptive recomputation distance\\
\hline
\?clone? & \?bool? & whether engine uses a clone when created\\
\hline
\?d_l? & \?unsigned int? & discrepancy limit (for \?LDS?)\\
\hline
\?nogoods_limit? & \?unsigned int? & depth limit for no-good generation\\
\hline
\?assets? & \?unsigned int? & number of assets in a portfolio\\
\hline
\?stop? & \?Search::Stop*? & stop object (\?NULL? if none)\\
\hline
\?cutoff? & \?Search::Cutoff*? & cutoff object (\?NULL? if none)\\
\hline
\?tracer? & \?SearchTracer*? & search tracer (\?NULL? if none)\\
\hline
\end{tabular}
\end{center}
\caption{Search options}
\label{fig:m:search:options}
\end{figure}

The meaning of the values for the search options are
straightforward but for \?threads? (\?cutoff? is explained in
\autoref{sec:m:search:restart}, \?assets? is explained in
\autoref{sec:m:search:portfolio}, \?nogoods_limit? is
explained in \autoref{sec:m:search:nogoods}, and \?tracer? is
explained in \autoref{sec:m:search:trace}).

Assume that your computer has
$m$ processing units\footnote{This is a very rough
  characterization: a processing unit could be a CPU, a processor
  core, or a multi-threading unit. If you want to find out how
  many processing units Gecode believes your machine has, invoke
  the configuration summary as described in
  \autoref{tip:m:comfy:conf}.} and that the value for \?threads?
is $n$.
\begin{itemize}
\item If $n=0$, then $m$ threads are used (as many as available
  processing units).
\item If $n\geq 1$, then $n$ threads are used (absolute number
  of threads to be used).
\item If $n\leq -1$, then $m+n$ threads are used (absolute
  number of processing units not to be used). For example, when
  $n=-6$ and $m=8$, then $2$ threads are used.
\item If $0<n<1$, then $n\cdot m$ threads are used (relative
  number of processing units to be used). For example, when
  $n=0.5$ and $m=8$, then $4$ threads are used.
\item If $-1<n<0$, then $(1+n)\cdot m$ threads are used
  (relative number of processing units not to be used). For
  example, when $n=-0.25$ and $m=8$, then $6$ threads are used.
\end{itemize}
Note that all values are of course rounded and that at least one
thread will be used.


\subsection{Stop objects}
\label{sec:m:search:stop}

A stop object (a subclass of \gecoderef[class]{Search::Stop})
implements a single virtual member function \?stop()? that takes
two arguments, the first of type
\gecoderef[class]{Search::Statistics} and the second of type
\gecoderef[class]{Search::Options},
and returns either \?true?  or \?false?. If a stop object is passed
to a search engine (by passing it as \?stop? member of a search
option), the search engine calls the \?stop()? function of the
stop object before every exploration step and passes the current
statistics as argument.  If the \?stop()? function returns true,
the search engine stops its execution.

When a search engine is stopped its \?next()? function returns
\?NULL? as solution. To find out whether a search engine has been
stopped or whether there are no more solutions, the \?stopped()?
member function of a search engine can be used. Search can be
resumed by calling \?next()? again after the stop object has been
modified (for example, by increasing the node or time limit).

Note that when using several threads for parallel search, each
thread checks whether it is stopped independently using the very
same stop object. If one thread is stopped, then the entire
search engine is stopped. 

\begin{figure}
\begin{center}
\begin{tabular}{|l|l|}
\hline
\multicolumn{1}{|c|}{class} & 
\multicolumn{1}{c|}{description} \\
\hline\hline
\gecoderef[class]{Search::NodeStop} & node limit exceeded\\
\hline
\gecoderef[class]{Search::FailStop} & failure limit exceeded\\
\hline
\gecoderef[class]{Search::TimeStop} & time limit exceeded\\
\hline
\end{tabular}
\end{center}
\caption{Predefined stop objects}
\label{fig:m:search:stop}
\end{figure}


Gecode provides several predefined stop objects, see
\gecoderef[group]{TaskModelSearchStop}. For an overview see
\autoref{fig:m:search:stop}. Objects of these classes can be
created conveniently by, for example:
\begin{code}
Stop* s = Search::Stop::node(l);
\end{code}
The class \gecoderef[class]{Search::Stop} also provides similar
static functions \?fail()? and \?time()?.

\tip{Number of threads for stop objects}{%
As mentioned above, each thread in parallel search uses the very same
stop object. For example, when using the predefined
\gecoderef[class]{Search::NodeStop} stop object with a node limit
of $n$, then each thread can explore up to $n$ nodes.

If you want to have finer control (say, only allow each thread to
explore up to $n/m$ nodes where  $m$ is the number of threads)
you can use the search option argument that is passed as the
second argument to the \?stop? member function to scale the node
limit according to the number of available threads.
}


\section{Restart-based search}
\label{sec:m:search:restart}

The idea of restart-based search is to run search with a given
\emph{cutoff} (Gecode uses the number of failures during search
as cutoff-measure). When search reaches the cutoff, it is stopped
and then restarted with a new and typically increased cutoff.

The whole point of restarting search is that it is not restarted
on exactly the same problem but on a modified or
re-configured problem. Possible modifications include but are not
limited to:
\begin{itemize}
\item Improved information from the search for branching
  heuristics such as action (see
  \autoref{sec:m:branch:action}) or AFC (see
  \autoref{sec:m:branch:afc}): the now stopped search has
  gathered some information of which branching can take advantage
  in the next restart of search.
\item The next search can use different random numbers that
  controls branching. A typical strategy would be to use
  tie-breaking for combining a branching heuristic with a random
  branching heuristic (see \autoref{sec:m:branch:tie}) and
  control the degree of randomness by a tie-breaking limit
  function.
\item The next search uses an entirely different branching
  heuristic.
\item The next search adds so-called no-goods derived from the
  now stopped search. No-goods are additional constraints that
  prevent the restarted search to make decisions during search
  that lead to failure in the stopped search. No-goods are
  discussed in detail in \autoref{sec:m:search:nogoods}.
\item The next search ``keeps'' only a randomly selected part of
  a previous solution and tries to find a different solution.
  This is often used for optimization problems and is known as
  LNS (Large Neighborhood Search)~\cite{LNS}. How restart-based
  can be used for LNS is discussed in
  \autoref{sec:m:search:restart:lns}.
\end{itemize}

For an example illustrating the effect of restart-based search,
see \autoref{sec:c:crossword:info}. A general overview of
restart-based search can be found in~\cite{vanBeek:CPH:2006}.

\subsection{Restart-based search as a meta search engine}
\label{sec:m:search:restart:meta}

Restart-based search in Gecode is implemented as a \emph{meta
  search engine}: the meta search engine uses one of the Gecode
search engines discussed in~\autoref{sec:m:search:simple} to
perform search for each individual restart. The meta engine then
controls the engine, the cutoff values, and how the problem is
configured before each restart. The interface of the meta search
engine in Gecode is exactly the same as the interface of a
non-meta search engine. In addition to the restart meta search
engine, Gecode offers a portfolio meta search engine which is
described in \autoref{sec:m:search:portfolio}.

The restart meta search engine \gecoderef[class]{RBS} is
parametric with respect to both 
the script to be solved (a subclass of \gecoderef[class]{Space})
and the search engine to be used.
For example, when we want to use the \gecoderef[class]{DFS}
engine for the script \?s? of class type \?Script?, the meta
engine \?e?  can be created by (\?o? are mandatory search
options, see below):
\begin{code}
RBS<Script,DFS> e(s,o);
\end{code}
Now \?e? implements exactly the same interface as the normal
engines (that is, \?next()? to request the next solution,
\?statistics()? to return the meta engine's statistic, and \?stopped()?
to check whether the meta engine has been stopped).

The meta engine honors all search options as discussed in
\autoref{sec:m:search:options}. If parallel search is requested,
the engine used by the meta engine will use the specified number
of processing units to perform parallel search. The meta engine
requires that the search options specify a
\gecoderef[class]{Search::Cutoff} object defining the cutoff
sequence.

\paragraph{Best solution search.}

Restart-based search can be used for both finding any solution or
finding a best solution. For searching for a best solution, the
meta engine should be used with the \gecoderef[class]{BAB}
engine, for example as:
\begin{code}
RBS<Script,BAB> e(s,o);
\end{code}

The behavior whether the engine performs a restart when a better
solution is performed or whether the \?BAB? engine continues to
find a better solution with a restart can be controlled as
described in \autoref{sec:m:search:restart:configure}.

When using restart-based search for finding a best solution it is
essential to use the \gecoderef[class]{BAB} engine when used as
part of a portfolio-based search engine, see
\autoref{sec:m:search:portfolio:arbitrary}.

\paragraph{Parallel search.}

The restart-based search engine supports parallel search in that
the engine used for performing the restarts can be run in
parallel. The number of threads used can be described by the
search options passed to the restart-based search engine as
described in \autoref{sec:m:search:parallel}.

\tip{Controlling restart-based search with the commandline
  driver}{
\label{tip:m:search:restartcmd}%
The commandline driver transparently supports restart-based
search. Depending on which options are passed on the commandline,
either a search engine or the restart-based meta search engine is
used for search. See \autoref{sec:m:driver:options} for details.
}

\subsection{Cutoff generators}
\label{sec:m:search:restart:cutoff}

The meta engine uses a cutoff generator that generates a sequence
of cutoff values. A cutoff generator must be implemented by
inheriting from the class \gecoderef[class]{Search::Cutoff}. This
abstract class requires that two virtual member functions
\?operator()()? and \?operator++()? are implemented, where the
first returns the current cutoff value and the second increments
to the next cutoff value and returns it. Cutoff values are of
type \?unsigned long int?.

When using the restart meta engine, an instance of a subclass of
\gecoderef[class]{Search::Cutoff} must be passed to the engine by
using the search options (see
\autoref{sec:m:search:options}). For example, when \?s? is a
space to be solved and \?c? a cutoff generator, then the restart
engine can be created by:
\begin{code}
Search::Options o;
o.cutoff = c;
RBS<Script,DFS> e(s,o);
\end{code}

Gecode provides some commonly used cutoff generators:
\begin{description}
\item[Geometric.] A geometric cutoff sequence is defined by the
  scale-factor \?s? and the base \?b?. Then, the sequence
  consists of the cutoff values:
$$
\mathtt{s}\cdot\mathtt{b}^i\qquad\text{for }i=0,1,2,\ldots
$$

\begin{samepage}
  A cutoff generator \?c? for a geometric cutoff sequence with
  scale-factor \?s? (of type \?unsigned long int?) and base \?b?
  (of type \?double?) is created by:
\begin{smallcode}
Search::Cutoff* c = Search::Cutoff::geometric(s,b);
\end{smallcode}
\end{samepage}
The generator is implemented by the class
\gecoderef[class]{Search::CutoffGeometric}.

\item[Luby.] A Luby cutoff sequence is based on the Luby-sequence
  from~\cite{Luby}. The sequence starts with a \?1?. The next
  part of the sequence is the entire previous sequence (only
  \?1?) with the last value of the previous sequence (\?1? again)
  doubled. This construction is then repeated, leading to the
  sequence:
$$
1,1,2,1,1,2,4,1,1,2,1,1,2,4,8,\ldots
$$
  To be practically useful, the values in the Luby sequence are
  scaled by multiplying them with a scale-factor \?s?.
  
  A cutoff generator \?c? for a Luby cutoff sequence with scale-factor
  \?s?  (of type \?unsigned long int?) is created by:
\begin{smallcode}
Search::Cutoff* c = Search::Cutoff::luby(s);
\end{smallcode}
The generator is implemented by the class
\gecoderef[class]{Search::CutoffLuby}.
\item[Random.]  A random cutoff sequence consists of uniformly
  randomly chosen values between a lower bound \?min? and an
  upper bound \?max?. To focus on rather different values, only
  values from the set of $\mathtt n+1$ values:
$$
\setc{\mathtt{min}+\lfloor i\cdot(\mathtt{max}-\mathtt{min})/\mathtt{n}\rfloor}{i=0,\ldots,\mathtt{n}}
$$
are chosen randomly.

   A cutoff generator \?c? for a random sequence with lower bound
   \?min?, upper bound \?max?, and number of values \?n? (all of
   type \?unsigned long int?)
   is created by:
\begin{smallcode}
Search::Cutoff* c = Search::Cutoff::rnd(seed,min,max,n);
\end{smallcode}
  where \?seed? (of type \?unsigned int?) defines the seed value
  for the random number generator used.
The generator is implemented by the class
\gecoderef[class]{Search::CutoffRandom}.
\item[Constant.] A constant cutoff sequence is defined by the
  scale-factor \?s?. Then, the sequence
  consists of the cutoff values:
$$
\mathtt{s},\mathtt{s},\mathtt{s},\ldots
$$
The generator is implemented by the class
\gecoderef[class]{Search::CutoffConstant}.

\begin{samepage}
  A cutoff generator \?c? for a constant cutoff sequence with
  scale-factor \?s? (of type \?unsigned long int?) is created by:
\begin{smallcode}
Search::Cutoff* c = Search::Cutoff::constant(s);
\end{smallcode}
\end{samepage}
\item[Linear.] A linear cutoff sequence is defined by the
  scale-factor \?s?. Then, the sequence
  consists of the cutoff values:
$$
1\cdot\mathtt{s},2\cdot\mathtt{s},3\cdot\mathtt{s},\ldots
$$

\begin{samepage}
  A cutoff generator \?c? for a linear cutoff sequence with
  scale-factor \?s? (of type \?unsigned long int?) is created by:
\begin{smallcode}
Search::Cutoff* c = Search::Cutoff::linear(s);
\end{smallcode}
\end{samepage}
The generator is implemented by the class
\gecoderef[class]{Search::CutoffLinear}.

\item[Append.] An appended cutoff sequence \?c? for \?n? values
  from the cutoff sequence $\mathtt{c}_1$ (with values
  $k_0,k_1,k_2,\ldots$) followed by the values
  from the cutoff sequence $\mathtt{c}_2$ (with values
  $l_0,l_1,l_2,\ldots$) consists of the following values:
  $$
k_0,k_1,\ldots,k_{\mathtt{n}-2},k_{\mathtt{n}-1},l_0,l_1,l_2,\ldots
$$
  A cutoff generator \?c? for an appended cutoff sequence with
  \?n? (of type \?unsigned long int?) values from cutoff generator
  \?c1? followed by values from cutoff generator \?c2? is created by:
\begin{smallcode}
Search::Cutoff* c = Search::Cutoff::append(c1,n,c2);
\end{smallcode}
The generator is implemented by the class
\gecoderef[class]{Search::CutoffAppend}.

\item[Merge.] A merged cutoff sequence \?c? for values
  from the cutoff sequence $\mathtt{c}_1$ (with values
  $k_0,k_1,k_2,\ldots$) merged with the values
  from the cutoff sequence $\mathtt{c}_2$ (with values
  $l_0,l_1,l_2,\ldots$) consists of the following values:
  $$
   k_0,l_0,k_1,l_1,k_2,l_2,\ldots
  $$
  A cutoff generator \?c? for a merged cutoff sequence with
  values from cutoff generator
  \?c1? merged with values from cutoff generator \?c2? is created by:
\begin{smallcode}
Search::Cutoff* c = Search::Cutoff::merge(c1,c2);
\end{smallcode}
The generator is implemented by the class
\gecoderef[class]{Search::CutoffMerge}.

\item[Repeat.] A repeated cutoff sequence \?c? with repeat factor
  \?n? (of type \?unsigned long int?) 
  for the cutoff sequence $\mathtt{c}'$ (with values
  $k_0,k_1,k_2,\ldots$) consists of the following values:
  $$
\begin{array}{c@{}c@{}c@{}l}
\underbrace{k_0,k_0,\ldots,k_0},&
\underbrace{k_1,k_1,\ldots,k_1},&
\underbrace{k_2,k_2,\ldots,k_2},&
\ldots\\
\mbox{\?n? times}&
\mbox{\?n? times}&
\mbox{\?n? times}
\end{array}
$$
  A cutoff generator \?c? for a repeated cutoff sequence with
  repeat factor
  \?n? (of type \?unsigned long int?) and values from the cutoff generator
  \?c1? is created by:
\begin{smallcode}
Search::Cutoff* c = Search::Cutoff::repeat(c1,n);
\end{smallcode}
The generator is implemented by the class
\gecoderef[class]{Search::CutoffRepeat}.

\end{description}


\subsection{Computing a next solution}
\label{sec:m:search:restart:next}

When the restart meta engine is asked for a next solution by
calling \?next()?, there are three possible scenarios:
\begin{itemize}
\item \?next()? returns a pointer to a space (which might be
  \?NULL? in case there are no more solutions or the engine has
  been stopped). Deleting the
  space is as with other engines the responsibility of the meta
  engine's user. 

  By default, asking the meta engine for another solution will
  perform a restart. However, this behavior can be changed such
  that the current cutoff value (minus the failed nodes it
  took to find the current solution) is used for finding a next
  solution. For details, see
  \autoref{sec:m:search:restart:configure}.
\item The meta engine reaches the current cutoff value. It
  restarts search with the next cutoff value.
\item The meta engine is stopped by the stop object passed to
  it. Then \?next()? returns \?NULL? and \?stopped()? returns
  \?true? (to be able to distinguish this scenario from the one
  where there are no more solutions).
\end{itemize}


\subsection{Master and slave configuration}
\label{sec:m:search:restart:configure}

The meta engine maintains a \emph{master} space and each time the
meta engine performs a restart, it passes a \emph{slave} space (a
clone of the master space) to the engine. Configuration is as
follows: the master is configured, the slave is created as a
clone of the master, and then
the slave is configured. Initially, when the meta engine starts
and creates a first slave space, it also configures the slave
space.

More accurately, it leaves the actual configuration to the user:
it calls the virtual member function \?master()? on the master
space and then calls the virtual member function \?slave()?  on
the slave space. As mentioned above, the \?slave()? function is
also called the first time a slave is created. In that way, by
redefining \?master()? and \?slave()? the user can control how
master and slave are being configured (this is exactly the same
idea how \?constrain()?  works for best solution search).

\begin{figure}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
\multicolumn{1}{|c|}{function} & 
\multicolumn{1}{c|}{type} & 
\multicolumn{1}{c|}{meaning} \\
\hline\hline
\?type()? & \?MetaInfo::Type? & type of meta information\\
\hline\hline
\multicolumn{3}{|c|}{restart-based information}\\
\hline
\?restart()? & \?unsigned long int? & number of restart\\
\?solution()? & \?unsigned long int? & number of solutions since
last restart\\
\?fail()? & \?unsigned long int? & number of failures since
last restart\\
\?last()? & \?const Space*? & last solution found (or \?NULL?)\\
\?nogoods()? & \?const NoGoods&? & no-goods recorded from restart\\
\hline\hline
\multicolumn{3}{|c|}{portfolio information}\\
\hline
\?asset()? & \?unsigned int? & number of asset (slave)\\
\hline
\end{tabular}
\end{center}
\caption[Meta information]{Meta information member functions}
\label{fig:m:search:mi}
\end{figure}

By default, every space implements the two member functions
\?master()? and \?slave()?. Both functions take an argument of
class \gecoderef[class]{MetaInfo} that contains information about
the current restart (and also for different assets in a
portfolio, see \autoref{sec:m:search:portfolio}). The class
\?MetaInfo? provides the member functions as shown in
\autoref{fig:m:search:mi}.

For a meta information object \?mi?, the function \?mi.type()?
returns either \?MetaInfo::RESTART? or \?MetaInfo::PORTFOLIO?. In
this section, we are only interested in the functions that are
concerned with restart-based search.

The default \?slave()? function does nothing and returns \?true?,
indicating that the search in the slave space is going to be
complete. This means that if the search in the slave space
finishes exhaustively, the meta search will also finish.
Returning \?false? instead would indicate that the slave search
is incomplete, for example if it only explores a limited
neighborhood of the previous solution.

The default \?master()? function does the following (for a
restart, that is):
\begin{itemize}
\item It calls the \?constrain()? member function with the last
  solution found as argument (if a solution has already been
  found).
\item It possibly posts no-goods as explained in
  \autoref{sec:m:search:nogoods}.
\item It returns \?true? forcing a restart even if a solution
  has been found. Returning \?false? instead would continue
  search without a restart.
\end{itemize}

For example, a class \?Script? can define the member functions as
follows:
\begin{code}
class Script : public Space {
  ...
  virtual bool master(const MetaInfo& mi) {
    // Configure the master
    ...
    // Whether to restart or not
    return true;
  }
  virtual bool slave(const MetaInfo& mi) {
    // Configure the slave
    ...
    // Search is complete
    return true;
  }
};
\end{code}

\begin{figure}
\insertlitcode{default master and slave functions}
\caption{Default \?master()? and \?slave()? functions}
\label{fig:m:search:restart:default}
\end{figure}

The default \?master()? and \?slave()? member functions are shown
in \autoref{fig:m:search:restart:default}. The part of the
\?master()? function that is
specific for restart-based search is as follows:
\insertlitcode{default master and slave functions:restart-based search}


\subsection{Large Neighborhood Search}
\label{sec:m:search:restart:lns}

The design of restart-based search in Gecode is general enough to
support LNS (Large Neighborhood Search)~\cite{LNS}. The idea of
LNS is quite simple, where LNS looks for a good solution:
\begin{itemize}
\item Search finds a first solution where typically preference is
  given to find a reasonably good solution quickly.
\item During LNS, a new problem is generated that only keeps part
  of the so-far best solution (typically, the part to keep is
  randomly selected). This is often referred to as
  \emph{relaxing} the so-far best solution. Then, search tries
  to find a next and better solution within a given cutoff.

  If the cutoff is reached without finding a solution, search can
  either decide to terminate or randomly retry again.
\end{itemize}

\begin{litcode}[texonly]{model sketch for LNS}
class Model : public Space {
protected:
  IntVarArray x;
  Rnd r;
public:
  Model(void) : ... {
    // Initialize master
    \begin{litblock}{anonymous}
    \end{litblock}
  }
  void first(void) {
    // Initialize slave for first solution
    \begin{litblock}{anonymous}
    \end{litblock}
  }
  void next(const Model& b) {
    // Initialize slave for next solution
    \begin{litblock}{anonymous}
    \end{litblock}
  }
  \begin{litblock}{anonymous}
  \end{litblock}
  \begin{litblock}{slave function}
  virtual bool slave(const MetaInfo& mi) {
    if (mi.type() == MetaInfo::RESTART) {
      if (mi.last() == nullptr) {
        first();
        return true;
      } else {
        next(static_cast<const Model&>(*mi.last()));
        return false;
      }
    } else {
      ...
    }
  }
  \end{litblock}
  virtual bool master(const MetaInfo& mi) {
    \begin{litblock}{anonymous}
    ...
    \end{litblock}
  }
};
\end{litcode}

\begin{figure}
\insertlitcode{model sketch for LNS}
\caption{Model sketch for LNS}
\label{fig:m:search:restart:sketch}
\end{figure}

\autoref{fig:m:search:restart:sketch} sketches a model that
supports LNS. The constructor \?Model()? initializes the model
with all variables and constraints that are common for
finding the first solution as well as for finding further
solutions. Note that the model has a random number generator of
class \gecoderef[class]{Rnd} as member \?r? to illustrate that
typically some form of randomness is needed for
restarting. However, in a real life problem additional data
structures might be needed.

\begin{samepage}
The \?first()? function is responsible for posting additional
constraints and branchings such that search can find the first
solution. The \?next()? function takes the so-far best solution
\?b? and posts additional constraints and branchings to find a
next and better solution than \?b?. This will typically mean that
some but not all variables in the current space are assigned to
values as defined by the so-far best solution \?b? or that
additional constraints are posted that depend on \?b?.
\end{samepage}

\begin{samepage}
Both \?first()? and \?next()? are executed on the slave space
when the restart-based search engine performs a restart or
executes search for the first time. This can be achieved by
defining the \?slave()? function as follows. Note how it returns \?true?
to indicate that the search is going to be complete until it has
found a first solution\footnote{Please note that the engine might
  restart several times until a first solution has been found.}
but \?false? for subsequent restarts, which only explore a neighborhood and
are therefore incomplete:
\insertlitcode{model sketch for LNS:slave function}
\end{samepage}
The default \?master()? function as shown in
\autoref{sec:m:search:restart:configure} is already general
enough to support LNS.

\paragraph{Relaxing variable assignments.}
\label{par:m:search:relax}

A typical way to relax a given solution, is to assign some but
not all variables before a restart to a value from a previous
solution. This is supported by the \?relax()? function for
integer, Boolean, set, and float variables.

Assume that \?x? is an array of integer variables in the \?Model?
script sketched in \autoref{fig:m:search:restart:sketch}. Then,
the following \?next()? function:
\begin{code}
void next(const Model& b) {
  relax(*this, x, b.x, r, 0.7);    
}
\end{code}
relaxes each variable in \?x? with a probability of $0.7$
(or, with other words: each variable in \?x? would be assigned
the value from \?b.x? with a probability of $0.3$). The random
numbers are drawn from the random number generator~\?r?.

The \?relax()? function makes sure that at least one of the
variables in~\?x? remains unassigned (if needed, the variable to
remain unassigned is determined uniformly randomly).

For an example using LNS and the \?relax()? function please
consult \gecoderef[example]{photo}.

\section{Portfolio search}
\label{sec:m:search:portfolio}

The idea of portfolio search is to run several copies, where each
copy is called an \emph{asset} or a \emph{slave}, of the same
problem independently where each copy typically uses a different
branching heuristic (the copies might of course also differ in
how the same problem is modeled). The goal is to increase the
likelihood of finding a solution to the problem quickly and hence
to increase search robustness.  

Portfolio search in Gecode is provided as a meta search engine,
for the general idea of a meta search engine, please consult
\autoref{sec:m:search:restart:meta}. For more information on
portfolios in constraint programming, see~\cite{portfolios}.

\subsection{Simple portfolio search as a meta search engine}
\label{sec:m:search:portfolio:meta}

Portfolio search is, like restart-based search, implemented as a
meta search engine. The meta engine creates one slave search engine per
asset of the portfolio and coordinates their execution. 
The portfolio search engine has two interfaces, a simple one that
is very similar to the interfaces of non-meta search engines and
of restart-based search engines, and a second interface that is
considerably more powerful in that it can mix different types of
search engines in one portfolio. The advanced interface is
described in \autoref{sec:m:search:portfolio:arbitrary}.

The key parameter for portfolio search is the number of
assets. For example, a portfolio engine with four assets can be
created by:
\begin{code}
Search::Options o;
o.assets = 4;
PBS<Script,DFS> e(s,o);
\end{code}
Here, for each asset an engine of type \?DFS? is created for a
clone of the master space \?s?. 

Before the clones are created, the \?master()? member function as
implemented by the 
\?Script? class is called. On each clone, the \?slave()? function
is called where the slave function is called with information
about the number of the asset (ranging from \?0? to \?3?, the
number of assets minus one). The following section explains the
details of how the master and the slaves are configured, whereas
\autoref{sec:m:search:portfolio:parallel} explains how assets of
a portfolio are executed sequentially or in parallel.

\subsection{Master and slave configuration}
\label{sec:m:search:portfolio:configure}

The \?master()? function provided by a script is called exactly
once on the master space from which clones are created for each
asset. The purpose of the \?master()? function can be to setup
certain aspects of a script specific to portfolio search.

The portfolio-specific part of the default \?master()? function
is as follows, the entire \?master()? function is shown in
\autoref{fig:m:search:restart:default}: 
\insertlitcode{default master and slave functions:portfolio search}
That is, by default all branchers contained in the master space
are deleted before the slave spaces are created, for more on
killing branchers see \autoref{sec:m:group:branch}. This provides
the opportunity to create branchers specific to each asset by the
\?slave()? function.

The default \?slave()? function does nothing, in order to be
meaningful for portfolio search a user needs to define
one. Assume that you have four different variants of your model,
each using a different brancher. Then the following \?slave()?
function creates branchers specific for each asset:
\begin{code}
virtual bool slave(const MetaInfo& mi) {
  if (mi.type() == MetaInfo::PORTFOLIO) {
    switch (mi.asset() & 3) {
    case 0: branch(...); break;
    case 1: branch(...); break;
    case 2: branch(...); break;
    case 3: branch(...); break;
  }
  return true;
}
\end{code}
where the function \?mi.asset()? returns the number of the asset
being created. Creating more than four asset for this
particular example seems to be not that
useful, but in \autoref{sec:m:search:portfolio:arbitrary} we are
going to discuss how different search engines can be run in one
portfolio. Here one could imagine a portfolio that includes an
engine running sequential search together with an engine that
runs exactly the same script, however with parallel search using
more than one thread.  Note that the return value of the
\?slave()? function has no meaning for portfolio search (but it
has for restart-based search).

For an example using several branchers using different random
seeds in a portfolio, see \gecoderef[example]{qcp}.

\tip{Kill your branchers, or maybe not$\ldots$}{
\label{tip:m:search:kill}%
Instead of killing your branchers in the master space of a
portfolio as shown above, a different option is to not post them
in the master space of a portfolio in the first place. Whether a
script should become the master of a portfolio is typically easy
to detect when using the options provided by the script
commandline driver. Here the number of assets can be queried by
the \?assets()? member function. If the value returned is larger
than~\?0?, the script will be run in a portfolio.  }

\subsection{Parallel and sequential portfolios}
\label{sec:m:search:portfolio:parallel}

Whether the assets in a portfolio are run in parallel or just
concurrently is controlled by the number of assets in relation to
the number of threads requested. The way how threads are
allocated to assets is \emph{conservative}: there
will be never more threads running than requested, possibly at
the expense of running fewer assets than requested.

\paragraph{Sequential portfolios.}

A sequential portfolio consisting of $n$ assets is executed in a
simple round-robin scheme: the first asset is given a certain slice,
measured in the number of failures encountered during search
for that asset. If a solution is found within this slice, the
portfolio search engine reports this solution (as a result of its
\?next()? function). If no solution is found, the portfolio
engine gives a slice to the second assets, and so on. If the
last asset exceeds its slice, search continues with the first
asset again.

The size of the slice can be controlled by the options passed to
the portfolio engine. For example,
\begin{code}
Search::Options o;
o.assets = 3;
o.slice  = 50;
PBS<Script,BAB> e(s,o);
\end{code}
creates a portfolio with three assets, where a slice is
$50$~failures. The default value for a slice is defined in the
namespace \gecoderef[namespace]{Search::Config}.

\paragraph{Parallel portfolios.}

If parallel execution is requested (the numbers of threads
requested is greater than one, see
\autoref{sec:m:search:options}), a parallel portfolio engine is
created where each asset is run in its own thread. For example,
\begin{code}
Search::Options o;
o.assets = 3; o.threads = 3;
PBS<Script,DFS> e(s,o);
\end{code}
will create three threads each running a (sequential) depth-first
search engine.

As mentioned before, threads are created conservatively. That is,
\begin{code}
Search::Options o;
o.assets = 4; o.threads = 2;
PBS<Script,DFS> e(s,o);
\end{code}
creates only two threads for two assets.

If more threads than assets are requested, the remaining
threads are passed on to the assets. For example, 
\begin{code}
Search::Options o;
o.assets = 2; o.threads = 4;
PBS<Script,DFS> e(s,o);
\end{code}
creates a portfolio with assets where each asset is a parallel
search engine using two threads. In more detail, requesting $n$
assets and $m$ threads and $m>n$, then for each asset
$\left\lfloor \frac{m}{n} \right\rfloor$ threads are requested.

\tip{Always use parallel portfolios}{ The only reasons for not
  using parallel portfolios is that the executing platform does
  not have threads (then a sequential instead of a parallel
  portfolio is chosen automatically anyway) or for debugging.
  Otherwise, an operating system scheduling several threads even
  on a single processing unit tends to be the better approach.  
}

\tip{Controlling portfolios from the commandline}{ 
  The commandline driver transparently supports portfolio search.
  Depending on which options are passed on the commandline,
  either a search engine or a portfolio engine is used for
  search. The number of assets (by \?-assets?), the size of a
  slice for a sequential portfolio (by \?-slice?), and the number
  of threads for a parallel portfolio (by \?-threads?) can be
  specified. See \autoref{sec:m:driver:options} for details.

}

\subsection{Mixed portfolios}
\label{sec:m:search:portfolio:arbitrary}

The interface discussed in the previous section creates only
assets where each asset runs the same search engine. This is
often not desirable. For example, a common strategy is to mix
assets using search with and without restarts.

Therefore a more expressive interface to portfolio search is
provided that is based on the idea of \emph{search engine
  builders} (SEBs). A search engine builder is defined by its \emph{type}
and is created using search options
as input (that is, each engine to be built can have its own
search options). Then the portfolio search engine creates an
engine as defined by the type and the options of all SEBs passed
as arguments. The type of a SEB can be either \?dfs? (depth-first
search), \?lds? (limited discrepancy search), \?bab? (branch-and-bound solution search for a best
solution), \?rbs? (restart-based search), or \?pbs? (portfolio
search). The types \?dfs?, \?lds?, and \?bab? are parametric with respect
to a script type (as the engines \?DFS?, \?LDS?, and \?BAB? are) and the
\?rbs? and \?pbs? types are parametric with respect to both the
script type and the engine type (as the meta engines \?RBS? and
\?PBS? are).

Consider the following example: we would like to create a
portfolio for the master space \?master? of type \?Script? which
consists of the following assets:
\begin{enumerate}
\item A depth-first search engine using two threads; and
\item Another depth-first search engine using a single thread; and
\item A restart-based meta engine using a depth-first engine with
  a single thread and a
  Luby cutoff sequence with scale factor \?10? (see
  \autoref{sec:m:search:restart:cutoff}).
\end{enumerate}
The portfolio engine should use one thread for each asset.

The respective portfolio engine can be created as follows:
\begin{code}
Search::Options s0, s1, s2;
s0.threads = 2;
s1.threads = 1;
s2.threads = 1;
s2.cutoff  = Search::Cutoff::luby(10);
Search::Options s;
s.threads = 3;
PBS<Script> e(master,
              SEBs({dfs<Script>(s0),
                    dfs<Script>(s1),
                    rbs<Script,DFS>(s2)}),
             s);
\end{code}
Note that the number of assets is defined by the number of SEBs
passed as argument and not by \?s.assets? as with the simpler
interface. Executing a function such as \?dfs()? in fact creates
a new SEB \?seb? that eventually must be deleted by 
\?delete seb?. When creating a portfolio engine from a SEB, the engine
takes care of deleting the SEB.

\paragraph{Best solution search.}

Whether a portfolio search engine created from SEBs performs best
solution search is determined by the SEBs. If the SEBs are
created by \?bab<Script>()?, \?rbs<Script,BAB>()?, or
\?pbs<Script,BAB>()? then the engine performs best solution
search. Mixing best solution search SEBs with non-best solution
search SEBs throws an exception of type
\gecoderef[class]{Search::MixedBest}. 

\tip{Mixing parallel and sequential portfolios}{
In case a really large number of assets \?n? is required but one
needs to keep the number of threads \?m? sufficiently small, one
can use SEBs to create a parallel portfolio search engine consisting of assets
which are sequential portfolios themselves. Let us assume in the
following for simplicity that \?n? is a multiple of \?m? and that
\?master? is the master space of type \?Script?.

Then the following code snippet creates a parallel portfolio containing
\?m? assets each being a sequential portfolio having
$\frac{\mathtt{n}}{\mathtt{m}}$ assets:
\begin{code}
SEBs sebs(m);
for (int i=0; i<m; i++) {
  Search::Options o;
  o.assets = n / m;
  sebs[i] = pbs<Script,DFS>(o);
}
Search::Options o;
o.threads = m;
PBS<Script> e(master, sebs, o);
\end{code}
}

\section{No-goods from restarts}
\label{sec:m:search:nogoods}

As discussed in \autoref{sec:m:search:restart}, the idea of using
restarts effectively is to restart with an improved problem with
the hope that search is capable of solving the improved problem.
No-goods are constraints that can be learned from the
configuration of a depth-first search engine after it has
stopped. The no-goods encode failures during search as
constraints: after restarting, propagation of the no-goods
ensures that decisions that lead to failure are avoided. Note
that no-goods are only available from the depth-first search
engines~\?DFS? and~\?BAB? but not from limited discrepancy
search~\?LDS?.

\begin{figure}
\centering
\psset{xunit=0.04,yunit=0.04,runit=0.04}
\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}{27.0}{n1222u}
   \DefineNode{240.0}{19.0}{n1222c}
   \DefineNode{208.0}{27.0}{n1221u}
   \DefineNode{208.0}{19.0}{n1221c}
  \DefineNode{160.0}{67.0}{n121u}
  \DefineNode{160.0}{57.0}{n121c}
   \DefineNode{176.0}{27.0}{n1212u}
   \DefineNode{176.0}{19.0}{n1212c}
   \DefineNode{144.0}{27.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}{27.0}{n1122u}
   \DefineNode{112.0}{19.0}{n1122c}
   \DefineFatLink{n112c}{n1122u}
   \DefineNode{80.0}{27.0}{n1121u}
   \DefineNode{80.0}{19.0}{n1121c}
   \DefineLink{n112c}{n1121u}
  \DefineFatLink{n11c}{n112u}
  \DefineNode{32.0}{67.0}{n111u}
  \DefineNode{32.0}{57.0}{n111c}
   \DefineNode{48.0}{27.0}{n1112u}
   \DefineNode{48.0}{19.0}{n1112c}
   \DefineLink{n111c}{n1112u}
   \DefineNode{16.0}{27.0}{n1111u}
   \DefineNode{16.0}{190}{n1111c}
   \DefineLink{n111c}{n1111u}
  \DefineLink{n11c}{n111u}
 \DefineFatLink{n1c}{n11u}
\ChoiceNode{128.0}{133.0}
 \ChoiceNode{64.0}{95.0}
  \ChoiceNode{96.0}{57.0}
%   \ChoiceNode{112.0}{19.0}
   \FailedNode{80.0}{19.0}
  \ChoiceNode{32.0}{57.0}
   \FailedNode{48.0}{19.0}
   \FailedNode{16.0}{19.0}
\rput(80,124){\makebox(0,0){\footnotesize$\strut \mathtt{x} \leq \mathtt 7$}}
\rput(30,80){\makebox(0,0){\footnotesize$\strut \mathtt{y} = \mathtt 0$}}
\rput(102,80){\makebox(0,0){\footnotesize$\strut \mathtt{y} \neq \mathtt 0$}}
\rput(70,38){\makebox(0,0){\footnotesize$\strut \mathtt{z} = \mathtt 3$}}
\rput(122,38){\makebox(0,0){\footnotesize$\strut \mathtt{z} \neq \mathtt 3$}}
\end{pspicture}
\caption{Search tree after cutoff $3$ has been reached}
\label{fig:m:search:nogoods}
\end{figure}

Consider the simple example depicted in
\autoref{fig:m:search:nogoods}. It shows a search tree that has
been explored by the restart-based search engine with a cutoff of
$3$~failures. The thick edges in the tree depict the path that is
stored by a search engine using depth-first search (such as
\gecoderef[class]{DFS} or \gecoderef[class]{BAB}).

What can be immediately derived from this configuration is that
the following two constraints (they correspond to conjunctions of
alternatives shown in \autoref{fig:m:search:nogoods}):
$$
(\mathtt{x}\leq\mathtt{7})\wedge(\mathtt{y}=\mathtt{0})
\qquad\text{and}\qquad
(\mathtt{x}\leq\mathtt{7})\wedge(\mathtt{y}\neq\mathtt{0})\wedge(\mathtt{z}=\mathtt{3})
$$
are \emph{no-goods}: they cannot be satisfied by any solution
of the problem (after all, search just proved that). The
alternatives in the conjunction are also known as \emph{no-good
  literals}.

When restarting search, the negation of the no-goods can be added
to the master space as constraints and can be propagated. That
is, the following constraints can be added:
$$
\neg\left((\mathtt{x}\leq\mathtt{7})\wedge(\mathtt{y}=\mathtt{0})\right)
\qquad\text{and}\qquad
\neg\left((\mathtt{x}\leq\mathtt{7})\wedge(\mathtt{y}\neq\mathtt{0})\wedge(\mathtt{z}=\mathtt{3})\right)
$$
or, equivalently, the constraints:
$$
\neg(\mathtt{x}\leq\mathtt{7})\vee\neg(\mathtt{y}=\mathtt{0})
\qquad\text{and}\qquad
\neg(\mathtt{x}\leq\mathtt{7})\vee\neg(\mathtt{y}\neq\mathtt{0})\vee\neg(\mathtt{z}=\mathtt{3})
$$

Now assume that when restarting, after some search the
constraint $\mathtt{x}\leq\mathtt{7}$ becomes subsumed. Then, it
can be propagated that $\mathtt{y}\neq\mathtt{0}$. With other
words, whenever $\mathtt{x}\leq\mathtt{7}$ holds, then also
$\mathtt{y}\neq\mathtt{0}$ holds. This explains (if you know
about resolution, you have figured out that one already anyway)
that it is equivalent to use the following two constraints:
$$
\neg(\mathtt{x}\leq\mathtt{7})\vee\neg(\mathtt{y}=\mathtt{0})
\qquad\text{and}\qquad
\neg(\mathtt{x}\leq\mathtt{7})\vee\neg(\mathtt{z}=\mathtt{3})
$$

No-goods from restarts in Gecode follow the idea
from~\cite{NogoodsRestarts}, however the implementation differs.
Moreover, the no-good literals used in Gecode can be arbitrary
constraints and hence generalize the ideas from~\cite{gnogoods}
and~\cite{NogoodsRestarts}. Also no-goods in Gecode support
choices of arbitrary arity and are not restricted to binary
choices. For more details, see \autoref{chap:b:advanced} and in
particular \autoref{sec:b:advanced:nogoods}.

\paragraph{Generating and posting no-goods.}

When the restart-based search engine reaches the current cutoff
limit or finds a solution it calls the \?master()? member
function as discussed in the previous section.

From the argument of class \gecoderef[class]{MetaInfo} that is passed to the \?master()? function a
no-good of class \gecoderef[class]{NoGoods} can be retrieved by
calling the \?nogoods()? function. A no-good It has really only
\?post()? as its single important member function. The following
\?master()? function posts all constraints corresponding to the
no-goods that can be derived from a restart (this is also the
default \?master()? function defined by the class
\gecoderef[class]{Space}, see also \autoref{sec:m:search:restart:configure}):
\begin{code}
virtual bool master(const MetaInfo& mi) {
  ...
  mi.nogoods().post(*this);
  ...
}
\end{code}

In order to post no-goods it must be enabled that a search engine
maintains its internal state such that no-goods can be extracted.
This is done by setting the no-goods depth limit (the member
\?nogoods_limit? of a search option of type \?unsigned int?) to a
value larger than zero. The value of \?nogoods_limit? describes
to which depth limit no-goods should be extracted from the path
of the search tree maintained by the search engine. For example,
the following code (it assumes that \?c? refers to a cutoff object):
\begin{code}
Search::Options o;
o.cutoff = c;
o.nogoods_limit = 128;
RBS<Script,DFS> e(s,o);
\end{code}
instructs the search engine to extract no-goods up to a depth
limit of~\?128?.

The larger the depth limit, the more no-goods can of course be
extracted. However, this comes at a cost:
\begin{itemize}
\item Gecode's search engines use an optimization that is called
  LAO (last alternative optimization, see also
  \autoref{sec:s:re:lao}). LAO saves space by avoiding to store
  choices on the search engine's stack when the last alternative
  of a choice is being explored. But no-goods can only be
  extracted if LAO is disabled as the last alternatives are
  required for the computation of no-goods. LAO is automatically
  disabled for the part of the search tree with a depth less than
  the no-goods depth limit. That is, an engine requires more
  memory during search with a larger depth limit. This can pose
  an issue for very deep search trees.
  
  What also becomes clear from this discussion is that the peak
  search depth reported by a search engine increases with
  an increased depth limit.
\item It is easy to see that no-goods get longer (with more
  literals) with increasing search tree depth. The larger a
  no-good gets, the less useful it gets: the likelihood that all
  literals but one are subsumed but not failed (which is required
  for propagation) decreases.
\item When the no-goods are posted, a single propagator for all
  no-goods is created. This propagator requires $O(n)$ memory for
  $n$ no-good literals. Hence, increasing the depth limit also
  increases the memory required by the propagator.
\end{itemize}

\tip{Controlling no-goods with the commandline
  driver}{
\label{tip:m:search:cmdnogoods}%
Whether no-goods are used and which no-goods depth
limit is used can also be controlled from the commandline via
the \?-nogoods? and \?-nogoods-limit? commandline options, see
\autoref{chap:m:driver}. 
}

\paragraph{No-goods from solutions restarts.}

The \?master()? function shown above posts no-goods even when the
restart meta search engine has found a solution. When the engine
continues this means that the same solution might not be found
again as it has been excluded by a no-good. The situation is even
slightly more complicated: the solution might not be excluded if
it has been found at a depth that exceeds the no-good depth
limit.

If no-goods should not be posted when a solution has been
found, the \?master()? function can be redefined as:
\begin{code}
virtual bool master(const MetaInfo& mi) {
  ...
  if (mi.solution() == 0)
    mi.nogoods().post(*this);
  ...
}
\end{code}


\paragraph{Limitations.}

Not all branchers support the generation of no-goods. In that
case the longest sequence of no-goods starting from the root of
the search tree up to the first choice that belongs to a brancher
that does not support no-goods is used.

All pre-defined branchers for integer, Boolean, and set variables
support no-goods unless user-defined commit functions are used
(see \autoref{sec:m:branch:userval}). Branchers for float
variables and branchers for executing code (see
\autoref{sec:m:branch:code}) do not support no-goods.

\paragraph{No-goods and parallel search.}

The reason why after a restart no-goods can be extracted is
because search computed the no-goods by exploring entire failed
subtrees during search. This might not be true during parallel
search. While parallel search engines also support the extraction
of no-goods, the number of no-goods that can be extracted tend to
be rather small.



\section{Tracing search}
\label{sec:m:search:trace}

The execution of search engines can be traced, where all
important events of a search engine can be recorded and processed
by a \emph{search tracer}. A search tracer is implemented by a
subclass of \gecoderef[class]{SearchTracer} where several virtual
member functions must be implemented that are called when a
corresponding event occurs:
\begin{itemize}
\item A single \emph{init-event} occurs when the initialization
  of a search engine together with all of its components such as
  sub-engines and workers is complete. See below for more
  details about sub-engines and workers.
\item A single \emph{done-event} occurs when all components
  (workers) of a search engine have been deleted.
\item Each time a new node of the search tree is created, a
  \emph{node-event} occurs that provides information about the
  newly created node and the edge leading to it (unless it is the
  root node).
\item Some search engines perform several \emph{rounds}: each
  time a new round starts, a \emph{round-event} occurs.
  Restart-based search (RBS) starts a new round by performing a
  restart (see \autoref{sec:m:search:restart}) and
  limited-discrepancy search (LDS) starts a new round for each
  probe with a different discrepancy.
\item Some search engines might skip edges, in these cases a
  \emph{skip-event} is generated. See below for more details.
\end{itemize}

\paragraph{Search tracers.}

\begin{figure}
\insertlitcode{example search tracer}
\caption{A simple tracer printing to \?std::cout?}
\label{fig:m:search:tracer}
\end{figure}

A simple search tracer printing information to \?std::cout? is
shown in \autoref{fig:m:search:tracer}. A similar search tracer
is defined by the class \gecoderef[class]{StdSearchTracer}.

As mentioned above, all events correspond to virtual member
functions that are called when an event occurs. The member
functions are executed in mutual exclusion as the events might
occur in parallel from search engines using multiple workers
(threads). 

\paragraph{Defining a search tracer.}

A search tracer can be defined as part of the search options (see
\autoref{sec:m:search:options}). For example, if \?t? is a search
tracer, then creating a depth-first search engine using the tracer
\?t? can be done as follows:
\begin{code}
Search::Options o;
o.tracer = t;
DFS<Script> e(s,o);
\end{code}

\paragraph{Init-event.}

After the search engine(s) have completed their initialization, the member
function \?init()? is called. The class
\gecoderef[class]{SearchTracer} provides member functions with
which the configuration of the search engine can be
inspected. Search engines are identified by engine identifiers of
type \?unsigned int?. 

The root engine has always the identifier \?0U?. Meta engines
such as restart-based search (RBS) and portfolio-based search
(PBS) have sub engines whereas non-meta engines have workers that
perform the actual exploration of the search tree. The following
code:
\insertlitcode{example search tracer:init}
lists all engines together with their engine identifiers starting
with the root engine (the member function \?engines()? returns the
number of engines). Information about an engine is provided by the
member function \?engine()? which takes an engine identifier and
returns a reference to an object of type
\gecoderef[class]{SearchTracer::EngineInfo} providing
information about an engine.

For simple engines (that is, non-meta engines) such as
depth-first (DFS), branch-and-bound (BAB), and
limited-discrepancy search (LDS), the following code prints
information about their workers:
\insertlitcode{example search tracer:init for engines}
An engine of type AOE (for any other engine) is an engine that
Gecode creates in certain situations if the root of the search
tree is already known to be failed.

For meta engines, the following code prints information about
their sub-engines:
\insertlitcode{example search tracer:init for meta engines}

For example, for a branch-and-bound engine with a single worker
(using a single thread), the \?init()? function prints:
\begin{cmd}
	0: BAB, workers: {0}
\end{cmd}

For a branch-and-bound engine with four workers (using four
threads), the \?init()? function prints:
\begin{cmd}
trace<Search>::init()
	0: DFS, workers: {0,1,2,3}
\end{cmd}

For a restart-based search engine using a depth-first engine with
a single worker (using a single thread), the \?init()? function
prints:
\begin{cmd}
trace<Search>::init()
	0: RBS, engines: {1}
	1: DFS, workers: {0}
\end{cmd}

For a portfolio-based search engines with two depth-first search
engines as assets using four threads, the \?init()? function prints:
\begin{cmd}
trace<Search>::init()
	0: PBS, engines: {1,2}
	1: DFS, workers: {0,1}
	2: DFS, workers: {2,3}
\end{cmd}
Note that assets can be also restart-based search engines.


\paragraph{Node-events.}

\begin{figure}
\insertlitcode{example search tracer:node}
\caption{Member function for node-events}
\label{fig:m:search:tracer:node}
\end{figure}


The virtual member function called for a node-event takes
information about an edge of type
\gecoderef[class]{SearchTracer::EdgeInfo} and a node of type
\gecoderef[class]{SearchTracer::NodeInfo} as input. The code
shown in \autoref{fig:m:search:tracer:node} prints the type of
the node. It then prints information about the worker identifier
(\?ni.wid()?) and node identifier (\?ni.nid()?). Both worker and
node identifiers are of type \?unsigned int?. Note that the edge
also has information about the parent node of the current node
and which worker created it. In case the edge does not exist
(that is, the test \?ei? is false), the node is in fact the root
node of the search tree. The string printed is the output printed
by the brancher corresponding to the edge (see
\autoref{sec:m:branch:print} for more information).

Note that the node identifiers are unique per worker. As the
number of workers is available with the \?workers()? member
function, the numbers can be made easily unique globally.

\paragraph{Round-events.}

A round-event is generated either before a restart by a
restart-based search engine or when a limited-discrepancy search
engine starts a new probe with an increased discrepancy. The
information passed to the \?round()? member function is the
engine identifier corresponding to the engine starting a new
round:
\insertlitcode{example search tracer:round}

Note that the node identifiers are not reset at a round-event.

\paragraph{Skip-events.}

A skip event occurs when a worker decides that a certain node
does not need to be explored. This can happen for
branch-and-bound search engines where an entire subtree is
pruned or for limited discrepancy search where a solution is
omitted as it had already been found during a previous probe with
a smaller discrepancy limit. The information provided to the
\?skip()? member function is of type
\gecoderef[class]{SearchTracer::EdgeInfo}:
\insertlitcode{example search tracer:skip}

\paragraph{Done-event.}

The done event is executed if all workers have terminated. Here
it just prints this fact:
\insertlitcode{example search tracer:done}

Note that, however that the tracer is not deleted after a done
event. This is the obligation of the user of the tracer.

\section{Using the CPProfiler}
\label{sec:m:search:cpprofiler}

The CPProfiler is a graphical tool for better understanding the
search space of a problem~\cite{cpprofiler}. It can be downloaded
from
\AURL{https://github.com/cp-profiler/cp-profiler}{\texttt{github.com/cp-profiler}}.

Gecode can connect to an already running instance of the
CPProfiler by means of creating a search tracer. The tracer then
sends all search trace information to the respective instance of
the CPProfiler, which then can use the trace information for
visualization and analysis.

A search tracer to connect to a running CPProfiler instance can
be created by creating an object of class
\gecoderef[class]{CPProfilerSearchTracer} as follows:
\begin{code}
auto t = new CPProfilerSearchTracer(id,name,port,gi);
\end{code}
where \?id? (an integer) defines the execution identifier to be
displayed by the CPProfiler, \?name? (a string of type
\?std::string?) defines the name displayed by the CPProfiler,
\?port? (an unsigned integer) defines the network port used by
the CPProfiler, and \?gi? is a pointer to an object of class
\gecoderef[class]{CPProfilerSearchTracer::GetInfo} for
information about a search tree to be displayed by the
CPProfiler. The arguments for \?port? and \?gi? are optional, the
default for \?port? is defined by
\?Search::Config::cpprofiler_port? (currently \?6565?) and the
default for \?gi? is \?nullptr?.

Note that commandline support for the CPProfiler is provided, see
\autoref{sec:m:driver:options}. There are options to specify the
execution identifier, the port, and whether default information
about nodes in the search tree should be transferred to the
CPProfiler.

An object that determines which information about a search tree
node should be displayed when the node is inspected in the
CPProfiler, can be defined by inheriting from the class
\gecoderef[class]{CPProfilerSearchTracer::GetInfo} and
defining the virtual member function:
\begin{code}
virtual std::string getInfo(const Space& home) const;
\end{code}
that must return an information string of type \?std::string?
for the search tree node \?home?.

\begin{litcode}{example search tracer}{schulte}
\begin{litblock}{anonymous}
#include <gecode/search.hh>

using namespace Gecode;
\end{litblock}
class SimpleSearchTracer : public SearchTracer {
protected:
  static const char* t2s(EngineType et)  {
    \begin{litblock}{anonymous}
    switch (et) {
    case EngineType::DFS: return "DFS";
    case EngineType::BAB: return "BAB";
    case EngineType::LDS: return "LDS";
    case EngineType::RBS: return "RBS";
    case EngineType::PBS: return "PBS";
    case EngineType::AOE: return "AOE";
    }
    \end{litblock}
  }
public:
  SimpleSearchTracer(void) {}
  \begin{litblock}{init}
  virtual void init(void) {
    std::cout << "trace<Search>::init()" << std::endl;
    for (unsigned int e=0U; e<engines(); e++) {
      std::cout << "\t" << e << ": " 
                << t2s(engine(e).type());
      if (engine(e).meta()) {
        \begin{litblock}{init for meta engines}
        std::cout << ", engines: {";
        for (unsigned int i=engine(e).efst(); i<engine(e).elst(); i++) {
          std::cout << i; if (i+1 < engine(e).elst()) std::cout << ",";
        }
        \end{litblock}
      } else {
        \begin{litblock}{init for engines}
        std::cout << ", workers: {";
        for (unsigned int i=engine(e).wfst(); i<engine(e).wlst(); i++) {
          std::cout << i; if (i+1 < engine(e).wlst()) std::cout << ",";
        }
        \end{litblock}
      }
      std::cout << "}" << std::endl;
    }
  }
  \end{litblock}
  \begin{litblock}{node}
  virtual void node(const EdgeInfo& ei, const NodeInfo& ni) {
    std::cout << "trace<Search>::node(";
    switch (ni.type()) {
    \begin{litblock}{anonymous}
    case NodeType::FAILED:
      std::cout << "FAILED";
      break;
    case NodeType::SOLVED:
      std::cout << "SOLVED";
      break;
    \end{litblock}
    case NodeType::BRANCH:
      std::cout << "BRANCH(" << ni.choice().alternatives() << ")";
      break;
    }
    std::cout << ',' << "w:" << ni.wid() << ','
              << "n:" << ni.nid() << ')';
    if (ei) {
      if (ei.wid() != ni.wid())
        std::cout << " [stolen from w:" << ei.wid() << "]";
      std::cout << std::endl << '\t' << ei.string()
                << std::endl;
    } else {
      std::cout << std::endl;
    }
  }
  \end{litblock}
  \begin{litblock}{round}
  virtual void round(unsigned int eid) {
    std::cout << "trace<Search>::round(e:" << eid << ")" << std::endl;
  }
  \end{litblock}
  \begin{litblock}{skip}
  virtual void skip(const EdgeInfo& ei) {
    std::cout << "trace<Search>Search::skip(w:" << ei.wid()
              << ",n:" << ei.nid()
              << ",a:" << ei.alternative() << ")" << std::endl;
  }
  \end{litblock}
  \begin{litblock}{done}
  virtual void done(void) {
    std::cout << "trace<Search>::done()" << std::endl;
  }
  \end{litblock}
  virtual ~SimpleSearchTracer(void) {}
};
\end{litcode}

\begin{litcode}[texonly]{default master and slave functions}
virtual bool Space::master(const MetaInfo& mi) {
  switch (mi.type()) {
  case MetaInfo::RESTART:
    \begin{litblock}{restart-based search}
    if (mi.last() != NULL)
      constrain(*mi.last());
    mi.nogoods().post(*this);
    return true;
    \end{litblock}
  case MetaInfo::PORTFOLIO:
    \begin{litblock}{portfolio search}
    BrancherGroup::all.kill(*this);
    break;
    \end{litblock}
  default:
    break;
  }
  return true;
}
virtual bool Space::slave(const MetaInfo& mi) {
  return true;
}
\end{litcode}