Article ID: | iaor20121261 |
Volume: | 39 |
Issue: | 9 |
Start Page Number: | 1988 |
End Page Number: | 2000 |
Publication Date: | Sep 2012 |
Journal: | Computers and Operations Research |
Authors: | Thompson Jonathan, Wu Yue, Lewis Rhyd, Song Xiang |
Keywords: | programming: integer, heuristics |
This paper introduces a fast heuristic based algorithm for the max–min multi‐scenario knapsack problem. The problem is a variation of the standard 0–1 knapsack problem, in which the profits of the items vary under different scenarios, though the capacity of the knapsack is fixed. The objective of the problem is to find the optimal packing of a set of items so that the minimum total profits of the items in the knapsack over all different scenarios is maximized. For some large‐scaled instances, traditional branch‐and‐bound techniques cannot find an optimal solution within reasonable time, thus we propose a collection of incomplete