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.
No takes yet. Share an insight, caveat, or question.
Khoury et al. (1993) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: