IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v34y2022i2p909-933.html
   My bibliography  Save this article

Branch-and-Bound for Biobjective Mixed-Integer Linear Programming

Author

Listed:
  • Nathan Adelgren

    (Department of Mathematics and Computer Science, Edinboro University, Edinboro, Pennsylvania 16444; Andlinger Center for Energy and the Environment, Princeton University, Princeton, New Jersey 08544)

  • Akshay Gupte

    (School of Mathematics, University of Edinburgh, Edinburgh EH9 3FD, United Kingdom)

Abstract

We present a generic branch-and-bound algorithm for finding all the Pareto solutions of a biobjective mixed-integer linear program. The main contributions are new algorithms for obtaining dual bounds at a node, checking node fathoming, presolve, and duality gap measurement. Our branch-and-bound is predominantly a decision space search method because the branching is performed on the decision variables, akin to single objective problems, although we also sometimes split gaps and branch in the objective space. The various algorithms are implemented using a data structure for storing Pareto sets. Computational experiments are carried out on literature instances and on a new set of instances that we generate using a benchmark library (MIPLIB2017) for single objective problems. We also perform comparisons against the triangle splitting method from literature, which is an objective space search algorithm. Summary of Contribution: Biobjective mixed-integer optimization problems have two linear objectives and a mixed-integer feasible region. Such problems have many applications in operations research, because many real-world optimization problems naturally comprise two conflicting objectives to optimize or can be approximated in such a manner and are even harder than single objective mixed-integer programs. Solving them exactly requires the computation of all the nondominated solutions in the objective space, whereas some applications may also require finding at least one solution in the decision space corresponding to each nondominated solution. This paper provides an exact algorithm for solving these problems using the branch-and-bound method, which works predominantly in the decision space. Of the many ingredients of this algorithm, some parts are direct extensions of the single-objective version, but the main parts are newly designed algorithms to handle the distinct challenges of optimizing over two objectives. The goal of this study is to improve solution quality and speed and show that decision-space algorithms perform comparably to, and sometimes better than, algorithms that work mainly in the objective-space.

Suggested Citation

  • 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.
  • Handle: RePEc:inm:orijoc:v:34:y:2022:i:2:p:909-933
    DOI: 10.1287/ijoc.2021.1092
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2021.1092
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2021.1092?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
    ---><---

    References listed on IDEAS

    as
    1. Jesús A. De Loera & Raymond Hemmecke & Matthias Köppe, 2009. "Pareto Optima of Multicriteria Integer Linear Programs," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 39-48, February.
    2. Satya Tamby & Daniel Vanderpooten, 2021. "Enumeration of the Nondominated Set of Multiobjective Discrete Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 72-85, January.
    3. Bérubé, Jean-François & Gendreau, Michel & Potvin, Jean-Yves, 2009. "An exact [epsilon]-constraint method for bi-objective combinatorial optimization problems: Application to the Traveling Salesman Problem with Profits," European Journal of Operational Research, Elsevier, vol. 194(1), pages 39-50, April.
    4. 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.
    5. Przybylski, Anthony & Gandibleux, Xavier, 2017. "Multi-objective branch and bound," European Journal of Operational Research, Elsevier, vol. 260(3), pages 856-872.
    6. Matthias Ehrgott, 2006. "A discussion of scalarization techniques for multiple objective integer programming," Annals of Operations Research, Springer, vol. 147(1), pages 343-360, October.
    7. 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.
    8. 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.
    9. Serpil Sayin, 2003. "A Procedure to Find Discrete Representations of the Efficient Set with Specified Coverage Errors," Operations Research, INFORMS, vol. 51(3), pages 427-436, June.
    10. Ted Ralphs & Matthew Saltzman & Margaret Wiecek, 2006. "An improved algorithm for solving biobjective integer programs," Annals of Operations Research, Springer, vol. 147(1), pages 43-70, October.
    11. 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.
    12. 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.
    13. Arne Herzel & Stefan Ruzika & Clemens Thielen, 2021. "Approximation Methods for Multiobjective Optimization Problems: A Survey," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1284-1299, October.
    14. Johannes O. Royset & R. Kevin Wood, 2007. "Solving the Bi-Objective Maximum-Flow Network-Interdiction Problem," INFORMS Journal on Computing, INFORMS, vol. 19(2), pages 175-184, May.
    15. 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.
    16. Sophie N. Parragh & Fabien Tricoire, 2019. "Branch-and-Bound for Bi-objective Integer Programming," INFORMS Journal on Computing, INFORMS, vol. 31(4), pages 805-822, October.
    17. William Pettersson & Melih Ozlen, 2020. "Multiobjective Integer Programming: Synergistic Parallel Approaches," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 461-472, April.
    18. Soylu, Banu, 2015. "Heuristic approaches for biobjective mixed 0–1 integer linear programming problems," European Journal of Operational Research, Elsevier, vol. 245(3), pages 690-703.
    19. Nicolas Jozefowiez & Gilbert Laporte & Frédéric Semet, 2012. "A Generic Branch-and-Cut Algorithm for Multiobjective Optimization Problems: Application to the Multilabel Traveling Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 24(4), pages 554-564, November.
    20. 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.
    21. 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.
    22. Banu Lokman & Murat Köksalan, 2013. "Finding all nondominated points of multi-objective integer programs," Journal of Global Optimization, Springer, vol. 57(2), pages 347-365, October.
    23. Klein, Dieter & Hannan, Edward, 1982. "An algorithm for the multiple objective integer linear programming problem," European Journal of Operational Research, Elsevier, vol. 9(4), pages 378-385, April.
    24. 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.
    25. Sune Lauth Gadegaard & Lars Relund Nielsen & Matthias Ehrgott, 2019. "Bi-objective Branch-and-Cut Algorithms Based on LP Relaxation and Bound Sets," INFORMS Journal on Computing, INFORMS, vol. 31(4), pages 790-804, October.
    26. Joshua Q. Hale & Helin Zhu & Enlu Zhou, 2020. "Domination Measure: A New Metric for Solving Multiobjective Optimization," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 565-581, July.
    27. Francis Sourd & Olivier Spanjaard, 2008. "A Multiobjective Branch-and-Bound Framework: Application to the Biobjective Spanning Tree Problem," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 472-484, August.
    28. Shashi Mittal & Andreas S. Schulz, 2013. "A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One," Operations Research, INFORMS, vol. 61(2), pages 386-397, April.
    29. Bazgan, Cristina & Jamain, Florian & Vanderpooten, Daniel, 2017. "Discrete representation of the non-dominated set for multi-objective optimization problems using kernels," European Journal of Operational Research, Elsevier, vol. 260(3), pages 814-827.
    30. Tobias Achterberg & Robert E. Bixby & Zonghao Gu & Edward Rothberg & Dieter Weninger, 2020. "Presolve Reductions in Mixed Integer Programming," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 473-506, April.
    31. S. Ruzika & M. M. Wiecek, 2005. "Approximation Methods in Multiobjective Programming," Journal of Optimization Theory and Applications, Springer, vol. 126(3), pages 473-501, September.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    2. 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.
    3. Natashia Boland & Hadi Charkhgard & Martin Savelsbergh, 2015. "A Criterion Space Search Algorithm for Biobjective Integer Programming: The Balanced Box Method," INFORMS Journal on Computing, INFORMS, vol. 27(4), pages 735-754, November.
    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. Dinçer Konur & Hadi Farhangi & Cihan H. Dagli, 2016. "A multi-objective military system of systems architecting problem with inflexible and flexible systems: formulation and solution methods," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(4), pages 967-1006, October.
    6. Sune Lauth Gadegaard & Lars Relund Nielsen & Matthias Ehrgott, 2019. "Bi-objective Branch-and-Cut Algorithms Based on LP Relaxation and Bound Sets," INFORMS Journal on Computing, INFORMS, vol. 31(4), pages 790-804, October.
    7. 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.
    8. Seyyed Amir Babak Rasmi & Ali Fattahi & Metin Türkay, 2021. "SASS: slicing with adaptive steps search method for finding the non-dominated points of tri-objective mixed-integer linear programming problems," Annals of Operations Research, Springer, vol. 296(1), pages 841-876, January.
    9. 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.
    10. 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.
    11. 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.
    12. I. Kaliszewski & J. Miroforidis, 2022. "Probing the Pareto front of a large-scale multiobjective problem with a MIP solver," Operational Research, Springer, vol. 22(5), pages 5617-5673, November.
    13. Nathan Adelgren & Pietro Belotti & Akshay Gupte, 2018. "Efficient Storage of Pareto Points in Biobjective Mixed Integer Programming," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 324-338, May.
    14. Tolga Bektaş, 2018. "Disjunctive Programming for Multiobjective Discrete Optimisation," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 625-633, November.
    15. Satya Tamby & Daniel Vanderpooten, 2021. "Enumeration of the Nondominated Set of Multiobjective Discrete Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 72-85, January.
    16. Przybylski, Anthony & Gandibleux, Xavier, 2017. "Multi-objective branch and bound," European Journal of Operational Research, Elsevier, vol. 260(3), pages 856-872.
    17. Hadi Charkhgard & Martin Savelsbergh & Masoud Talebian, 2018. "Nondominated Nash points: application of biobjective mixed integer programming," 4OR, Springer, vol. 16(2), pages 151-171, June.
    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. 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.
    20. 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.

    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:inm:orijoc:v:34:y:2022:i:2:p:909-933. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.