The class Steiner minimal tree problem: a lower bound and test problem generation

The class Steiner minimal tree problem is an extension of the standard Stei ner minimal tree problem in graphs, motivated by the problem of wire routin g in the area of physical design of very large scale integration (VLSI). Th is problem is NP-hard, even if there are no Steiner nodes and the graph is a tree; moreover, there exists no polynomial time approximation algorithm w ith a constant bound on the relative error under the hypothesis that P not equal NP [16]. Hence, fast and good heuristic algorithms are needed in prac tice. In this paper, we present an integer programming formulation of the p roblem. Using Lagrangean relaxation and subgradient optimization, we derive a lower bound. In order to test the lower bound, we present a procedure fo r generating test problems for the class Steiner minimal tree problem that have known optimal solutions. The computational experiments for the test pr oblems demonstrate that the lower bound is very tight and differs from the optimal solutions by only a few percent on average for sparse graphs.