A New Exact Algorithm to Optimize a Linear Function over the Set of Efficient Solutions for Biobjective Mixed Integer Linear Programs
Alvaro Sierra Altamiranda, Hadi Charkhgard
INFORMS Journal on Computing · 2019 · Volume 31 · Issue 4
Abstract
We present the first (criterion space search) algorithm for optimizing a linear function over the set of efficient solutions of biobjective mixed integer linear programs. The proposed algorithm is developed based on the triangle splitting method [Boland N, Charkhgard H, Savelsbergh M (2015) A criterion space search algorithm for biobjective mixed integer programming: The triangle splitting method. INFORMS J. Comput . 27(4):597–618.], which can find a full representation of the nondominated frontier of any biobjective mixed integer linear program. The proposed algorithm is easy to implement and converges quickly to an optimal solution. An extensive computational study shows the efficacy of the algorithm. We numerically show that the proposed algorithm can be used to quickly generate a provably high-quality approximate solution because it maintains a lower and an upper bound on the optimal value of the linear function at any point in time.
Keywords
biobjective mixed integer linear programming, criterion space search algorithm, optimization over efficient frontier, triangle splitting method
Enable JavaScript for citation tools and additional paper interactions.