Revise the "How does it work" chapter

[d-krupke]

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.

[leonlan]

Do you have any preliminary ideas to address this? I want to delve a bit deeper into CP-SAT so I'd interested to on this issue next.

[d-krupke]

I think I would like to explain the basics of LCG here. Also write a little more about the history of different techniques. Not going anywhere too much into detail but mention the key concepts and provide a reference to the details. Just having a list with the references may be of little use if you cannot imagine what is behind these keywords. I will put it onto my list to think about a way we could together work on this.

[leonlan]

Alright, keep me posted!

[d-krupke]

What may be a good point to start the revision of this section is to extend the enumeration of What happens in CP-SAT on solve to a proper text.

It is probably helpful to give some simple examples on what roughly happens in the individual steps, e.g., during probing.

I actually would also like to bring back the encoding and propagation from Stuckey's paper. There is also some related explanations in the slides of Pierre Flener.

[leonlan]

Thanks for the update! I was planning to work my way through Pierre Flener's course in the next two months. I'll take notes and comment on this issue when I have things to showcase.

[d-krupke]

As it is related, I added a short section on presolve to the parameters section https://d-krupke.github.io/cpsat-primer/05_parameters.html#presolve. However, it does not really go into any detail here.

[d-krupke]

This blog post may also be useful. It is incomplete but has some nice references and some extra information I don't have. https://xiang.es/posts/explaining-cp-sat/

[d-krupke]

There is also the paper "ViolationLS: Constraint-Based Local Search in CP-SAT" which should be integrated into this chapter. I haven't read it, yet, but will do so the next days.

[d-krupke]

I just did some smaller revisions on this chapter. There is still a lot to improve. I would like to add a diagram and references to the actual code here.