Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

pganalyze.com

Post reply on HN
Print view View original

11–20 of 41 posts

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

#11

Post by cchianel »

0cf8612b2e1e wrote: post #9

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 thes…

I think the reason why these tools are not accessible as they could be is because the vast majority of solvers are MIPs (Mixed Integer Programming) based, meaning the domain need to be written down using mathematical equations. This in turn means a user would need to be familiar with both the domain and mathematics in order to correctly write constraints.

That being said, MIPs are not the only kind of solvers. There are also "local search" based constraint solvers, which does not have the restriction that each constraint must be modelled as a relation or equation of integer variables. In local search solvers, the constraints are mostly treated as a black box that tells how good a particular solution is. As a consequent, local search solvers are typically unable to find the optimal solution (since it would require testing all possible solutions because the constraint is treated as a black box), but rather finds a "near-optimal" solution in reasonable time.

One local search based solver is Timefold Solver. In it, users annotate their domain so the solver knows what are the variables and possible values. This means instead of your constraints dealing with `int`, it would deal with `Shift` and `Employee`, and can access any of their methods.

Disclosure: I work on Timefold Solver

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

#12

Post by ayhanfuat »

Murky3515 wrote: post #3
bartkappenburg wrote: post #2

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.

>the realization that translating constraints to a model (variables, structure etc) is 90% of the work and the most difficult part. LLMs can help a lot there. I've been wanting to write an LLM => Constraint model adapter that does it for you. It's such low hanging fruit, I wonder if anyone else would benefit from it though.

It is indeed a very good fit. There is some cool research about it: https://github.com/skadio/ner4opt

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

#13

Post by tannhaeuser »

Murky3515 wrote: post #3
bartkappenburg wrote: post #2

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.

>the realization that translating constraints to a model (variables, structure etc) is 90% of the work and the most difficult part. LLMs can help a lot there. I've been wanting to write an LLM => Constraint model adapter that does it for you. It's such low hanging fruit, I wonder if anyone else would benefit from it though.

Indeed, it seems like an obvious thing to do. But just as you noted, it's not very clear LLMs really can improve over Prolog in terms of expressiveness and practicality given that Prolog already was designed for natural language parsing and is a concise formalism based on predicate logic (and ultimately propositional and first order logic) with constraint domain theory embeddings such as for arithmetic. Prolog syntax is also the starting point for most constraint solvers, and Prolog evaluation is also often referred to as basis for generalization into constraint solving. Though I'm not sure this generalization bears much value tbh when the break-through successes in constraint solving were particular domain-specific techniques (SAT solvers, interval propagation, arc consisteny/finite domain propagation, etc).

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

#14

Post by taeric »

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

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

#15

Post by taeric »

richard___ wrote: post #4

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

I would assume largely similarly? https://www.amazon.com/gp/product/1107658799/ is the book I last went through on this and it covers a lot of the same ideas. In particular, I'm assuming the section of this post that aims to minimize some value are directly using the same stuff.

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

#16

Post by wjholden »

0cf8612b2e1e wrote: post #9

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 thes…

I agree, the theory isn't nearly as difficult as the reductions. Dennis Yurichev's "SAT/SMT by Example" (https://smt.st/) is a great resource on this topic, although pretty intimidating.

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

#17

Post by mncharity »

pjot wrote: post #10
bartkappenburg wrote: post #2

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.

I used program called GAMS in mine. Its syntax structure is totally free form! https://www.gams.com/latest/docs/UG_GAMSPrograms.html#UG_GAM...

I'm intrigued by bits like Outside Margin Comments[1] - `$onMargin minCol 20 maxCol 45` - text before column 20 and after column 45 is treated as a comment - 1970s.

[1] https://www.gams.com/latest/docs/UG_GAMSPrograms.html#UG_GAM...

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

#18

Post by dd82 »

0cf8612b2e1e wrote: post #9

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 thes…

> 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

Exactly. I was looking at using a sat solver for a rules engine and couldn't make heads or tails how to use it. After alot of deduction, got a basic POC working, but couldn't extend it to what was actually needed. But the gulf between toy implementations and anything more substantial was very large.

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

#19

Post by akutlay »

bartkappenburg wrote: post #2

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.

I would say the most difficult part is to run it in production with minimal issues. Scaling them and making them robust to changes in data takes a long time.

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

#20

Post by mark_l_watson »

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.

Post reply on HN