Explore / Methods & Algorithms / Routing / ILP and Flow-Based Global Routing

ILP and Flow-Based Global Routing

Routing research global routing 2006 Cho and Pan (BoxRouter); Wu, Davoodi, Linderoth (GRIP) optimal but does not scale

The idea

Every other page in this catalog searches or negotiates. This one declares. Give each net a set of candidate paths, attach one binary variable to each, and state the whole problem as an ILP (Integer Linear Programming) instance:

minimize sum of cost(net, path) × x(net, path)

x(net, path) 1 if the net uses that candidate path, else 0
cost(net, path) the path's wirelength or detour

subject to two families of constraints:

sum over paths of x(net, path) = 1 for every net

sum over paths crossing e of x(net, path) ≤ capacity(e) for every edge e

capacity(e) how many wires the GCell edge e can carry

A solver then returns a routing and a certificate: no feasible assignment of the given candidates is cheaper. Congestion is not negotiated over iterations; it is a constraint the answer satisfies from birth. The relaxation of the same program (allowing fractional x) is a multi-commodity flow, whose solution bounds how good any routing can be.

From drawn paths to the program

The encoding is an incidence table, built before the program exists. A pattern enumerator draws each net's candidates on the GCell graph and stores every candidate as its explicit list of edges plus its cost. Each stored path then becomes one table row:

uses(p, e) = 1 if stored path p crosses edge e, else 0

p one drawn candidate; its geometry is fixed and known before the program is written
e a GCell edge with scarce capacity; only these need columns

For the two-net example in the walkthrough, with the gap A and gap B crossings as the two scarce edges:

variable	cost (detour)	uses gap A	uses gap B
x(N1, A)	2	1	0
x(N1, B)	6	0	1
x(N2, A)	2	1	0
x(N2, B)	8	0	1

The whole program reads off this table. Across each net's pair of rows, the pick-one constraint: x(N1, A) + x(N1, B) = 1. Down each edge's column, summing the rows that hold a 1, the capacity constraint: x(N1, A) + x(N2, A) ≤ 1 for gap A. The objective weights each variable by its cost column. The solver never sees geometry, only the table, and when it returns x(N1, B) = 1 the route is read back by lookup: the stored edge list behind that row is N1's route. This is also why the optimality certificate is only as strong as the menu: a path nobody drew has no row.

The flow-based encoding is the alternative that lets the solver build routes instead of choosing them: one variable per net per GCell edge, with conservation constraints (a net's chosen edges must pair up at every GCell except its two pins) forcing any feasible assignment to trace a connected path. It needs no enumeration and can find routes outside any menu, at the price of far more variables. Column generation bridges the two: solve with a small menu, let the relaxation's dual prices steer a shortest-path oracle to a missing cheaper candidate, add it as a new row, and repeat.

The recipe

Step 1 (candidates). Generate a small candidate set per net, typically the L and Z patterns of pattern routing.

Step 2 (declare). Emit the objective and constraints above.

Step 3 (solve, within a budget). Hand the program to an ILP (Integer Linear Programming) solver. Because the full-chip program is intractable, production-adjacent systems bound the instance: BoxRouter solves exact programs inside progressively growing boxes around congested regions; GRIP partitions the die and solves the pieces near-optimally.

Watch it work: two nets, declared and solved

The two-net bottleneck from the PathFinder page, taken from drawn geometry to proven answer: the walkthrough enumerates each net's candidates, reduces them to the incidence table the program actually sees, reads the constraints off the table, solves, and looks the winning routes back up. The solver proves the same allocation the negotiation converges to.

Pros, cons, and the trade-off

Strengths

Provable optimality: the only approach on these pages that returns a certificate, within the candidate set.
Gold standard: near-optimal ILP solutions calibrate every heuristic router; contest benchmarks are scored against them.
Constraints are first-class: capacity, and anything else linear, is declared once instead of encoded into cost schedules.
Sound bounds: the flow relaxation lower-bounds the achievable wirelength before any router runs.

Weaknesses

Does not scale: integer programming is NP (Nondeterministic Polynomial time) hard, and millions of nets produce programs no solver finishes.
Only as good as its candidates: a route outside the enumerated set is invisible, optimality certificate notwithstanding.
Windowing reintroduces heuristics: box growth and partitioning schedules are hand-tuned, the mechanism the declaration was meant to remove.

The trade-off

The ILP view trades scalability for truth: it cannot route a full chip, but it is how the field knows what the right answer looks like. Heuristic routers are validated by approaching ILP (Integer Linear Programming) results on instances small enough to solve, and the exact methods are applied to the hard windows where negotiation fails to converge.

Is it actually used today?

The evidence for ILP (Integer Linear Programming) routing comes from benchmarking, windowed exact solvers, and bounds analysis rather than production mainlines.

Benchmarking: GRIP-family solvers produced near-optimal results on the ISPD (International Symposium on Physical Design) global-routing contest benchmarks, and remain the reference heuristic routers are measured against.
Windowed exact solving: the BoxRouter idea, exact programs on bounded congested regions inside a heuristic outer loop, recurs in academic routers and in commercial congestion-repair passes.
Bounds and analysis: multi-commodity-flow relaxations supply lower bounds used to judge routability and router quality in research.