A New Exact Algorithm to Optimize a Linear Function over the Set of Efficient Solutions for Biobjective Mixed Integer Linear Programs

Alvaro Sierra Altamiranda () and Hadi Charkhgard ()
Additional contact information
Alvaro Sierra Altamiranda: Department of Industrial and Management Systems Engineering, University of South Florida, Tampa, Florida 33620
Hadi Charkhgard: Department of Industrial and Management Systems Engineering, University of South Florida, Tampa, Florida 33620

INFORMS Journal on Computing, 2019, vol. 31, issue 4, 823-840

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 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0851 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:31:y:2019:i:4:p:823-840

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().