A virtual pegging approach to the max–min optimization of the bi-criteria knapsack problem

Abstract

We are concerned with a variation of the knapsack problem, the bi-objective max–min knapsack problem (BKP), where the values of items differ under two possible scenarios. We have given a heuristic algorithm and an exact algorithm to solve this problem. In particular, we introduce a surrogate relaxation to derive upper and lower bounds very quickly, and apply the pegging test to reduce the size of BKP. We also exploit this relaxation to obtain an upper bound in the branch-and-bound algorithm to solve the reduced problem. To further reduce the problem size, we propose a ‘virtual pegging’ algorithm and solve BKP to optimality. As a result, for problems with up to 16,000 items, we obtain a very accurate approximate solution in less than a few seconds. Except for some instances, exact solutions can also be obtained in less than a few minutes on ordinary computers. However, the proposed algorithm is less effective for strongly correlated instances.

Keywords:

• knapsack problem
• bi-objective combinatorial optimization
• pegging test

2000 AMS Subject Classification :

• 90C27
• 90C29
• 49K35

Acknowledgements

The authors are grateful to anonymous referees for their careful reading of the manuscript and helpful comments.