Optimization Online


A Criterion Space Search Algorithm for Biobjective Mixed Integer Programming: the Boxed Line Method

Tyler Perini(perinita***at***gatech.edu )
Natashia Boland(natashia.boland***at***isye.gatech.edu )
Diego Pecin(diego.pecin***at***isye.gatech.edu )
Martin Savelsbergh(martin.savelsbergh***at***isye.gatech.edu )

Abstract: Criterion space search algorithms for multiobjective integer and mixed integer programming have gained in popularity in the past decade and many of the fastest algorithms for generating the nondominated frontier belong to this class of algorithms. We propose a new criterion space search algorithm for solving biobjective mixed integer programs: the Boxed Line Method. For one variant of the algorithm, we show that the number of single-objective mixed integer programs solved is a linear function of the number of line segments in the nondominated frontier. A computational study demonstrates that the algorithm also performs well in practice, outperforming existing algorithms.

Keywords: biobjective mixed integer programming, criterion space search, performance analysis

Category 1: Applications -- OR and Management Sciences

Citation: H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology, Atlanta, 09/2017.

Download: [PDF]

Entry Submitted: 09/23/2017
Entry Accepted: 09/25/2017
Entry Last Modified: 09/23/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society