Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem
Bezalel Gavish · Journal of the ACM · 1983
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.2.