Using and Understanding OR-Tools' CP-SAT: A Primer and Cheat Sheet

By Dominik Krupke, TU Braunschweig

Many combinatorially difficult optimization problems can, despite their proven theoretical hardness, be solved reasonably well in practice. The most successful approach is to use Mixed Integer Linear Programming (MIP) to model the problem and then use a solver to find a solution. The most successful solvers for MIPs are Gurobi and CPLEX, which are both commercial and expensive (though, free for academics). There are also some open source solvers, but they are often not as powerful as the commercial ones. However, even when investing in such a solver, the underlying techniques (Branch and Bound & Cut on Linear Relaxations) struggle with some optimization problems, especially if the problem contains a lot of logical constraints that a solution has to satisfy. In this case, the Constraint Programming (CP) approach may be more successful. For Constraint Programming, there are many open source solvers, but they usually do not scale as well as MIP-solvers and are worse in optimizing objective functions. While MIP-solvers are frequently able to optimize problems with hundreds of thousands of variables and constraints, the classical CP-solvers often struggle with problems with more than a few thousand variables and constraints. However, the relatively new CP-SAT of Google's OR-Tools suite shows to overcome many of the weaknesses and provides a viable alternative to MIP-solvers, being competitive for many problems and sometimes even superior.

This unofficial primer shall help you use and understand this powerful tool, especially if you are coming from the Mixed Integer Linear Programming -community, as it may prove useful in cases where Branch and Bound performs poorly.

If you are relatively new to combinatorial optimization, I suggest you to read the relatively short book In Pursuit of the Traveling Salesman by Bill Cook first. It tells you a lot about the history and techniques to deal with combinatorial optimization problems, on the example of the famous Traveling Salesman Problem. The Traveling Salesman Problem seems to be intractable already for small instances, but it is actually possible to solve instances with thousands of cities in practice. It is a very light read and you can skip the more technical parts if you want to. As an alternative, you can also read this free chapter, coauthored by the same author and watch this very amusing YouTube Video (1hour). If you are short on time, at least watch the video, it is really worth it. While CP-SAT follows a slightly different approach than the one described in the book/chapter/video, it is still important to see why it is possible to do the seemingly impossible and solve such problems in practice, despite their theoretical hardness. Additionally, you will have learned the concept of Mathematical Programming, and know that the term "Programming" has nothing to do with programming in the sense of writing code (otherwise, additionally read the just given reference). The course Discrete Optimization on Coursera with Pascal Van Hentenryck and Carleton Coffrin is also highly recommendable and gives you an intense crash course on nearly all important topics in applied combinatorial optimization. After that (or if you are already familiar with combinatorial optimization), the following content awaits you in this primer:

Content:

1. Installation: Quick installation guide.
2. Example: A short example, showing the usage of CP-SAT.
3. Alternatives: An overview of the different optimization techniques and tools available. Putting CP-SAT into context.
4. Modelling: An overview of variables, objectives, and constraints. The constraints make the most important part.
5. Parameters: How to specify CP-SATs behavior, if needed. Timelimits, hints, assumptions, parallelization, ...
6. Coding Patterns: Basic design patterns for creating maintainable algorithms.
7. How does it work?: After we know what we can do with CP-SAT, we look into how CP-SAT will do all these things.
8. Benchmarking your Model: How to benchmark your model and how to interpret the results.
9. Large Neighborhood Search: The use of CP-SAT to create more powerful heuristics.

Target audience: People (especially my students at TU Braunschweig) with some background in integer programming /linear optimization, who would like to know an actual viable alternative to Branch and Cut. However, I try to make it understandable for anyone interested in combinatorial optimization.

About the Main Author: Dr. Dominik Krupke is a postdoctoral researcher with the Algorithms Group at TU Braunschweig. He specializes in practical solutions to NP-hard problems. Initially focused on theoretical computer science, he now applies his expertise to solve what was once deemed impossible. This primer, first developed as course material for his students, has been extended in his spare time to cater to a wider audience.

Found a mistake? Please open an issue or a pull request. You can also just write me a quick mail to krupked@gmail.com.

Want to Contribute? If you are interested in contributing, please open an issue or email me with a brief description of your proposal. We can then discuss the details. I welcome all assistance and am open to expanding the content. Contributors to any section or similar input will be recognized as coauthors.

Want to use/share this content? This tutorial can be freely used under CC-BY 4.0. Smaller parts can even be copied without any acknowledgement for non-commercial, educational purposes.

Why are there so many platypuses in the text? I enjoy incorporating elements in my texts that add a light-hearted touch. The choice of the platypus is intentional: much like CP-SAT integrates diverse elements from various domains, the platypus combines traits from different animals. It is a unique mammal that lays eggs, possesses a beak, and is venomous. The platypus also symbolizes Australia, home to the development of a key technique in CP-SAT - Lazy Clause Generation (LCG). Also, I like platypuses, and hope to see a real one someday.

The CP-SAT Primer is authored by Dominik Krupke at TU Braunschweig, Algorithms Division. It is licensed under the CC-BY-4.0 license.

The primer is written for educational purposes and does not claim to be complete or correct. If you find this primer helpful, please star the GitHub repository. As an academic, I also enjoy hearing about how you use CP-SAT to solve real-world problems.