A test problem generator for the Steiner problem in graphs

ABSTRACT

In this paper we present a new binary-programming formulation for the Steiner problem in graphs (SPG), which is well known to be NP-hard. We use this formulation to generate test problems with known optimal solutions. The technique uses the KKT optimality conditions on the corresponding quadratically constrained optimization problem.

REFERENCES

• 1: ANE~A, Y.P. 1980. An integer linear programming approach to the Steiner problem in graphs. Networks 10, 167-178.
• 2: BAZARAA, M. S., AND SHETTY, C.M. 1979. Nonlinear Programming Theory and Algorithms. Wiley, New York.
• 3: COURANT, R., AND ROBBINS, $. 1941. What Is Mathemahcs. Oxford Press, New York, 1941.
• 4: DREYFUS, S. E., AND WAGNER, R. A. 1971. The Steiner problem in graphs. Networks 1, 195 207.
• 5: Du, D.-Z., AND HWANG, F.K. 1990. The Steiner ratio conjecture of Gilbert and Pollak is true. In Proceedings of the National Academy of Science USA on Mathematics, 87, 9464 9466.
• 6: GILBERT, E. N., AND POLLAK, H. O. 1968 Steiner minimal trees. SIAJl4 J. Appl. Math. 16, 1-29.
• 7: HAKIMI, S.L. 1971. Steiner's problem in graphs and its implications. Networks 1, 113-133.
• 8: HANAN, M 1975. Layout, interconnection and placement. Networks 5, 85-88.
• 9: HWANG, F. K., AND RICHARDS, D.S. 1992. Steiner tree problems. Networks 22.55 89.
• 10: KHOURY, B. N., PARDALOS, P. M., AND HEARN, D.W. 1993. Equivalent formulations for the Steiner problem m graphs. In Network Optimization Problems, D.-Z. Du and P. M. Pardalos, Eds., World Scientific, 111-124.
• 11: LAWLER, E.L. 1976. Combinatorial Optimtzatwn. Networks and Matro~ds. Holt, Rinehart and Winston, New York.
• 12: Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
• 13: MACULAN, N. 1987. The Steiner problem in graphs. Ann. Discrete Math. 31, 185-212.
• 14: MAGNANTI, T. L., AND WONG, R.T. 1984. Network design and transportation planning: Models and algorithms. Transportation Sct. 18, 1-55.
• 15: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 16: Panos M. Pardalos, Construction of test problems in quadratic bivalent programming, ACM Transactions on Mathematical Software (TOMS), v.17 n.1, p.74-87, March 1991 [doi>10.1145/103147.103156]
• 17: Panos M. Pardalos, Generation of large-scale quadratic programs for use as global optimization test problems, ACM Transactions on Mathematical Software (TOMS), v.13 n.2, p.133-137, June 1987 [doi>10.1145/328512.328516]
• 18: ROSE, J. S., BLYTHE, D. R., SNELGROVE, W. M., AND VRANESIC, Z.G. 1986. Fast, high quahty VLSI placement on an MIMD multlprocessor. In Proceeding of the IEEE International Conference on Computer-Aided Destgn (Santa Clara, Calif.). IEEE, New York, 42-45,
• 19: J. B. Rosen , S. Suzuki, Pracniques: construction of nonlinear programming test problems, Communications of the ACM, v.8 n.2, p.113, Feb. 1965 [doi>10.1145/363744.363779]
• 20: L. A. Sanchis, On the complexity of test case generation for NP-hard problems, Information Processing Letters, v.36 n.3, p.135-140, Nov. 1990 [doi>10.1016/0020-0190(90)90082-9]
• 21: SMITH, J. M., AND LIEBMAN, J. S. 1986 Steiner trees, Steiner circuits, and the interference problem in building design. Eng. Optim 4, 15-36.
• 22: P. Winter, Steiner problem in networks: a survey, Networks, v.17 n.2, p.129-167, Summer 1987 [doi>10.1002/net.3230170203]
• 23: Y F Wu , P Widmayer , C K Wong, A faster approximation algorithm for the Steiner problem in graphs, Acta Informatica, v.23 n.2, p.223-229, April 1986 [doi>10.1007/BF00289500]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency; Certification and testing

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Steiner problem in graphs, integer programming, test problems