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
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.
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.
I’d definitely be interested in that.
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.
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.)
MiniZinc is a constraint programming system. There is a good Coursera class using MiniZinc.
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.
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.
Its syntax structure is totally free form!
https://www.gams.com/latest/docs/UG_GAMSPrograms.html#UG_GAM...
[1] https://www.gams.com/latest/docs/UG_GAMSPrograms.html#UG_GAM...
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.
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
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.
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.
