IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v147y2006i1p317-34110.1007-s10479-006-0073-0.html
   My bibliography  Save this article

A decision-theoretic approach to robust optimization in multivalued graphs

Author

Listed:
  • Patrice Perny
  • Olivier Spanjaard
  • Louis-Xavier Storme

Abstract

This paper is devoted to the search of robust solutions in finite graphs when costs depend on scenarios. We first point out similarities between robust optimization and multiobjective optimization. Then, we present axiomatic requirements for preference compatibility with the intuitive idea of robustness in a multiple scenarios decision context. This leads us to propose the Lorenz dominance rule as a basis for robustness analysis. Then, after presenting complexity results about the determination of Lorenz optima, we show how the search can be embedded in algorithms designed to enumerate k best solutions. Then, we apply it in order to enumerate Lorenz optimal spanning trees and paths. We investigate possible refinements of Lorenz dominance and we propose an axiomatic justification of OWA operators in this context. Finally, the results of numerical experiments on randomly generated graphs are provided. They show the numerical efficiency of the suggested approach. Copyright Springer Science + Business Media, LCC 2006

Suggested Citation

  • Patrice Perny & Olivier Spanjaard & Louis-Xavier Storme, 2006. "A decision-theoretic approach to robust optimization in multivalued graphs," Annals of Operations Research, Springer, vol. 147(1), pages 317-341, October.
    • Handle: RePEc:spr:annopr:v:147:y:2006:i:1:p:317-341:10.1007/s10479-006-0073-0
    DOI: 10.1007/s10479-006-0073-0
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-006-0073-0
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-006-0073-0?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. Yaari, Menahem E, 1987. "The Dual Theory of Choice under Risk," Econometrica, Econometric Society, vol. 55(1), pages 95-115, January.
    2. Kostreva, Michael M. & Ogryczak, Wlodzimierz & Wierzbicki, Adam, 2004. "Equitable aggregations and multiple criteria analysis," European Journal of Operational Research, Elsevier, vol. 158(2), pages 362-377, October.
    3. Richard Bellman, 1954. "Some Applications of the Theory of Dynamic Programming---A Review," Operations Research, INFORMS, vol. 2(3), pages 275-288, August.
    4. Hites, R. & De Smet, Y. & Risse, N. & Salazar-Neumann, M. & Vincke, P., 2006. "About the applicability of MCDA to some robustness problems," European Journal of Operational Research, Elsevier, vol. 174(1), pages 322-332, October.
    5. Ehrgott, Matthias & Skriver, Anders J. V., 2003. "Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach," European Journal of Operational Research, Elsevier, vol. 147(3), pages 657-664, June.
    6. Brucker, Peter J. & Hamacher, Horst W., 1989. "k-optimal solution sets for some polynomially solvable scheduling problems," European Journal of Operational Research, Elsevier, vol. 41(2), pages 194-202, July.
    7. Richard Bellman, 1954. "On some applications of the theory of dynamic programming to logistics," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 1(2), pages 141-153, June.
    8. Sen, Amartya, 1997. "On Economic Inequality," OUP Catalogue, Oxford University Press, number 9780198292975.
    9. Ogryczak, Wlodzimierz, 2000. "Inequality measures and equitable approaches to location problems," European Journal of Operational Research, Elsevier, vol. 122(2), pages 374-391, April.
    10. Dubois, D. & Fortemps, Ph., 2005. "Selecting preferred solutions in the minimax approach to dynamic programming problems under flexible constraints," European Journal of Operational Research, Elsevier, vol. 160(3), pages 582-598, February.
    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. Dugardin, Frédéric & Yalaoui, Farouk & Amodeo, Lionel, 2010. "New multi-objective method to solve reentrant hybrid flow shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 203(1), pages 22-31, May.
    2. Jonas Ide & Anita Schöbel, 2016. "Robustness for uncertain multi-objective optimization: a survey and analysis of different concepts," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(1), pages 235-271, January.
    3. Andrew J. Keith & Darryl K. Ahner, 2021. "A survey of decision making and optimization under uncertainty," Annals of Operations Research, Springer, vol. 300(2), pages 319-353, May.
    4. Maedeh Fasihi & Reza Tavakkoli-Moghaddam & Fariborz Jolai, 2023. "A bi-objective re-entrant permutation flow shop scheduling problem: minimizing the makespan and maximum tardiness," Operational Research, Springer, vol. 23(2), pages 1-41, June.
    5. Galand, Lucie & Perny, Patrice & Spanjaard, Olivier, 2010. "Choquet-based optimisation in multiobjective shortest path and spanning tree problems," European Journal of Operational Research, Elsevier, vol. 204(2), pages 303-315, July.
    6. Virginie Gabrel & Cécile Murat & Aurélie Thiele, 2018. "Portfolio optimization with pw-robustness," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(3), pages 267-290, September.
    7. Tim Holzmann & J. Cole Smith, 2019. "Shortest path interdiction problem with arc improvement recourse: A multiobjective approach," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(3), pages 230-252, April.
    8. Klamroth, Kathrin & Köbis, Elisabeth & Schöbel, Anita & Tammer, Christiane, 2017. "A unified approach to uncertain optimization," European Journal of Operational Research, Elsevier, vol. 260(2), pages 403-420.
    9. Bouyssou, Denis & Marchant, Thierry, 2014. "An axiomatic approach to bibliometric rankings and indices," Journal of Informetrics, Elsevier, vol. 8(3), pages 449-477.
    10. Mut, Murat & Wiecek, Margaret M., 2011. "Generalized equitable preference in multiobjective programming," European Journal of Operational Research, Elsevier, vol. 212(3), pages 535-551, 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. Galand, Lucie & Perny, Patrice & Spanjaard, Olivier, 2010. "Choquet-based optimisation in multiobjective shortest path and spanning tree problems," European Journal of Operational Research, Elsevier, vol. 204(2), pages 303-315, July.
    2. Karsu, Özlem & Morton, Alec & Argyris, Nikos, 2018. "Capturing preferences for inequality aversion in decision support," European Journal of Operational Research, Elsevier, vol. 264(2), pages 686-706.
    3. Xiaoyue Li & John M. Mulvey, 2023. "Optimal Portfolio Execution in a Regime-switching Market with Non-linear Impact Costs: Combining Dynamic Program and Neural Network," Papers 2306.08809, arXiv.org.
    4. Mahmoud Mahfouz & Angelos Filos & Cyrine Chtourou & Joshua Lockhart & Samuel Assefa & Manuela Veloso & Danilo Mandic & Tucker Balch, 2019. "On the Importance of Opponent Modeling in Auction Markets," Papers 1911.12816, arXiv.org.
    5. Argyris, Nikolaos & Karsu, Özlem & Yavuz, Mirel, 2022. "Fair resource allocation: Using welfare-based dominance constraints," European Journal of Operational Research, Elsevier, vol. 297(2), pages 560-578.
    6. Boute, Robert N. & Gijsbrechts, Joren & van Jaarsveld, Willem & Vanvuchelen, Nathalie, 2022. "Deep reinforcement learning for inventory control: A roadmap," European Journal of Operational Research, Elsevier, vol. 298(2), pages 401-412.
    7. Dawei Chen & Fangxu Mo & Ye Chen & Jun Zhang & Xinyu You, 2022. "Optimization of Ramp Locations along Freeways: A Dynamic Programming Approach," Sustainability, MDPI, vol. 14(15), pages 1-13, August.
    8. Harrold, Daniel J.B. & Cao, Jun & Fan, Zhong, 2022. "Data-driven battery operation for energy arbitrage using rainbow deep reinforcement learning," Energy, Elsevier, vol. 238(PC).
    9. Francesco Andreoli & Claudio Zoli, 2020. "From unidimensional to multidimensional inequality: a review," METRON, Springer;Sapienza Università di Roma, vol. 78(1), pages 5-42, April.
    10. Bartłomiej Kocot & Paweł Czarnul & Jerzy Proficz, 2023. "Energy-Aware Scheduling for High-Performance Computing Systems: A Survey," Energies, MDPI, vol. 16(2), pages 1-28, January.
    11. Wadi Khalid Anuar & Lai Soon Lee & Hsin-Vonn Seow & Stefan Pickl, 2021. "A Multi-Depot Vehicle Routing Problem with Stochastic Road Capacity and Reduced Two-Stage Stochastic Integer Linear Programming Models for Rollout Algorithm," Mathematics, MDPI, vol. 9(13), pages 1-44, July.
    12. Peter Schober & Julian Valentin & Dirk Pflüger, 2022. "Solving High-Dimensional Dynamic Portfolio Choice Models with Hierarchical B-Splines on Sparse Grids," Computational Economics, Springer;Society for Computational Economics, vol. 59(1), pages 185-224, January.
    13. Matthias Breuer & David Windisch, 2019. "Investment Dynamics and Earnings‐Return Properties: A Structural Approach," Journal of Accounting Research, Wiley Blackwell, vol. 57(3), pages 639-674, June.
    14. Claudio Zoli, 2002. "Inverse stochastic dominance, inequality measurement and Gini indices," Journal of Economics, Springer, vol. 77(1), pages 119-161, December.
    15. Diefenbach, Heiko & Emde, Simon & Glock, Christoph H., 2020. "Loading tow trains ergonomically for just-in-time part supply," European Journal of Operational Research, Elsevier, vol. 284(1), pages 325-344.
    16. Michael J. Pennock & William B. Rouse & Diane L. Kollar, 2007. "Transforming the Acquisition Enterprise: A Framework for Analysis and a Case Study of Ship Acquisition," Systems Engineering, John Wiley & Sons, vol. 10(2), pages 99-117, June.
    17. Quetschlich, Mathias & Moetz, André & Otto, Boris, 2021. "Optimisation model for multi-item multi-echelon supply chains with nested multi-level products," European Journal of Operational Research, Elsevier, vol. 290(1), pages 144-158.
    18. Gutjahr, Walter J., 2021. "Inequity-averse stochastic decision processes," European Journal of Operational Research, Elsevier, vol. 288(1), pages 258-270.
    19. Iman Ahmadianfar & Saeed Noshadian & Nadir Ahmed Elagib & Meysam Salarijazi, 2021. "Robust Diversity-based Sine-Cosine Algorithm for Optimizing Hydropower Multi-reservoir Systems," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 35(11), pages 3513-3538, September.
    20. Medernach, Emmanuel & Sanlaville, Eric, 2012. "Fair resource allocation for different scenarios of demands," European Journal of Operational Research, Elsevier, vol. 218(2), pages 339-350.

    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:annopr:v:147:y:2006:i:1:p:317-341:10.1007/s10479-006-0073-0. 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.