Title: Solving the generalized assignment problem using polyhedral results
Authors: Cattrysse, Dirk ×
Degraeve, Zeger
Tistaert, J #
Issue Date: 1998
Series Title: European Journal of Operational Research vol:108 issue:3 (Aug.) pages:618-628
Abstract: The Generalized Assignment Problem (GAP) consists of finding a maximal profit assignment of n tasks over m capacity constrained agents, whereby each task has to be processed by only one agent. An improved implementation of the standard procedure for generating lifted cover inequalities describing an approximation to the convex hull of the knapsack constraints in the GAP polytope is developed. This improvement yields a good upper bound and closes the gap by an additional 15% on average. Based on this result, 2 heuristics are proposed for finding close-to-optimal solutions, giving a tight lower bound. Computational results on a set of 60 representative and highly capacitated problems indicate that these solutions lie within 0.06% of the optimum. After applying some pre-processing techniques and using the obtained bounds, the generated instances are solved to optimality by Branch-and-Bound within reasonable computing time
ISSN: 0377-2217
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Centre for Industrial Management / Traffic & Infrastructure
Research Center for Operations Research and Business Statistics (ORSTAT), Leuven
× corresponding author
# (joint) last author

Files in This Item:

There are no files associated with this item.

Request a copy


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

© Web of science