the quadratic multiple knapsack problem and three heuristic approaches to it
The quadratic multiple knapsack problem extends the quadratic knapsack problem with K knapsacks, each with its own capacity C k . A greedy heuristic fills the knapsacks one at a time with objects whose contributions are likely to be large relative to their weights. A hill-climber and a genetic algorithm encode candidate solutions as strings over {0,1,..., K } with length equal to the number of objects. The hill-climber's neighbor operator is also the GA's mutation. In tests on 60 problem instances, the GA performed better than the greedy heuristic on the smaller instances, but it fell behind as the numbers of objects and knapsacks grew. The hill-climber always outperformed the greedy heuristic, and on the larger instances, also the GA.
quadratic multiple knapsack problem knapsack problems greedy heuristic hill-climber genetic algorithm