Application Area: VLSI Design / Wire Routing
The Steiner Tree Packing Problem arises in VLSI design and wire routing, where multiple connection requirements must be satisfied simultaneously without conflicts. This variant is particularly relevant for modern chip design with multiple routing layers.
Find a packing of node-disjoint Steiner trees with given terminals in a graph.
Problem Variant Specifications:
- Geometry: Switchbox problem on a square grid (terminals on edges)
- Multi-layer: Multiple square grids stacked vertically
- Holes: Some parallelepiped sections of the 3D graph are removed
- Disjointness: Each Steiner tree must use disjoint nodes
Goal: Connect all specified terminal sets using Steiner trees such that no two trees share vertices, minimizing total cost or maximizing the number of successfully routed nets.
- instances/ - VLSI routing problem instances
- models/ - Mathematical model formulations
- solutions/ - Optimal or best-known solutions
- check/ - Solution verification tools
- info/ - Additional documentation and papers
- misc/ - Utility scripts and generators
- Hoang, N.-D., Koch, T. (2012). Steiner Tree Packing Revisited. Mathematical Methods of Operations Research, 76:95-123. ZIB Report 12-12.
Additional references are available in the info/ directory.