# Meta Open-Sources Rebalancer: A Production-Grade Assignment Solver for Large-Scale Resource Allocation
## What Is Rebalancer?
Rebalancer is an open-source optimization library developed internally at Meta and now released publicly under the Apache 2.0 license. It is designed to solve **assignment problems** — the fundamental challenge of deciding which objects belong in which bins when subject to constraints and optimization objectives. The library is written in C++ and exposes a Python interface, making it accessible to a wide range of engineers and researchers. It has been in active production use at Meta for over nine years, handling billions of resource allocation decisions across the company’s infrastructure.
The project ships as version 1.0.4 on PyPI, with prebuilt wheels available for Linux x86-64 and macOS 14+ ARM64 architectures. Installation is straightforward via `pip install rebalancer`. Additional packaging formats include .deb and .rpm packages for Debian-based and Red Hat-based Linux distributions, as well as a Homebrew package for macOS users. The project is currently classified as Alpha on PyPI. A companion debugging tool called **Rebalancer Explorer** is also available as a Dockerized web interface.
—
## The Assignment Problem at Scale
Assignment problems appear throughout modern computing infrastructure. Racks must be assigned to data centers, servers must be allocated to services, individual computational tasks must be placed onto servers, and user traffic must be routed across geographic regions. These problems share a common structure: a set of objects with specific resource requirements must be mapped to a set of containers (bins) that have finite capacity, while simultaneously satisfying constraints like replication rules, affinity policies, or load balancing targets.
Meta identified two major obstacles that had historically made these problems difficult to solve in practice. First, translating high-level engineering policies into precise mathematical formulations was cumbersome and error-prone. Second, many of these problems are NP-hard, meaning they become computationally intractable as the number of objects and bins grows — far exceeding the capacity of many commercial optimization solvers.
Rebalancer addresses both challenges by introducing a clean separation between **how a problem is specified** and **how it is solved**. This two-layer architecture lets modelers focus on describing what they want rather than wrestling with solver internals.
—
## How the Specification Layer Works
The specification system is built on three conceptual layers:
**Modeling constructs** provide the building blocks for describing a problem. Dimensions represent attributes such as CPU capacity, memory, or storage. Partitions group individual objects together. Scopes define groups of bins that share a common context. Utilization captures how much of a given resource is consumed.
**The Expression API** allows users to aggregate and transform utilization values. Operations like SUM and MAX compute aggregate statistics across a set of objects, while transformations like SQUARE or NORMALIZE modify the values in mathematically meaningful ways.
**The Spec API** offers dozens of predefined objectives and constraints that cover the most common patterns seen in production systems. Each constraint and objective is a reusable component that can be combined with others to build complex formulations.
To illustrate, consider a task placement scenario where tasks are modeled as objects, servers as bins, and racks as scopes. A `CapacitySpec` enforces that no server exceeds its CPU and storage limits. A `GroupCountSpec` ensures that only one job type is placed per rack. A `BalanceSpec` minimizes the variance of utilization across servers, spreading load evenly across both CPU and storage dimensions. This declarative approach means the modeler describes the policy in terms engineers understand, and the system translates it into something a solver can execute.
—
## The Solving Architecture: Expression Graph and Two Solvers
Once a specification is defined, Rebalancer compiles it into a **directed acyclic expression graph**. Leaf nodes represent the utilization values of individual bins. Above them sit aggregation and transformation nodes that compute derived quantities like sums, maximums, or squared values. The user provides an initial assignment and a stopping condition, and any constraints already violated by the initial state are promoted to high-priority goals.
Rebalancer offers two distinct solving strategies, and the same expression graph feeds both of them.
### Optimal Solver (Mixed Integer Programming)
The expression graph is translated into a mixed integer program (MIP) and passed to one of three supported backends: FICO Xpress, Gurobi, or the open-source HiGHS solver. Meta applies several techniques to keep the model tractable, including variable aggregation and symmetry breaking. The theoretical worst-case model size grows proportionally to the product of objects and bins — O(objects × bins). For the largest problems Meta encounters, even these optimizations are insufficient for MIP solvers to find solutions in reasonable time.
### Local Search Solver
The local search solver operates directly on the expression graph without translating it into a MIP. It explores candidate moves — reassigning individual objects from one bin to another — and evaluates each move using the expression graph’s current state. The worst-case neighborhood size is O(objects + bins), which is dramatically smaller than the MIP formulation. Moves are evaluated in parallel, enabling millions of evaluations per second, and the search space is aggressively pruned to avoid redundant exploration.
Meta’s production pattern is to use local search for the vast majority of large-scale problems and reserve MIP for small-to-medium instances, often prototyping with MIP first to establish a baseline before migrating to local search for production workloads.
—
## Production Numbers at Meta
The scale at which Rebalancer operates is substantial:
– Approximately **40 million assignment problems** are solved per day across more than 30 unique problem formulations.
– The **P99 solve time** is **12 seconds** for problems involving 265,000 objects distributed across 3,200 bins.
– Problems exceeding **1 million objects** and **5,000 bins** average **171 seconds** to solve, drawn from over 3,400 recorded runs.
These numbers demonstrate that Rebalancer is not merely a research prototype — it is a battle-tested system running at hyperscale, making real-time allocation decisions that affect Meta’s global infrastructure.
—
## Best Use Cases for Rebalancer
Rebalancer is designed for any domain where objects must be assigned to containers under capacity and policy constraints. The most common patterns observed at Meta include:
### 1. Cluster Task Placement
Assigning shards, containers, or computational tasks to servers while respecting CPU and memory limits and ensuring replicas are spread across different racks for fault tolerance. This pattern powers Meta’s Shard Manager and Resource Allocation Service (RAS).
### 2. Traffic and Workload Balancing Across Regions
Routing user requests or batch jobs to data centers, trading off latency against server load. Meta uses this pattern in its Taiji system for edge traffic and for distributing machine learning training workloads by priority.
### 3. Operational and Business Assignments
Beyond infrastructure, the same framework maps support tickets to engineers, schedules meetings to rooms, or assigns desks to people — all under capacity and policy rules. Meta has applied Rebalancer to all three of these operational patterns.
—
## Debugging With Rebalancer Explorer
Because the process of tuning solver behavior is complex and iterative, Meta built **Rebalancer Explorer** — a Dockerized web-based user interface designed specifically for modelers debugging their specifications. It visualizes which constraints are actively binding, how relaxing a constraint affects the solution, and why a particular object ended up in a particular bin. This tool has significantly reduced the time engineers spend diagnosing why a solver is producing unexpected assignments.
—
## Comparison With Open-Source Alternatives
Rebalancer occupies a distinct niche among open-source optimization tools. The table below compares it with two widely used alternatives:
| Feature | Rebalancer | Google OR-Tools | Timefold Solver (Community) |
|—|—|—|—|
| **License** | Apache 2.0 | Apache 2.0 | Apache 2.0 (Enterprise edition is commercial) |
| **Core Language** | C++ | C++ | Java |
| **APIs** | C++, Python | C++, Python, Java, C# | Java, Kotlin |
| **Focus** | Generic object-to-bin assignment | Broad suite: CP-SAT, LP, MIP wrappers, routing, packing, assignment | Planning: routing, rostering, scheduling, task assignment |
| **Local Search** | Yes, parallel, on expression graph | Yes, in routing solver (guided local search, simulated annealing, tabu) | Yes, core engine (tabu, simulated annealing, late acceptance) |
| **MIP Backends** | FICO Xpress, Gurobi, HiGHS | Wrappers for commercial and open-source MIP solvers | Not used |
| **Debugging UI** | Rebalancer Explorer (Docker) | Not listed in README | Benchmarker; score analysis in commercial editions |
| **Installation** | `pip install rebalancer` | `pip install ortools` | Maven, JDK 21+ |
OR-Tools provides a broader toolkit covering more problem classes, and Timefold is specifically tailored for JVM-based planning and scheduling. Rebalancer’s distinguishing strength is the ability to describe a single assignment specification that can be solved either via local search or MIP, depending on problem size, without changing the model itself.
—
## Key Takeaways
– Rebalancer models any assignment problem as objects, bins, constraints, and objectives using a declarative specification language.
– Specifications compile into a directed acyclic expression graph that can be solved by either a local search engine or a MIP solver.
– MIP backends include FICO Xpress, Gurobi, and the open-source HiGHS.
– Meta runs approximately 40 million problems per day in production with a P99 latency of 12 seconds at 265k objects and 3.2k bins.
– The library is Apache 2.0 licensed, built in C++ with Python bindings, and available via PyPI today.
– A dedicated debugging UI called Rebalancer Explorer helps modelers understand and iterate on solver behavior.
– It is distinct from OR-Tools and Timefold in its focus on a unified specification layer that supports both local search and MIP solving for the same problem formulation.
—
## Frequently Asked Questions
**Q: What types of assignment problems can Rebalancer solve?**
A: Rebalancer is built for generic object-to-bin assignment problems. This includes task placement on servers, traffic routing across data centers, shard distribution, support ticket routing, meeting room scheduling, and any scenario where entities with specific requirements must be assigned to containers with capacity limits and policy constraints.
**Q: What Python versions and operating systems are supported?**
A: The current release requires Python 3.12 or later. Prebuilt wheels are available for Linux x86-64 and macOS 14+ on ARM64. Additional packages exist for .deb, .rpm, and Homebrew-based installations.
**Q: Can Rebalancer handle problems with millions of objects?**
A: Yes. Meta routinely solves problems with over 1 million objects and 5,000 bins using Rebalancer’s local search solver, with average solve times around 171 seconds for that scale.
**Q: Why does Meta use both a local search solver and a MIP solver?**
A: The MIP solver provides provably optimal solutions and is ideal for small-to-medium problems and prototyping. The local search solver scales far better to large problems where MIP formulations become too large to solve in practice. The same specification works with both solvers, making it easy to prototype with MIP and migrate to local search for production.
**Q: Is Rebalancer suitable for non-infrastructure problems?**
A: Yes. While it was developed for large-scale infrastructure resource allocation, Rebalancer’s generic object-to-bin model applies to any domain with assignment structure, including operational tasks like matching support tickets to engineers or scheduling meetings into available rooms.
**Q: How does the Rebalancer Explorer help?**
A: Rebalancer Explorer is a Dockerized web application that provides visual feedback on constraint binding, relaxation effects, and the reasoning behind specific assignment decisions. It is designed to significantly reduce the time modelers spend debugging solver behavior.
**Q: What makes Rebalancer different from Google OR-Tools?**
A: OR-Tools is a broad optimization suite covering constraint programming, linear programming, mixed integer programming, and routing. Rebalancer is narrowly focused on the object-to-bin assignment pattern, with a unified specification language and two solver backends (local search and MIP) that share the same expression graph. This focused design simplifies the modeling workflow for assignment problems specifically.
—
## Conclusion
Meta’s decision to open-source Rebalancer represents a significant contribution to the optimization tooling ecosystem. By releasing a production-hardened assignment solver that has been validated at the scale of one of the world’s largest technology infrastructures, Meta gives the broader community access to a system that has already solved tens of billions of real-world allocation problems. The clean separation between specification and solving, combined with the flexibility to switch between local search and MIP backends, makes Rebalancer a compelling choice for engineers facing assignment challenges at any scale — from small clusters to hyperscale deployments. With Apache 2.0 licensing, Python accessibility, and active documentation, the project is positioned to find adoption well beyond Meta’s own engineering teams.
Thank you for reading
