Given a set of objects and a set of bins, how do we assign objects to bins in a way that optimizes specific objectives while meeting certain constraints? 

This question arises at all layers of Meta’s infrastructure stack including in

The main challenges to designing a reusable framework for solving problems like these are its usability and scalability. Usability is impeded by practitioners struggling to translate real-life policies into the precise mathematical formulas required by formal optimization methods, while scalability is hampered by NP-hard problems that cannot be solved efficiently by commercial solvers.

Rebalancer addresses both of these challenges by separating a problem’s specification from its solution. Rebalancer provides a language for describing problems using objects, bins, constraints, and objectives, as in the examples above. Once a problem is described in this way, Rebalancer transforms the problem into a directed-acyclic graph called an expression graph. Rebalancer’s solving algorithm uses the expression graph to either design a local search heuristic or to build a mixed integer program (MIP) solvable with either a commercial (FICO Xpress or Gurobi) or open source solver (HiGHS).

Rebalancer’s specification language employs a three-step approach to incrementally elevate the level of abstraction for ease of use. 

In the example above, tasks are modeled as objects and servers are modeled as bins into which tasks are to be placed. Servers are physically situated in racks; this grouping is modeled as a scope . Tasks take a certain amount of CPU and storage and servers have a limited amount of each.

Source link