d-krupke / cpsat-primer

The CP-SAT Primer: Using and Understanding Google OR-Tools' CP-SAT Solver

PostDoc Researcher at the Algorithms Group (Prof. Fekete), TU Braunschweig, Germany.

I am an experienced algorithm engineer with a background in theoretical computer science. I have a knack for tackling complex, especially NP-hard, problems by fusing theoretical rigor with practical implementation. My work has been recognized with best paper (CIAC, ALENEX) and student awards.

---

Skills

Technical Skills 💡

• Combinatorial Optimization: Proficient in solving NP-hard problems to optimality using techniques like Mixed Integer Programming, Constraint Programming, custom branch-and-bound algorithms, SAT-solvers, and Second Order Cone Programming.
• Approximation & Meta-heuristics: Skilled in finding near-optimal solutions via approximation algorithms, meta-heuristics, and LNS-variants.
• Algorithmic Foundations: Strong background in theoretical computer science, with a comprehensive understanding of algorithmic concepts and their practical applications, such as complexity, approximation, and graph theory.
• Programming & Performance: Adept in writing maintainable Python and C++ code for complex algorithms, with expertise in performance tuning and modularization. Check out my repositories for examples.
• Data Analysis & Visualization: Capable of managing, evaluating, and quality-checking complex data, as well as visualizing data sets for insights and decision-making. Refer to my dissertation for exemplary empirical evaluations.
• Machine Learning: Familiar with machine learning techniques and have applied them successfully in research projects. Eager to explore their potential to augment classical algorithms, although this is neither a primary focus nor an area of expertise.

Research Skills 📚

• Theory-Practice Bridge: Skillful in bridging the gap between theoretical computer science and practical implementation, highlighted by interdisciplinary collaborations and consultancy.
• Interdisciplinary Collaboration: Extensive involvement in projects across diverse fields such as robotics, bioinformatics, automotive, and satellite management.
• Creativity & Curiosity: Demonstrated curiosity and creativity in learning and combining new techniques, as evidenced by the diverse techniques used in my dissertation and the variety of projects undertaken.

Soft Skills 🤝

• Teaching & Presentation: Proficient in teaching and presenting complex topics, as proven by the positive evaluation of my lecture on algorithm engineering and the popularity of my online material.
• Project Management: Experienced in managing multiple projects and student teams concurrently, as evidenced by the number of successfully completed projects.

---

🔬 Research	📖 Publications	🎓 Dissertation
Explore my ongoing research projects.	Discover my published works.	My dissertation for a coherrent sample of my work (2017-2022).

---

🤝 Let's Connect!

I am open to research stays and collaborative opportunities to broaden my expertise and contribute to groundbreaking research. Let's work together to solve challenging problems and make a lasting impact.

cpsat-primer's Issues

Write a section onto how to benchmark models

Benchmarking different models is not trivial, however it is something I frequently do. It may be fitting, to provide a nice example on how to do a proper evaluation fitting for a publication.

As example, we could use different TSP models. (1) The circuit-constraint (2) the MTZ formulation (3) the classical Dantzig formulation that will require multiple iterations because CP-SAT does not support lazy constraints.

Show all the steps if implementing and evaluating this via Git tags. Can be used for generally teaching about empirical evaluations of optimization algorithms.

Change example code to new snake case methods

OR-Tools now has the pythonic snake case convention as default, while still having backwards compatibility to the old Google-style. I have already updated the text, but the examples are still in the old style. Would be great to update them, too.

Update for CP-SAT ~~9.9~~ 9.10

The interface changed in CP-SAT of ortools 9.9. While it seems to be compatible with most parts, there are some breaking changes with specific features. Identify and fix those.

Also, there is the question of changing to the new more Pythonic interface. This is prettier but would be incompatible with older versions.

Write a section about solving large problems using lazy and LNS

Some problems are too large to be solved with CP-SAT directly. Write about techniques on solving those. Maybe do an example with coloring.

• Iteratively add constraints and variables lazily, only when they become important.
• Partitioning the problem and using Large Neighborhood Search.

Suggestions for Chapter 6: Parameters

• Style: I think it's a bit too much to list all the (sub-)solvers used in
  https://d-krupke.github.io/cpsat-primer/05_parameters.html#parallelization. The current layout makes it hard to read and it is a lot of information that might not be relevant to readers. Is there a reference that we can refer to instead, or can we think of a better way of visualizing this as a table?

• Content: I have seem multiple times Laurent Perron mention that it is really recommended to use OR-Tools with 8 cores, or even 16 cores. Should we mention this somewhere in the parallelization section as well?

• Content: We could also mention what the default setting of the solver is regarding parallelization, which is to use all available cores by default right?

• Structure: There are three sections that are not strictly "parameters" (exporting model, adding assumptions, adding hints). The section then ends with "decision strategy", which is a parameter again. I don't think this is problematic but I noticed it.

• Structure: I think it's easier to start with hints first and then discuss assumptions. Hints are similar to warm-starts, which most readers understand. Assumptions are more niche because they only apply to boolean variables.

• Content: The assumptions section starts begin with

  "Often, you may need to explore the impact of forcing certain variables to specific values."

  This is a bit deceptive because assumptions can only force boolean variables. In combination with the restructuring point above I suggest 1) discussing parameter "fix_variables_to_their_hinted_value" in the hints section, which does practically the same 2) rewriting the assumptions section to emphasize that this is only for fixing bools.

• New content: This section starts with a brief mention of protobufs. This was a completely new concept to me when I started reading into OR-Tools but it's a common practice by Google and similar ideas apply to other software (e.g., intermediate data representation for modeling APIs). Perhaps we can add a section to the advanced topics on protobufs? I can make a separate issue for that.

subsolvers for BoolVar

I use CpModel and my variables are all BoolVar(0-1) .

I want ask : Which subsolvers are unuseful that I can exclude them ?

Thank you !
And waiting your advise.

Evaluate the automatic `AllDifferent` optimization of CP-SAT

CP-SAT will automatically detect mutual !=, but only if no AllDifferent is used.
Check on the coloring problem, how well it works.

1. Implement coloring with only !=.
2. Implement coloring with only != and deactivating this optimization (either by adding a AllDifferent or setting the corresponding parameter to False)
3. Implement coloring with AllDifferent but only on pairs.
4. Implement coloring with AllDifferent on quick greedy sets.
5. Implement coloring with AllDifferent and proper clique optimization.

All variants should use symmetry breaking, by first computing a large clique and then assigning each vertex in this clique a fixed color.
Do a simple greedy algorithm first (e.g., by networkx) to get an upper bound on the colors.

Obsolote parameter `min_num_lns_workers`

Hi @d-krupke, great work on the CP-SAT primer! It's easy to read, and the interleaved code examples make it very practical. I'm definitely going to recommend your book to others who are interested in CP-SAT.

I was reading chapter 5 and this part stood out to me:

If you want to use more workers heuristically searching for good solutions, you can specify solver.parameters.min_num_lns_workers.

In the proto specification for parameters, there's a comment about min_num_lns_workers being a no-op:

https://github.com/google/or-tools/blob/d4f9b80c95816dd2c817bf65a2996d7dd6d83d11/ortools/sat/sat_parameters.proto#L572-L573

This changed about eight months ago:
https://github.com/google/or-tools/blame/v9.8/ortools/sat/sat_parameters.proto#L571

My suggestion would be to remove the line about this parameter in chapter 5 or to replace it with another parameter, but I'm not familiar enough yet with CP-SAT know which one.

What to expect from the CP-SAT Primer book?

Prelude

Here's my understanding of the CP-SAT Primer book.

The CPSAT-Primer book is an introduction to Google OR-Tools' CP-SAT solver. The book covers the whole of CP-SAT's modeling interface (chapter 2-5) and basics related to solving such as parameters and logging (chapter 6-7). There are many examples that showcase how to use CP-SAT to solve combinatorial optimization problems (primarily knapsack and TSP). The details of how CP-SAT works are briefly discussed in chapter 10, and as you humbly acknowledge, the linked resources do a great job at explaining the inner workings of CP-SAT. Since CP-SAT is a solver portfolio of many sophisticated techniques, it only makes sense that this is not explained in detail in CP-SAT Primer. Furthermore, the book is also a collection of meta-skills related to solving optimization problems: coding patterns (chapter 8), developing an optimization API (chapter 9), benchmarking (chapter 12), etc. I am a big fan of this book, because I personally have been going through all these steps myself and I would have benefited a lot from a book like this early in my PhD.

Discussion point

My main discussion point is: what is the CP-SAT Primer book exactly, and what is its intended audience? It can be a bit confusing for readers what to expect from this book because, from what I perceived, it is an introduction of CP-SAT and related topics that you have encountered in your work as well. Because that is not explicitly mentioned anywhere and the sections are interwoven, I got quite confused about this, and I also recognize that this is an "organic growth" process that the book is going through.

Suggestions

I have the following two suggestions to improve clarity regarding "what to expect."

Restructure the sections

I think it would be helpful to make a more clear distinction between the sections related to CP-SAT and other topics.
Based on the title and introduction, I would expect mostly topics on CP-SAT.

Part 1: Introduction to CP-SAT

1. Installation: Quick installation guide.
2. Example: A short example, showing the usage of CP-SAT.
3. Basic Modeling: An overview of variables, objectives, and constraints.
4. Advanced Modeling: More complex constraints, such as circuit constraints and intervals.
5. Parameters: How to specify CP-SATs behavior, if needed. Timelimits, hints, assumptions, parallelization, ...
6. Understanding the Log: How to interpret the log
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. Alternatives: An overview of the different optimization techniques and tools available. Putting CP-SAT into context.
9. Large Neighborhood Search: The use of CP-SAT to create more powerful heuristics.

Part 2: Software skills for optimization (or something else
9. Coding Patterns: Basic design patterns for creating maintainable algorithms.
7. (DRAFT) Building an Optimization API How to build a scalable API for long running optimization jobs.
10. Benchmarking your Model: How to benchmark your model and how to interpret the results.

Part 2 is much more advanced and not really relevant immediately for those who just want to get an introduction to CP-SAT.
The topics are, however, extremely relevant, but it having this structure allows readers to much easier cherry-pick what they want to read.

Restructure "Introduction"

The current intro is structured like this:

• Introduction paragraph
• 1 sentence on what is this primer about
• Lots of background recommended readings
• Intended target audience
• Table of content

I think this kind of structure is clearer:

• Introduction paragraph
• Much longer paragraph on what is this book about
  • In part 1, CP-SAT modeling, solving, examples, etc.
  • In part 2, metaskills related to more general modeling -- can be skipped but extremely useful
• Inteded target audience
  • Students from your course
  • Readers interested in CP-SAT
  • Readers interested in more advanced skills related to optimization
• Table of content
• Background

Opinion not to be taken harsh: you provide a lot of helpful recommendations but they sometimes distract from the main text to "get to the point." The introduction has a similar build-up and I'll point it out in other chapters once I get to creating the issues related to those chapters.

(PS: In the coming days, I will make separate issues for other, overarching discussion points. For collections of improvements related to a single chapter I will also make individual issues.)

Add further plots and their code to benchmarking`

There are more approaches and plots to benchmark a model.

In especially, it is actually quite easy to set up a good framework for evaluating the influence of different parameters on the performance. This could work quite model agnostic only based on the protobuf files. One could even build an automatic parameter tuner.

I would refrain from adding too much functionality here as the parameters can quickly change, but at least having some basic framework would be quite helpful and not too difficult. Maybe even integrate it with the log analyzer?

Error in a formula, and a few typos

In the formula (which I cannot copy and paste) following "Let us look on an overly simplified example: Consider the formula [...]": setting x_0 to 0 constrains both x_1 and x_2 to 1. You mention just x_1 and then go on to set x_2 to 0.

Miscellaneous typos:

• "Math Programming Modelling Bascis" -> "Math Programming Modelling Basics". (Splitting hair: the spelling is inconsistent, "math" is American whereas "modelling" is British.)
• "It does not relay on the linear relaxation as much as MIP-solvers do." -> "It does not rely on the linear relaxation as much as MIP-solvers do."
• "CP-SAT can work much more efficient" -> "CP-SAT can work much more efficiently"
• "You can use this constraint very flexible for many tour problems." -> "You can use this constraint very flexibly for many tour problems."
• "AddCircuit can solve the eculidean TSP" -> "AddCircuit can solve the Euclidean TSP"
• "You need them to insert them into the no-overlap constraint." -> "You need to insert them into the no-overlap constraint." ?
• "More specific, CP-SAT will stop as soon as the objective value" -> "More specifically, CP-SAT will stop as soon as the objective value"
• "feeding information of previous itertions into the model." -> "feeding information of previous iterations into the model."
• "luckily there is literatur for you" -> "luckily there is literature for you"
• "We are not learning anything that is not available in the original formular" -> "We are not learning anything that is not available in the original formulas"
• "Branching can be interpreted fixing a variable" -> "Branching can be interpreted as fixing a variable"
• "I don't think very high of most meta-heuristics" -> "I don't think very highly of most meta-heuristics"

Suggestions for chapter 4: basic modeling

Some suggestions for chapter 4 that may need discussion before implementing. Once we have agreed on how to proceed I'll make a PR for the changes.

• Is the new_constant any useful? I cannot think of any reasons. If not, then we could just remove this part.

  Additionally, there is the new_constant-method, which allows you to create a variable that is constant. I have not found a use case for this yet, let me know if you have one.

• The paragraphs on domain variables can use a small example to illustrate the meaning. The naming of "domain" variables is a bit unfortunate because integer variables also have a domain which made me confused. My suggestion is to change the following sentence:

  Unlike regular integer variables, domain variables are tailored to represent a specific set of values.

  to something like this:

  Unlike regular integer variables, which must have a domain between a given range of values (e.g., [1, 100]), domain variables can specify a custom set of values as domain (e.g., {1, 3, 5}).

• Do you want to use the new PEP8 style everywhere? There are still some places where you use the old style (x_vars[i].Not()). Related #34.

• In subsection Adding Logical AND Constraints: after explaining the add_bool_and there is a paragraph on reification:

  The add_bool_and method is most effective when used with the only_enforce_if method. For cases not utilizing only_enforce_if a simple AND-clause such as (b1∧¬b2∧¬b3) becomes redundant by simply substituting b1 with 1 and ( b_2, \)b_3 with 0. In straightforward scenarios, consider substituting these variables with their constant values to reduce unnecessary complexity, especially in larger models where size and manageability are concerns. In smaller or simpler models, CP-SAT efficiently handles these redundancies, allowing you to focus on maintaining clarity and readability in your model.

  This section comes too early: the reader does not yet know what reification is. I think this paragraph should be moved to the corresponding section.

Broken Inline LaTeX

Thank you for putting together this extremely helpful primer! In reading through your work, I just found a few spots with broken inline latex I thought I'd point out.

In DPLL and Unit Propagation :

If we have a clause $(x_1\vee x_2 \vee \overline{x_3})$ and we have

In LCG Encoding:

Because otherwise we would need a quadratic amount of consistency constraints ($[x=v] \rightarrow [x\not=v'] \forall v\not=v' \in D(x)$).

In Branching/Searching:

The arrows pointing towards a node can be seen as conjunctive implication clauses ($x\wedge y \Rightarrow z$), that are added lazily by the propagators.

Thanks again for your help in figuring out what CP-SAT does under the hood.

Write a section on CP-SAT with C++ (potentially mixed with Python using PyBind11)

Sometimes, the performance of Python is simply too slow to build larger models. In this case, parts of the code can be written in C++ and integrated into Python using PyBind11. My desk neighbor Phillip Keldenich actually wrote a conan package for CP-SAT, which can be automatically build in Python using my skbuild-conan.

Could be nice to have a tutorial on how to do that.

Suggestions for Chapter 5: Advanced Modelling

• Structure: It could be beneficial to rearrange the topics here: specifically, I suggest putting the Intervals section right after Tour constraints. Scheduling is one of the most used applications of OR-Tools, while automaton/reservoir constraints seem more niche to me.

• Question: There are a lot of different interval variable creation methods (fixed size, optional, etc.). Are they different from each other or is it just a simple interface? For instance, you can also pass constant values to the start/end/size arguments in new_interval_var. I would assume that preprocessing takes care of the redundancies but I'm not sure about that.

  The new_optional_interval_var is the most expressive but also the most expensive, while the new_fixed_size_interval_var is the least expressive and the easiest to optimize.

• Content: In my opinion, it is a bit much to describe all types of intervals here. Only keeping variable-sized interval variables should be enough to explain the concept of interval variables, while the fixed-size types can be briefly mentioned in a line or two afterwards (and the reason when to use fixed-size intervals). (Note: My perspective mostly comes from OR-Tools' machine scheduling examples which don't use fixed-size intervals.)

Add overview of available techniques to solve NP-hard optimization problems.

It would probably be nice to have an overview of available techniques to solve NP-hard techniques such that one can see the place of CP-SAT in the bigger picture.

Here some notes on it to begin with:

• Mixed Integer Programming: Expressing your problem with fractional/integral variables+linear constraints/objective and handing it to a solver.
  • Rule of thumb: Good if it has a good linear relaxation (such as for network flow problems). Good if the primary task is to optimize a solution, not to find a feasible one (e.g., if it has a lot of logic involved).
  • Fair support of lazy model building (adding constraints and variables only if necessary).
  • Popular solvers: Gurobi, CBC, CPLEX...
  • Easy to use/implement.
  • Complex techniques in the background that require a lot of study to really master this technique.
• Custom Branch and Bound (without Linear Relaxation):
  • Sometimes best option if you need to do higher level branching (not just restricting a variable to some values).
  • Difficult to implement as you have to do most things on your own.
  • Example: CE-TSP
• LCG-based Constraint Programming such as CP-SAT:
  • Rule of thumb: Good if the problem has a lot of logic involved.
  • No support of lazy model building in CP-SAT. You can only extract some information from the previous iteration by hand with some chance to speed up the next iteration.
  • Easy to use/implement.
• (Cardinality-)SAT:
  • Extremely fast if your problem is essentially a boolean formula.
  • Only finds you a feasible solution, the optimization for some objective has to be done by you.
  • Many solvers allow excellent lazy model building as they maintain their state. Using Assumptions you can also do a lot of fast probing.
  • The solvers are not as intricate as MIP-solvers, but modelling a problem requires more knowledge and tricks.

Other techniques not mentioned:

• FD-based Constraint Programming:
  • Probably not the way to go. If you know of some example where they are better than, e.g., CP-SAT, please let me know.
• Quadratic Programming etc.
  • Usually not as powerful as MIP-solvers and most of the time you can get along with linear models.

Proper Example for Reservoir Constraint

The Reservoir Constraint could need a good example. I tried to quickly build one but the constraint is not trivial to use and the example did not work out. Unfortunately, there are a lot of other areas that need attention more urgently so I do not know when I would find the time myself.

The example could be added directly in the text, like for the other advanced constraints.

Add a simple introduction to branch and bound based on Knapsack

Knapsack has a trivial relaxation and thus can be used to explain Branch and Bound without knowledge of Linear Programming.
I guess that this would be the best start to explain the fundamentals of nearly all exact solvers. We do this in our bachelor lecture "Algorithms and Datastructure 2"

Some questions

Hi,
Thanks for sharing such good project.
I have some questions:

1. You say:
   ⚠️ If you use intersecting linear constraints, you may get problems because the intersection point needs to be integral. There is no such thing as a feasibility tolerance as in Mixed Integer Programming-solvers.
   it means cp-sat solver can't solve a general linear programming? Sorry I can't understand what the problems in intersecting linear constraints.
2. About Circuit/Tour-Constraints, I think this is specialize for sub-tour problem, but when I want to add AddCircuit(), would the number of arcs grow exponentially? I didn't use this method, so I'm confusing this part, is there any refference examples ?
3. I think the Array operations part is not clear explain, is there any more source to study?

Looking forward to your reply, thank you.
Zhe.

Add a section on testing optimization models

Testing optimization models is not too difficult once you know how to do it. I am already giving some hints in the coding patterns, but maybe it would be good to have a more explicit section on that.

Continue on Piecewise Linear Approximation

I already wrote a first section on piecewise linear approximation. However, it is missing a few points and is not tested properly on real problems (I have used some similar code, but could not just copy and paste it into the Primer for various reasons). Also the stepwise function could be integrated.

Deployment to Cloud for the API

Instead of just using some worker containers, it may be cheaper to deploy the code to the cloud and use google cloud run to schedule and run the optimization on demand. Especially for low frequency APIs, this can be significantly cheaper as you only need to rent an expensive cloud machine for the time you are actually optimizing. Should not be too complicated, but I am not a cloud expert, so I am slow in getting all the details right and not just having a "worked for me".

Revise the "How does it work" chapter

This chapter is older and oversimplifies too many things. CP-SAT has gotten quite complex, and the text may no longer represents that. There are some nice aspects of CP-SAT that could be explained here. Also the literature section could be made a little prettier and less opinionated.

Develop a utility package accommodating this primer

I have started to develop utilities for generalizing some common modelling techniques for CP-SAT. It would be nice to have it available as simple Python package. The primary issue right now with that would be that as soon as there is a package, the expectations are higher, and, thus, more testing etc. is required. I may not have the time for that.

Extend the AddCircuitConstraint-section

The AddCircuitConstraint-section is currently difficult to understand. The example should probably be expanded to a full TSP example, maybe even a variant such as k-TSP that can easily be modeled with this constraint.

Instructions for a local build

I realized that one of my "fixes" in #41 instead did not fix. Locally building the book would have helped prevent that, and it would be helpful to have instructions to build this book locally described somewhere.

Based on https://github.com/d-krupke/cpsat-primer/blob/main/.github/workflows/deploy.yml:

• Install mdbook
• Run python3 build.py
• cd .mdbook
• mdbook build
• mdbook watch --open .

What's a good place to describe these instructions?