Using OR-Tools CP-SAT for Scheduling Problems
atalaykutlay.com
Using OR-Tools CP-SAT for Scheduling Problems
1–10 of 31 posts
Re: Using OR-Tools CP-SAT for Scheduling Problems
#2In 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.
Re: Using OR-Tools CP-SAT for Scheduling Problems
#3In 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 h…
"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?
Re: Using OR-Tools CP-SAT for Scheduling Problems
#4In 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 h…
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.
Re: Using OR-Tools CP-SAT for Scheduling Problems
#5In 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 h…
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.
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.
Re: Using OR-Tools CP-SAT for Scheduling Problems
#6[deleted]
Re: Using OR-Tools CP-SAT for Scheduling Problems
#7I 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.
Re: Using OR-Tools CP-SAT for Scheduling Problems
#8Although 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).
Re: Using OR-Tools CP-SAT for Scheduling Problems
#9Although 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 li…
Interesting! Could you give example of problems you're using this for, to get an idea of where they'd be best suited?
Re: Using OR-Tools CP-SAT for Scheduling Problems
#10I'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 [2] https://www.usenix.org/system/files/osdi20-suresh.pdf