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.
Original language | English |
---|---|
Pages (from-to) | S271-S282 |
Journal | Management Science |
Volume | 44 |
Issue number | 12 PART 2 |
DOIs | |
Publication status | Published - 1998 Dec |
Keywords
- Generalized Assignment Problem
- Generalized Multi-Assignment Problem
- Lagrangian Dual Ascent
- Lagrangian Dual-Based Branch and Bound
- Subgradient Search
ASJC Scopus subject areas
- Strategy and Management
- Management Science and Operations Research