Integer Linear Programming Floorplanning

The idea

State floorplanning as constraints and hand it to mathematics. Block i has continuous variables (x_i, y_i) and possibly a rotation bit. For every pair (i, j), non-overlap means at least one of four relations holds: i left of j, i right of j, i below j, i above j. Encode the choice with two binary variables per pair and big-M constraints such as:

• x_i, w_i block i's position and width (continuous variables)
• p_ij, q_ij binary variables selecting which relation holds for the pair
• M a constant large enough to disable the inequality when not selected

where the binaries switch each inequality on or off and M is a sufficiently large constant. Add die bounds, minimize chip width times height (linearized, or minimize the half-perimeter with a fixed aspect), and a branch-and-bound Integer Linear Programming solver returns the optimal floorplan, with a certificate.

The wall

The formulation carries O(n²) binaries, and big-M constraints produce notoriously loose linear relaxations, so branch-and-bound trees explode: practical exactness ends somewhere in the tens of blocks even with modern commercial solvers. The 1991 paper already prescribed the survival strategy: solve successive small subproblems (add a few blocks at a time to a partial floorplan), trading global optimality for tractability.

Why it still matters

Exactness is valuable at the scale where it is achievable: channel-level subproblems, datapath tiles, calibrating heuristics (how far from optimal is my annealer on 15-block instances?), and constraint-dense corners of a design where feasibility itself is the question. The linear programming relaxation also survives inside heuristics: fix a topology from any representation and the optimal sizing/position problem becomes an ordinary linear program, solved exactly in milliseconds.

Where you meet it today

Optimality studies, analog and datapath tile assembly, and as the sizing subroutine inside topology-searching floorplanners.