6 ms·

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

254 points by lfittl 2y ago

bartkappenburg 2y ago
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.
- Murky3515 2y ago
  >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.
  - bobim 2y ago
    I think that I would. Using natural language to describe the problem and constraints would be much better than figuring out mid project that the variable structure I've chosen does not allow to express a particular constraint. Defining the right structure is just Art at this point.
  - flats 2y ago
    They're already very good at it—I myself have been using OR-Tools's CP-SAT solver for a large bin packing problem at work (via https://github.com/ankane/or-tools-ruby https://github.com/ankane/or-tools-ruby) & Chat-GPT was a big help working out the details of some of the constraints and objectives.
  - ayhanfuat 2y ago
    It is indeed a very good fit. There is some cool research about it: https://github.com/skadio/ner4opt https://github.com/skadio/ner4opt
  - tannhaeuser 2y ago
    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).
- pjot 2y ago
  I used program called GAMS in mine. Its syntax structure is totally free form! https://www.gams.com/latest/docs/UG_GAMSPrograms.html#UG_GAMSPrograms_FormatOfGAMSInput https://www.gams.com/latest/docs/UG_GAMSPrograms.html#UG_GAM...
  - mncharity 2y ago
    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_GAMSPrograms_CommentsOutsideMargin https://www.gams.com/latest/docs/UG_GAMSPrograms.html#UG_GAM...
  - dualogy 2y ago
    Another "friendly syntax, multi-solver" approach is MiniZinc.org.
- akutlay 2y ago
  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.
richard___ 2y ago
How does this compare with mixed integer programming? For problems in physics
- sevensor 2y ago
  A whole bunch of problems can be set up either way. MILP always has an objective, and the constraints are always linear combinations of the decisions. Gurobi is so incredibly fast that it might be worth contorting your problem into a MILP just so you can get solutions at all.
- taeric 2y ago
  I would assume largely similarly? https://www.amazon.com/gp/product/1107658799/ 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.
- sirwhinesalot 2y ago
  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.
tociye9860 2y ago
[dead]
0cf8612b2e1e 2y ago
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.
- cchianel 2y ago
  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
  - Exuma 2y ago
    What’s a real world thing or two that this could solve vs writing code
    - cchianel 2y ago
      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/stable/python/employee-scheduling https://github.com/TimefoldAI/timefold-quickstarts/tree/stab...) - Vehicle routing (https://github.com/TimefoldAI/timefold-quickstarts/tree/stable/python/vehicle-routing https://github.com/TimefoldAI/timefold-quickstarts/tree/stab...) - School timetabling (https://github.com/TimefoldAI/timefold-quickstarts/tree/stable/python/school-timetabling https://github.com/TimefoldAI/timefold-quickstarts/tree/stab...)
taeric 2y ago
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.)
mark_l_watson 2y ago
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-with-minizinc-and-python 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.
- lloydatkinson 2y ago
  Do you have a link to the Coursera course?
  - i_don_t_know 2y ago
    I believe Mark is referring to this series of three classes: https://www.coursera.org/learn/basic-modeling https://www.coursera.org/learn/basic-modeling https://www.coursera.org/learn/advanced-modeling https://www.coursera.org/learn/advanced-modeling https://www.coursera.org/learn/solving-algorithms-discrete-optimization https://www.coursera.org/learn/solving-algorithms-discrete-o... They are indeed excellent and highly enjoyable.
d_burfoot 2y ago
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.
- turndown 2y ago
  I can guarantee you a blog post detailing how to do this would go triple platinum
- jgalt212 2y ago
  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
Elucalidavah 2y ago
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.
- cpa 2y ago
  It's quite niche but it exists: https://en.wikipedia.org/wiki/Geometric_constraint_solving https://en.wikipedia.org/wiki/Geometric_constraint_solving

254 points by lfittl 2y ago

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.

Murky3515 2y ago
>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.
- bobim 2y ago
  I think that I would. Using natural language to describe the problem and constraints would be much better than figuring out mid project that the variable structure I've chosen does not allow to express a particular constraint. Defining the right structure is just Art at this point.
- flats 2y ago
  They're already very good at it—I myself have been using OR-Tools's CP-SAT solver for a large bin packing problem at work (via https://github.com/ankane/or-tools-ruby https://github.com/ankane/or-tools-ruby) & Chat-GPT was a big help working out the details of some of the constraints and objectives.
- ayhanfuat 2y ago
  It is indeed a very good fit. There is some cool research about it: https://github.com/skadio/ner4opt https://github.com/skadio/ner4opt
- tannhaeuser 2y ago
  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).
pjot 2y ago
I used program called GAMS in mine. Its syntax structure is totally free form! https://www.gams.com/latest/docs/UG_GAMSPrograms.html#UG_GAMSPrograms_FormatOfGAMSInput https://www.gams.com/latest/docs/UG_GAMSPrograms.html#UG_GAM...
- mncharity 2y ago
  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_GAMSPrograms_CommentsOutsideMargin https://www.gams.com/latest/docs/UG_GAMSPrograms.html#UG_GAM...
- dualogy 2y ago
  Another "friendly syntax, multi-solver" approach is MiniZinc.org.
akutlay 2y ago
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.

richard___ 2y ago

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

sevensor 2y ago
A whole bunch of problems can be set up either way. MILP always has an objective, and the constraints are always linear combinations of the decisions. Gurobi is so incredibly fast that it might be worth contorting your problem into a MILP just so you can get solutions at all.
taeric 2y ago
I would assume largely similarly? https://www.amazon.com/gp/product/1107658799/ 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.
sirwhinesalot 2y ago
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.

tociye9860 2y ago

[dead]

0cf8612b2e1e 2y ago

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.

cchianel 2y ago
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
- Exuma 2y ago
  What’s a real world thing or two that this could solve vs writing code
  - cchianel 2y ago
    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/stable/python/employee-scheduling https://github.com/TimefoldAI/timefold-quickstarts/tree/stab...) - Vehicle routing (https://github.com/TimefoldAI/timefold-quickstarts/tree/stable/python/vehicle-routing https://github.com/TimefoldAI/timefold-quickstarts/tree/stab...) - School timetabling (https://github.com/TimefoldAI/timefold-quickstarts/tree/stable/python/school-timetabling https://github.com/TimefoldAI/timefold-quickstarts/tree/stab...)

taeric 2y ago

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

mark_l_watson 2y ago

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-with-minizinc-and-python 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.

lloydatkinson 2y ago
Do you have a link to the Coursera course?
- i_don_t_know 2y ago
  I believe Mark is referring to this series of three classes: https://www.coursera.org/learn/basic-modeling https://www.coursera.org/learn/basic-modeling https://www.coursera.org/learn/advanced-modeling https://www.coursera.org/learn/advanced-modeling https://www.coursera.org/learn/solving-algorithms-discrete-optimization https://www.coursera.org/learn/solving-algorithms-discrete-o... They are indeed excellent and highly enjoyable.

d_burfoot 2y ago

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.

turndown 2y ago
I can guarantee you a blog post detailing how to do this would go triple platinum
jgalt212 2y ago
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

Elucalidavah 2y ago

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.

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