MetaBy Richard Barnes, Neeraj Kumar, Pol Mauri RuizAnnouncement
Meta has open-sourced Rebalancer, a generic library for solving assignment problems that has been used internally for over nine years. Rebalancer separates problem specification from solution, using a three-step approach with modeling constructs like dimensions, partitions, scopes, and utilization, and a high-level spec API for common objectives and constraints. Problems are translated into an expression graph, and Rebalancer offers two solving techniques: an optimal solver using mixed integer programming (MIP) with commercial or open-source solvers, and a local search solver that evaluates millions of moves per second for large-scale problems. The local search solver handles problems with over a million objects and 5k bins, with an average solve time of 171 seconds. Rebalancer is used for roughly 40 million assignment problems daily across Meta’s infrastructure, and the open-source release includes a debugging UI called Rebalancer Explorer. The accompanying paper was published at OSDI’24.
Assignment problems arise across Meta’s infrastructure, including hardware placement, service placement, task placement, and traffic routing. Practitioners struggle to translate real-life policies into precise mathematical formulas, and NP-hard problems cannot be solved efficiently by commercial solvers at scale.
Rebalancer separates problem specification from solution using a language of objects, bins, constraints, and objectives. It provides a three-step specification approach with modeling constructs (dimensions, partitions, scopes, utilization) and a high-level spec API. Problems are translated into an expression graph. Rebalancer offers two solving techniques: an optimal solver using mixed integer programming (MIP) with commercial or open-source solvers, and a local search solver that evaluates millions of moves per second. It also includes a debugging UI called Rebalancer Explorer.
Rebalancer separates problem specification from solution, using an expression graph and two solving techniques (optimal MIP and local search) to handle both small and large-scale problems.
The local search solver can handle problems with over a million objects and 5k bins, with an average solve time of 171 seconds, and evaluates millions of moves per second.
Rebalancer is used for roughly 40 million assignment problems daily across Meta’s infrastructure, with a P99 solve time of 12 seconds for problems with 265k objects and 3.2k bins.
Rebalancer offers an optimal solver using mixed integer programming (MIP) with commercial or open-source solvers, and a local search solver that evaluates millions of moves per second. The right technique depends on problem size and requirements.
Rebalancer's local search solver works directly on the expression graph, exploring moves with a neighborhood size O(|objects|+|bins|). It evaluates millions of moves per second and can handle problems with over a million objects.
Rebalancer includes Rebalancer Explorer, a Dockerized web UI that helps answer questions about binding constraints, the effect of relaxing constraints, and why an object was placed in a particular bin.
Summaries are generated from the original by a language model. Check the original before relying on it.
See the idea
A five-checkpoint workflow for assignment problems: write the spec, name the objective, test whether choices interact, pick a solver class by scale, then validate against live state.
Keep reading
The Good Stuff
Paid picks we use ourselves. Links carry a referral code — a subscription through one earns us a commission at no extra cost to you.
One useful email. Unsubscribe anytime.
