Article ID: | iaor20072067 |
Country: | Germany |
Volume: | 147 |
Issue: | 1 |
Start Page Number: | 43 |
End Page Number: | 70 |
Publication Date: | Oct 2006 |
Journal: | Annals of Operations Research |
Authors: | Saltzman Matthew J., Wiecek Margaret M., Ralphs Ted K. |
A parametric algorithm for identifying the Pareto set of a biobjective integer program is proposed. The algorithm is based on the weighted Chebyshev (Tchebycheff) scalarization, and its running time is asymptotically optimal. A number of extensions are described, including: a technique for handling weakly dominated outcomes, a Pareto set approximation scheme, and an interactive version that provides access to all Pareto outcomes. Extensive computational tests on instances of the biobjective knapsack problem and a capacitated network routing problem are presented.