A Multiplier Adjustment Method for the Generalized Assignment Problem

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.