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.
Citation
H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology, Atlanta, 09/2017.