Meta AI Open-Sources Rebalancer: A C++ Assignment Solver That Runs About 40 Million Placement Problems a Day

Meta has open-sourced Rebalancer, a C++ library with a Python interface for solving assignment problems. It decides which objects go into which bins under constraints and objectives. According to the Engineering at Meta’s post, Rebalancer has handled resource allocation across Meta for over 9 years. The release ships under Apache 2.0 with documentation, a PyPI package and a debugging UI called Rebalancer Explorer.

Is it deployable? Yes. pip install rebalancer installs v1.0.4 for Python 3.12+, with prebuilt wheels for Linux x86-64 and macOS 14+ ARM64. .deb, .rpm and Homebrew packages also exist. PyPI still classifies the project as Alpha.

What Problem Does Rebalancer Solve?

Assignment problems show up across Meta’s stack. Racks go into datacenters, servers go to services, tasks go to servers, and user traffic goes to datacenters. Meta names 2 blockers: usability and scalability. Engineers struggle to turn policies into precise formulas, and many problems are NP-hard and too large for commercial solvers.

Rebalancer’s answer is to separate how a problem is specified from how it is solved. The design is detailed in the OSDI 2024 paper, Optimizing Resource Allocation in Hyperscale Datacenters.

How the Specification Layer Works

The spec language has 3 layers:

Modeling constructs: dimensions (attributes such as CPU or storage), partitions (groups of objects), scopes (groups of bins) and utilization.
Expression API: aggregate utilization with SUM or MAX, or transform it with operations such as SQUARE.
Spec API: dozens of predefined objectives and constraints, listed in the docs.

Meta’s example models tasks as objects, servers as bins and racks as a scope. A CapacitySpec caps CPU and storage per server. A GroupCountSpec keeps 1 job type per rack. A BalanceSpec balances each server’s utilization across both dimensions.

One Expression Graph, Two Solvers

Rebalancer compiles the spec into a directed acyclic expression graph. Leaf nodes hold utilization values; aggregation and transformation nodes sit above them. Users supply an initial assignment and a stopping condition. Constraints that the initial assignment already violates become high-priority goals.

Optimal solver: The graph is translated into a mixed integer program for FICO Xpress, Gurobi or HiGHS. Variable aggregation and symmetry breaking shrink models. The worst-case model size is still O(objects × bins). Meta’s largest problems are too big for any MIP solver.

Local search: This solver works directly on the expression graph. It explores moves of objects to other bins, with a worst-case neighborhood of O(objects + bins). It then applies the best candidate that breaks no constraint. Evaluation is parallelized, reaching millions of evaluations per second, and the search space is pruned.

Meta uses local search for almost all large problems and MIP for small to mid-size ones, often prototyping with MIP first.

Production Numbers at Meta

About 40 million assignment problems solved per day, across 30+ unique formulations.
P99 solve time of 12 seconds on 265k objects and 3.2k bins.
Problems above 1 million objects and 5k bins average 171 seconds, across 3.4k+ runs.

Best Use Cases for Rebalancer

Placing shards, tasks or containers on a cluster: Assign work to servers under CPU and memory caps while spreading replicas across racks. Meta’s Shard Manager and RAS run this pattern.
Balancing traffic and workloads across regions: Route user traffic or jobs to datacenters, trading latency against load. Taiji does this for edge traffic, and Meta balances ML training by priority.
Operational assignment outside infrastructure: Map support tickets to engineers, meetings to rooms or desks to people under capacity rules. Meta has done all 3.

Debugging With Rebalancer Explorer

Modelers at Meta spent most of their time debugging solver behavior. Rebalancer Explorer is a Dockerized web UI built for this. It shows binding constraints, relaxation effects, and why an object landed in a bin.

Interactive Explainer

<div id="mtp-rebal">
<div class="hd">
<div class="eyebrow">Interactive explainer · Meta Rebalancer</div>
<h3>How Rebalancer puts objects into bins</h3>
<p class="sub">Play with a small task-placement problem, watch the expression graph update, and see when Meta picks local search over MIP.</p>
</div>
<div class="tabs" role="tablist">
<button class="tab on" data-p="0">1 · Local search</button>
<button class="tab" data-p="1">2 · Expression graph</button>
<button class="tab" data-p="2">3 · Which solver?</button>
<button class="tab" data-p="3">4 · At Meta scale</button>
</div>

<!– PANE 1 –>
<div class="pane on" id="mtpP0">
<p class="note">12 <b>tasks</b> (objects, number = CPU units) go onto 4 <b>servers</b> (bins) in 2 <b>racks</b> (scopes). Each server has a <b>CapacitySpec</b> of 16 CPU. The goal is a <b>BalanceSpec</b>: minimize the sum of squared utilization. Each step evaluates every single move and swap, then applies the best one.</p>
<div class="btns">
<button class="b pri" id="mtpRun"> Run local search</button>
<button class="b" id="mtpStep">Step once</button>
<button class="b" id="mtpShuf">Random bad start</button>
<button class="b" id="mtpReset">Reset</button>
</div>
<div class="stats">
<div class="st"><div class="k">Step</div><div class="v" id="mtpS">0</div></div>
<div class="st"><div class="k">Moves evaluated</div><div class="v" id="mtpE">0</div></div>
<div class="st"><div class="k">Capacity overflow</div><div class="v" id="mtpV">0</div></div>
<div class="st"><div class="k">Balance objective</div><div class="v" id="mtpO">0</div></div>
</div>
<div class="racks" id="mtpRacks"></div>
<div class="spark"><div class="k">Objective over steps (lower is better, ideal = 324)</div>
<svg id="mtpSpark" viewBox="0 0 800 70" width="100%" height="70" preserveAspectRatio="none"></svg>
</div>
<div class="log" id="mtpLog">Server S1 starts 4 CPU over capacity. Press Run.</div>
</div>

<!– PANE 2 –>
<div class="pane" id="mtpP1">
<p class="note">Rebalancer compiles specs into a <b>directed acyclic expression graph</b>. Leaves hold each server’s utilization; SQUARE, SUM and MAX nodes sit above them. When one task moves, only the leaves it touches and their ancestors need new values. The graph uses the same live state as tab 1.</p>
<div class="btns">
<button class="b pri" id="mtpGMove">Move a random task</button>
<button class="b" id="mtpGBest">Apply best local-search move</button>
</div>
<div class="gwrap"><svg id="mtpGraph" viewBox="0 0 820 300" width="100%"></svg></div>
<div class="log" id="mtpGLog">Press a button to move a task.</div>
</div>

<!– PANE 3 –>
<div class="pane" id="mtpP2">
<p class="note">The MIP model needs about one binary variable per object per bin, so it grows as <b>O(objects × bins)</b>. A local-search neighborhood grows as <b>O(objects + bins)</b>. Drag the sliders or load Meta’s published sizes.</p>
<div class="btns">
<button class="b" data-o="500" data-bn="20">Small: 500 × 20</button>
<button class="b" data-o="265000" data-bn="3200">Meta P99: 265k × 3.2k</button>
<button class="b" data-o="1000000" data-bn="5000">Meta XL: 1M × 5k</button>
</div>
<div class="sl"><label>Objects <b id="mtpOv"></b></label><input type="range" id="mtpOs" min="1" max="6.3" step="0.01" value="2.7"></div>
<div class="sl"><label>Bins <b id="mtpBv"></b></label><input type="range" id="mtpBs" min="0.3" max="4" step="0.01" value="1.3"></div>
<div class="cmp">
<div class="row"><div class="t">MIP binary variables, worst case <span id="mtpMv"></span></div><div class="track"><i id="mtpMb" style="background:linear-gradient(90deg,#FF8A5A,#FF5A6E)"></i></div></div>
<div class="row"><div class="t">Local-search neighborhood, worst case <span id="mtpLv"></span></div><div class="track"><i id="mtpLb" style="background:linear-gradient(90deg,#0866FF,#38D6FF)"></i></div></div>
</div>
<div class="verdict" id="mtpVerdict"></div>
<p class="note" style="margin-top:10px">Bars use a log scale. Size bands in the verdict are illustrative; Meta’s stated rule is local search for almost all large problems and MIP for small to mid-size ones.</p>
</div>

<!– PANE 4 –>
<div class="pane" id="mtpP3">
<p class="note">Production figures published by Meta for Rebalancer (Engineering at Meta, Sep 21 2026).</p>
<div class="grid" id="mtpCards">
<div class="card"><div class="n"><span data-c="40">0</span><em>M</em></div><div class="d">assignment problems solved per day</div></div>
<div class="card"><div class="n"><span data-c="30">0</span><em>+</em></div><div class="d">unique problem formulations</div></div>
<div class="card"><div class="n"><span data-c="12">0</span><em>s</em></div><div class="d">P99 solve time on 265k objects and 3.2k bins</div></div>
<div class="card"><div class="n"><span data-c="171">0</span><em>s</em></div><div class="d">average solve for 1M+ objects and 5k bins</div></div>
<div class="card"><div class="n"><span data-c="3.4" data-d="1">0</span><em>k+</em></div><div class="d">runs at that 1M+ object scale</div></div>
<div class="card"><div class="n"><span data-c="9">0</span><em>+ yrs</em></div><div class="d">in use across Meta before open-sourcing</div></div>
</div>
<div class="pills">
<span class="pill">Shard Manager: shards → servers</span>
<span class="pill">RAS: servers → services</span>
<span class="pill">Taiji: edge traffic → datacenters</span>
<span class="pill">Serverless function grouping</span>
<span class="pill">ML training balancing</span>
<span class="pill">Meetings → rooms</span>
</div>
</div>

<div class="ft">
<span>Sources: <a href=" target="_blank" rel="noopener">Engineering at Meta</a> · <a href=" target="_blank" rel="noopener">GitHub</a> · Tabs 1 to 3 are simplified simulations</span>
<span class="brand">Built by Marktechpost</span>
</div>
</div>

/* expression graph */
var G=document.getElementById(‘mtpGraph’),gLog=document.getElementById(‘mtpGLog’);
var LX=[110,300,490,680];
function drawGraph(live){
live=live||[];var u=util(asg),sc=score(asg),h=””;
function on(s){return live.indexOf(s)>-1;}
var any=live.length>0;
for(var s=0;s<4;s++){
h+='<path class="edge’+(on(s)?’ live’:”)+’" d="M’+LX[s]+’,232 L’+LX[s]+’,172"/>’;
h+='<path class="edge’+(on(s)?’ live’:”)+’" d="M’+LX[s]+’,138 C’+LX[s]+’,100 300,110 300,78"/>’;
h+='<path class="edge’+(on(s)?’ live’:”)+’" d="M’+(LX[s]+40)+’,233 C’+(LX[s]+60)+’,200 650,130 650,78"/>’;
}
h+='<path class="edge’+(any?’ live’:”)+’" d="M300,44 L300,22"/><path class="edge’+(any?’ live’:”)+’" d="M650,44 L650,22"/>’;
function node(x,y,w,label,val,l){return ‘<g class="node’+(l?’ live’:”)+’"><rect x="’+(x-w/2)+’" y="’+(y-17)+’" width="’+w+’" height="34" rx="8"/><text x="’+x+’" y="’+(y-2)+’">’+label+'</text><text class="val" x="’+x+’" y="’+(y+11)+’">’+val+'</text></g>’;}
for(var k=0;k<4;k++){h+=node(LX[k],250,96,’U(S’+(k+1)+’)’,’= ‘+u[k],on(k));h+=node(LX[k],155,96,’SQUARE’,’= ‘+u[k]*u[k],on(k));}
h+=node(300,61,120,’SUM’,’= ‘+sc[1],any);h+=node(650,61,120,’MAX’,’= ‘+Math.max.apply(null,u),any);
h+='<text x="300" y="14" fill="#4C9BFF" font-size="11" font-weight="700" text-anchor="middle">BalanceSpec objective</text>’;
h+='<text x="650" y="14" fill="’+(Math.max.apply(null,u)>CAP?’#FF5A6E’:’#2BD99F’)+’" font-size="11" font-weight="700" text-anchor="middle">CapacitySpec: MAX ≤ ‘+CAP+(Math.max.apply(null,u)>CAP?’ (violated)’:’ (ok)’)+'</text>’;
h+='<text x="410" y="292" fill="#93A3BF" font-size="11" text-anchor="middle">Leaves: utilization per server · nodes recomputed this move: ‘+(any?(live.length*2+2):0)+’ of 10</text>’;
G.innerHTML=h;
}
document.getElementById(‘mtpGMove’).onclick=function(){stop();var i=Math.floor(Math.random()*12),s;do{s=Math.floor(Math.random()*4);}while(s===asg[i]);var old=asg;asg=asg.slice();asg[i]=s;evals++;step++;hist.push(score(asg)[1]);render([i]);var d=diff(old,asg);drawGraph(d);gLog.textContent=”Moved t”+(i+1)+’ S’+(old[i]+1)+’ → S’+(s+1)+’. Only ‘+(d.length*2+2)+’ of 10 nodes needed new values.’;};
document.getElementById(‘mtpGBest’).onclick=function(){stop();var r=bestMove();evals+=r.n;if(!r.best){gLog.textContent=”Local optimum reached. Try a random move first.”;render();return;}var old=asg;asg=r.best.a;step++;hist.push(score(asg)[1]);render(r.best.ids);var d=diff(old,asg);drawGraph(d);gLog.textContent=”Best of “+r.n+’ candidates: ‘+r.best.txt+’. Recomputed ‘+(d.length*2+2)+’ of 10 nodes.’;};

/* solver picker */
var Os=document.getElementById(‘mtpOs’),Bs=document.getElementById(‘mtpBs’);
function fmt(n){if(n>=1e9)return (n/1e9).toFixed(n>=1e10?0:1)+’B’;if(n>=1e6)return (n/1e6).toFixed(n>=1e7?0:1)+’M’;if(n>=1e3)return (n/1e3).toFixed(n>=1e4?0:1)+’k’;return Math.round(n)+”;}
function pick(){
var o=exactO||Math.round(Math.pow(10,+Os.value)),b=exactB||Math.round(Math.pow(10,+Bs.value)),m=o*b,l=o+b;exactO=exactB=0;
document.getElementById(‘mtpOv’).textContent=fmt(o);document.getElementById(‘mtpBv’).textContent=fmt(b);
document.getElementById(‘mtpMv’).textContent=”≈ “+fmt(m);document.getElementById(‘mtpLv’).textContent=”≈ “+fmt(l);
document.getElementById(‘mtpMb’).style.width=Math.min(100,Math.log10(m)/11*100)+’%’;
document.getElementById(‘mtpLb’).style.width=Math.min(100,Math.log10(l)/11*100)+’%’;
var v=document.getElementById(‘mtpVerdict’),t;
if(m<=1e6){t=”<b>Optimal (MIP) solver is a good start.</b> Small model: hand it to HiGHS, Gurobi or FICO Xpress and get a provably optimal assignment.”;v.style.borderColor=”#2BD99F”;}
else if(m<=1e8){t=”<b>Prototype with MIP, then move to local search.</b> Meta says this is a common path: find a strong baseline with the optimal solver, then migrate.”;v.style.borderColor=”#4C9BFF”;}
else{t=”<b>Local search.</b> The MIP would need ≈ “+fmt(m)+’ binary variables in the worst case, while each local-search neighborhood stays near ‘+fmt(l)+’. Meta runs almost all large problems this way.’;v.style.borderColor=”#38D6FF”;}
v.innerHTML=t;postH();
}
var exactO=0,exactB=0;Os.oninput=pick;Bs.oninput=pick;
document.querySelectorAll(‘#mtpP2 button[data-o]’).forEach(function(btn){btn.onclick=function(){exactO=+btn.dataset.o;exactB=+btn.dataset.bn;Os.value=Math.log10(+btn.dataset.o);Bs.value=Math.log10(+btn.dataset.bn);pick();};});

/* stats */
var counted=false;
function count(){
var cards=document.querySelectorAll(‘#mtpCards .card’);
cards.forEach(function(c,i){c.classList.remove(‘in’);setTimeout(function(){c.classList.add(‘in’);},90*i);});
document.querySelectorAll(‘#mtpCards [data-c]’).forEach(function(el){var tgt=+el.dataset.c,dp=+(el.dataset.d||0),t0=null;
function f(ts){if(!t0)t0=ts;var p=Math.min(1,(ts-t0)/1100),e=1-Math.pow(1-p,3);el.textContent=(tgt*e).toFixed(dp);if(p<1)requestAnimationFrame(f);}requestAnimationFrame(f);});
}

/* tabs */
var tabs=R.querySelectorAll(‘.tab’);
tabs.forEach(function
R.querySelectorAll(‘.pane’).forEach(function(p){p.classList.remove(‘on’);});document.getElementById(‘mtpP’+t.dataset.p).classList.add(‘on’);
if(t.dataset.p===’3′)count();if(t.dataset.p===’1′)drawGraph(null);setTimeout(postH,60);setTimeout(postH,450);};});

hist=[score(asg)[1]];render();pick();
window.addEventListener(‘load’,postH);window.addEventListener(‘resize’,postH);setTimeout(postH,300);
})();
</script>
</body></html>”>

Rebalancer vs Closest Open Source Alternatives

Feature	Meta Rebalancer	Google OR-Tools	Timefold Solver (Community)
License	Apache 2.0	Apache 2.0	Apache 2.0 (Enterprise edition is commercial)
Core language	C++	C++	Java
APIs	C++, Python	C++, Python, Java, C#	Java, Kotlin
Focus	Generic assignment (objects to bins)	Broad suite: CP-SAT, LP, MIP wrappers, routing, packing, assignment	Planning: routing, rostering, scheduling, task assignment
Local search	Yes, parallel, on expression graph	Yes, in routing solver (guided local search, simulated annealing, tabu)	Yes, core engine (tabu, simulated annealing, late acceptance)
MIP backends	FICO Xpress, Gurobi, HiGHS	Wrappers for commercial and open source MIP solvers	Not used
Debugging UI	Rebalancer Explorer (Docker)	Not listed in README	Benchmarker; score analysis in commercial editions
Install	`pip install rebalancer`	`pip install ortools`	Maven, JDK 21+

OR-Tools covers more problem classes, and Timefold targets JVM scheduling and routing. Rebalancer’s edge is one assignment spec that runs on both local search and MIP.

Key Takeaways

Rebalancer models any assignment problem as objects, bins, constraints and objectives.
Specs compile into an expression graph solved by local search or a MIP solver.
MIP backends include FICO Xpress, Gurobi and open source HiGHS.
Meta runs about 40M problems a day; P99 is 12s on 265k objects and 3.2k bins.
Apache 2.0, C++ and Python APIs, installable from PyPI today.

Check out the Paper, GitHub Repo and Technical details. All credit goes to the researcher of this project. Also, feel free to follow us on Twitter and don’t forget to join our 150k+ML SubReddit and Subscribe to our Newsletter. Wait! are you on telegram? now you can join us on telegram as well.

[Sponsored] The web is the one API most agents are missing. Databases, calendars and repos have APIs. The open web mostly doesn’t. The TinyFish MCP server gives any MCP client four tools: TinySearch, TinyFetch (full pages as markdown, JavaScript included), TinyBrowser for logins and forms, and TinyAgent for multi-step jobs. Search and Fetch are free.

The post Meta AI Open-Sources Rebalancer: A C++ Assignment Solver That Runs About 40 Million Placement Problems a Day appeared first on MarkTechPost.

Source link