Finding minimum cost directed trees with demands and capacities

Finding minimum cost directed trees with demands and capacities

0.00 Avg rating0 Votes
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: ,
Keywords: networks: path
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.