Reproduce “CvxCluster: Solving Large, Complex, Granular Resource Allocation Problems 100-1000x Faster” on OpenResearch

About this paper

Obi Nnorom Jr, Stephen Boyd, Philip Levis

CvxCluster combines a convex relaxation with shadow-price-guided greedy placement to schedule tasks across heterogeneous, policy-constrained clusters without solving the full integer allocation problem. Compared with MILP baselines, it achieves up to roughly 2,500× faster static placement, scales to about 100,000 servers, and sustains nearly 19,000 task placements per second while keeping placement quality within a few percent in tested settings.

Key insights

• Shadow prices provide a compact global signal for coordinating local placement decisions, separating expensive allocation reasoning from a fast discrete assignment procedure.
• Shape-specific prices preserve information about heterogeneous hardware and generally produce better placement objectives than a single global price vector, with only modest additional computation.
• The relaxation-to-greedy pipeline trades a small amount of optimality for much lower latency; the remaining quality gap is concentrated mainly among lower-priority tasks and can increase under anti-affinity constraints.

Summary by alphaXiv.