Article ID: | iaor20052710 |
Country: | Netherlands |
Volume: | 159 |
Issue: | 3 |
Start Page Number: | 545 |
End Page Number: | 557 |
Publication Date: | Dec 2004 |
Journal: | European Journal of Operational Research |
Authors: | Ong Hoon Liong, Zhang Cai Wen |
Keywords: | heuristics, programming: linear, programming: multiple criteria |
In this paper, we propose a simple and useful method, the core of which is an efficient LP-based heuristic, for solving biobjective 0–1 knapsack problems. Extensive computational experiments show that the proposed method is able to generate a good approximation to the nondominated set very efficiently. We also suggest three qualitative criteria to evaluate such an approximation. In addition, the method can be extended to other problems having properties similar to the knapsack problem.