1.8. The content of the manual

The manual is divided in four parts:

• Part I: Basics: a gentle introduction to the basic working of the library.
• Part II: Customization: real problems need customized search algorithms and this is what the second part is all about. We explain the basic inner working of the solver and its customization.
• Part III: Routing: we provide a general routing solver on top of our Constraint Programming solver that can already solve numerous node and vehicle problems out of the box. Its rich API provides a good basis to develop specialized routing algorithms including for some arc routing problems.
• Part IV: Technicalities: we detail non-basic but useful techniques of the CP solver and its inner working.

The appendix consists of an index. You can access the index anytime by clicking on the two links at the right in the header and footer bars in the web version of this manual.

Each chapter in the three first parts is illustrated by one typical problem except the chapter Meta-heuristics: several previous problems where we try to solve previously seen problems.

Each problem is explained from scratch so you can follow even if you’ve never heard about them.

1.8.1. Part I: Basics

Chapter 2: First steps with or-tools: cryptarithmetic puzzles:

We start by helping you download and install the or-tools library. Be careful to know exactly what third-party libraries you want to use with or-tools. We then use the very basic functionalities of the CP solver. We’ll encounter the Solver class and use the integer variables IntVar. The model used in this chapter is very simple and we’ll add basic algebraic equalities with the help of MakeSum(), MakeProd(), MakeEquality() and AddConstraint(). The AllDifferent constraint will make its first apparence too. More importantly, we’ll use a DecisionBuilder to define the search phase and launch the search with NextSolution(). To conduct the search, we use SearchMonitors and collect solutions with SolutionCollectors and Assigments. Finally, we’ll say a few words about the way to pass read-only parameters to the solver and about the other available programming languages in or-tools (Python, Java and C#). Although this chapter is a gentle introduction to the basic use of the library, it also focuses on some basic but important manipulations needed to get things right. Don’t miss them!

Chapter 3: Using objectives in constraint programming: the Golomb Ruler Problem:

In this chapter, we not only look for a feasible solution but for an optimal solution, i.e. a solution that optimizes an objective function. To solve the Golomb Ruler Problem, we’ll try five different models and compare them two by two. To have an intuition of the models passed to the solver and the progress of the search, we show you how to inspect the model you constructed and how to collect some statistics about the search. Several flags are available to tune the search, collect statistics, etc. We present some of them and how to trigger them. To limit the search in some way, use SearchLimits. As SearchLimits use custom made functions or methods, this will be our first (but certainly not last) encounter with callbacks and functors. Two very useful techniques to tighten a model are introduced: adding better bounds and breaking symmetries. Finally, we explain how our CP solver optimizes while it basically “only” finds feasible solutions.

Chapter 4: Reification:

[TO BE WRITTEN]

1.8.2. Part II: Customization

Chapter 5: Defining search primitives: the n-Queens Problem:

The or-tools CP solver is quite flexible and comes with several tools (Decisions, DecisionBuilders, ...) that we call search primitives. Some are predefined and can be used right out of the box while others can be customized thanks to callbacks. You can also combine different search strategies. SearchMonitors allow you to guide the search thanks to callbacks. DecisionBuilders and Decisions define the search tree. We explain their mechanisms and how they are embedded in the main search algorithm of the CP solver. We also show where exactly in this main search algorithm most of the callbacks of the SearchMonitors are triggered. The presented algorithm is a simplified version of the real algorithm but you’ll get a pretty clear idea of the real algorithm. To better understand all these tools, we use the wonderful cpviz library to visualize the search tree and the variable propagations. The basic branching in the search tree is done by selecting variables, then selecting values these variables can or can not hold. We list the available branching strategies. Once you master all these basic search concepts, we show you how to customize them, i.e. how to create your own search primitives. This chapter is difficult but essential to understand the basic working of the CP solver. To reward your efforts and struggles to master this chapter, we end it with some cool stuff about how to break symmetries during the search (on the fly!) using SymmetryManagers and SymmetryBreakers.

Chapter 6: Local Search: the Job-Shop Problem:

Scheduling is one of the fields where constraint programming has been applied with great success. It is thus not surprising that the CP community has developed specific tools to solve scheduling problems. In this chapter, we introduce the ones that have been implemented in or-tools. To address difficult problems - like the job-shop problem - we make use of (meta-)heuristics. Local search is a general framework to seek a better solution starting from an initial solution. We explain what local search is and show how it’s done in or-tools. We present a simplified version of our local search algorithm but, again, you’ll have a pretty clear idea of the real algorithm and where exactly the callbacks of the SearchMonitors are triggered. LocalSearchOperators are the main actors: they are in charge to find candidate solutions given an initial solution. We show how to construct your own customized LocalSearchOperators and present the most interesting ones that are already implemented in or-tools. The CP solver verifies the feasibility of all constructed candidate solutions but if you know how to quickly disregard some candidate solutions (because you know they are infeasible or not desirable), you can help the CP solver by creating your own LocalSearchFilters. We’ll show you how and also present a list of available LocalSearchFilers that you might want to use.

Chapter 7: Meta-heuristics: several previous problems:

[TO BE WRITTEN]

Chapter 8: Custom constraints: the alldifferent_except_0 constraint:

[TO BE WRITTEN]

1.8.3. Part III: Routing

Chapter 9: Travelling Salesman Problems with constraints: the TSP with time windows:

This chapter is our first encounter with the Routing Library (RL) and what better problem than the Travelling Salesman Problem (TSP) to introduce it? We overview the library and the problems it can solve. We then delve into the specifics of the mathematical model we use to represent all these problems: first the variables, then the constraints. In particular, we’ll see the auxiliary graph that we use to model multiple depots. Every calculation is done on the auxiliary graph and you just have to translate the solutions back to your original nodes. We show you how to switch between our auxiliary graph and your original graph. To solve the Routing Problems, we use Local Search. Several specialized PathOperators are implemented and we show you how to create your customized versions. We try to solve the TSPLIB instances. You can add “quantities” along the arcs. This is done by adding Dimensions. The quantities can represent goods, people, volumes, ... but also distances and times. We model time windows with Dimensions for instance.

Chapter 10: Vehicule Routing Problems with constraints: the capacitated vehicle routing problem:

[TO BE WRITTEN]

1.8.4. Part IV: Technicalities

Chapter 11: Utilities:

This chapter is about supplementary tools you can use to enhance your work-flow with the or-tools library. We’ll cover:

• Logging:
• Asserting:
• Timing:
• Profiling:
• Debugging:
• Serializing:
• Visualizing:
• Randomizing:
• Using FlatZinc:

Chapter 12: Modeling tricks:

[TO BE WRITTEN]

Chapter 13: Under the hood:

[TO BE WRITTEN]

1.8.5. Appendices

In this last part of the manual, you’ll find an index.