Publication

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

Bibliographic Details
Summary:	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.
Main Authors:	Alves, Cláudio
Other Authors:	Mansi, Raid; Pinto, Telmo; Carvalho, J. M. Valério de
Subject:	Integer programming Column generation Max-min knapsack problem
Year:	2012
Country:	Portugal
Document type:	conference paper
Access type:	restricted access
Associated institution:	Universidade do Minho
Language:	English
Origin:	RepositóriUM - Universidade do Minho

Description
Summary:	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.

No funded projects found.