Title: A polyhedral approach for the generalized assignment problem
Authors: Degraeve, Zeger
Tistaert, J
Issue Date: 1995
Publisher: K.U.Leuven - Departement toegepaste economische wetenschappen
Series Title: DTEW Research Report 9533 pages:1-16
Abstract: The generalized assignment problem (GAP) consists of finding a maximal profit assignment of n jobs over m capacity constrained agents, whereby each job has to be processed by only one agent. This contribution approaches the GAP from the polyhedral point of view. A good upper bound is obtained by approximating the convex hull of the knapsack constraints in the GAP-polytope using theoretical work of Balas. Based on this result, we propose a procedure for finding close-to-optimal solutions, which gives us a lower bound. Computational results on a set of 60representative and highly capacitated problems indicate that these solutions lie within 0.06% of the optimum. After applying some preprocessing techniques and using the obtained bounds, we solve the generated instances to optimality by branch and bound within reasonable computing time.
Publication status: published
KU Leuven publication type: IR
Appears in Collections:Research Center for Operations Research and Business Statistics (ORSTAT), Leuven

Files in This Item:
File Status SizeFormat
OR_9533.pdf Published 644KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.