3 ms·

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 l

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.

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.