1. A test problem generator for the Steiner problem in graphs
- Author
-
D.-Z. Du, B. N. Khoury, and Panos M. Pardalos
- Subjects
Quadratic growth ,symbols.namesake ,Mathematical optimization ,Constrained optimization problem ,Karush–Kuhn–Tucker conditions ,Applied Mathematics ,symbols ,Steiner tree problem ,Integer programming ,Software ,Mathematics ,Generator (mathematics) ,Test (assessment) - 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.
- Published
- 1993
- Full Text
- View/download PDF