Premium
An integer linear programming approach to the steiner problem in graphs
Author(s) -
Aneja Y. P.
Publication year - 1980
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230100207
Subject(s) - steiner tree problem , integer programming , generality , mathematics , set (abstract data type) , integer (computer science) , linear programming , scheme (mathematics) , mathematical optimization , discrete mathematics , combinatorics , computer science , psychology , mathematical analysis , psychotherapist , programming language
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.