A scatter search method for bi-criteria {0,1}-knapsack problems

This paper presents a scatter search (SS) based method for finding a good approximation of the non-dominated frontier for large size bi-criteria {0,1}-knapsack instances. The method follows the usual structure of SS: (1) diversification, (2) improvement, (3) reference set update, (4) subset generation, and (5) solution combination. For each component specific procedures were built which strongly benefit from the single criterion problem, and also from the characteristics of the neighbourhood of bi-criteria non-dominated solutions. These aspects permit the guidance and restriction of the exploration of the decision space. Experiments were carried out on a large set of instances and the computational results are presented. The approach seems to be very efficient and the quality of the approximation is quite good. These points are also discussed in the paper.