An integer linear programming approach to the steiner problem in graphs

Abstract

Abstract Consider a connected undirected graph G[N; E ] with N = S ∪ P , the set of nodes, where P is designated as the set of Steiner points. A weight is associated with each edge e i of the set E . The problem of obtaining a minimal weighted tree which spans the set S of nodes has been termed in literature as the Steiner problem in graphs. A specialized integer programming (set covering) formulation is presented for the problem. The number of constraints in this formulation grows exponentially with the size of the problem. A method called the row generation scheme is developed to solve the above problem. The method requires knowing the constraints only implicitly. Several other problems which can be put in a similar framework can also be handled by the above scheme. The generality of the scheme and its efficiency is discussed. Finally the computational result is demonstrated.