A Multiplier Adjustment Method for the Generalized Assignment Problem

Marshall L. Fisher, R. Jaikumar and Luk N. Van Wassenhove
Additional contact information
Marshall L. Fisher: The Wharton School, University of Pennsylvania, Philadelphia, Pennsylvania 19104
R. Jaikumar: School of Business, Harvard University, Boston, Massachusetts 02160
Luk N. Van Wassenhove: Katholieke Universiteit Leuven

Management Science, 1986, vol. 32, issue 9, 1095-1103

Abstract: We describe a branch and bound algorithm for the generalized assignment problem in which bounds are obtained from a Lagrangian relaxation with the multipliers set by a heuristic adjustment method. The algorithm was tested on a large sample of small random problems and a number of large problems derived from a vehicle routing application. Computation times were reasonable in all cases and the branch and bound trees generated had nearly two orders of magnitude fewer nodes than for competing algorithms. Although comparison of running times on different machines is difficult, the multiplier adjustment method appears to be about one order of magnitude faster than the best previously existing algorithms for this problem.

Keywords: generalized assignment problem; branch and bound; Lagrangean relaxation (search for similar items in EconPapers)
Date: 1986
References: Add references at CitEc
Citations: View citations in EconPapers (62)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.32.9.1095 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:32:y:1986:i:9:p:1095-1103

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().