from Hacker News

A practical introduction to constraint programming using CP-SAT and Python

by lfittl on 7/3/24, 4:48 PM with 39 comments

• by 0cf8612b2e1e on 7/3/24, 7:38 PM

  I have used constraint solvers in the past, and they are truly magical in what they can do. The problem is that there are not many available resources for the novice. Most of the material you can find is how to solve sudoku (the hello world of the space) or highly technical primary research literate meant exclusively for domain experts. Which is a shame, because I think huge swaths of problems could be solved by these tools if they were more accessible. “Accessible” still meaning it requires a programmer, because shaping a problem into the constraints DSL is not going to be in the wheelhouse of most.

• by taeric on 7/3/24, 9:38 PM

  Core to a lot of this, is learning how to model things in such a way that you can send them to a solver. After that, how to take a solution and present it in a way that can be understood.

  It is a shame, as most programs work against the ideas here by trying to have a singular representation of their data. This is just not reasonable for most things and leads to a lot of contortions to get the algorithms to work on a new representation.

  This article touches on it with the brief touch of declarative at the top. I always regret that more of my code is not translating between representations more often. You can wind up with very concise representations when you do this, and then you can get a double bonus by having things run faster by virtue of being concise.

  (And, yes, I realize I'm basically describing many data pipelines. Where you spend most of your time translating and fanning out data to places for more compute to be done on it.)

• by mark_l_watson on 7/4/24, 2:43 AM

  I have a short chapter on using MiniZinc with Python in one of my old books that I am currently rewriting https://leanpub.com/pythonai/read#constraint-programming-wit... (link directly to this chapter online)

  MiniZinc is a constraint programming system. There is a good Coursera class using MiniZinc.

• by bartkappenburg on 7/3/24, 6:52 PM

  I used a lot of solvers in the early 2000s in my Operations Research master after my econometrics study. While now working on software (web) that uses python I’m thrilled to see these deep dives on this subject!

  I love the subject and reading this brought back a lot of memories. Also the realization that translating constraints to a model (variables, structure etc) is 90% of the work and the most difficult part.

• by d_burfoot on 7/4/24, 3:21 PM

  I have a client that runs a sports camp for kids. The kids get to request what sports they want to play, and what friends they want to be in class with. This creates a scheduling problem that's hard for a human, and previously they spent several man-weeks per year dealing with it. I built them a simple system that connects their data to an optimizer based on OR-Tools, now their scheduling is done with a few clicks.

• by Elucalidavah on 7/4/24, 4:25 PM

  Is there a parametric CAD that works primarily as a constraint solver?

  It so often bothers me that I have to guesstimate some values for parameters I don't initially care about, instead of constraining the parameters I care about and then optimizing the rest.

• by richard___ on 7/3/24, 7:04 PM

  How does this compare with mixed integer programming? For problems in physics