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.