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

Bi-objective Branch-and-Cut Algorithms Based on LP Relaxation and Bound Sets

Author

Listed:
  • Sune Lauth Gadegaard

    (Department of Economics and Business Economics, School of Business and Social Sciences, Aarhus University, DK-8210 Aarhus V, Denmark;)

  • Lars Relund Nielsen

    (Department of Economics and Business Economics, School of Business and Social Sciences, Aarhus University, DK-8210 Aarhus V, Denmark;)

  • Matthias Ehrgott

    (Department of Management Science, Lancaster University, Lancaster LA1 4YX, United Kingdom)

Abstract

Most real-world optimization problems are multi-objective by nature, with conflicting and incomparable objectives. Solving a multi-objective optimization problem requires a method that can generate all rational compromises between the objectives. This paper proposes two distinct bound set-based branch-and-cut algorithms for general bi-objective combinatorial optimization problems based on implicit and explicit lower-bound sets. The algorithm based on explicit lower-bound sets computes, for each branching node, a lower-bound set and compares it with an upper-bound set. The other fathoms branching nodes by generating a single point on the lower-bound set for each local nadir point. We outline several approaches for fathoming branching nodes, and we propose an updating scheme for the lower-bound sets that prevents us from solving the bi-objective linear programming relaxation of each branching node. To strengthen the lower-bound sets, we propose a bi-objective cutting-plane algorithm that adjusts the weights of the objective functions such that different parts of the feasible set are strengthened by cutting planes. In addition, we suggest an extension of the branching strategy “Pareto branching.” We prove the effectiveness of the algorithms through extensive computational results.

Suggested Citation

  • 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.
  • Handle: RePEc:inm:orijoc:v:31:y:2019:i:4:p:790-804
    DOI: 10.1287/ijoc.2018.0846
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2018.0846
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2018.0846?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. Chalmet, L. G. & Lemonidis, L. & Elzinga, D. J., 1986. "An algorithm for the bi-criterion integer programming problem," European Journal of Operational Research, Elsevier, vol. 25(2), pages 292-300, May.
    2. Y. P. Aneja & K. P. K. Nair, 1979. "Bicriteria Transportation Problem," Management Science, INFORMS, vol. 25(1), pages 73-78, 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. Gülseren Kiziltan & Erkut Yucaou{g}lu, 1983. "An Algorithm for Multiobjective Zero-One Linear Programming," Management Science, INFORMS, vol. 29(12), pages 1444-1453, December.
    5. Fernandez, Elena & Puerto, Justo, 2003. "Multiobjective solution of the uncapacitated plant location problem," European Journal of Operational Research, Elsevier, vol. 145(3), pages 509-529, March.
    6. Przybylski, Anthony & Gandibleux, Xavier, 2017. "Multi-objective branch and bound," European Journal of Operational Research, Elsevier, vol. 260(3), pages 856-872.
    7. Ramos, R. M. & Alonso, S. & Sicilia, J. & Gonzalez, C., 1998. "The problem of the optimal biobjective spanning tree," European Journal of Operational Research, Elsevier, vol. 111(3), pages 617-628, December.
    8. Christian Roed Pedersen & Lars Relund Nielsen & Kim Allan Andersen, 2008. "The Bicriterion Multimodal Assignment Problem: Introduction, Analysis, and Experimental Results," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 400-411, August.
    9. 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.
    10. Dial, Robert B., 1979. "A model and algorithm for multicriteria route-mode choice," Transportation Research Part B: Methodological, Elsevier, vol. 13(4), pages 311-316, December.
    11. 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.
    12. 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.
    13. Przybylski, Anthony & Gandibleux, Xavier & Ehrgott, Matthias, 2008. "Two phase algorithms for the bi-objective assignment problem," European Journal of Operational Research, Elsevier, vol. 185(2), pages 509-533, March.
    14. 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.
    15. 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.
    16. Florios, Kostas & Mavrotas, George & Diakoulaki, Danae, 2010. "Solving multiobjective, multiconstraint knapsack problems using mathematical programming and evolutionary algorithms," European Journal of Operational Research, Elsevier, vol. 203(1), pages 14-21, May.
    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. 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.
    2. 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.
    3. 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.
    4. 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.

    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. Przybylski, Anthony & Gandibleux, Xavier, 2017. "Multi-objective branch and bound," European Journal of Operational Research, Elsevier, vol. 260(3), pages 856-872.
    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. 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.
    4. 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.
    5. Markus Leitner & Ivana Ljubić & Markus Sinnl, 2015. "A Computational Study of Exact Approaches for the Bi-Objective Prize-Collecting Steiner Tree Problem," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 118-134, February.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. Masar Al-Rabeeah & Santosh Kumar & Ali Al-Hasani & Elias Munapo & Andrew Eberhard, 2019. "Bi-objective integer programming analysis based on the characteristic equation," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 10(5), pages 937-944, October.
    13. 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.
    14. Mavrotas, George & Florios, Kostas, 2013. "An improved version of the augmented epsilon-constraint method (AUGMECON2) for finding the exact Pareto set in Multi-Objective Integer Programming problems," MPRA Paper 105034, University Library of Munich, Germany.
    15. 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.
    16. Alves, Maria Joao & Climaco, Joao, 2007. "A review of interactive methods for multiobjective integer and mixed-integer programming," European Journal of Operational Research, Elsevier, vol. 180(1), pages 99-115, July.
    17. 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.
    18. 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.
    19. 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.
    20. Audrey Cerqueus & Xavier Gandibleux & Anthony Przybylski & Frédéric Saubion, 2017. "On branching heuristics for the bi-objective 0/1 unidimensional knapsack problem," Journal of Heuristics, Springer, vol. 23(5), pages 285-319, October.

    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:31:y:2019:i:4:p:790-804. 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.