IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v322y2025i2p376-400.html
   My bibliography  Save this article

Benders decomposition for bi-objective linear programs

Author

Listed:
  • Raith, Andrea
  • Lusby, Richard
  • Sohrabi Yousefkhan, Ali Akbar

Abstract

In this paper, we develop a new decomposition technique for solving bi-objective linear programming problems. The proposed methodology combines the bi-objective simplex algorithm with Benders decomposition and can be used to obtain a complete set of efficient extreme solutions, and the corresponding set of extreme non-dominated points, for a bi-objective linear programme. Using a Benders-like reformulation, the decomposition approach decouples the problem into a bi-objective master problem and a bi-objective subproblem, each of which is solved using the bi-objective parametric simplex algorithm. The master problem provides candidate efficient solutions that the subproblem assesses for feasibility and optimality. As in standard Benders decomposition, optimality and feasibility cuts are generated by the subproblem and guide the master problem solve. This paper discusses bi-objective Benders decomposition from a theoretical perspective, proves the correctness of the proposed reformulation and addresses the need for so-called weighted optimality cuts. Furthermore, we present an algorithm to solve the reformulation and discuss its performance for three types of bi-objective optimisation problems.

Suggested Citation

  • Raith, Andrea & Lusby, Richard & Sohrabi Yousefkhan, Ali Akbar, 2025. "Benders decomposition for bi-objective linear programs," European Journal of Operational Research, Elsevier, vol. 322(2), pages 376-400.
    • Handle: RePEc:eee:ejores:v:322:y:2025:i:2:p:376-400
    DOI: 10.1016/j.ejor.2024.09.004
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724006957
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.09.004?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

    for a different version of it.

    References listed on IDEAS

    as
    1. Glize, Estèle & Roberti, Roberto & Jozefowiez, Nicolas & Ngueveu, Sandra Ulrich, 2020. "Exact methods for mono-objective and Bi-Objective Multi-Vehicle Covering Tour Problems," European Journal of Operational Research, Elsevier, vol. 283(3), pages 812-824.
    2. Jean-François Cordeau & Goran Stojković & François Soumis & Jacques Desrosiers, 2001. "Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling," Transportation Science, INFORMS, vol. 35(4), pages 375-388, November.
    3. Yogesh Agarwal & Yash Aneja, 2012. "Fixed-Charge Transportation Problem: Facets of the Projection Polyhedron," Operations Research, INFORMS, vol. 60(3), pages 638-654, June.
    4. Bastian Amberg & Boris Amberg & Natalia Kliewer, 2019. "Robust Efficiency in Urban Public Transportation: Minimizing Delay Propagation in Cost-Efficient Bus and Driver Schedules," Service Science, INFORMS, vol. 53(1), pages 89-112, February.
    5. QIU, Feng & AHMED, Shabbir & DEY, Santanu S & WOLSEY, Laurence A, 2014. "Covering linear programming with violations," LIDAM Reprints CORE 2618, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. Feng Qiu & Shabbir Ahmed & Santanu S. Dey & Laurence A. Wolsey, 2014. "Covering Linear Programming with Violations," INFORMS Journal on Computing, INFORMS, vol. 26(3), pages 531-546, August.
    7. Lusby, Richard M. & Haahr, Jørgen Thorlund & Larsen, Jesper & Pisinger, David, 2017. "A Branch-and-Price algorithm for railway rolling stock rescheduling," Transportation Research Part B: Methodological, Elsevier, vol. 99(C), pages 228-250.
    8. Y. P. Aneja & K. P. K. Nair, 1979. "Bicriteria Transportation Problem," Management Science, INFORMS, vol. 25(1), pages 73-78, January.
    9. Gustavo Angulo & Shabbir Ahmed & Santanu S. Dey, 2016. "Improving the Integer L-Shaped Method," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 483-499, August.
    10. Roberto Roberti & Enrico Bartolini & Aristide Mingozzi, 2015. "The Fixed Charge Transportation Problem: An Exact Algorithm Based on a New Integer Programming Formulation," Management Science, INFORMS, vol. 61(6), pages 1275-1291, June.
    11. Valentina Cacchiani & Juan-José Salazar-González, 2017. "Optimal Solutions to a Real-World Integrated Airline Scheduling Problem," Transportation Science, INFORMS, vol. 51(1), pages 250-268, February.
    12. Natashia Boland & Matteo Fischetti & Michele Monaci & Martin Savelsbergh, 2016. "Proximity Benders: a decomposition heuristic for stochastic programs," Journal of Heuristics, Springer, vol. 22(2), pages 181-198, April.
    13. Yossiri Adulyasak & Jean-François Cordeau & Raf Jans, 2015. "Benders Decomposition for Production Routing Under Demand Uncertainty," Operations Research, INFORMS, vol. 63(4), pages 851-867, August.
    14. Jeremy A. Bloom, 1983. "Solving an Electricity Generating Capacity Expansion Planning Problem by Generalized Benders' Decomposition," Operations Research, INFORMS, vol. 31(1), pages 84-100, February.
    15. Maher, Stephen J., 2021. "Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework," European Journal of Operational Research, Elsevier, vol. 290(2), pages 479-498.
    16. Christian Artigues & Nicolas Jozefowiez & Boadu M. Sarpong, 2018. "Column generation algorithms for bi-objective combinatorial optimization problems with a min–max objective," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(2), pages 117-142, June.
    17. H. Isermann, 1974. "Technical Note—Proper Efficiency and the Linear Vector Maximum Problem," Operations Research, INFORMS, vol. 22(1), pages 189-191, February.
    18. Moradi, Siamak & Raith, Andrea & Ehrgott, Matthias, 2015. "A bi-objective column generation algorithm for the multi-commodity minimum cost flow problem," European Journal of Operational Research, Elsevier, vol. 244(2), pages 369-378.
    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. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    2. J. Cole Smith, 2019. "In Memoriam: Shabbir Ahmed (1969–2019)," INFORMS Journal on Computing, INFORMS, vol. 31(4), pages 633-635, October.
    3. Stephen J. Maher, 2021. "Enhancing large neighbourhood search heuristics for Benders’ decomposition," Journal of Heuristics, Springer, vol. 27(4), pages 615-648, August.
    4. Özgün Elçi & John Hooker, 2022. "Stochastic Planning and Scheduling with Logic-Based Benders Decomposition," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2428-2442, September.
    5. Xueting Cui & Xiaoling Sun & Shushang Zhu & Rujun Jiang & Duan Li, 2018. "Portfolio Optimization with Nonparametric Value at Risk: A Block Coordinate Descent Method," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 454-471, August.
    6. Chen, Liang & Chen, Sheng-Jie & Chen, Wei-Kun & Dai, Yu-Hong & Quan, Tao & Chen, Juan, 2023. "Efficient presolving methods for solving maximal covering and partial set covering location problems," European Journal of Operational Research, Elsevier, vol. 311(1), pages 73-87.
    7. Ragheb Rahmaniani & Shabbir Ahmed & Teodor Gabriel Crainic & Michel Gendreau & Walter Rei, 2020. "The Benders Dual Decomposition Method," Operations Research, INFORMS, vol. 68(3), pages 878-895, May.
    8. Maher, Stephen J., 2021. "Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework," European Journal of Operational Research, Elsevier, vol. 290(2), pages 479-498.
    9. Camilo Ortiz-Astorquiza & Ivan Contreras & Gilbert Laporte, 2019. "An Exact Algorithm for Multilevel Uncapacitated Facility Location," Transportation Science, INFORMS, vol. 53(4), pages 1085-1106, July.
    10. Álvaro Porras & Concepción Domínguez & Juan Miguel Morales & Salvador Pineda, 2023. "Tight and Compact Sample Average Approximation for Joint Chance-Constrained Problems with Applications to Optimal Power Flow," INFORMS Journal on Computing, INFORMS, vol. 35(6), pages 1454-1469, November.
    11. Pavlo Glushko & Csaba I. Fábián & Achim Koberstein, 2022. "An L-shaped method with strengthened lift-and-project cuts," Computational Management Science, Springer, vol. 19(4), pages 539-565, October.
    12. Anthony Przybylski & Xavier Gandibleux & Matthias Ehrgott, 2010. "A Recursive Algorithm for Finding All Nondominated Extreme Points in the Outcome Set of a Multiobjective Integer Programme," INFORMS Journal on Computing, INFORMS, vol. 22(3), pages 371-386, August.
    13. Teodor Gabriel Crainic & Mike Hewitt & Francesca Maggioni & Walter Rei, 2021. "Partial Benders Decomposition: General Methodology and Application to Stochastic Network Design," Transportation Science, INFORMS, vol. 55(2), pages 414-435, March.
    14. Xiaodi Bai & Jie Sun & Xiaojin Zheng, 2021. "An Augmented Lagrangian Decomposition Method for Chance-Constrained Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1056-1069, July.
    15. Lu, Mengshi & Nakao, Hideaki & Shen, Siqian & Zhao, Lin, 2021. "Non-profit resource allocation and service scheduling with cross-subsidization and uncertain resource consumptions," Omega, Elsevier, vol. 99(C).
    16. Yongjia Song & James R. Luedtke & Simge Küçükyavuz, 2014. "Chance-Constrained Binary Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 735-747, November.
    17. Sophie N. Parragh & Fabien Tricoire & Walter J. Gutjahr, 2022. "A branch-and-Benders-cut algorithm for a bi-objective stochastic facility location problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(2), pages 419-459, June.
    18. Zheng Zhang & Brian T. Denton & Xiaolan Xie, 2020. "Branch and Price for Chance-Constrained Bin Packing," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 547-564, July.
    19. Weijun Xie & Shabbir Ahmed, 2020. "Bicriteria Approximation of Chance-Constrained Covering Problems," Operations Research, INFORMS, vol. 68(2), pages 516-533, March.
    20. Daş, Gülesin Sena & Gzara, Fatma & Stützle, Thomas, 2020. "A review on airport gate assignment problems: Single versus multi objective approaches," Omega, Elsevier, vol. 92(C).

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:eee:ejores:v:322:y:2025:i:2:p:376-400. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.