return to table of content

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

0cf8612b2e1e
15 replies
3d22h

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
7 replies
3d21h

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
6 replies
3d15h

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

cchianel
4 replies
3d12h

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

pbronez
3 replies
2d22h

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.

cchianel
2 replies
2d13h

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.

dcsan
1 replies
2d10h

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

cchianel
0 replies
1d22h

Does

  constraint_factory.create_from_chain(
      ForEach(Shift)
      | Filter(lambda shift: shift.required_skill not in shift.employee.skills)
      | Penalize(HardSoftScore.ONE_HARD)
      | AsConstraint("Missing required skill")
  )
Feel more Pythonic than

  (
      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")
  )

?

FredPret
0 replies
3d4h

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.

jmjrawlings
2 replies
3d13h

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.

stergios
0 replies
3d

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.

lloydatkinson
0 replies
3d12h

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.

dd82
1 replies
3d17h

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.

sirwhinesalot
0 replies
3d12h

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

wjholden
0 replies
3d19h

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.

richardw
0 replies
3d11h

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.

bartkappenburg
9 replies
3d23h

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
4 replies
3d23h

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.

tannhaeuser
0 replies
3d21h

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

flats
0 replies
3d23h

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) & Chat-GPT was a big help working out the details of some of the constraints and objectives.

bobim
0 replies
3d23h

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.

dualogy
0 replies
3d13h

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

akutlay
0 replies
3d16h

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___
3 replies
3d23h

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

taeric
0 replies
3d20h

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.

sirwhinesalot
0 replies
3d12h

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.

sevensor
0 replies
3d23h

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.

mark_l_watson
2 replies
3d15h

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.

lloydatkinson
1 replies
3d12h

Do you have a link to the Coursera course?

d_burfoot
2 replies
3d3h

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
0 replies
3d2h

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

jgalt212
0 replies
3d2h

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
1 replies
3d2h

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.

taeric
0 replies
3d20h

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