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

21–30 of 41 posts

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

#21

Post by Exuma »

cchianel wrote: post #11
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…

What’s a real world thing or two that this could solve vs writing code

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

#22

Post by jmjrawlings »

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…

You totally nailed it. The actual syntax / API of constraint solvers are so simple they can be learned in no time at all. What actually takes time and expertise is modelling problems in this fashion and there are almost 0 real world (in size and complexity) examples out there for others to reference.

I have about 5 years of experience in MiniZinc solving scheduling problems but sadly all that code is locked behind closed doors never to be open sourced. I would love put together some fully worked constraint programming examples complete with containerisation / visualisation/ modeling etc but the barrier to doing so is finding problems that are actually worth solving and have open source data to work on.

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

#23

Post by dualogy »

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

Another "friendly syntax, multi-solver" approach is MiniZinc.org.

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

#24

Post by sirwhinesalot »

richard___ wrote: post #4

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

CP-SAT is integer only, so I'm guessing for physics it's not great (you can scale your reals but that's not as good as working with floating point directly).

The advantage of CP-SAT is that it handles boolean and integer variables and constraints much more efficiently than a MIP solver, specially higher-level constraints like all_different.

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

#25

Post by sirwhinesalot »

dd82 wrote: post #18
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 implemen…

SAT is kind of the assembly language of constraint solving, using a higher level paradigm like CP/SMT/ASP should be easier.

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

#26

Post by lloydatkinson »

jmjrawlings wrote: post #22
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…

You totally nailed it. The actual syntax / API of constraint solvers are so simple they can be learned in no time at all. What actually takes time and expertise is modelling problems in this fashion and there are almost 0 real world (in size and complexity) examples out there for others to reference. I have about 5 years of experience in MiniZinc solving scheduling problems but sadly all that code is locked behind cl…

What about some really solid examples for real world stuff like teacher, classroom, student, resource scheduling? Then people could derive simpler ones like normal employee scheduling too.

I’d definitely be interested in that.

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

#27

Post by lloydatkinson »

mark_l_watson wrote: post #20

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.

Do you have a link to the Coursera course?

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

#28

Post by cchianel »

Exuma wrote: post #21
cchianel wrote: post #11

Earlier quoted context omitted.

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…

What’s a real world thing or two that this could solve vs writing code

Well, you still write code. The difference is the code is written either in ordinary Python or Java and not as mathematical equations.

For example, to do the "Some employees are qualified to do either role, but others can only be a cashier, or a restocker." constraint in the article, it would be written like this:

  def required_skill(constraint_factory: ConstraintFactory):
      return (constraint_factory.for_each(Shift)
              .filter(lambda shift: shift.required_skill not in shift.employee.skills)
              .penalize(HardSoftScore.ONE_HARD)
              .as_constraint("Missing required skill")
              )
Some examples taken from Timefold quickstarts:

- Employee scheduling (https://github.com/TimefoldAI/timefold-quickstarts/tree/stab...)

- Vehicle routing (https://github.com/TimefoldAI/timefold-quickstarts/tree/stab...)

- School timetabling (https://github.com/TimefoldAI/timefold-quickstarts/tree/stab...)

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

#29

Post by richardw »

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’m a long time coder but a bit rusty now. Last year I built a football team optimiser using Google’s OR tools (various optional constraints like being with friends and trying to balance skill levels across teams). LLM’s can go quite far in terms of getting you into the approximately correct direction fairly quickly. They fail right now at really getting it right but I was far enough that I could then take it the rest of the way.

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

#30

Post by i_don_t_know »

lloydatkinson wrote: post #27
mark_l_watson wrote: post #20

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.

Do you have a link to the Coursera course?

I believe Mark is referring to this series of three classes:

https://www.coursera.org/learn/basic-modeling

https://www.coursera.org/learn/advanced-modeling

https://www.coursera.org/learn/solving-algorithms-discrete-o...

They are indeed excellent and highly enjoyable.

Post reply on HN