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

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.

• 저널Management Science · 44(12-part-2) · S271–S282
• 토픽Vehicle Routing Optimization Methods · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.44.12.s271
• 저자June S. Park, Byung Ha Lim, Youngho Lee