An Improved Dual-Based Algorithm for the Generalized Assignment Problem.

The generalized assignment problem (GAP) examines the minimum cost assignment of n jobs to m agents such that each job is assigned to exactly one agent subject to an agent's capacity. Existing solution algorithms have not solved GAPs with more than 100 decision variables. This paper designs and validates an optimization algorithm for the GAP that effectively solves GAPs with up to 500 variables. Compared with existing procedures, this algorithm requires fewer enumeration nodes and shorter running times. Improved performance stems from an enhanced Lagrangean dual-ascent procedure that solves a Lagrangean dual at each enumeration node, from adding a surrogate constraint to the Lagrangean relaxed model, and from an elaborate branch and bound scheme. An empirical investigation of various problem structures, not considered in existing literature, is also presented.