What to expect from the CP-SAT Primer book?

[leonlan]

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.)

[d-krupke]

You are making a good point and this is something I have actually been thinking about, too, the last two weeks. This has already been reflected by the fact that I removed "Cheat Sheet" from the title.

The primer actually started as a cheat sheet of maybe 4 pages for my students to help them with their exercises. It then grew to become a "primer", and now it is has grown even more. New sections were usually added whenever I needed to show my students how to do a certain thing and then I just added it to the primer, too, so I can easily reuse it. However, there have been too many additions without caring about the overall structure and this needs to change to make it accessible again.

I love your idea with Part 1 and Part 2, and the other points seem to be good, too. I try to make an action plan, soon. Unfortunately, my vacation days are over and I have to somehow squeeze it in between my other responsibilities, but I am eager to finally fix the structure of the primer.

[d-krupke]

Maybe, I would consider LNS an advanced technique and also move it to Part 2 🤔
@leonlan Did you have a concrete reason to leave it in Part 1 or was this just gut feeling?

[leonlan]

Maybe, I would consider LNS an advanced technique and also move it to Part 2 🤔 @leonlan Did you have a concrete reason to leave it in Part 1 or was this just gut feeling?

Just a gut feeling :-) Moving it outside of part 1 makes sense as well.

[d-krupke]

Did some experimenting with the structure in the lunch-break, and this structure actually feels much cleaner. However, would still have to change the introduction to accommodate it, which is obviously not something I can do in a break.

[d-krupke]

Couldn't let it rest and started revising the intro. There is now an extensive content section directly after the introduction paragraph, hopefully giving the reader a much better overview of what to expect.

[leonlan]

The revised structure and introduction look awesome, great job! I consider this issue to be resolved.