Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem

Abstract

The Capacltated Minmaal Directed Tree Problem is fundamental m many network design problems. A new linear integer programming formulauon of the problem which leads to a Dantzlg-Wolfe decomposmon and to a new Lagrangean relaxation procedure for the Capacaated Mmunal Directed Tree Problem as presented This relaxation is used for deriving tight lower bounds on the optunal solution and m heunsucs for obtaining approxtmate solutions The effectiveness of the procedure is demonstrated in computational tests Categories and SubJect Descriptors: C.