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

31–40 of 41 posts

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

#31

Post by FredPret »

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

Knapsack problems, some simple scheduling problems, even the travelling salesman problem.

Many problems in business and manufacturing fit this bill. Optimal product mix, optimal routing, choosing the best spot for a warehouse, scheduling employees, constructing an investment protfolio, coming up with a diet that fits certain criteria, etc.

I even remember a practice problem from uni where we had to optimally distribute songs on two sides of a tape album (it was an old professor), satisfying constraints such as “each side should have a ballad” and “each side has at most x minutes of running time”.

You can do this with regular coding too, but if you can easily construct a certain kind of mathematical model of your problem, you can easily solve it with linear programming.

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

#32

Post by d_burfoot »

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.

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

#33

Post by turndown »

d_burfoot wrote: post #32

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.

I can guarantee you a blog post detailing how to do this would go triple platinum

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

#34

Post by jgalt212 »

d_burfoot wrote: post #32

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.

yep, once you have the data, constraints, and utility functions properly* in the system you can brute force your way to many good enough solutions very quickly.

I coach a basketball league that has 8 periods. No player can play 2 more periods that any other player. The number of possible line-ups per game while still hitting the playing time contraint is astronomical. Very easy to find a series line-ups that fits the constraint, but very hard to find an optimal or near-optimal series of line-ups. It gets even more fun when you have to adjust for late arrivals or unannounced no-shows.

* not always completely doable

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

#35

Post by Elucalidavah »

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.

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

#36

Post by cpa »

Elucalidavah wrote: post #35

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.

It's quite niche but it exists: https://en.wikipedia.org/wiki/Geometric_constraint_solving

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

#37

Post by stergios »

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…

If you want to get better at mathematical modelling in general I recommend a traditional text book dedicated to modeling, like the 11th edition of "Introduction to Operations Research" by Hillier and Lieberman.

As for the "mathematical equations" referred to by a parent, we're talking linear algebraic equations with perhaps a 2nd order term thrown in for quadratic models. I think these should be within the grasp of someone who wants to delve into the topic, and if not perhaps it's a good place to start dig deeper.

edited to be less of a prick.

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

#38

Post by pbronez »

cchianel wrote: post #28
Exuma wrote: post #21

Earlier quoted context omitted.

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

Great to see this math being made more accessible!

The Python examples seem to have a very strong Java smell. That might just be my prefer for functional styles over OOP styles though.

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

#39

Post by cchianel »

pbronez wrote: post #38
cchianel wrote: post #28

Earlier quoted context omitted.

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

Great to see this math being made more accessible! The Python examples seem to have a very strong Java smell. That might just be my prefer for functional styles over OOP styles though.

Let us know how we can improve! Feel free to start a discussion (https://github.com/TimefoldAI/timefold-solver/discussions) or submit an issue (https://github.com/TimefoldAI/timefold-solver-python/issues).

We aim to treat Python as a first-class citizen (while keeping it maintainable). For instance, many of the Java methods are mapped to properties on the Python classes with more Pythonic names (see `ScoreExplanation` for an example).

I suspect what gives the Java smell is probably the `SolverFactory`/`SolverConfig`, which is a lot of boilerplate code. A lot of the code can be generated, although we would need to design an API for that.

The fluent (method chaining) API might also be giving the Java smell; I don't see many fluent API being used in Python. In particular, needing to either end lines with `\` or surround the statement with brackets make long fluent chains annoying to use. This is harder to change, since there is no Pythonic alternative that I know of for method chaining.

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

#40

Post by dcsan »

cchianel wrote: post #39
pbronez wrote: post #38

Earlier quoted context omitted.

Great to see this math being made more accessible! The Python examples seem to have a very strong Java smell. That might just be my prefer for functional styles over OOP styles though.

Let us know how we can improve! Feel free to start a discussion ( https://github.com/TimefoldAI/timefold-solver/discussions ) or submit an issue ( https://github.com/TimefoldAI/timefold-solver-python/issues ). We aim to treat Python as a first-class citizen (while keeping it maintainable). For instance, many of the Java methods are mapped to properties on the Python classes with more Pythonic names (see `ScoreExplana…

Langchain did something overloading the | or operator in their LCEL DSL to form LLM pipelines. It feels like abusing python but it's familiar enough as a Unix syntax
Post reply on HN