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.
Volume (Year): 44 (1998)
Issue (Month): 12-Part-2 (December)
|Contact details of provider:|| Postal: 7240 Parkway Drive, Suite 300, Hanover, MD 21076 USA|
Web page: http://www.informs.org/
More information through EDIRC
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Marshall L. Fisher & R. Jaikumar & Luk N. Van Wassenhove, 1986. "A Multiplier Adjustment Method for the Generalized Assignment Problem," Management Science, INFORMS, vol. 32(9), pages 1095-1103, September.
- Laguna, Manuel & Kelly, James P. & Gonzalez-Velarde, JoseLuis & Glover, Fred, 1995. "Tabu search for the multilevel generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 82(1), pages 176-189, April.
- Mohammad M. Amini & Michael Racer, 1994. "A Rigorous Computational Comparison of Alternative Solution Methods for the Generalized Assignment Problem," Management Science, INFORMS, vol. 40(7), pages 868-890, July.
- Robert M. Nauss, 1976. "An Efficient Algorithm for the 0-1 Knapsack Problem," Management Science, INFORMS, vol. 23(1), pages 27-31, September.
When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:44:y:1998:i:12-part-2:p:s271-s282. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc)
If references are entirely missing, you can add them using this form.