An improved algorithm for solving biobjective integer programs |
| |
Authors: | Ted K Ralphs Matthew J Saltzman Margaret M Wiecek |
| |
Institution: | (1) Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA, USA;(2) Department of Mathematical Sciences, Clemson University, Clemson, SC, USA |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|