A fast and robust algorithm for solving biobjective mixed integer programs

Diego Pecin, Ian Herszterg, Tyler Perini (), Natashia Boland and Martin Savelsbergh
Additional contact information
Diego Pecin: Erasmus University Rotterdam
Ian Herszterg: Georgia Institute of Technology
Tyler Perini: United States Naval Academy
Natashia Boland: Georgia Institute of Technology
Martin Savelsbergh: Georgia Institute of Technology

Mathematical Methods of Operations Research, 2024, vol. 100, issue 1, No 9, 262 pages

Abstract: Abstract We present a fast and robust algorithm for solving biobjective mixed integer linear programs. Two existing methods are studied: $$\epsilon $$ ϵ -Tabu Method and the Boxed Line Method. By observing structural characteristics of nondominated frontiers and computational bottlenecks, we develop enhanced versions of each method. Limitations of the current state of test instances are observed, and a new body of instances are generated to diversify computational standards. We demonstrate efficacy with a computational study. The enhancement to $$\epsilon $$ ϵ -Tabu Method offers an average speed-up factor of 3 on some instances; the enhancement to Boxed Line Method offers an average speed-up factor of 18 on some instances. A hybrid, two-phase method is designed to leverage the strengths of each method with its corresponding enhancement, thus having a robust approach to a wider range of instances; it outperforms on all instances with a typical speed-up factor of 2–3. We also demonstrate that it is capable of producing a high-quality approximation of the nondominated frontier in a fraction of the time required to produce the complete nondominated frontier. Graphic Abstract

Keywords: Biobjective mixed integer program; Criterion space search; Approximation (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s00186-023-00843-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:mathme:v:100:y:2024:i:1:d:10.1007_s00186-023-00843-y

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-023-00843-y

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().