criterion space search

A Fast and Robust Algorithm for Solving Biobjective Mixed Integer Programs

  • Natashia Boland
  • Ian Herszterg
  • Diego Pecin
  • Martin Savelsbergh
  • Tyler Perini
    • Categories Multi-Criteria Optimization Tags , ,

    We present a fast and robust algorithm for solving biobjective mixed integer programs. The algorithm extends and merges ideas from two existing methods: the Boxed Line Method and the epsilon-Tabu Method. We demonstrate its efficacy in an extensive computational study. We also demonstrate that it is capable of producing a high-quality approximation of the nondominated … Read more

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

  • Natashia Boland
  • Diego Pecin
  • Martin Savelsbergh
  • Tyler Perini
    • Categories Applications - OR and Management Sciences Tags , ,

    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 … Read more