Article ID: | iaor19921084 |
Country: | Switzerland |
Volume: | 33 |
Start Page Number: | 285 |
End Page Number: | 303 |
Publication Date: | Nov 1991 |
Journal: | Annals of Operations Research |
Authors: | Bousba Choaib, Wolsey Laurance A. |
Keywords: | networks: path |
Given a directed graph, the authors consider the problem of finding a rooted directed tree (or branching) satisfying given demands at all the nodes and capacity constraints on the arcs. Various integer programming formulations are compared, including flow and multicommodity flow formulations and two partitioning-type formulations involving directed subtrees. Computational results concerning an application to the design of a low voltage electricity network are given. For the class of problems considered, one of the partitioning formulations allows us to solve problems with up to 100 nodes and several hundred arcs.