A column generation approach for the bi-objective max-min knapsack problem
Cláudio Alves, Raid Mansi, Telmo Pinto, José Valério de Carvalho
Proceedings of the 1st International Conference on Operations Research and Enterprise Systems - ICORES 2012
Vilamoura, Portugal, February 2012

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.

BIBTEX ENTRY
@inproceedings{AlvesMansiPintoCarvalhoICORES12,
author = {Cl{\'a}udio Alves and Ra{\"i}d Mansi and Jos{\'e} Val{\'e}rio de Carvalho and Telmo Pinto},
title = {A column generation approach for the bi-objective max-min knapsack problem},
booktitle = {Proceedings of the 1st International Conference on Operations Research and Enterprise Systems - ICORES 2012},
address = {Vilamoura, Portugal},
year = {2012}}