41. Getting started

This chapters presents how to implement simple search engines. The focus is on understanding the basic operations available on spaces to implement search engines. None of the engines presented here is realistic as they do not use recomputation. The full picture is developed in Recomputation and An example engine.

Overview. Space-based search sets the stage by explaining space operations for programming search engines. A depth-first search engine that makes the simplifying assumption that all choices explored during search are binary is shown in Binary depth-first search. The next section, Depth-first search, shows depth-first search for choices with an arbitrary number of alternatives. How best solution search can be programmed from spaces is exemplified by a simple branch-and-bound search engine in Branch-and-bound search.

41.1. Space-based search

Search engines compute with spaces: a space implements a constraint model and exploration of its search space is implemented by operation on spaces. The operations on spaces include: computing the status of a space by the status() function, creating a clone of a space by the clone() function, and committing to an alternative of a choice by the commit() function. To commit to an alternative, a space provides the function choice() that returns a choice defining how the space can be committed to one of its alternatives. Another operation required to program exploration is the function alternatives() defined by a choice that returns the number of alternatives of a choice.

Spaces implement also a constrain() function for best solution search. Its discussion is postponed to Branch-and-bound search.

This section reviews the above operations from the perspective of a search engine, the perspective how branchers are controlled by these operations is detailed in What to implement?. Gecode’s architecture for search is designed such that a search engine does not need to know which problem is being solved by a search engine: any problem implemented with spaces can be solved by a search engine, and different search engines can be used for solving the same problem. The basic idea of this factorization is due to [47].

Note that here and in the following, spaces and choices are always assumed to be pointers to the respective objects. Pointers are necessary as search engines dynamically create and delete spaces and choices.

Status computation. A search engine needs to decide how to proceed during search by computing the status of a space by invoking its status() function. The status() function performs constraint propagation (see Constraint propagation in a nutshell) followed by determining the next brancher for branching, if possible (see What to implement?). Depending on the result of constraint propagation and brancher selection, the status() function returns one of the following values of the type SpaceStatus (see TaskSearch):

• SS_FAILED: the space is failed. The search engine needs to backtrack and revisit other spaces encountered during exploration.

  An important responsibility of a search engine is to perform resource management for spaces. In the case of failure, the typical action is to delete the failed space.

• SS_SOLVED: the space is solved. Hence the search engine has found a solution and typically returns the solution.

  For most engines, the responsibility for deleting a solution lies with the user of a search engine.

  Following the discussion in Garbage collection of branchers., calling the choice() function of a solved space performs garbage collection for branchers that are not any longer needed. Binary depth-first search shows an example search engine that performs garbage collection on solved spaces.

• SS_BRANCH: the space requires branching for search to proceed.

  The first step in branching is to compute a choice by calling the choice() function of a space. The returned choice can be used for committing to alternatives of a space. In particular, a choice returned by the choice() function provides a function alternatives() that returns how many alternatives the choice has.

  The pointer to the choice that is returned by the choice() function of a space s is const. That is, the following code:

  const Choice* ch = s->choice();
  

  gets a const pointer to a choice (the choice cannot be modified). Note that it is the obligation of the search engine to eventually delete the choice by

  delete ch;
  

Cloning spaces. A central requirement for a search engine is that it can return to a previous state: as spaces constitute the nodes of the search tree, a previous state is nothing but a space again. 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 modify spaces, provisions must be taken that search can actually return to the clone of a previous space. This is provided by the clone() function of a space: it returns a clone of a space. This clone can be stored by a search engine such that the engine can return to a previous state. Spaces that are clones of each other are equivalent: space operations will have exactly the same effect on equivalent spaces.

The clone() function of a space can only be called on a space that is stable and not failed (that is, the status() function on a space must return SS_SOLVED or SS_BRANCH). Otherwise, Gecode throws an exception of type SpaceNotStable if the space is not stable and of type SpaceFailed if the space is failed.

Committing to alternatives. Given a space s and a choice ch (assumed to be a const pointer), the space s can be committed to the i-th alternative by calling the commit() function of a space as follows:

s->commit(*ch,i);

The choice ch must be compatible with the space s. Before defining when a choice is compatible with a space, let us look at two examples.

Suppose a search engine has invoked status() on a space s which returned SS_BRANCH. The next step is to obtain a choice ch for s and a clone c of s by:

const Choice* ch = s->choice();
Space* c = s->clone();

Further assume that the choice is binary (that is, ch->alternatives() returns 2). A search engine can explore both alternatives (typically, the search engine performs the commit() for the second [1] alternative much later) by:

s->commit(*ch,0);
c->commit(*ch,1);

That is, a choice ch is compatible with the space s from which it has been computed and with the clone c of s.

Tip 41.1 (Printing information about alternatives.).

Sometimes it might be helpful to print what the commit() function does. For this reason, a space provides a print() function that compared to commit() takes an output stream of type std::ostream& as additional argument.

For example, the following

s->print(*ch,0,std::out); 
std::out << std::endl;
c->print(*ch,1,std::out);
std::out << std::endl;

prints information about what the commit() function in the above example actually does.

◄

A search engine for best solution search performs slightly different operations. Let us follow an example scenario. First, the search engine starts exploring the first alternative by:

s->commit(*ch,0);

Then search continues with s. Let us assume that the search engine finds a better solution when continuing search from s. Hence, the search engine adds additional constraints to the clone c to make sure that exploration from c yields a better solution (the constraints are added by calling the constrain() function of a space, see Branch-and-bound search). And only then the search engine commits the clone c to the second alternative by:

c->commit(*ch,1);

That is, a choice ch is also compatible with the clone c of s, even though additional constraints have been added to c after it had been created by cloning.

In fact, the relation that a choice is compatible with a space is quite liberal. The full notion of compatibility is needed for recomputation and is discussed in Choice compatibility.

Parallel search. Gecode’s kernel is constructed that clones of spaces can be used in different threads. Howeever, no two threads can simultaneously perform operations on the same space.

Statistics support. The three main space operations (status(), clone(), and commit()) provide support for execution statistics. For example, statistics from the execution of status() on a space s can be collected in the object stat by:

StatusStatistics stat;
s->status(stat);

The classes for the statistics correspond to the space operations:

status()	StatusStatistics
clone()	CloneStatistics
commit()	CommitStatistics

Statistics information is collected by accumulation. That is, for spaces s1 and s2, the following:

StatusStatistics stat;
s1->status(stat);
s2->status(stat);

collects the combined statistics of performing status() on s1 and s2.

The statistics classes also implement addition operators. The following is equivalent to the previous example:

StatusStatistics stat;
{
  StatusStatistics a, b;
  s1->status(a);
  s2->status(b);
  stat = a + b;
}

which is also equivalent to:

StatusStatistics stat;
{
  StatusStatistics a, b;
  s1->status(a); stat += a;
  s2->status(b); stat += b;
}

41.2. Binary depth-first search

This section shows a simple search engine that performs left-most depth-first search. It makes the additional simplification that all choices are binary, the general case is discussed in Depth-first search.

Program 41.1 Depth-first search for binary choices

...
Space* dfs(Space* s) {
  switch (s->status()) {
  case SS_FAILED:
    // [dfs binary:failed]
  case SS_SOLVED:
    // [dfs binary:solved]
  case SS_BRANCH:
    { 
      // [dfs binary:prepare for branching]
      // [dfs binary:first alternative]
      // [dfs binary:second alternative]
    }
  }
}

Download: dfs-binary.cpp

Program 41.1 shows the definition of the function dfs() that implements the search engine. It takes a space as input and returns a space as a solution or NULL if no solution exists. The resource policy it implements is that it takes responsibility for deleting the space s with which dfs() is called initially. The solution it returns must eventually be deleted by the caller of dfs() (if the initial space happens to be a solution, the engine does not delete it). The search engine starts by executing the status() function on s and hence triggers propagation and possibly brancher selection.

In this chapter and in Recomputation we use recursive functions to implement exploration during search. This is rather inefficient with respect to both runtime and space in C++. A more realistic implementation uses an explicit stack, for an example see An example engine.

Failure and solutions. In case the space s is failed, the search engine deletes the space and returns NULL as specified:

failed ≡

    delete s; return NULL;

If the space s is solved, the search engine triggers garbage collection of remaining branchers as mentioned in Space-based search and returns the solution:

solved ≡

    (void) s->choice(); return s;

Branching. Following the discussion in Space-based search, before the search engine can start committing to alternatives and perform recursive search, it needs to compute a choice for committing and a clone for backtracking:

prepare for branching ≡

      const Choice* ch = s->choice();
      Space* c = s->clone();

The search engine tries the first alternative by committing the space s to it and continues search recursively:

first alternative ≡

      s->commit(*ch,0);
      if (Space* t = dfs(s)) {
        delete ch; delete c;
        return t;
      }

If the recursive call to dfs() returns a solution (that is, t is different from NULL and hence the condition of the if statement is true) the engine deletes both choice and clone and returns the solution t.

Saving memory. It is absolutely essential that the search engine uses the original space s for further exploration and stores the clone c for backtracking. Exchanging the roles of s and c by:

c->commit(*ch,0);
if (Space* t = dfs(c)) {
  delete ch; delete s;
  return t;
}

would also find the same solution. However, this search engine would most likely need more memory. Spaces that already have been used for propagation (such as s) typically require more memory than a pristine clone (see also Managing propagator state). Hence, any search engine should maintain the invariant that it stores pristine clones for backtracking, but never spaces that have been used for propagation.

If the first alternative did not lead to a solution, search commits the clone c to the second alternative, deletes the now unneeded choice, and recursively continues search:

second alternative ≡

      c->commit(*ch,1);
      delete ch;
      return dfs(c);

41.3. Depth-first search

This section demonstrates how left-most depth-first search with choices having an arbitrary number of alternatives can be implemented. By this, the section presents the general version of the search engine from Binary depth-first search.

Program 41.2 Depth-first search

...
Space* dfs(Space* s) {
  switch (s->status()) {
  ...
  case SS_BRANCH:
    {
      const Choice* ch = s->choice();
      unsigned int n = ch->alternatives();
      // [dfs:single alternative]
      // [dfs:several alternatives]
    }
    break;
  }
}

Download: dfs.cpp

Program 41.2 outlines the depth-first search engine, where computing the space status and handling failed and solved spaces is the same as in Binary depth-first search. If the search engine needs to branch, it computes the choice ch for branching and the number of alternatives n.

Choices can actually have a single alternative, for example for assigning variables (see Assigning integer, Boolean, set, and float variables). This special case should be optimized as in fact no clone needs to be stored for backtracking. Hence:

single alternative ≡

      if (n == 1) {
        s->commit(*ch,0);
        delete ch;
        return dfs(s);
      }

If the choice has more than a single alternative, a clone c is created and a loop iterates over all alternatives:

several alternatives ≡

      Space* c = s->clone();
      for (unsigned int a=0; a<n; a++) {
        // [dfs:space to explore]
        // [dfs:recursive search]
      }
      delete ch;
      return NULL;

If the loop terminates, no solution has been found and hence NULL is returned.

When trying the a-th alternative, the search engine determines which space e to choose to continue exploration:

space to explore ≡

        Space* e;
        if (a == 0)
          e = s;
        else if (a == n-1)
          e = c;
        else
          e = c->clone();

The choice of e avoids the creation of an unnecessary clone for the last alternative.

After committing the space to explore the a-th alternative, search continues recursively. If a solution t has been found, it is returned after the search engine deletes the clone (unless it has already been used for the last alternative) and the choice:

recursive search ≡

        e->commit(*ch,a);
        if (Space* t = dfs(e)) {
          if (a != n-1) delete c;
          delete ch;
          return t;
        }

41.4. Branch-and-bound search

This section shows how to program a best solution search engine. It chooses branch-and-bound search as an example where choices are again assumed to binary for simplicity. The non-binary case can be programmed similar to Depth-first search.

Constraining spaces. A space to be used for best solution search must implement a constrain() function as discussed in Best solution search. The key aspect of a best solution search engine is that it must be able to add constraints to a space such that the space can only lead to solutions that are better than a previously found solution.

Assume that a best solution search engine has found a so-far best solution b (a space). Then, by

s->constrain(*b);

the engine can add constraints to the space s that guarantee that only solutions that are better than b are found by search starting from s.

The Space class actually already implements a constrain() function which does nothing. That is, a space to be used with a best solution search engine must redefine the default constrain() function by inheritance.

Search engine.

Program 41.3 Branch-and-bound search

...
void bab(Space* s, unsigned int& n, Space*& b) {
  switch (s->status()) {
  ...
  case SS_SOLVED:
    // [bab:solved]
    break;
  case SS_BRANCH:
    {
      const Choice* ch = s->choice();
      Space* c = s->clone();
      // [bab:remember number of solutions]
      // [bab:explore first alternative]
      // [bab:constrain clone]
      // [bab:explore second alternative]
      delete ch;
    }
    break;
  }
}

Space* bab(Space* s) {
  unsigned int n = 0; Space* b = NULL;
  bab(s,n,b);
  return b;
}

Download: bab.cpp

The basic structure of the branch-and-bound search engine is shown in Program 41.3. A user of the search engine calls the function bab() taking a single space as argument. The function either returns the best solution or NULL if no solution exists.

The function bab() that takes three arguments implements the actual exploration. The space s is the space that is currently being explored, the unsigned integer n counts the number of solutions found so far, and the space b is the so-far best solution. Note that both n and b are passed by reference and hence the variables are shared between all recursive invocations of the search engine. The number of solutions n is used for deciding when a space must be constrained to yield better solutions.

The single argument bab() function initializes n and b to capture that no solution has been found yet. After executing the bab() search engine, b refers to the best solution (or is NULL) and is returned after garbage collecting remaining branchers.

Finding a solution. The search engine is constructed such that every solution found is better than the previous. Hence, when a solution is found, the previous so-far best solution is deleted [2] and is updated to the newly found solution. As a new solution is found also the number of solutions n is incremented:

solved ≡

    n++;
    delete b; 
    (void) s->choice(); b = s->clone(); delete s;

The search engine first garbage collects branchers (by calling choice()) and remembers a pristine clone of the solution found.

Branching. Exploring the first alternative differs considerably from exploring the second alternative of a choice. When exploring the first alternative, it is guaranteed that the current space s can only lead to better solutions. If a solution is found by exploring the first alternative (or if several solutions are found), then a constraint must be added to the clone c such that only better solutions can be found when continuing exploration with c for the second alternative. To detect whether a solution has been found when exploring the first alternative, the search engine remembers the number of solutions m before starting to explore the first alternative as follows:

remember number of solutions ≡

      unsigned int m=n;

Exploring the first alternative is as to be expected:

explore first alternative ≡

      s->commit(*ch,0);
      bab(s,n,b);

Before exploring the second alternative, the engine checks whether new solutions have been found during the exploration of the first alternative. If new solutions have been found, the clone c is constrained to yield better solutions:

constrain clone ≡

      if (n > m)
        c->constrain(*b);

The second alternative is explored as follows:

explore second alternative ≡

      c->commit(*ch,1);
      bab(c,n,b);

Note that execution of the constrain() function might constrain some variables and possibly add new propagators (even new variables). Even though c might not be any longer an identical clone of s, the choice ch is still compatible with the space c (see Space-based search).

[1]

Even though the alternatives are numbered starting from 0 we refer to the alternative with number 0 as the first alternative and the alternative with number 1 as the second alternative.

[2]

Actually, b is NULL for the first solution found. However, it is legal in C++ to invoke the delete operator on a NULL-pointer.