A BRANCH-AND-PRICE ALGORITHM FOR THE GENERALIZED ASSIGNMENT PROBLEM

Authors
SAVELSBERGH M
Citation
M. Savelsbergh, A BRANCH-AND-PRICE ALGORITHM FOR THE GENERALIZED ASSIGNMENT PROBLEM, Operations research, 45(6), 1997, pp. 831-841
Citations number
19
Journal title
Operations research → ACNP
ISSN journal
0030364X
Volume
45
Issue
6
Year of publication
1997
Pages
831 - 841
Database
ISI
SICI code
0030-364X(1997)45:6<831:ABAFTG>2.0.ZU;2-O
Abstract
The generalized assignment problem examines the maximum profit assignm ent of jobs to agents such that each job is assigned to precisely one agent subject to capacity restrictions on the agents. A new algorithm for the generalized assignment problem is presented that employs both column generation and branch-and-bound to obtain optimal integer solut ions to a set partitioning formulation of the problem.