An Improved Algorithm for Biobjective Integer Programs

T.K. Ralphs (tkralphslehigh.edu)
M.J. Saltzman (mjsclemson.edu)
M.M. Wiecek (wmalgorclemson.edu)

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: biobjective programming, bicriteria optimization, multicriteria optimization, integer programming, discrete optimization, Pareto outcomes, nondominated outcomes, efficient solutions, scalarization

Category 1: Other Topics (Multi-Criteria Optimization )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Optimization Software and Modeling Systems (Problem Solving Environments )

Citation: Lehigh University Industrial and Systems Engineering Technical Report 04T-004

Download: [Postscript][PDF]

Entry Submitted: 10/08/2004
Entry Accepted: 10/08/2004
Entry Last Modified: 08/16/2005

Modify/Update this entry