Effective algorithm and heuristic for the generalized assignment problem |
| |
Affiliation: | 1. Electrical Engineering Department, Federal University of Juiz de Fora (UFJF), Brazil;2. Computer Science Department, Federal University of Juiz de Fora (UFJF), Brazil;3. Smarti9 Ltda. - Juiz de Fora, Brazil |
| |
Abstract: | We present new Branch-and-Bound algorithm for the generalized assignment problem. A standard subgradient method (SM), used at each node of the decision tree to solve the Lagrangian dual, provides an upper bound. Our key contribution in this paper is a new heuristic, applied at each iteration of the SM, which tries to exploit the solution of the relaxed problem, by solving a smaller generalized assignment problem. The feasible solution found is then subjected to a solution improvement heuristic. We consider processing the root node as a Lagrangian heuristic. Computational comparisons are made with new existing methods. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|