[HN Gopher] A practical introduction to constraint programming u...
___________________________________________________________________
A practical introduction to constraint programming using CP-SAT and
Python
Author : lfittl
Score : 134 points
Date : 2024-07-03 16:48 UTC (6 hours ago)
(HTM) web link (pganalyze.com)
(TXT) w3m dump (pganalyze.com)
| bartkappenburg wrote:
| 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 wrote:
| >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 wrote:
| 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 wrote:
| 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.
| ayhanfuat wrote:
| It is indeed a very good fit. There is some cool research
| about it: https://github.com/skadio/ner4opt
| tannhaeuser wrote:
| 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 wrote:
| 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...
| richard___ wrote:
| How does this compare with mixed integer programming? For
| problems in physics
| sevensor wrote:
| 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 wrote:
| 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.
| 0cf8612b2e1e wrote:
| 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 wrote:
| 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
| taeric wrote:
| 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.)
___________________________________________________________________
(page generated 2024-07-03 23:00 UTC)