Skip to content

CONCEPT Cited by 1 source

Assignment problem

Definition

An assignment problem is the combinatorial-optimization problem of assigning a set of objects to a set of bins so as to optimize one or more objectives while satisfying constraints. It is the general primitive that sits above a large family of infrastructure decisions — placement, scheduling, routing, and allocation — and its general form is NP-hard (Source: sources/2026-09-21-meta-open-sourcing-rebalancer-a-generic-high-performance-library).

The vocabulary is deliberately generic so many concrete problems map into it:

Concrete problem Objects Bins Typical objectives / constraints
Hardware placement racks data centers spread across electrical fault domains; power/cooling limits
Service placement servers services meet demand; spread across failure domains; packing efficiency
Task placement tasks servers resource limits; co-location / anti-affinity
Traffic routing user traffic data centers minimize network latency; balance DC load

Relationship to bin-packing

Bin-packing is a special case of the assignment problem: pack items (objects) into fixed-capacity bins to minimize the number of bins used (or maximize fill). The assignment framing generalizes it by allowing arbitrary objectives (fault-domain spread, latency, balance across multiple dimensions) and arbitrary constraints beyond capacity — so cluster scheduling, VM placement, and traffic engineering are all assignment problems, with bin-packing as the capacity-only instance.

Why it's hard: usability and scalability

Two challenges recur whenever a team tries to build a reusable assignment solver (Source: sources/2026-09-21-meta-open-sourcing-rebalancer-a-generic-high-performance-library):

  • Usability — practitioners struggle to translate real-world policy ("one job type per rack," "balance CPU and storage," "spread across fault domains") into the precise mathematical formulas formal optimization methods require.
  • Scalability — the problems are NP-hard, so exact solvers (mixed-integer programming) can't handle the largest instances; a MIP model can be quadratic in |objects|·|bins|.

How solvers tackle it

  • Exact / optimal (mixed-integer programming, MIP). Encode the problem as integer decision variables and feed it to a MIP solver (FICO Xpress, Gurobi, the open-source HiGHS). Practical for small/mid-size instances; model-size reduction techniques include variable aggregation, interchangeability, and symmetry breaking. Also useful to prototype against and to tune heuristics offline.
  • Local search (metaheuristic). Start from an initial assignment and iteratively move objects between bins, evaluate candidate assignments, and apply the best feasible improving one until progress stalls or a stopping condition is hit. The neighborhood per step is roughly O(|objects|+|bins|), so it scales to very large problems where the exact MIP would be intractable. This is what dominates at hyperscale.

A common production workflow prototypes on the exact solver to establish a high-quality baseline, then migrates to local search for scale — and uses the exact solver offline to tune the heuristic.

Separating specification from solution

A load-bearing lesson from Meta's Rebalancer is that a reusable assignment framework should separate how a problem is specified from how it is solved: describe the problem declaratively (objects / bins / constraints / objectives), compile it into a solver-agnostic intermediate representation (an expression graph), and only then choose a backend (MIP or local search). The same specification can then be solved different ways without rewriting the model — "crucial to usability, scalability, and extensibility."

Seen in

Last updated · 766 distilled / 2,225 read