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

Thomas Riis Stidsen, Kim Allan Andersen, Bernd Dammann

Research output: Contribution to journalJournal articleResearchpeer-review

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.
Original languageEnglish
JournalManagement Science
Volume60
Issue number4
Pages (from-to)1009-1032
ISSN0025-1909
DOIs
Publication statusPublished - 2014

Keywords

  • OPERATIONS
  • MANAGEMENT
  • ASSIGNMENT PROBLEM
  • OPTIMIZATION
  • POINTS
  • biobjective optimization
  • integer programming
  • branch and bound
  • Biobjective optimization
  • Branch and bound
  • Integer programming
  • Algorithms
  • Branch and bound method
  • Linear programming
  • Multiobjective optimization
  • Bi-objective optimization
  • Branch-and-bound algorithms
  • Linear objective functions
  • Mixed integer programming
  • Mixed-integer programs
  • Optimization problems
  • Pareto-optimal front
  • Real-world optimization
  • Problem solving

Fingerprint Dive into the research topics of 'A Branch and Bound Algorithm for a Class of Biobjective Mixed Integer Programs'. Together they form a unique fingerprint.

Cite this