7.1. Search limits and SearchLimits

1. C++ code:
   1. limits.h

To control the search, we also need a way to stop the search when some criteria are met. By default, our meta-heuristics never stop. This can easily be done with the help of a SearchLimit.

Warning

Our meta-heuristic search never stops. Add a SearchLimit to limit the search.

We will use the SearchLimits defined in limits.h throughout the whole chapter.

7.1.1. An example of a custom Searchlimit: NoImprovementLimit

We have already met SearchLimits in the sub-section SearchLimits and even used callbacks to define our SearchLimit in the sub-section The initial solution where we disregarded a given time limit if the search produced enough solutions between checks. We go a little bit more into details here.

It is not always possible to create a CustomLimit with an appropriate callback to meet a desired end search criteria. For instance, let’s say we would like to stop the search after a certain number of solutions have been found but without any improvements in the objective value. To do so, we need to have access to the objective value every time a new solution has been found. The Solver class doesn’t provide any method to access its current objective value. What we need is a custom SearchMonitor. Or more precisely, a custom SearchLimit.

SearchLimits are specialized SearchMonitors to end a Search. The SearchLimit class itself is a pure virtual base class for all SearchLimits. Its only constructor is:

explicit SearchLimit(Solver* const s);

Several methods must be defined in order to have a valid SearchLimit:

• bool Check(): check the status of the limit. A return value of true indicates that we have indeed crossed the limit. In that case, this method will not be called again and the remaining search will be discarded. This method is called in the BeginNextDecision() and RefuteDecision() callbacks.
• void Init(): called when the search limit is initialized in the EnterSearch() callback.
• void Copy(const SearchLimit* const limit): copies a limit. Warning: this leads to a direct (no check) down-casting of limit, so one needs to be sure both SearchLimits are of the same type.
• SearchLimit* MakeClone() const: allocates a clone of the limit.

OK, let’s get our hands dirty and code! You can find the code in the file limits.h.

Our class inherits publicly from SearchLimit:

class NoImprovementLimit : public SearchLimit {
  ...
};

We’ll consider both minimizing and maximazing depending on a bool in the constructor[1]:

class NoImprovementLimit : public SearchLimit {
public:
  NoImprovementLimit(Solver * const solver,
                     IntVar * const objective_var,
                     const int solution_nbr_tolerance,
                     const bool minimize = true);

solution_nbr_tolerance represents the number of solutions allowed without any improvements in the objective value. We keep a reference to the objective variable given by the objective_var argument.

To be able to retrieve the current solution objective value, we keep a copy of the current solution in a prototype_ variable:

std::unique_ptr<Assignment> prototype_ = new Assignment(solver);
prototype_->AddObjective(objective_var);

and we add the objective variable to it.

The most interesting method is not the Check() method that only returns a Boolean limit_reached_ but the AtSolution() method that computes this Boolean. Remember that the AtSolution() method is called whenever a new solution has been found. Here is the code:

virtual bool AtSolution() {
  ++nbr_solutions_with_no_better_obj_;

  prototype_->Store();

  const IntVar* objective = prototype_->Objective();

  if (minimize_ && objective->Min() < best_result_) {
    best_result_ = objective->Min();
    nbr_solutions_with_no_better_obj_ = 0;
  } else if (!minimize_ && objective->Max() > best_result_) {
    best_result_ = objective->Max();
    nbr_solutions_with_no_better_obj_ = 0;
  }

  if (nbr_solutions_with_no_better_obj_ > solution_nbr_tolerance_) {
    limit_reached_ = true;
  }
  return true;
}

For each solution, we increase the counter nbr_solutions_with_no_better_obj_ at line 2. We reset this counter to 0 in lines 8 to 14 if the current solution has a better objective value than the best known so far. To do this we store the current solution in our prototype_ Assignment on line 4.

We will use the NoImprovementLimit class in the next sections. Beware of the warning formulated in the section Composite objects.

7.1.2. A callback to catch the CTRL-C interrupt

Warning

The CatchCTRLBreakLimit class is only available in linux for the moment.

CTRL-C (the Ctrl key in combination with the C key) sends the SIGINT signal which will interrupt the application except if we catch this signal and exit peacefully. Because meta-heuristics can take a long time before even producing a solution or find a better solution, we have implemented a CatchCTRLBreakLimit class that allows the CP Solver to fail peacefully instead of abruptly interrupting the search process. The code involved is beyond the scope of this manual (if you are curious, have a look at the file limits.h). As usual, we have defined a factory method:

SearchLimit * MakeCatchCTRLBreakLimit(Solver * const solver);

that you can use to create a new CatchCTRLBreakLimit object.

Be aware that in linux, the SIGINT signal is caught if you include limits.h and that if you don’t use this SearchLimit you will not be able to stop your current search by pressing CRTL-C.

Warning

In linux, don’t include the file limits.h if you don’t use CatchCTRLBreakLimit and plan to press CRTL-C to stop the solving process.

Footnote

[1]	We don’t follow the code convention of using a maximize bool but the fully attentive reader noticed it, didn’t she?