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

By Alves, C.; Mansi, R.; Pinto, T.; Valério De Carvalho, J.

ICORES 2012 - Proceedings of the 1st International Conference on Operations Research and Enterprise Systems



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.


Google Scholar: