A hybrid tabu search/branch & bound approach to solving the generalized assignment problem |
| |
Authors: | Andrew J Woodcock John M Wilson |
| |
Institution: | 1. Nottingham University Business School, NG8 1BB, UK;2. Loughborough University, LE11 3TU, UK;3. Aberystwyth University, SY23 2DD, UK |
| |
Abstract: | A new approach for solving the generalized assignment problem (GAP) is proposed that combines the exact branch & bound approach with the heuristic strategy of tabu search (TS) to produce a hybrid algorithm for solving GAP. The algorithm described uses commercial software to solve sub-problems generated by the TS guiding strategy. The TS approach makes use of the concept of referent domain optimisation and introduces novel add/drop strategies. In addition, the linear programming relaxation of GAP that forms part of the branch & bound approach is itself helpful in suggesting which variables might take binary values. Computational results on benchmark test instances are presented and compared with results obtained by the standard branch & bound approach and also several other heuristic approaches from the literature. The results show the new algorithm performs competitively against the alternatives and is able to find some new best solutions for several benchmark instances. |
| |
Keywords: | Integer programming Tabu search Branch and bound Generalized assignment problem |
本文献已被 ScienceDirect 等数据库收录! |