Constraint Programming Courses and techniques

[jjtolton]

Continuing discussion from #2511 (reply in thread)

A general topic to discuss constraint programming, constraint programming courses, papers, techniques, etc...

[jjtolton]

I'm very interested in the theory and techniques...

On edx.org there is a free MOOC, "LouvainX: Constraint Programming: Learn the basics of constraint programming from the implementation of solvers to modeling techniques for solving concrete combinatorial problems such as routing and scheduling."

"This course is being instructed by AI4OPT principal investigator Pascal Van Hentenryck..."

https://www.edx.org/learn/computer-programming/universite-catholique-de-louvain-constraint-programming

https://www.ai4opt.org/news-events/constraint-programming-course-edx

The course teaches the architecture of a constraint programming solver/relevant theory and how to implementing it from the scratch, so to speak, but the implementation language is Java.

Also, a paper: Tejas Santanam, Pascal Van Hentenryck: Modern Constraint Programming Education: Lessons for the Future, 2023

https://arxiv.org/abs/2306.13676

PS: There are more free MOOC courses on CP and optimization (but not in the context of Prolog).

We are quite spoiled with Scryer. Just from what I've seen so far glancing at the curriculum:

And in this:

I'd be interested to learn more about the vehicle routing problem, but my guess is that for [1] it's quite related to this discussion and this search problem discussion, and I'm thinking [2] is almost certainly a case of this scheduling with resource constraints problem. And what I love with Scryer is that there's no special framework required! You can "reason" about the problem instead of it feeling like magic.

That being said, the Vehicle Routing Problem and the Cumulative Scheduling Problem sound really interesting and very practical, and I'd love to learn about them and see how to implement them in Scryer!

My guess is that the VRP can be expressed very elegantly as a recursive relationship, once I learn how to minimize constraints.

I'd also be very curious what cumulative scheduling means!

Thanks for sharing these, this is by far and away my favorite area of programming!

[jjtolton]

I'd studied Peter Norvig's sudoku solver for a long time because it was the closest thing I could find to a constraint solver that didn't rely on "magic" like a special framework. But it was a really sophisticated technique, hard to generalize, and most importantly your coworkers would really be annoyed if you tried to do something like that!!!

However it feels like a much easier "sell" with Prolog because it's really readable, even if you don't completely understand it, secondly because clpz is so integral to Scryer itself, assuming you already convinced your coworkers or clients that Scryer is a good idea, clpz is an easy sell. @triska even goes out of his way to say that using clpz is not cheating! 🤣

[haijinSk]

On CP there are, of course, books (even for free as PDF); as I see it now, at least in my imagination, outside of Prolog context, there is MiniZinc (MOOCs for MiniZinc as well), but closer to Prolog, there is (I think: traditional) ECLiPSe Constraint Logic Programming System (Wiki: The ECLiPSe language is largely backward-compatible with Prolog).

Yes, now CP is "everywhere", be it Prolog, or "Prolog-like" system, or a system with Prolog roots as Picat programming language; there is Ciao Prolog system, ...

The ECLiPSe system, on their web site, if one wants to learn from video presentations something about CP, they have (among other things), this:

"This is a self-study course on Constraint Programming using the ECLiPSe language, consisting of video lectures and accompanying material."

https://eclipseclp.org/ELearning/index.html

PS: Here, I'm not advocating any system/language, except constraint programming as an idea (to learn about); today, there are more ways to CP and to solving search problems, and to logic, relational, and declarative programming.

[jjtolton]

Yes indeed. I also realize I'm conflating two things... one is programming with CP, the other is implementing CP. So for instance, in PN's sudoku I mentioned above, the implementation is some really interesting CP but it also only applies exclusively to that one problem, and you'd have to be pretty familiar with the arc-3 consistency algorithm to even understand what's going on, and then you'd have to be comfortable with the mutual recursion introduced. Then in a lot of cases, you need to implement backtracking search independently on top of your constraint propagation! 😰

And by now, you are 30 hours into a client project and you need to justify why you are messing around with all of that just to verify that the user signup form is valid 😑 😑 😑

[jjtolton]

Some additional resources I've found very useful for programming with constraints. The following resources are pretty academic but help get a structured overview:

• Chapter 6 of Artificial Intelligence, a Modern Approach
• Distributed Constraint Satisfaction. Although the second half of the book deals with distributed constraint satisfaction, the first half of the book quickly gets you up to speed (at a high level) with the most recent learnings on regular CSPs.
• Evolutionary Optimization Algorithms. Although this book is more about optimization rather than constraint, it's really good to illustrate advanced CLP programming which uses optimization in conjunction with CLP. See @triska 's article and especially the "Related material" section at the bottom. The book is also an excellent read, in general.

If you are familiar with Python, Peter Norvig's CS212 course has some excellent units on CSP:
Full Playlist
videos 77-152 are all about CSP, but with a heavy focus on Python, so possibly a distraction.

While the above resources are good, I think application Prolog takes it to the next level.

• Prolog Programming for Artificial Intelligence shows some really good examples of using CLP to solve problems, particularly in later chapters. I do not like the coding style, though. But I am actively working/suffering through rewrites of the CLP problems. They do a very good job of showing CLP(FD) (we would use clp(z)) applications on CSPs, and they go beyond what the other resources do into partial order planning, graphplan, and scheduling algorithms. So this one is a major tradeoff -- on the one hand, it is a very good balance of being approachable while being an introduction to advanced practical applications. On the other hand, you almost can't use any of the code from the book because it does not fit with Scryer/Vienesse/pure/Vegan paradigms at all.

I have some other books on the shelf, but I haven't gotten through them yet to give you a good synopsis of how useful they may be or not.

• The Craft of Prolog has a lot of CSP problems without using CLP
• Prolog Programming in Depth chapter 8 does the same thing.

So those are two options of exploring CPS without CLP.

However, in exploring this problem recently, I have determined that it is almost always better to go with CLP if you have it available. The reason is because (according to AIMA Ch.6) more sophisticated search/planning/constraint techniques (such as Angelic Planning and Hierarchical Task Networks) admit not only boolean logic but "wiggly" logic, meaning the planner/agent/scheduler has the option to defer the choice until a later point when a solution is most optimal. This wiggly logic would be possible to encode by hand but is already captured really nicely by clp logic. That's my 2 cents anyway.

So I still like knowing the predicate based approach, but I will be implementing (mostly exclusively) using CLP libraries unless I have a very good reason not to.

[jjtolton]

After going through multiple algorithms in Prolog Programming for AI, this one stands out as the most important:

• Scheduling, rewritten for Scryer.

The single most important insight I've gotten about CSP in Prolog/Scryer is that CSP means effectively assigning CLP constraints, and then letting CLP do the work, and then using labeling/2 at the end if necessary. That's pretty much the only thing that's happening in this scheduling code, and it's extremely effective.

That seems to be the entire punchline of CSP programming in Prolog. Everything outside of that is "regular" programming, as far as I can tell.

[jjtolton]

I didn't mention it elsewhere simple because it partially seems so obvious, but @triska has many excellent CSP and CLP videos on his website and YouTube series. In some ways they are much better than books because the information content is extremely dense and to the point. At some point I'd like to go through and start indexing the work.

[jjtolton]

In the implementation category, this MIT mathematical programming course seems like it might be interesting.