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

Thomas Stidsen (), Kim Allan Andersen () and Bernd Dammann ()
Additional contact information
Thomas Stidsen: DTU Management, Technical University of Denmark, 2800 Copenhagen, Denmark
Kim Allan Andersen: CORAL, Department of Economics and Business, Aarhus University, 8000 Aarhus C, Denmark
Bernd Dammann: DTU Compute, Technical University of Denmark, 2800 Copenhagen, Denmark

Management Science, 2014, vol. 60, issue 4, 1009-1032

Abstract: 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. This paper was accepted by Dimitris Bertsimas, optimization.

Keywords: biobjective optimization; integer programming; branch and bound (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (39)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.2013.1802 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:60:y:2014:i:4:p:1009-1032

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().