IDEAS home Printed from https://ideas.repec.org/a/spr/mathme/v100y2024i1d10.1007_s00186-023-00843-y.html
   My bibliography  Save this article

A fast and robust algorithm for solving biobjective mixed integer programs

Author

Listed:
  • 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)

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

Suggested Citation

  • Diego Pecin & Ian Herszterg & Tyler Perini & Natashia Boland & Martin Savelsbergh, 2024. "A fast and robust algorithm for solving biobjective mixed integer programs," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 100(1), pages 221-262, August.
    • Handle: RePEc:spr:mathme:v:100:y:2024:i:1:d:10.1007_s00186-023-00843-y
    DOI: 10.1007/s00186-023-00843-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00186-023-00843-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s00186-023-00843-y?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Klamroth, Kathrin & Lacour, Renaud & Vanderpooten, Daniel, 2015. "On the representation of the search region in multi-objective optimization," European Journal of Operational Research, Elsevier, vol. 245(3), pages 767-778.
    2. Y. P. Aneja & K. P. K. Nair, 1979. "Bicriteria Transportation Problem," Management Science, INFORMS, vol. 25(1), pages 73-78, January.
    3. Fattahi, Ali & Turkay, Metin, 2018. "A one direction search method to find the exact nondominated frontier of biobjective mixed-binary linear programming problems," European Journal of Operational Research, Elsevier, vol. 266(2), pages 415-425.
    4. Boland, Natashia & Charkhgard, Hadi & Savelsbergh, Martin, 2017. "The Quadrant Shrinking Method: A simple and efficient algorithm for solving tri-objective integer programs," European Journal of Operational Research, Elsevier, vol. 260(3), pages 873-885.
    5. Kerstin Dächert & Kathrin Klamroth, 2015. "A linear bound on the number of scalarizations needed to solve discrete tricriteria optimization problems," Journal of Global Optimization, Springer, vol. 61(4), pages 643-676, April.
    6. Thomas Stidsen & Kim Allan Andersen & Bernd Dammann, 2014. "A Branch and Bound Algorithm for a Class of Biobjective Mixed Integer Programs," Management Science, INFORMS, vol. 60(4), pages 1009-1032, April.
    7. Mavrotas, G. & Diakoulaki, D., 1998. "A branch and bound algorithm for mixed zero-one multiple objective linear programming," European Journal of Operational Research, Elsevier, vol. 107(3), pages 530-541, June.
    8. Soylu, Banu, 2018. "The search-and-remove algorithm for biobjective mixed-integer linear programming problems," European Journal of Operational Research, Elsevier, vol. 268(1), pages 281-299.
    9. Kirlik, Gokhan & Sayın, Serpil, 2014. "A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems," European Journal of Operational Research, Elsevier, vol. 232(3), pages 479-488.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Carlos Henggeler Antunes & Carlos M. Fonseca & Luís Paquete & Michael Stiglmayr, 2024. "Special issue on exact and approximation methods for mixed-integer multi-objective optimization," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 100(1), pages 1-4, August.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Julius Bauß & Michael Stiglmayr, 2024. "Augmenting bi-objective branch and bound by scalarization-based information," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 100(1), pages 85-121, August.
    2. Ozgu Turgut & Evrim Dalkiran & Alper E. Murat, 2019. "An exact parallel objective space decomposition algorithm for solving multi-objective integer programming problems," Journal of Global Optimization, Springer, vol. 75(1), pages 35-62, September.
    3. Nathan Adelgren & Akshay Gupte, 2022. "Branch-and-Bound for Biobjective Mixed-Integer Linear Programming," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 909-933, March.
    4. De Santis, Marianna & Grani, Giorgio & Palagi, Laura, 2020. "Branching with hyperplanes in the criterion space: The frontier partitioner algorithm for biobjective integer programming," European Journal of Operational Research, Elsevier, vol. 283(1), pages 57-69.
    5. David Bergman & Merve Bodur & Carlos Cardonha & Andre A. Cire, 2022. "Network Models for Multiobjective Discrete Optimization," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 990-1005, March.
    6. Forget, Nicolas & Gadegaard, Sune Lauth & Nielsen, Lars Relund, 2022. "Warm-starting lower bound set computations for branch-and-bound algorithms for multi objective integer linear programs," European Journal of Operational Research, Elsevier, vol. 302(3), pages 909-924.
    7. Tyler Perini & Natashia Boland & Diego Pecin & Martin Savelsbergh, 2020. "A Criterion Space Method for Biobjective Mixed Integer Programming: The Boxed Line Method," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 16-39, January.
    8. Przybylski, Anthony & Gandibleux, Xavier, 2017. "Multi-objective branch and bound," European Journal of Operational Research, Elsevier, vol. 260(3), pages 856-872.
    9. Guillermo Cabrera-Guerrero & Matthias Ehrgott & Andrew J. Mason & Andrea Raith, 2022. "Bi-objective optimisation over a set of convex sub-problems," Annals of Operations Research, Springer, vol. 319(2), pages 1507-1532, December.
    10. Fritz Bökler & Sophie N. Parragh & Markus Sinnl & Fabien Tricoire, 2024. "An outer approximation algorithm for generating the Edgeworth–Pareto hull of multi-objective mixed-integer linear programming problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 100(1), pages 263-290, August.
    11. Holzmann, Tim & Smith, J.C., 2018. "Solving discrete multi-objective optimization problems using modified augmented weighted Tchebychev scalarizations," European Journal of Operational Research, Elsevier, vol. 271(2), pages 436-449.
    12. Boland, Natashia & Charkhgard, Hadi & Savelsbergh, Martin, 2019. "Preprocessing and cut generation techniques for multi-objective binary programming," European Journal of Operational Research, Elsevier, vol. 274(3), pages 858-875.
    13. Dächert, Kerstin & Klamroth, Kathrin & Lacour, Renaud & Vanderpooten, Daniel, 2017. "Efficient computation of the search region in multi-objective optimization," European Journal of Operational Research, Elsevier, vol. 260(3), pages 841-855.
    14. Kerstin Dächert & Tino Fleuren & Kathrin Klamroth, 2024. "A simple, efficient and versatile objective space algorithm for multiobjective integer programming," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 100(1), pages 351-384, August.
    15. Ceyhan, Gökhan & Köksalan, Murat & Lokman, Banu, 2019. "Finding a representative nondominated set for multi-objective mixed integer programs," European Journal of Operational Research, Elsevier, vol. 272(1), pages 61-77.
    16. Konur, Dinçer & Campbell, James F. & Monfared, Sepideh A., 2017. "Economic and environmental considerations in a stochastic inventory control model with order splitting under different delivery schedules among suppliers," Omega, Elsevier, vol. 71(C), pages 46-65.
    17. Doğan, Ilgın & Lokman, Banu & Köksalan, Murat, 2022. "Representing the nondominated set in multi-objective mixed-integer programs," European Journal of Operational Research, Elsevier, vol. 296(3), pages 804-818.
    18. Boland, Natashia & Charkhgard, Hadi & Savelsbergh, Martin, 2017. "The Quadrant Shrinking Method: A simple and efficient algorithm for solving tri-objective integer programs," European Journal of Operational Research, Elsevier, vol. 260(3), pages 873-885.
    19. Cacchiani, Valentina & D’Ambrosio, Claudia, 2017. "A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs," European Journal of Operational Research, Elsevier, vol. 260(3), pages 920-933.
    20. Yıldız, Gazi Bilal & Soylu, Banu, 2019. "A multiobjective post-sales guarantee and repair services network design problem," International Journal of Production Economics, Elsevier, vol. 216(C), pages 305-320.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:mathme:v:100:y:2024:i:1:d:10.1007_s00186-023-00843-y. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.