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 sol
utions. The technique uses the KKT optimality conditions on the corres
ponding quadratically constrained optimization problem.