Meta Engineering (AI) has open-sourced Rebalancer, a high-performance library designed to solve assignment problems. This tool has been used internally at Meta for over nine years to manage resource allocation across its infrastructure stack.
Key Points
- Rebalancer separates concerns such as problem specification, efficient memory storage, solving, and debugging.
- It addresses usability and scalability challenges in optimization by providing a language to describe problems using objects, bins, constraints, and objectives.
- The library transforms problem descriptions into a directed-acyclic graph, known as an expression graph.
- Rebalancer can design a local search heuristic or build a mixed integer program (MIP) solvable by commercial solvers like FICO Xpress or Gurobi, or the open-source solver HiGHS.
- Its specification language uses a three-step approach to incrementally raise the level of abstraction for ease of use.
- Rebalancer offers two solving techniques: an Optimal Solver for small to mid-size problems and a Local Search Solver for large-scale problems.
- The Local Search Solver works directly on the expression graph, exploring local neighborhoods with a worst-case size of O(|objects|+|bins|).
Context
According to Meta Engineering (AI), assignment problems involve allocating objects to bins while optimizing objectives and meeting constraints. These problems arise across all layers of Meta's infrastructure. The main challenges in creating a reusable framework for such problems are usability, due to the difficulty of translating real-life policies into mathematical formulas, and scalability, as many are NP-hard and cannot be efficiently solved by commercial solvers.
Why It Matters
This release provides builders with a proven tool for tackling complex resource allocation and assignment problems, offering both optimal and scalable local search solutions. It could simplify the process of defining and solving optimization challenges that previously required extensive mathematical formulation or custom solver development.
What To Do
- Review the Rebalancer documentation for an exhaustive list of available specifications.
- Consider Rebalancer's two distinct solving techniques, Optimal Solver and Local Search Solver, to determine which best fits the scale and time requirements of your assignment problems.
- Note how Rebalancer uses variable aggregation, interchangeability, and symmetry breaking to reduce MIP model sizes.
- Test the Local Search Solver for large-scale problems, as Meta uses it for almost all of its own large-scale applications.