CvxCluster: Solving Large, Complex, Granular Resource Allocation Problems 100-1000x Faster

Cluster resource allocation is a computationally hard problem, traditionally tackled with mixed integer programming (MIP) or heuristic search. Researchers from Stanford (Obi Nnorom Jr., Stephen Boyd, Philip Levis) propose CvxCluster, a novel method that reformulates the problem as a convex optimization task. This shift from discrete to continuous optimization enables dramatically faster solution times. The algorithm operates in two stages: first, it solves a convex relaxation to compute principled resource prices for each machine. Second, it uses these prices to drive a lightweight greedy procedure that places tasks efficiently.

In experiments using real Azure traces, CvxCluster scaled to over 100,000 servers and sustained arrival rates 500,000 times the baseline. It ran 100 to 2,500 times faster than a state-of-the-art MIP solver while remaining within 3% of the optimal objective. The method supports complex constraints such as job anti-affinity, machine types, and GPU servers. The key insight: by making the problem continuous, convex optimization can find solutions that are just as good or better than prior heuristics, but orders of magnitude faster. This could transform how cloud providers handle resource allocation in large-scale data centers.