A Lagrangian dual-based branch-and-bound algorithm for the generalized multi-assignment problem

A Lagrangian dual-based branch-and-bound algorithm for the generalized multi-assignment problem

0.00 Avg rating0 Votes
Article ID: iaor20001070
Country: United States
Volume: 44
Issue: 12, Part 2
Publication Date: Dec 1998
Journal: Management Science
Authors: , ,
Keywords: lagrange multipliers
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.

Reviews

Required fields are marked *. Your email address will not be published.