Overview
On a circuit board, every group of related pins needs a path, and routing one group may block the next. A routing algorithm can fail because its search strategy got stuck or because the board cannot be routed at all. ReSPack takes away that ambiguity in a synthetic benchmark by constructing a valid routing when it creates each instance.
Key Findings
A wire can find the right pin and still ruin the board
Imagine routing a circuit board one connection at a time. A short first route can cut off a path another pin group will need. Moving to a second layer may help, until a keep-out region or spacing rule makes that route impossible too. A useful benchmark needs cases that expose these conflicts and a way to tell that each case has a valid solution. ReSPack starts from that last requirement and generates both the problem and a feasible route.
Draw a feasible route, then hand over the pins
Each group of pins needs a tree that follows a rectangular grid. Intermediate grid points let several routes within a group share branches. The tree edges span the terminals in group . Writing for the vertices used by a tree, the benchmark minimizes total wire length while enforcing that the different nets use disjoint vertices.
The benchmark sets for every edge. ReSPack builds the trees sequentially, sampling how many terminals to use and drawing candidates from the largest connected component that remains available. Each tree must pass the constraint checks before it is saved. The released challenge contains the terminal groups. The routes built along the way supply feasible references. Problem definition and generator, Sections 2–3
The layout is only the first rule
The generator can reserve areas where wires cannot run, enforce spacing between different wires, and cap the path length between any two terminals in the same tree. A keep-out region and spacing rule reduce the grid available to later trees. The generator tests length after constructing a tree. These checks make it possible to vary the difficulty of the rules without losing the assurance that a released case has a feasible reference.
The fixed benchmark has two layers and eight grid sizes, from 8 × 8 to 1,024 × 1,024. It offers 100 instances per grid size and constraint setting. A solver faces three sets of rules at each size. It can solve the basic packing problem, work around prohibited areas, or meet all three constraints together.
| Selected grid size | Trees | Mean terminals with all three rules | Reference edge density with all three rules |
|---|---|---|---|
| 8 × 8 | 4 | 10.8 | 16.6% |
| 32 × 32 | 16 | 64.1 | 11.5% |
| 256 × 256 | 128 | 512.1 | 9.7% |
| 1,024 × 1,024 | 512 | 2,603.4 | 10.7% |
The density in Table 1 is the fraction of grid edges used by the generator's reference solution. At the largest scale, the solver still has to route more than 2,600 terminals on average. Benchmark sizes, Table 1
Ask how often a solver finishes and how short its routes are
The authors test an exact mixed-integer solver, sequential heuristics, and methods that account for congestion. On the two-layer 32 × 32 benchmark, Table 2 reports the following mean success rates.
| Method | Basic packing | All three additional rules |
|---|---|---|
| Sequential-1 | 59.0% | 2.6% |
| PathFinder-1 | 100.0% | 0.8% |
| RankingCost-MT | 100.0% | 8.0% |
Success asks whether the solver found a valid route. For successful solutions, the reported percentage cost gap is
The reference is the route created by the generator. A negative gap means a shorter route than that reference. The exact solver is omitted from the combined-constraint experiments because the formulation would require substantial changes. The tested methods ran out of attempts or time without finding any feasible solutions on the extra-large cases, even though the generator supplied valid routes. Evaluation results, Table 2 and Section 4.3
Questions & Answers
The opening answers are simulated author responses based on the paper.
Q: Why can the baseline beat the supplied route?
A: The generated route proves feasibility. It comes from a heuristic and can be longer than a route found later.
Q: What does the largest grid tell us?
A: The benchmark includes grids up to 1024 × 1024 with two layers. The paper omits extra-large results because its baselines failed to find feasible solutions at that scale.
Q: Can a solver with cheaper routes be the worse choice overall?
A: Yes. Route cost is only observable for the boards the solver actually completes. In the 32 × 32 experiments, PathFinder-1 goes from full success to under 1% when the added constraints apply. SCIP is omitted in the setting with all three constraints, so the supplied feasible route is a cost reference there. Cost, feasibility, and runtime together show how much routing work the solver gets done.
Future Ideas
Train a router to spot the order that causes a dead end
Use ReSPack to generate layouts where a small change in net order separates a routable attempt from a failed one. Train a model to choose a net to reroute based on the layout after a congestion deadlock. Build a deterministic checker for all spacing and path-length constraints. Compare against PathFinder and the learned net-ordering baseline at equal runtime on held-out generator configurations and separately on real design layouts. Measure complete valid routings, wire length, and time spent rerouting.
Include RankingCost-MT, which already learns a net ordering, as a comparison. A held-out set of actual layouts can test whether the learned rerouting rule transfers beyond the generator.