| Article ID: | iaor20042833 |
| Country: | United Kingdom |
| Volume: | 30 |
| Issue: | 12 |
| Start Page Number: | 1865 |
| End Page Number: | 1886 |
| Publication Date: | Oct 2003 |
| Journal: | Computers and Operations Research |
| Authors: | Captivo M. Eugnia, Clmaco Joo, Figueira Jos, Martins Ernesto, Santos Jos Luis |
| Keywords: | networks: path |
This paper examines the performances of a new labeling algorithm to find all the efficient paths (or non-dominated evaluation vectors) of the bicriteria 0–1 knapsack problem. To our knowledge this is the first time a bicriteria 0–1 knapsack is solved taking advantage of its previous conversion into a bicriteria shortest path problem over an acyclic network. Computational experiments and results are also presented regarding bicriteria instances of up to 900 items. The algorithm is very efficient for the hard bicriteria 0–1 knapsack instances considered in the paper.