AN APPLICATION OF LAGRANGEAN DECOMPOSITION TO THE RESOURCE-CONSTRAINED MINIMUM WEIGHTED ARBORESCENCE PROBLEM

The resource‐constrained minimum weighted arborescence problem, a 0‐1 integer programming model with application in hierarchical distribution network design, is introduced. Since the model is NP‐hard, an enumeration method is required to solve it to optimality. Lagrangean decomposition, a special form of Lagrangean relaxation, is applied to the model. Both analytically and empirically, Lagrangean decomposition is shown to improve on bounds obtained by a conventional Lagrangean relaxation. An enumeration algorithm, that embeds a specialized Lagrangean dual ascent scheme to solve a Lagrangean decomposition dual, is designed, and problems with up to 1000 0‐1 variables are solved. Copyright © 1990 Wiley Periodicals, Inc., A Wiley Company