Article ID: | iaor20001070 |
Country: | United States |
Volume: | 44 |
Issue: | 12, Part 2 |
Publication Date: | Dec 1998 |
Journal: | Management Science |
Authors: | Park June S., Lee Youngho, Lim Byung Ha |
Keywords: | lagrange multipliers |
This paper develops a Lagrangian dual-based branch-and-bound algorithm for the generalized multi-assignment problem (GMAP) which includes the well-known generalized assignment problem (GAP) as a special case. In GMAP, an object may be required to be duplicated in multiple locations. We develop a Lagrangian dual ascent algorithm for GMAP. This dual ascent and the subgradient search each possess advantages that can be combined to develop a new Lagrangian dual search algorithm. The latter algorithm, when incorporated into a branch-and-bound algorithm as the lower bounding scheme, can accelerate the search process. Computational results demonstrate the efficiency and robustness of this branch-and-bound algorithm not only for GMAPs, but for GAPs that are more difficult than could be solved by previous algorithms.