A Criterion Space Search Algorithm for Biobjective Mixed Integer Programming: the Boxed Line Method
Tyler Perini (perinitagatech.edu )
Abstract: Despite recent interest in multiobjective integer programming, few algorithms exist for solving biobjective mixed integer programs. We present such an algorithm: the Boxed Line Method. For one of its variants, we prove that the number of single-objective integer programs solved is bounded by a linear function of the number of nondominated line segments in the nondominated frontier; this is the first such complexity result. An extensive computational study demonstrates that the Box Line Method is also efficient in practice, and that it outperforms existing algorithms on a diverse set of instances.
Keywords: multiobjective, integer programming, criterion space search
Category 1: Applications -- OR and Management Sciences
Citation: H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology, Atlanta, 09/2017.
Entry Submitted: 09/23/2017
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|