4 ms·

Using OR-Tools CP-SAT for Scheduling Problems

87 points by akutlay 5mo ago

asdfasgasdgasdg 5mo ago
In a past life we used OR-Tools for a problem of assigning data shards to serving tasks, where the data shards had heterogenous demands (e.g. some shards were low traffic but demanded sub millisecond latency targets and thus were served from RAM, others were higher traffic but could tolerate being served from flash, etc.). It's insane how expressive this thing is! But the problem got to be so large that we ended up having to hand-roll something less optimal because it would take multiple minutes to generate assignments -- think: millions of shards, tens of thousands of serving tasks, and I want to say it was ultimately nine dimensions of constraints.
- Filligree 5mo ago
  "Multiple minutes" doesn't sound like a lot. With millions of shards, do you really need to regenerate the assignment layout every couple of minutes?
  - asdfasgasdgasdg 5mo ago
    It's important to get it done reasonably quickly because the disks at the time were ephemeral, so how quickly we could solve the problem effectively limited our rolling restart rate.
- akutlay 5mo ago
  You may have tried this already but often times systems require things to be sticky (ex: to increase caching efficiency) and that usually helps solving large problems since most solvers accept "hints" or "warm starts". CP-SAT does a great job accepting hints and cuts down the search time significantly if the hint is good.
  - driscoll42 5mo ago
    Several tools similar also can take in previous starts that are partially correct and use them to get closer. For my work, I am finding the local-mip package great for finding primal solutions better than CP-SAT, and then using HiGHS for my branch & bounder a great combination and feeding the results from local-mip to HiGHS. I do wish more tools could take in branching prioritizations or hints, I tried SCIOPT and it just didn't work as well as HiGHS even with priorization.
  - lsuresh 5mo ago
    When I last used it for such use cases, it was better to decompose the problem into something incremental (so fixed placements become constants). Most of the latencies we saw were spent in the presolve phase which scaled with overall input size.
deleted 5mo ago
[deleted]
sobellian 5mo ago
I use CP-SAT for automated design problems. I need a guarantee on solution quality, so gen AI is a nonstarter. The problem formulation is quite messy and has constraints that can vary by locale. CP-SAT handles it pretty well. The one thing I've been trying to model well are cover constraints where for each x : xs, there is some y : ys st. pred(x, y). I've tried both boolean matrices and index constraints, and they work but seem to be quite taxing on the solver. Maybe there's a better formulation.
- ibejoeb 5mo ago
  Is it a geometric problem, like every point must reside within the plane? Are you optimizing also, like finding the smallest bounding box that includes the most points? You can usually express these as global constraints, like non-overlapping intervals, or you can use these to precompute feasible candidates rather than manually encoding giant matrices that contain knowable bad values.
  - sobellian 5mo ago
    It is a geometric problem. I do have no-overlap constraints, but the cover constraints relate to topology and scheduling. High level, I am taking a rectangle and generating a set of guillotine cuts. I have a list of locations that must lie on a guillotine cut. Some locations are known a priori, some are optimization variables. I have a hierarchical objective which in the end includes minimizing #cuts and material (length of each cut x a density associated with each cut according to several constraints).
- jkaptur 5mo ago
  I’m not an expert here, but it sounds like you’re forcing a first-order logic problem into a propositional logic box. A “native” first-order logic solver like Z3 might be something to try.
cchianel 5mo ago
Although this post discusses Constraint Programming - Satisfiability (CP-SAT) Solvers and Mixed Integer Problem (MIP) Solvers, it does not discuss Metaheuristic Solvers. Metaheuristic solvers are different in that you don't need to model your problem as a mixed integer problem. Instead, all it cares about is having a function that returns something you can compare. This allows you to model your problem however you like. Some metaheurstic techniques include Simulated Annealing, Late Acceptance Local Search, and Tabu Search. Metaheuristic solvers may not generate optimal solutions (after all, by their nature, they don't know the structure of the problem), but they generate "good enough" and "close to optimal" solutions. Metaheurstic solvers tends to beat MIP and CP-SAT for VRP, whereas MIP and CP-SAT are better for bin packing. If you want to try using a Metaheuristic solver, I can recommend Timefold, which allows you to define your constraints using your domain objects in an incremental matter (it has SQL/Java-Streams like syntax, which in my opinion, is more readable than formulas) (disclosure: I work for Timefold).
- oulipo2 5mo ago
  Interesting! Could you give example of problems you're using this for, to get an idea of where they'd be best suited?
  - nickpsecurity 5mo ago
    If I understand them correctly, they're saying to use standard, optimization methods after writing a fitness or evaluation function to score your possible solutions. Which is a normal, non-SAT way of doing optimization. So, you could use it for any application you saw benefit from genetic algorithms, simulated annealing, or tabu search. You can even use those to optimize neural networks without backpropagation and with fewer, local optima. Many papers on this but it's computationally heavier.
  - LPisGood 5mo ago
    Metaheuristics (for example, genetic algorithms) are applicable for any type of optimization problem, but especially those which are non-linear in nature. Modern mixed integer linear program solvers are impressively good, but the less linear a problem is, the harder it is to model as a MIP. One practical consideration often ignored is difficulty of implementation. To make a MIP model, you only have the tools of linear programming: equations and linear inequalities, like mx >= y. If you want a MIP, you need to write down ALL aspects of your problem as a list of inequalities, which can be difficult for some real world domains. There is a real art to MIP modeling. On the other hand, metaheuristics are like an interface where you only need to implement a few functions in plain old code and you can get good answers. It’s not quite that simple, since there is still an art to modeling a problem in a suitable input format for a meta heuristic (for example in genetic algorithm, how do I write my delivery schedule as a genome?), but the upshot is that it doesn’t have to be a mathematically precise formulation to work correctly.
lsuresh 5mo ago
I'm a big fan of the CP-SAT solver. It was a remarkable piece of tech to learn about (especially Peter Stuckey's talks on lazy clause generation [1]). I'd used it in a past life to build a Kubernetes scheduler [2] and tackle some cluster management problems. [1] https://www.youtube.com/watch?v=lxiCHRFNgno https://www.youtube.com/watch?v=lxiCHRFNgno [2] https://www.usenix.org/system/files/osdi20-suresh.pdf https://www.usenix.org/system/files/osdi20-suresh.pdf
__MatrixMan__ 5mo ago
I didn't consider SAT solvers to be AI, but searching for "ortools" points to https://developers.google.com/optimization https://developers.google.com/optimization which has a big "Google AI" indicator on it. Who cares, I thought. But certain managers are now very keen on making a lot of noise about just how effectively their teams are using AI. So I took my four python scripts which together form a pipeline that solves a scheduling problem with OR-Tools and renamed my README.md to skill.md so agents would think it was for them. The LLM does pretty much nothing except run the commands in order, CP-SAT does the real work and is being confused for AI. Yet when I demoed it people were like: > wow, neat, look at what's now possible in this dawning age of AI I've not bothered to tell them that it's 1960's technology and that the AI part of it could also be adequately performed by a README with less than 100 words. I guess everything that the managers haven't heard of is now "AI" and golly look how effectively we're all using it.
- LPisGood 5mo ago
  SAT solving, constraint programming, and (integer) linear programming are absolutely AI. These are techniques that let computers make smart decisions. Maybe they’re not AI in the way you’ve heard marketing teams use it recently, but they are artificial intelligence nonetheless. If you open any AI textbook written before 2022 there is almost surely a chapter on these methods (c.f. Russel and Norvig’s Artificial Intelligence: A Modern Approach).
  - __MatrixMan__ 5mo ago
    I must've missed that part when I encountered them at university, but I'm happy to have been wrong. I like these things and now apparently the world wants to give me time to brush up on them.
  - IanCal 5mo ago
    Strongly seconded (I studied this in 2005-2009). I don’t think there’s a brilliantly defined line between AI and not AI but it’s relatively key that you define a problem and something else then figures out a solution. Lots of things like shortest path using a* is AI for example. You don’t even need to get to a fuzzy point to consider something AI. I don’t think people appreciate just how general LLMs are, and how incredibly narrow even the broadest AI systems were really not that long ago.
deleted 5mo ago
[deleted]
thisisauserid 5mo ago
When you have 50 technicians going to 500 sites, that is not a Traveling Salesman Problem. It might seem like a Vehicle Routing Problem but it isn't that either. Batch a cheap process at night that runs CP-SAT solution. If someone calls in sick, be prepared to run it again with more horsepower so you can update it.
marcta 5mo ago
The CP-SAT primer by Dr. Dominik Krupke is excellent for working with OR-Tools: https://d-krupke.github.io/cpsat-primer https://d-krupke.github.io/cpsat-primer

87 points by akutlay 5mo ago

In a past life we used OR-Tools for a problem of assigning data shards to serving tasks, where the data shards had heterogenous demands (e.g. some shards were low traffic but demanded sub millisecond latency targets and thus were served from RAM, others were higher traffic but could tolerate being served from flash, etc.). It's insane how expressive this thing is! But the problem got to be so large that we ended up having to hand-roll something less optimal because it would take multiple minutes to generate assignments -- think: millions of shards, tens of thousands of serving tasks, and I want to say it was ultimately nine dimensions of constraints.

Filligree 5mo ago
"Multiple minutes" doesn't sound like a lot. With millions of shards, do you really need to regenerate the assignment layout every couple of minutes?
- asdfasgasdgasdg 5mo ago
  It's important to get it done reasonably quickly because the disks at the time were ephemeral, so how quickly we could solve the problem effectively limited our rolling restart rate.
akutlay 5mo ago
You may have tried this already but often times systems require things to be sticky (ex: to increase caching efficiency) and that usually helps solving large problems since most solvers accept "hints" or "warm starts". CP-SAT does a great job accepting hints and cuts down the search time significantly if the hint is good.
- driscoll42 5mo ago
  Several tools similar also can take in previous starts that are partially correct and use them to get closer. For my work, I am finding the local-mip package great for finding primal solutions better than CP-SAT, and then using HiGHS for my branch & bounder a great combination and feeding the results from local-mip to HiGHS. I do wish more tools could take in branching prioritizations or hints, I tried SCIOPT and it just didn't work as well as HiGHS even with priorization.
- lsuresh 5mo ago
  When I last used it for such use cases, it was better to decompose the problem into something incremental (so fixed placements become constants). Most of the latencies we saw were spent in the presolve phase which scaled with overall input size.

deleted 5mo ago

[deleted]

sobellian 5mo ago

I use CP-SAT for automated design problems. I need a guarantee on solution quality, so gen AI is a nonstarter. The problem formulation is quite messy and has constraints that can vary by locale. CP-SAT handles it pretty well. The one thing I've been trying to model well are cover constraints where for each x : xs, there is some y : ys st. pred(x, y). I've tried both boolean matrices and index constraints, and they work but seem to be quite taxing on the solver. Maybe there's a better formulation.

ibejoeb 5mo ago
Is it a geometric problem, like every point must reside within the plane? Are you optimizing also, like finding the smallest bounding box that includes the most points? You can usually express these as global constraints, like non-overlapping intervals, or you can use these to precompute feasible candidates rather than manually encoding giant matrices that contain knowable bad values.
- sobellian 5mo ago
  It is a geometric problem. I do have no-overlap constraints, but the cover constraints relate to topology and scheduling. High level, I am taking a rectangle and generating a set of guillotine cuts. I have a list of locations that must lie on a guillotine cut. Some locations are known a priori, some are optimization variables. I have a hierarchical objective which in the end includes minimizing #cuts and material (length of each cut x a density associated with each cut according to several constraints).
jkaptur 5mo ago
I’m not an expert here, but it sounds like you’re forcing a first-order logic problem into a propositional logic box. A “native” first-order logic solver like Z3 might be something to try.

cchianel 5mo ago

Although this post discusses Constraint Programming - Satisfiability (CP-SAT) Solvers and Mixed Integer Problem (MIP) Solvers, it does not discuss Metaheuristic Solvers. Metaheuristic solvers are different in that you don't need to model your problem as a mixed integer problem. Instead, all it cares about is having a function that returns something you can compare. This allows you to model your problem however you like. Some metaheurstic techniques include Simulated Annealing, Late Acceptance Local Search, and Tabu Search. Metaheuristic solvers may not generate optimal solutions (after all, by their nature, they don't know the structure of the problem), but they generate "good enough" and "close to optimal" solutions. Metaheurstic solvers tends to beat MIP and CP-SAT for VRP, whereas MIP and CP-SAT are better for bin packing. If you want to try using a Metaheuristic solver, I can recommend Timefold, which allows you to define your constraints using your domain objects in an incremental matter (it has SQL/Java-Streams like syntax, which in my opinion, is more readable than formulas) (disclosure: I work for Timefold).

oulipo2 5mo ago
Interesting! Could you give example of problems you're using this for, to get an idea of where they'd be best suited?
- nickpsecurity 5mo ago
  If I understand them correctly, they're saying to use standard, optimization methods after writing a fitness or evaluation function to score your possible solutions. Which is a normal, non-SAT way of doing optimization. So, you could use it for any application you saw benefit from genetic algorithms, simulated annealing, or tabu search. You can even use those to optimize neural networks without backpropagation and with fewer, local optima. Many papers on this but it's computationally heavier.
- LPisGood 5mo ago
  Metaheuristics (for example, genetic algorithms) are applicable for any type of optimization problem, but especially those which are non-linear in nature. Modern mixed integer linear program solvers are impressively good, but the less linear a problem is, the harder it is to model as a MIP. One practical consideration often ignored is difficulty of implementation. To make a MIP model, you only have the tools of linear programming: equations and linear inequalities, like mx >= y. If you want a MIP, you need to write down ALL aspects of your problem as a list of inequalities, which can be difficult for some real world domains. There is a real art to MIP modeling. On the other hand, metaheuristics are like an interface where you only need to implement a few functions in plain old code and you can get good answers. It’s not quite that simple, since there is still an art to modeling a problem in a suitable input format for a meta heuristic (for example in genetic algorithm, how do I write my delivery schedule as a genome?), but the upshot is that it doesn’t have to be a mathematically precise formulation to work correctly.

lsuresh 5mo ago

I'm a big fan of the CP-SAT solver. It was a remarkable piece of tech to learn about (especially Peter Stuckey's talks on lazy clause generation [1]). I'd used it in a past life to build a Kubernetes scheduler [2] and tackle some cluster management problems. [1] https://www.youtube.com/watch?v=lxiCHRFNgno https://www.youtube.com/watch?v=lxiCHRFNgno [2] https://www.usenix.org/system/files/osdi20-suresh.pdf https://www.usenix.org/system/files/osdi20-suresh.pdf

__MatrixMan__ 5mo ago

I didn't consider SAT solvers to be AI, but searching for "ortools" points to https://developers.google.com/optimization https://developers.google.com/optimization which has a big "Google AI" indicator on it. Who cares, I thought. But certain managers are now very keen on making a lot of noise about just how effectively their teams are using AI. So I took my four python scripts which together form a pipeline that solves a scheduling problem with OR-Tools and renamed my README.md to skill.md so agents would think it was for them. The LLM does pretty much nothing except run the commands in order, CP-SAT does the real work and is being confused for AI. Yet when I demoed it people were like: > wow, neat, look at what's now possible in this dawning age of AI I've not bothered to tell them that it's 1960's technology and that the AI part of it could also be adequately performed by a README with less than 100 words. I guess everything that the managers haven't heard of is now "AI" and golly look how effectively we're all using it.

LPisGood 5mo ago
SAT solving, constraint programming, and (integer) linear programming are absolutely AI. These are techniques that let computers make smart decisions. Maybe they’re not AI in the way you’ve heard marketing teams use it recently, but they are artificial intelligence nonetheless. If you open any AI textbook written before 2022 there is almost surely a chapter on these methods (c.f. Russel and Norvig’s Artificial Intelligence: A Modern Approach).
- __MatrixMan__ 5mo ago
  I must've missed that part when I encountered them at university, but I'm happy to have been wrong. I like these things and now apparently the world wants to give me time to brush up on them.
- IanCal 5mo ago
  Strongly seconded (I studied this in 2005-2009). I don’t think there’s a brilliantly defined line between AI and not AI but it’s relatively key that you define a problem and something else then figures out a solution. Lots of things like shortest path using a* is AI for example. You don’t even need to get to a fuzzy point to consider something AI. I don’t think people appreciate just how general LLMs are, and how incredibly narrow even the broadest AI systems were really not that long ago.

deleted 5mo ago

[deleted]

thisisauserid 5mo ago

When you have 50 technicians going to 500 sites, that is not a Traveling Salesman Problem. It might seem like a Vehicle Routing Problem but it isn't that either. Batch a cheap process at night that runs CP-SAT solution. If someone calls in sick, be prepared to run it again with more horsepower so you can update it.

marcta 5mo ago

The CP-SAT primer by Dr. Dominik Krupke is excellent for working with OR-Tools: https://d-krupke.github.io/cpsat-primer https://d-krupke.github.io/cpsat-primer