.png){kind=icon}
.png){kind=icon}
Return
Solving the generalised assignment problem using polyhedral results
.png){kind=icon}
PRE
AI
DOI：10.1016/S0377-2217(97)00054-4.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The Generalised Assignment Problem (GAP) consists of finding a maximal profit assignment of n tasks over in capacity constrained agents, whereby each task has to be processed by only one agent. We develop 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. This improvement yields a good upper bound and closes the gap by an additional 15% on average. Based on this result, we propose two heuristics for finding close-to-optimal solutions, giving us 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, we solve the generated instances to optimality by Branch-and-Bound (B & B) within reasonable computing time. (C) 1998 Elsevier Science B.V.
Keywords:
generalised assignment problem
knapsack polytope
decomposition
integer programming
branch-and-bound
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
Organization
No organization information available