A Branch and Bound Algorithm for a Class of Biobjective Mixed Integer Programs

• 成果类型: Article
• 署名作者: Stidsen, Thomas; Andersen, Kim Allan; Dammann, Bernd
• 署名单位: Technical University of Denmark; Aarhus University; Technical University of Denmark
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2013.1802
• 发表日期: 2014
• 页码: 1009-1032
• 关键词: biobjective optimization; integer programming; branch and bound

摘要

Most real-world optimization problems are multiobjective by nature, involving noncomparable objectives. Many of these problems can be formulated in terms of a set of linear objective functions that should be simultaneously optimized over a class of linear constraints. Often there is the complicating factor that some of the variables are required to be integral. The resulting class of problems is named multiobjective mixed integer programming (MOMIP) problems. Solving these kinds of optimization problems exactly requires a method that can generate the whole set of nondominated points (the Pareto-optimal front). In this paper, we first give a survey of the newly developed branch and bound methods for solving MOMIP problems. After that, we propose a new branch and bound method for solving a subclass of MOMIP problems, where only two objectives are allowed, the integer variables are binary, and one of the two objectives has only integer variables. The proposed method is able to find the full set of nondominated points. It is tested on a large number of problem instances, from six different classes of MOMIP problems. The results reveal that the developed biobjective branch and bound method performs better on five of the six test problems, compared with a generic two-phase method. At this time, the two-phase method is the most preferred exact method for solving MOMIP problems with two criteria and binary variables.