Computing the Pareto front of bi-objective mixed-integer linear programming problems

Bratislava Popovic, Term project, Spring 2009

Supervisors: Marco Laumanns, Gabrio Caimi

Keywords: Bi-objective optimization, Mixed integer programming, Pareto front, output sensitive complexity

Abstract

Many real-world problems involve multiple conflicting objectives. Railway timetables, for instance, should provide short travel times for customers, but large buffer times to avoid delay propagation. A detailed knowledge of the trade-offs between the conflicting goals and attainable compromises is therefore very important for the decision makers. That is why the identification of Pareto optimal solutions is a key task in multi-objective optimization. In this thesis we develop, implement and test an algorithm to compute the entire Pareto front of bi-objective Mixed-Integer Linear Programming (MILP) problems exactly. The developed algorithm iteratively explores the objective space, looking for yet undiscovered Pareto optimal objective vectors, by solving a sequence of single-objective MILPs. We compare our results with the ones obtained using the multi-criteria branch and bound (MCBB) algorithm described by Mavrotas et al. in 2005.