Finding minimum cost directed trees with demands and capacities (Q1179742)

The paper deals with the exact calculation of a fixed-charge minimum-cost directed spanning tree by branch-and-bound methods. Known cut generation techniques based on single- and multicommodity flow models are compared with a new technique based on directed subtree decomposition of the original network. Computational results indicate that the subtree decomposition method is better than the other two for finding lower bounds and good feasible solutions. Networks of up to 106 nodes and 385 arcs have been solved by the method.