Meta open-sources Rebalancer, a library for assignment problems

Meta open-sources Rebalancer

Meta has released Rebalancer under the Apache 2.0 license. The library solves assignment problems: given sets of objects and bins, it finds the assignment that satisfies constraints while optimizing specified objectives. Meta says the solver has been used inside the company for more than nine years.

The release includes the facebook/rebalancer GitHub repository, documentation, a PyPI package, and Rebalancer Explorer, a Dockerized UI for debugging solver behavior.

One library, many assignment problems

The same formulation appears at several layers of Meta's stack: racks are placed in datacenters to spread them across electrical fault domains within power and cooling limits; servers are assigned to services to improve fault tolerance and packing efficiency; and user traffic is routed across distributed datacenters to balance latency and load.

Rebalancer addresses the two obstacles that usually block reusable optimization frameworks: usability and scalability. Instead of translating policies into formulas by hand, engineers describe a problem with objects, bins, constraints, and objectives; Rebalancer turns that description into a directed acyclic graph, an expression graph. Specs such as CapacitySpec, GroupCountSpec, and BalanceSpec turn recurring goals into reusable recipes.

Optimal solver and local search

The optimal solver translates the graph into a mixed integer program for FICO Xpress, Gurobi, or HiGHS, shrinking it with variable aggregation and symmetry breaking. The worst-case model size still grows as objects times bins, so the largest problems are beyond any MIP solver.

The local search solver works directly on the graph, exploring moves of objects between bins. Its neighborhood grows only with the sum of objects and bins, and millions of evaluations per second are possible, so at Meta almost all large-scale problems use local search.

Scale at Meta, and beyond

Meta says Rebalancer solves roughly 40 million assignment problems a day across more than 30 formulations. The P99 solve time is 12 seconds on a problem with 265,000 objects and 3,200 bins; above 1 million objects and 5,000 bins the average solve time is 171 seconds, across more than 3,400 runs.

Outside infrastructure it has been used to assign meetings to rooms, route support tickets to engineers, and optimize desk placements. Meta notes such problems are common in healthcare, energy, logistics, and education.