6.9. Summary

Again, another dense chapter. In this chapter, we saw basically 4 things:

  • what Local Search is and how it behaves practically;
  • how Local Search is implemented in or-tools;
  • what kind of customized classes are used to tackle Scheduling Problems in or-tools;
  • the Job-Shop Problem as an illustrative example.

More precisely, we saw a description of the Job-Shop Problem and how to model it with the disjunctive model. This allowed us to introduce the IntervalVars and SequenceVars variables that are typically used in Scheduling. We also combined two DecisionBuilders in a top-down fashion. After describing general features of Local Search, we have seen its general implementation in or-tools and in particular where the callbacks of the SearchMonitors are called in the Local Search algorithm. Finally, we saw how by implementing LocalSearchOperators and LocalSearchFilters we can define our neighborhoods for the Local Search algorithm.

There are some interesting examples in the directory examples/cpp and the reader is encouraged to read them carefully.

Google or-tools
open source library

User's Manual

Google search



Tutorial examples

Current chapter

6. Local Search: the Job-Shop Problem

Previous section

6.8. Filtering

Next section

7. Meta-heuristics: several previous problems