Strategic oscillation for the quadratic multiple knapsack problem |
| |
Authors: | Carlos García-Martínez Fred Glover Francisco J. Rodriguez Manuel Lozano Rafael Martí |
| |
Affiliation: | 1. Department of Computing and Numerical Analysis, University of Córdoba, Córdoba, 14071, Spain 2. OptTek Systems, Boulder, CO, USA 3. Department of Computer Sciences and Artificial Intelligence, University of Granada, Granada, 18071, Spain 4. Department of Statistics and Operations Research, University of Valencia, Valencia, Spain
|
| |
Abstract: | The quadratic multiple knapsack problem (QMKP) consists in assigning a set of objects, which interact through paired profit values, exclusively to different capacity-constrained knapsacks with the aim of maximising total profit. Its many applications include the assignment of workmen to different tasks when their ability to cooperate may affect the results. Strategic oscillation (SO) is a search strategy that operates in relation to a critical boundary associated with important solution features (such as feasibility). Originally proposed in the context of tabu search, it has become widely applied as an efficient memory-based methodology. We apply strategic oscillation to the quadratic multiple knapsack problem, disclosing that SO effectively exploits domain-specific knowledge, and obtains solutions of particularly high quality compared to those obtained by current state-of-the-art algorithms. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|