5.9. Summary

This chapter is the first one of the second part of this manual and we have switched into high gear. The first part was about the basics of the solver, now we entered the core part: how to customize the CP solver to our needs. This cannot be done without a basic understanding of the solver and this chapter provided you with enough insights into the main solving algorithm. In particular, we saw some search primitives and how to customize them. We also saw how they are called in the main search algorithm.

Our illustrative problem for this chapter is the n-Queens Problem. We have only proposed a basic model as our focus was to customize search primitives, not devise a good model. To better compare search strategies, we saw how to use the cpviz library to visualize the search tree and the propagations of the constraints.

Search primitives are blocks used by the CP solver to construct the search tree and conduct the search. Among them, we saw in details:

  • SearchMonitors to control and monitor the search;
  • DecisionBuilders and Decisions to create the search tree.

To customize search primitives, you can, in order of complexity:

  • combine existing ones;
  • redefine callbacks;
  • implement your own version of some search primitive classes;
  • mix all of the above.

For each case, we have seen an example.

Finally, we continued our discussion of symmetries in the search tree and saw a new way to skip them on the fly with the help of SymmetryBreakers. By devising better search primitives and algorithms, we went from a few seconds to only a few milli-seconds to solve the n-Queens Problem for n = 7..12.

You might be curious, as we are, to combine our best search strategy and the SymmetryBreakers. This is done in the next sub-section.

5.9.1. Combining both approaches

  1. C++ code:
    1. nqueens8.cc

We have improved our search strategy and search time little by little. We started by a simple approach (file nqueens1.cc and algorithm A in the next table) and ended up with our best algorithm discussed in section Second try: dynamic variable selection (and define our own DecisionBuilder class). We then saw a completely different approach and used SymmetryBreakers with a default search algorithm (file nqueens7.cc and algorithm B in the next table). What about combining both approaches (file nqueens8.cc and algorithm C in the next table)?

n Statistics Algorithm A Algorithm B Algorithm C
7 Failures 92 24 24
Branches 82 44 41
8 Failures 328 71 54
Branches 654 139 100
9 Failures 1216 272 186
Branches 2430 541 367
10 Failures 4500 1074 642
Branches 8998 2142 1275
11 Failures 17847 4845 2465
Branches 35692 9686 4924
12 Failures 86102 23159 11770
Branches 172202 46312 23511

To give you an idea of the progress we made, the following table gives you the time needed to solve the 14-Queens Problem with the three algorithms:

Algorithms Time (s)
A 21,582
B 6,096
C 2.945

Combining both approaches did result in a clear cut gain but it is not always the case. Sometimes, two good ideas don’t mix that well.

Google or-tools
open source library

User's Manual

Google search

Search:

Welcome

Tutorial examples

Current chapter

5. Defining search primitives: the n-Queens Problem

Previous section

5.8. Breaking symmetries with SymmetryBreakers

Next section

6. Local Search: the Job-Shop Problem

Current section