Rebalancer: Open-Source Library for Assignment Problems

Open-sourcing Rebalancer, a high-performance library for solving assignment problems, to enhance usability and scalability.

"Assignment problems demand both precision and speed; Rebalancer offers a structured approach without vendor lock-in."

The constraint behind the work

Meta faced the need to solve millions of assignment problems daily, ranging from infrastructure optimization to resource allocation. These problems varied in size and complexity, requiring a solution that could handle both small and large-scale instances efficiently. The existing tools either lacked the performance needed for large problems or were too rigid for the diverse formulations Meta encountered. This drove the development of Rebalancer—a library designed to separate problem specification, storage, solving, and debugging into distinct layers. This modularity aimed to improve both usability and scalability, allowing engineers to tackle a wide range of assignment problems without rewriting core logic for each new use case.

The engineering choice

Rebalancer was built to address Meta’s internal needs for a flexible, high-performance library that could handle a variety of assignment problem formulations. Over nine years of use, it has proven effective in solving roughly 40 million assignment problems per day, supporting more than 30 unique problem formulations. The library separates concerns into four main areas: problem specification, storage, solving, and debugging. This design choice enables users to define problems in a declarative manner, store them efficiently in memory, solve them using one of two techniques (optimal or local search), and debug outcomes effectively. The separation of these concerns reduces cognitive load and allows for easier maintenance and extension.

How it works

Rebalancer translates assignment problems into expression graphs, which are then processed by one of two solving techniques. The optimal solver guarantees the best possible solution, while the local search solver provides a good solution in less time, suitable for large-scale problems. This dual-approach allows users to balance solution quality against time constraints depending on their specific requirements. The expression graph model enables efficient manipulation and evaluation of problem constraints and objectives, making it easier to adapt the library to new problem formulations without significant re-engineering.

In practice: For a problem involving 265k objects and 3.2k bins, Rebalancer achieves a P99 solve time of 12 seconds. When scaling up to problems with more than 1 million objects and 5k bins, the average solve time is 171 seconds, with over 3.4k such runs occurring daily.

The scale assumptions

Rebalancer is designed to handle both medium and large-scale assignment problems. Its architecture assumes that problems can range from tens of thousands of objects and bins to well over a million objects with thousands of bins. The library’s performance characteristics are tuned for these scales, with observed solve times indicating its capability to manage substantial computational loads. However, specific performance bottlenecks or areas for improvement are not detailed in the source material, leaving some room for further optimization depending on use case.

Operational lessons

One key operational lesson from Rebalancer’s design is the importance of modularity. By separating problem specification from solving and debugging, Meta has created a system that is both flexible and maintainable. This modularity allows teams to swap out components—such as different solving algorithms—without disrupting the entire workflow. Another lesson is the value of a dual-solver strategy: offering both optimal and local search solutions allows operators to choose the appropriate trade-off between solution quality and compute time based on the urgency and requirements of the task.

Watch out: While Rebalancer performs well at scale, users should be aware that solve times can vary significantly depending on problem size and complexity. For very large problems, the local search solver may become necessary to meet time constraints, even though it does not guarantee an optimal solution.

Trade-offs the source accepts

Meta accepts several trade-offs with Rebalancer. The primary trade-off is between solution quality and solve time. The optimal solver guarantees the best possible assignment but may be too slow for very large problems, whereas the local search solver provides a good—but not necessarily the best—solution in less time. Another trade-off is the potential memory overhead associated with storing large expression graphs for massive assignment problems. While Rebalancer is designed to store problems efficiently in memory, extremely large instances may still require careful management of memory resources to avoid degradation in performance.

What smaller teams can reuse

Smaller teams can benefit from Rebalancer’s modular design and open-source availability. The library’s separation of concerns makes it accessible even to teams with limited resources, as they can focus on problem specification and debugging without needing to build solving algorithms from scratch. The expression graph model also provides a flexible foundation for defining and solving new types of assignment problems, allowing smaller teams to adapt the library to their specific needs without extensive re-engineering. Additionally, the Apache 2.0 license under which Rebalancer is released ensures that small teams can use, modify, and distribute the library freely, making it a viable option for a wide range of applications.

Who should act

Teams that regularly encounter assignment problems—particularly those involving resource allocation, scheduling, or matching—should consider adopting Rebalancer. The library is especially relevant for organizations that need to solve large-scale assignment problems daily and require a balance between solution quality and compute time. Infrastructure teams, operations teams, and any group dealing with optimization challenges where assignments must be made between objects and bins will find Rebalancer a useful tool. Its open-source nature also makes it an attractive option for research groups and academic institutions exploring new solving techniques or problem formulations.

Bottom line

Rebalancer offers a structured, high-performance approach to solving assignment problems, with a modular design that supports both optimal and local search solving strategies. Its open-source release under the Apache 2.0 license makes it accessible to a broad audience, enabling teams to tackle a wide range of optimization challenges without vendor lock-in. While it is particularly suited for large-scale problems, its flexibility also benefits smaller teams that need to solve complex assignments efficiently.

Sources

Open-Sourcing Rebalancer: A Generic, High-Performance Library for Solving Assignment Problems