 Implementing an efficient fptas for the 0-1 multi-objective knapsack problemCristina Bazgan, Hadrien Hugot and Daniel Vanderpooten European Journal of Operational Research, 2009, vol. 198, issue 1, 47-56 Abstract: 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. Keywords: Multi-objective; knapsack; problem; Approximation; Dynamic; programming; Dominance; relations; Combinatorial; optimization (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:198:y:2009:i:1:p:47-56 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.