Implementing an efficient fptas for the 0–1 multi-objective knapsack problem
Bazgan, Cristina; Hugot, Hadrien; Vanderpooten, Daniel (2009), Implementing an efficient fptas for the 0–1 multi-objective knapsack problem, European Journal of Operational Research, 198, 1, p. 47-56. http://dx.doi.org/10.1016/j.ejor.2008.07.047
TypeArticle accepté pour publication ou publié
Journal nameEuropean Journal of Operational Research
MetadataShow full item record
Abstract (EN)In the present work, we are interested in the practical behavior of a new fully polynomial time approximation schemes (fptas) to solve the approximation version of the 0–1 multi-objective knapsack problem. The proposed methodology makes use of very general techniques (such as dominance relations in dynamic programming) and thus may be applicable in the implementation of fptas for other problems as well.Extensive numerical experiments on various types of instances in the bi and tri-objective cases establish that our method performs very well both in terms of CPU time and size of solved instances. We point out some reasons for the good practical performance of our algorithm. A comparison with an exact method and the fptas proposed in [Erlebach, T., Kellerer, H., Pferschy, U., 2002. Approximating multiobjective knapsack problems. Management Science 48 (12), 1603–1612] is also performed.
Subjects / KeywordsMulti-objective knapsack problem; Dominance relations; Dynamic programming; Approximation; Combinatorial optimization
Showing items related by title and author.
Discrete representation of the non-dominated set for multi-objective optimization problems using kernels Bazgan, Cristina; Jamain, Florian; Vanderpooten, Daniel (2017) Article accepté pour publication ou publié
An efficient procedure for finding best compromise solutions to the multi-objective assignment problem Belhoul, Lyes; Galand, Lucie; Vanderpooten, Daniel (2014) Article accepté pour publication ou publié