← Back to Problems
04 / steiner

Steiner Tree Packing

VLSI Design / Wire Routing
Binary ILP / QUBO graph-theory VLSI NP-hard
Instances 190
Optimally solved 29 / 190
Variable range 16–2,601,600
Objective minimize

Overview

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.

Problem Description

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.

Submissions (0)

No submissions for this problem yet. Submit one →

Instances (190)

190 of 190
Name Grid Layers Terminals Holes Best objective Source Status Download
stp_s003_l1_t2_h0_rs97531 3 1 2 0 4 Reference solution Optimal ↓ raw
stp_s003_l1_t2_h3_rs24098 3 1 2 3 4 Reference solution Optimal ↓ raw
stp_s003_l1_t2_h5_rs24098 3 1 2 5 4 Reference solution Optimal ↓ raw
stp_s003_l1_t3_h0_rs24098 3 1 3 0 6 Reference solution Optimal ↓ raw
stp_s003_l1_t3_h1_rs24098 3 1 3 1 4 Reference solution Optimal ↓ raw
stp_s003_l2_t2_h4_rs24098 3 2 2 4 4 Reference solution Optimal ↓ raw
stp_s003_l2_t2_h5_rs37235 3 2 2 5 5 Reference solution Optimal ↓ raw
stp_s004_l1_t2_h4_rs37235 4 1 2 4 6 Reference solution Optimal ↓ raw
stp_s004_l1_t3_h3_rs24098 4 1 3 3 6 Reference solution Optimal ↓ raw
stp_s004_l1_t3_h3_rs97531 4 1 3 3 3 Reference solution Optimal ↓ raw
stp_s020_l2_t3_h2_rs24098 20 2 3 2 228 Reference solution Optimal ↓ raw
stp_s020_l2_t3_h3_rs97531 20 2 3 3 363 Reference solution Best known ↓ raw
stp_s020_l2_t4_h0_rs24098 20 2 4 0 189 Reference solution Best known ↓ raw
stp_s020_l2_t4_h3_rs37235 20 2 4 3 189 Reference solution Optimal ↓ raw
stp_s020_l3_t3_h2_rs24098 20 3 3 2 355 Reference solution Optimal ↓ raw
stp_s020_l3_t4_h0_rs24098 20 3 4 0 344 Reference solution Best known ↓ raw
stp_s020_l3_t4_h2_rs97531 20 3 4 2 264 Reference solution Optimal ↓ raw
stp_s020_l3_t4_h3_rs97531 20 3 4 3 217 Reference solution Optimal ↓ raw
stp_s020_l4_t3_h3_rs37235 20 4 3 3 390 Reference solution Best known ↓ raw
stp_s020_l4_t4_h0_rs24098 20 4 4 0 228 Reference solution Best known ↓ raw
stp_s020_l4_t4_h3_rs37235 20 4 4 3 189 Reference solution Optimal ↓ raw
stp_s020_l5_t3_h3_rs24098 20 5 3 3 296 Reference solution Best known ↓ raw
stp_s020_l5_t4_h0_rs24098 20 5 4 0 242 Reference solution Best known ↓ raw
stp_s020_l5_t4_h3_rs97531 20 5 4 3 95 Reference solution Optimal ↓ raw
stp_s030_l2_t3_h1_rs97531 30 2 3 1 389 Reference solution Optimal ↓ raw
stp_s030_l2_t3_h3_rs97531 30 2 3 3 388 Reference solution Optimal ↓ raw
stp_s030_l2_t4_h2_rs97531 30 2 4 2 387 Reference solution Optimal ↓ raw
stp_s030_l2_t5_h1_rs24098 30 2 5 1 430 Reference solution Optimal ↓ raw
stp_s030_l3_t3_h1_rs97531 30 3 3 1 327 Reference solution Optimal ↓ raw
stp_s030_l3_t3_h2_rs97531 30 3 3 2 343 Reference solution Optimal ↓ raw
stp_s030_l3_t4_h0_rs24098 30 3 4 0 304 Reference solution Best known ↓ raw
stp_s030_l3_t5_h1_rs24098 30 3 5 1 476 Reference solution Optimal ↓ raw
stp_s030_l4_t3_h1_rs97531 30 4 3 1 328 Reference solution Optimal ↓ raw
stp_s030_l4_t4_h0_rs97531 30 4 4 0 480 Reference solution Best known ↓ raw
stp_s030_l4_t4_h2_rs97531 30 4 4 2 424 Reference solution Optimal ↓ raw
stp_s030_l5_t3_h1_rs97531 30 5 3 1 320 Reference solution Optimal ↓ raw
stp_s030_l5_t4_h0_rs24098 30 5 4 0 447 Reference solution Optimal ↓ raw
stp_s040_l2_t3_h0_rs97531 40 2 3 0 - - Open ↓ raw
stp_s040_l2_t3_h2_rs24098 40 2 3 2 - - Open ↓ raw
stp_s040_l2_t4_h0_rs97531 40 2 4 0 - - Open ↓ raw
stp_s040_l2_t4_h3_rs123 40 2 4 3 - - Open ↓ raw
stp_s040_l3_t3_h0_rs97531 40 3 3 0 - - Open ↓ raw
stp_s040_l3_t4_h0_rs97531 40 3 4 0 - - Open ↓ raw
stp_s040_l3_t4_h1_rs24098 40 3 4 1 - - Open ↓ raw
stp_s040_l4_t3_h0_rs97531 40 4 3 0 - - Open ↓ raw
stp_s040_l4_t4_h0_rs123 40 4 4 0 - - Open ↓ raw
stp_s040_l4_t4_h0_rs97531 40 4 4 0 - - Open ↓ raw
stp_s040_l4_t4_h1_rs24098 40 4 4 1 - - Open ↓ raw
stp_s040_l4_t5_h0_rs24098 40 4 5 0 - - Open ↓ raw
stp_s040_l5_t3_h0_rs97531 40 5 3 0 - - Open ↓ raw
stp_s040_l5_t4_h0_rs24098 40 5 4 0 - - Open ↓ raw
stp_s040_l5_t4_h1_rs24098 40 5 4 1 - - Open ↓ raw
stp_s040_l5_t5_h0_rs24098 40 5 5 0 - - Open ↓ raw
stp_s050_l2_t3_h1_rs97531 50 2 3 1 834 Reference solution Best known ↓ raw
stp_s050_l2_t3_h3_rs24098 50 2 3 3 - - Open ↓ raw
stp_s050_l2_t4_h0_rs24098 50 2 4 0 - - Open ↓ raw
stp_s050_l2_t4_h1_rs97531 50 2 4 1 756 Reference solution Best known ↓ raw
stp_s050_l2_t4_h3_rs24098 50 2 4 3 - - Open ↓ raw
stp_s050_l2_t5_h1_rs97531 50 2 5 1 - - Open ↓ raw
stp_s050_l3_t3_h3_rs24098 50 3 3 3 - - Open ↓ raw
stp_s050_l3_t4_h0_rs123 50 3 4 0 - - Open ↓ raw
stp_s050_l3_t4_h0_rs24098 50 3 4 0 - - Open ↓ raw
stp_s050_l3_t4_h2_rs123 50 3 4 2 - - Open ↓ raw
stp_s050_l3_t4_h2_rs24098 50 3 4 2 - - Open ↓ raw
stp_s050_l3_t5_h1_rs97531 50 3 5 1 - - Open ↓ raw
stp_s050_l3_t6_h2_rs97531 50 3 6 2 343 Reference solution Best known ↓ raw
stp_s050_l4_t4_h0_rs123 50 4 4 0 - - Open ↓ raw
stp_s050_l4_t4_h2_rs123 50 4 4 2 - - Open ↓ raw
stp_s050_l4_t4_h2_rs24098 50 4 4 2 - - Open ↓ raw
stp_s050_l4_t5_h0_rs97531 50 4 5 0 - - Open ↓ raw
stp_s050_l5_t4_h0_rs97531 50 5 4 0 - - Open ↓ raw
stp_s050_l5_t4_h2_rs97531 50 5 4 2 - - Open ↓ raw
stp_s060_l2_t4_h0_rs24098 60 2 4 0 - - Open ↓ raw
stp_s060_l2_t4_h1_rs123 60 2 4 1 - - Open ↓ raw
stp_s060_l2_t4_h1_rs24098 60 2 4 1 - - Open ↓ raw
stp_s060_l2_t5_h1_rs24098 60 2 5 1 - - Open ↓ raw
stp_s060_l3_t3_h2_rs97531 60 3 3 2 - - Open ↓ raw
stp_s060_l3_t4_h0_rs123 60 3 4 0 - - Open ↓ raw
stp_s060_l3_t4_h1_rs123 60 3 4 1 321 Reference solution Best known ↓ raw
stp_s060_l3_t4_h1_rs24098 60 3 4 1 - - Open ↓ raw
stp_s060_l3_t4_h2_rs123 60 3 4 2 - - Open ↓ raw
stp_s060_l3_t4_h2_rs97531 60 3 4 2 - - Open ↓ raw
stp_s060_l3_t5_h0_rs24098 60 3 5 0 - - Open ↓ raw
stp_s060_l3_t5_h0_rs97531 60 3 5 0 - - Open ↓ raw
stp_s060_l3_t5_h1_rs24098 60 3 5 1 - - Open ↓ raw
stp_s060_l3_t5_h2_rs24098 60 3 5 2 - - Open ↓ raw
stp_s060_l3_t5_h2_rs97531 60 3 5 2 - - Open ↓ raw
stp_s060_l3_t6_h2_rs24098 60 3 6 2 - - Open ↓ raw
stp_s060_l4_t3_h0_rs24098 60 4 3 0 - - Open ↓ raw
stp_s060_l4_t3_h1_rs97531 60 4 3 1 - - Open ↓ raw
stp_s060_l4_t3_h2_rs24098 60 4 3 2 - - Open ↓ raw
stp_s060_l4_t4_h0_rs123 60 4 4 0 - - Open ↓ raw
stp_s060_l4_t4_h0_rs24098 60 4 4 0 - - Open ↓ raw
stp_s060_l4_t4_h1_rs123 60 4 4 1 - - Open ↓ raw
stp_s060_l4_t4_h1_rs24098 60 4 4 1 - - Open ↓ raw
stp_s060_l4_t5_h1_rs24098 60 4 5 1 - - Open ↓ raw
stp_s060_l5_t3_h0_rs97531 60 5 3 0 291 Reference solution Optimal ↓ raw
stp_s060_l5_t3_h1_rs97531 60 5 3 1 - - Open ↓ raw
stp_s060_l5_t4_h0_rs123 60 5 4 0 - - Open ↓ raw
stp_s060_l5_t4_h1_rs123 60 5 4 1 - - Open ↓ raw
stp_s060_l5_t4_h1_rs24098 60 5 4 1 - - Open ↓ raw
stp_s060_l5_t5_h0_rs24098 60 5 5 0 - - Open ↓ raw
stp_s060_l5_t5_h1_rs24098 60 5 5 1 - - Open ↓ raw
stp_s060_l5_t6_h2_rs37235 60 5 6 2 - - Open ↓ raw
stp_s070_l2_t3_h0_rs97531 70 2 3 0 - - Open ↓ raw
stp_s070_l2_t4_h0_rs123 70 2 4 0 - - Open ↓ raw
stp_s070_l2_t6_h1_rs37235 70 2 6 1 - - Open ↓ raw
stp_s070_l3_t4_h0_rs24098 70 3 4 0 - - Open ↓ raw
stp_s070_l3_t4_h2_rs24098 70 3 4 2 - - Open ↓ raw
stp_s070_l3_t4_h2_rs97531 70 3 4 2 - - Open ↓ raw
stp_s070_l3_t5_h0_rs24098 70 3 5 0 - - Open ↓ raw
stp_s070_l3_t5_h2_rs24098 70 3 5 2 - - Open ↓ raw
stp_s070_l4_t3_h0_rs97531 70 4 3 0 - - Open ↓ raw
stp_s070_l4_t4_h0_rs97531 70 4 4 0 - - Open ↓ raw
stp_s070_l4_t4_h1_rs24098 70 4 4 1 - - Open ↓ raw
stp_s070_l4_t4_h1_rs97531 70 4 4 1 - - Open ↓ raw
stp_s070_l4_t4_h2_rs24098 70 4 4 2 - - Open ↓ raw
stp_s070_l4_t6_h0_rs97531 70 4 6 0 375 Reference solution Best known ↓ raw
stp_s070_l5_t3_h0_rs97531 70 5 3 0 - - Open ↓ raw
stp_s070_l5_t4_h0_rs24098 70 5 4 0 - - Open ↓ raw
stp_s070_l5_t4_h1_rs24098 70 5 4 1 - - Open ↓ raw
stp_s070_l5_t4_h2_rs24098 70 5 4 2 - - Open ↓ raw
stp_s070_l5_t5_h0_rs24098 70 5 5 0 - - Open ↓ raw
stp_s070_l5_t5_h1_rs97531 70 5 5 1 - - Open ↓ raw
stp_s080_l2_t4_h0_rs123 80 2 4 0 - - Open ↓ raw
stp_s080_l2_t4_h1_rs123 80 2 4 1 - - Open ↓ raw
stp_s080_l2_t4_h1_rs24098 80 2 4 1 - - Open ↓ raw
stp_s080_l2_t5_h0_rs24098 80 2 5 0 - - Open ↓ raw
stp_s080_l3_t3_h1_rs97531 80 3 3 1 - - Open ↓ raw
stp_s080_l3_t4_h0_rs123 80 3 4 0 - - Open ↓ raw
stp_s080_l3_t5_h0_rs24098 80 3 5 0 - - Open ↓ raw
stp_s080_l3_t5_h0_rs97531 80 3 5 0 - - Open ↓ raw
stp_s080_l4_t3_h0_rs24098 80 4 3 0 - - Open ↓ raw
stp_s080_l4_t3_h1_rs97531 80 4 3 1 - - Open ↓ raw
stp_s080_l4_t4_h0_rs123 80 4 4 0 - - Open ↓ raw
stp_s080_l4_t4_h0_rs24098 80 4 4 0 - - Open ↓ raw
stp_s080_l4_t4_h0_rs97531 80 4 4 0 - - Open ↓ raw
stp_s080_l4_t5_h0_rs24098 80 4 5 0 - - Open ↓ raw
stp_s080_l4_t5_h1_rs97531 80 4 5 1 - - Open ↓ raw
stp_s080_l5_t4_h0_rs123 80 5 4 0 - - Open ↓ raw
stp_s080_l5_t4_h0_rs24098 80 5 4 0 - - Open ↓ raw
stp_s090_l2_t3_h0_rs24098 90 2 3 0 - - Open ↓ raw
stp_s090_l2_t3_h1_rs123 90 2 3 1 - - Open ↓ raw
stp_s090_l2_t3_h1_rs24098 90 2 3 1 - - Open ↓ raw
stp_s090_l2_t3_h1_rs97531 90 2 3 1 - - Open ↓ raw
stp_s090_l2_t3_h2_rs24098 90 2 3 2 - - Open ↓ raw
stp_s090_l2_t3_h2_rs97531 90 2 3 2 - - Open ↓ raw
stp_s090_l2_t5_h0_rs97531 90 2 5 0 - - Open ↓ raw
stp_s090_l3_t3_h0_rs97531 90 3 3 0 - - Open ↓ raw
stp_s090_l3_t3_h1_rs97531 90 3 3 1 - - Open ↓ raw
stp_s090_l3_t3_h2_rs123 90 3 3 2 - - Open ↓ raw
stp_s090_l3_t4_h0_rs97531 90 3 4 0 - - Open ↓ raw
stp_s090_l3_t5_h0_rs24098 90 3 5 0 - - Open ↓ raw
stp_s090_l3_t5_h0_rs97531 90 3 5 0 - - Open ↓ raw
stp_s090_l3_t5_h1_rs24098 90 3 5 1 - - Open ↓ raw
stp_s090_l3_t6_h0_rs97531 90 3 6 0 - - Open ↓ raw
stp_s090_l4_t3_h0_rs24098 90 4 3 0 - - Open ↓ raw
stp_s090_l4_t3_h0_rs97531 90 4 3 0 - - Open ↓ raw
stp_s090_l4_t3_h1_rs97531 90 4 3 1 - - Open ↓ raw
stp_s090_l4_t3_h2_rs123 90 4 3 2 - - Open ↓ raw
stp_s090_l4_t4_h0_rs97531 90 4 4 0 - - Open ↓ raw
stp_s090_l4_t4_h1_rs97531 90 4 4 1 - - Open ↓ raw
stp_s090_l4_t5_h0_rs24098 90 4 5 0 - - Open ↓ raw
stp_s090_l5_t3_h0_rs97531 90 5 3 0 - - Open ↓ raw
stp_s090_l5_t4_h0_rs97531 90 5 4 0 - - Open ↓ raw
stp_s090_l5_t4_h1_rs97531 90 5 4 1 - - Open ↓ raw
stp_s090_l5_t6_h0_rs37235 90 5 6 0 - - Open ↓ raw
stp_s100_l2_t3_h0_rs97531 100 2 3 0 - - Open ↓ raw
stp_s100_l2_t3_h2_rs123 100 2 3 2 - - Open ↓ raw
stp_s100_l2_t3_h3_rs24098 100 2 3 3 - - Open ↓ raw
stp_s100_l2_t4_h0_rs97531 100 2 4 0 - - Open ↓ raw
stp_s100_l2_t4_h3_rs24098 100 2 4 3 - - Open ↓ raw
stp_s100_l2_t5_h0_rs97531 100 2 5 0 - - Open ↓ raw
stp_s100_l3_t3_h1_rs24098 100 3 3 1 - - Open ↓ raw
stp_s100_l3_t3_h2_rs24098 100 3 3 2 - - Open ↓ raw
stp_s100_l3_t3_h3_rs97531 100 3 3 3 - - Open ↓ raw
stp_s100_l3_t4_h1_rs24098 100 3 4 1 - - Open ↓ raw
stp_s100_l3_t4_h3_rs24098 100 3 4 3 - - Open ↓ raw
stp_s100_l4_t3_h0_rs24098 100 4 3 0 - - Open ↓ raw
stp_s100_l4_t3_h0_rs97531 100 4 3 0 - - Open ↓ raw
stp_s100_l4_t3_h1_rs24098 100 4 3 1 - - Open ↓ raw
stp_s100_l4_t3_h2_rs123 100 4 3 2 - - Open ↓ raw
stp_s100_l4_t3_h2_rs24098 100 4 3 2 - - Open ↓ raw
stp_s100_l4_t4_h3_rs24098 100 4 4 3 - - Open ↓ raw
stp_s100_l4_t6_h2_rs37235 100 4 6 2 - - Open ↓ raw
stp_s100_l5_t3_h0_rs97531 100 5 3 0 - - Open ↓ raw
stp_s100_l5_t3_h1_rs24098 100 5 3 1 - - Open ↓ raw
stp_s100_l5_t3_h2_rs24098 100 5 3 2 - - Open ↓ raw
stp_s100_l5_t3_h2_rs97531 100 5 3 2 - - Open ↓ raw
stp_s100_l5_t4_h2_rs97531 100 5 4 2 - - Open ↓ raw
View on GitHub ↗ View Leaderboard Browse All Instances