A Lagrangian Dual-Based Branch-and-Bound Algorithm for the Generalized Multi-Assignment Problem

June S. Park, Byung Ha Lim and Youngho Lee
Additional contact information
June S. Park: Department of Management Sciences, 108 Pappajohn Business Adm. Bldg., The University of Iowa, Iowa City, Iowa 52242-1000
Byung Ha Lim: US West Advanced Technologies, Applied Research, Suite 280, 4001 Discovery Drive, Boulder, Colorado 80303
Youngho Lee: US West Advanced Technologies, Applied Research, Suite 280, 4001 Discovery Drive, Boulder, Colorado 80303

Management Science, 1998, vol. 44, issue 12-Part-2, S271-S282

Abstract: 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.

Keywords: Generalized Multi-Assignment Problem; Generalized Assignment Problem; Lagrangian Dual Ascent; Subgradient Search; Lagrangian Dual-Based Branch and Bound (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.44.12.S271 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:44:y:1998:i:12-part-2:p:s271-s282

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().