Premium
An application of lagrangean decomposition to the resource‐constrained minimum weighted arborescence problem
Author(s) -
Guignard Monique,
Rosenwein Moshe B.
Publication year - 1990
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230200306
Subject(s) - decomposition , mathematical optimization , relaxation (psychology) , enumeration , mathematics , benders' decomposition , decomposition method (queueing theory) , integer programming , dual (grammatical number) , resource allocation , computer science , combinatorics , discrete mathematics , psychology , social psychology , ecology , art , computer network , literature , biology
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.