A column generation approach for the bi-objective max-min knapsack problem

Abstract

In this paper, we propose a new approach to compute strong lower and upper bounds for the bi-objective maxmin knapsack problem. It relies on a reformulation of the problem using the Dantzig-Wolfe decomposition principle. The model resulting from this decomposition is an exponential integer linear program whose linear relaxation can be solved efficiently using a column generation procedure. We describe the details of this decomposition and the related column generation algorithm. To evaluate the performance of our approach, we conducted a set of comparative computational experiments on instances obtained with a generator described in the literature. The results obtained show that our approach outperforms other state-of-the-art methods.