Introduction

Imagine you are laying out a new hospital. You have a fixed set of rooms (locations) and a set of departments (facilities). Some departments send patients back and forth constantly — the emergency room and radiology, say — while others barely interact. The rooms, meanwhile, sit at fixed distances from one another.

Your job: decide which department goes in which room so that the total walking is as small as possible. The cost of any layout is simple to write down — for every pair of departments, multiply how much flow passes between them by the distance between the rooms you put them in, and add it all up.

This is the Quadratic Assignment Problem (QAP), posed by Tjalling Koopmans and Martin Beckmann in 1957. It sounds like a tidy little optimization. It is, in fact, one of the most stubbornly NP-hard problems we know — so hard that some instances with just 30 facilities have resisted exact solution for decades on serious hardware.

Swap the Facilities

Below are four facilities (A, B, C, D) sitting on four locations arranged in a square. The lines show the flow between facilities; the cost of the layout is every flow multiplied by the distance between the spots you placed those two facilities, summed up. Click two cells to swap the facilities in them and watch the total cost swing.

<p class="hint">Four facilities (A, B, C, D) sit on four locations in a square. The cost is every <b>flow</b> between two facilities times the <b>distance</b> between the spots you put them. Click two cells to <b>swap</b> their facilities. Checking a layout is instant — finding the best is the hard part.</p>
<div class="wrap">
  <div id="grid" class="grid"></div>
  <div class="panel">
    <div class="cost">Cost: <span id="cost">–</span></div>
    <div class="best" id="best"></div>
    <div class="flows" id="flows"></div>
  </div>
</div>
<div class="btns">
  <button id="find" type="button">Find the best layout</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.wrap { display: flex; gap: 1.4rem; flex-wrap: wrap; align-items: flex-start; }
.grid { display: grid; grid-template-columns: repeat(2, 88px); grid-template-rows: repeat(2, 88px); gap: 16px; }
.cell { width: 88px; height: 88px; display: flex; flex-direction: column; align-items: center; justify-content: center;
        font: 700 30px system-ui, sans-serif; border-radius: 12px; cursor: pointer; user-select: none;
        background: #e8eef3; color: #1d3557; border: 2px solid #cdd9e3; transition: all .12s; }
.cell:hover { background: #d8e2ea; }
.cell.sel { border-color: #e63946; background: #fbe3e5; box-shadow: 0 0 0 2px #e6394633; }
.cell small { font: 600 11px system-ui, sans-serif; color: #5a7088; margin-top: 2px; }
.panel { font-size: .92rem; min-width: 180px; }
.cost { font-size: 1.3rem; font-weight: 700; color: #1d3557; margin-bottom: .3rem; }
.best { font-size: .9rem; font-weight: 600; color: #0a7d33; min-height: 1.3em; margin-bottom: .6rem; }
.flows { font: 13px ui-monospace, monospace; color: #555; line-height: 1.6; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: 1rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Quadratic Assignment Problem (QAP). We place facilities A,B,C,D on 4 locations.
// cost(perm) = sum over facility pairs i<j of  flow[i][j] * dist[loc(i)][loc(j)].
// Moving one facility changes its distance to EVERY other -> quadratic coupling.
// Brute force tries all n! permutations; here n=4 so 24 layouts.
const FAC = ['A','B','C','D'];
// Symmetric flow between facilities (how much they interact).
// A-D and B-C are the heavy pairs; the others barely interact.
const FLOW = [
  [0, 1, 2, 9],   // A-D very heavy
  [1, 0, 8, 2],   // B-C heavy
  [2, 8, 0, 1],
  [9, 2, 1, 0]
];
// Location coordinates on the square (2x2). dist = Euclidean.
const LOC = [ {x:0,y:0}, {x:1,y:0}, {x:0,y:1}, {x:1,y:1} ]; // 0=TL 1=TR 2=BL 3=BR
const D = LOC.map(a => LOC.map(b => Math.hypot(a.x-b.x, a.y-b.y)));

// assign[loc] = facility index placed at that location. Start A,B,C,D in order.
let assign = [0,1,2,3];
let sel = -1;

// Cost of a placement: for each pair of LOCATIONS, flow between the facilities
// there times the distance between the locations.
function cost(a){
  let s = 0;
  for(let i=0;i<4;i++) for(let j=i+1;j<4;j++)
    s += FLOW[a[i]][a[j]] * D[i][j];
  return s;
}
function fmt(v){ return Math.round(v*100)/100; }

function render(){
  const g = document.getElementById('grid'); g.innerHTML='';
  const names = ['TL','TR','BL','BR'];
  for(let i=0;i<4;i++){
    const d = document.createElement('div');
    d.className = 'cell' + (sel===i?' sel':'');
    d.innerHTML = FAC[assign[i]] + '<small>'+names[i]+'</small>';
    d.addEventListener('click', ()=>pick(i));
    g.appendChild(d);
  }
  document.getElementById('cost').textContent = fmt(cost(assign));
  // Show the flows so the puzzle is legible.
  const fl = document.getElementById('flows');
  const pairs = [];
  for(let i=0;i<4;i++) for(let j=i+1;j<4;j++)
    if(FLOW[i][j]>0) pairs.push(i18nFmt('flow(%v%,%v2%) = %v3%', { v: FAC[i], v2: FAC[j], v3: FLOW[i][j] }));
  fl.innerHTML = i18nFmt('<b>Flows</b><br>%pairs%', { pairs: pairs.join('<br>') });
}
function pick(i){
  if(sel===-1){ sel=i; }
  else if(sel===i){ sel=-1; }
  else { const t=assign[sel]; assign[sel]=assign[i]; assign[i]=t; sel=-1;
         document.getElementById('best').textContent=''; }
  render();
}
function permutations(arr){
  if(arr.length<=1) return [arr];
  const out=[];
  for(let i=0;i<arr.length;i++){
    const rest=arr.slice(0,i).concat(arr.slice(i+1));
    for(const p of permutations(rest)) out.push([arr[i],...p]);
  }
  return out;
}
function find(){
  let best=null, bestC=Infinity, checked=0;
  for(const p of permutations([0,1,2,3])){ checked++;
    const c=cost(p); if(c<bestC){ bestC=c; best=p; } }
  assign = best.slice(); sel=-1; render();
  document.getElementById('best').textContent =
    i18nFmt('✓ Optimal cost %fmt% after checking %checked% of 24 layouts.', { fmt: fmt(bestC), checked: checked });
  console.log('Best layout', best.map(i=>FAC[i]).join(''), 'cost', fmt(bestC));
}
document.getElementById('find').addEventListener('click', find);
document.getElementById('reset').addEventListener('click', ()=>{
  assign=[0,1,2,3]; sel=-1; document.getElementById('best').textContent=''; render(); });
render();
Result
Console

Notice how a single swap can send the cost up or down by a lot — moving one facility changes its distance to every other facility at once. That coupling is what the word quadratic means here. Press Find the best layout and the computer brute-forces all permutations. Four facilities give only 24 arrangements; but the count is n!, so 10 facilities already mean over 3 million layouts and 30 facilities mean more arrangements than there are atoms in the observable universe.

The Real Complexity

How hard is QAP, really?

  • Checking a layout is trivial: just add up flow times distance over every pair.
  • Brute force tries every permutation of facilities onto locations — n! layouts, hopeless past a couple of dozen facilities.
  • It's NP-hard. In 1976, Sahni and Gonzalez proved that QAP is NP-hard. Worse, they showed that even approximating the optimum within any constant factor is itself NP-hard — so unlike many problems, you cannot count on a polynomial-time algorithm to even get close.
  • It contains famous problems. The Traveling Salesman Problem is a special case of QAP, and so are problems like graph layout and minimum-cost wiring. Solving QAP fast would solve all of them.

That is the punchline. Where the Traveling Salesman Problem couples one visit to the next one, QAP couples every facility to every other. The result is one of the canonical hard cases of combinatorial optimization, and a vivid instance of the question behind P vs NP. Today's solvers attack moderate instances with branch-and-bound and clever lower bounds, but the worst cases remain genuinely intractable.

Where It Matters

"Place these things so that interacting pairs end up close together" is a shape that shows up everywhere, and QAP is its exact mathematical form:

  • Factory and hospital layout — the original use: arrange machines or departments so heavily-communicating ones sit nearby.
  • Keyboard and dashboard design — assigning letters to keys (or controls to a cockpit) so the busiest pairs are easiest to reach is a QAP.
  • Chip and circuit-board placement — VLSI engineers place components to minimize total wire length, a giant QAP instance.
  • Logistics and campus planning — locating warehouses, offices, or buildings so frequent trips stay short.

QAP is also a close cousin of facility location: both decide where things go, but QAP's cost couples every pair at once, which is exactly what makes it explode.

Conclusion

The Quadratic Assignment Problem looks innocent: just decide where to put things. But because moving one item reshuffles its distance to everything else, the cost landscape is a minefield of local traps, and the only guaranteed way to the true optimum is to wade through a factorial sea of layouts.

That is why, nearly seventy years after Koopmans and Beckmann wrote it down, QAP instances of size 30 can still be open challenges. The next time you rearrange a room and somehow everything feels worse, take heart — you've bumped into P vs NP wearing the disguise of furniture, and there may be no shortcut to the perfect arrangement at all.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/quadratic-assignment/Content licensed under CC BY-NC 4.0.