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

Robust min-max (regret) optimization using ordered weighted averaging

Author

Listed:
  • Baak, Werner
  • Goerigk, Marc
  • Kasperski, Adam
  • Zieliński, Paweł

Abstract

In decision-making under uncertainty, several criteria have been studied to aggregate the performance of a solution over multiple possible scenarios. This paper introduces a novel variant of ordered weighted averaging (OWA) for optimization problems. It generalizes the classic OWA approach, which includes the robust min–max optimization as a special case, as well as the min–max regret optimization. We derive new complexity results for this setting, including insights into the inapproximability and approximability of this problem. In particular, we provide stronger positive approximation results that asymptotically improve the previously best-known bounds for the classic OWA approach.

Suggested Citation

  • Baak, Werner & Goerigk, Marc & Kasperski, Adam & Zieliński, Paweł, 2025. "Robust min-max (regret) optimization using ordered weighted averaging," European Journal of Operational Research, Elsevier, vol. 322(1), pages 171-181.
    • Handle: RePEc:eee:ejores:v:322:y:2025:i:1:p:171-181
    DOI: 10.1016/j.ejor.2024.10.028
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724008257
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.10.028?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. Vittorio Bilò & Ioannis Caragiannis & Angelo Fanelli & Michele Flammini & Gianpiero Monaco, 2017. "Simple Greedy Algorithms for Fundamental Multidimensional Graph Problems," Post-Print hal-02089412, HAL.
    2. Reimann, Olivier & Schumacher, Christian & Vetschera, Rudolf, 2017. "How well does the OWA operator represent real preferences?," European Journal of Operational Research, Elsevier, vol. 258(3), pages 993-1003.
    3. Ogryczak, Wlodzimierz & Sliwinski, Tomasz, 2003. "On solving linear programs with the ordered weighted averaging objective," European Journal of Operational Research, Elsevier, vol. 148(1), pages 80-91, July.
    4. Chassein, André & Dokka, Trivikram & Goerigk, Marc, 2019. "Algorithms and uncertainty sets for data-driven robust shortest path problems," European Journal of Operational Research, Elsevier, vol. 274(2), pages 671-686.
    5. Gorissen, Bram L. & Yanıkoğlu, İhsan & den Hertog, Dick, 2015. "A practical guide to robust optimization," Omega, Elsevier, vol. 53(C), pages 124-137.
    6. Chassein, André & Goerigk, Marc & Kasperski, Adam & Zieliński, Paweł, 2020. "Approximating combinatorial optimization problems with the ordered weighted averaging criterion," European Journal of Operational Research, Elsevier, vol. 286(3), pages 828-838.
    7. Büsing, Christina & Goetzmann, Kai-Simon & Matuschke, Jannik & Stiller, Sebastian, 2017. "Reference points and approximation algorithms in multicriteria discrete optimization," European Journal of Operational Research, Elsevier, vol. 260(3), pages 829-840.
    8. Baak, Werner & Goerigk, Marc & Hartisch, Michael, 2024. "A preference elicitation approach for the ordered weighted averaging criterion using solution choice observations," European Journal of Operational Research, Elsevier, vol. 314(3), pages 1098-1110.
    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. Baak, Werner & Goerigk, Marc & Hartisch, Michael, 2024. "A preference elicitation approach for the ordered weighted averaging criterion using solution choice observations," European Journal of Operational Research, Elsevier, vol. 314(3), pages 1098-1110.
    2. Chassein, André & Goerigk, Marc & Kasperski, Adam & Zieliński, Paweł, 2020. "Approximating combinatorial optimization problems with the ordered weighted averaging criterion," European Journal of Operational Research, Elsevier, vol. 286(3), pages 828-838.
    3. Sarhadi, Hassan & Naoum-Sawaya, Joe & Verma, Manish, 2020. "A robust optimization approach to locating and stockpiling marine oil-spill response facilities," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 141(C).
    4. Peng Li & Ju Liu & Cuiping Wei, 2019. "A Dynamic Decision Making Method Based on GM(1,1) Model with Pythagorean Fuzzy Numbers for Selecting Waste Disposal Enterprises," Sustainability, MDPI, vol. 11(20), pages 1-19, October.
    5. Antonio G. Martín & Manuel Díaz-Madroñero & Josefa Mula, 2020. "Master production schedule using robust optimization approaches in an automobile second-tier supplier," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 28(1), pages 143-166, March.
    6. Khoirunnisa Rohadatul Aisy Muslihin & Endang Rusyaman & Diah Chaerani, 2022. "Conic Duality for Multi-Objective Robust Optimization Problem," Mathematics, MDPI, vol. 10(21), pages 1-22, October.
    7. Shunichi Ohmori, 2021. "A Predictive Prescription Using Minimum Volume k -Nearest Neighbor Enclosing Ellipsoid and Robust Optimization," Mathematics, MDPI, vol. 9(2), pages 1-16, January.
    8. Lee, Jisun & Joung, Seulgi & Lee, Kyungsik, 2022. "A fully polynomial time approximation scheme for the probability maximizing shortest path problem," European Journal of Operational Research, Elsevier, vol. 300(1), pages 35-45.
    9. Knoke, Thomas & Kindu, Mengistie & Jarisch, Isabelle & Gosling, Elizabeth & Friedrich, Stefan & Bödeker, Kai & Paul, Carola, 2020. "How considering multiple criteria, uncertainty scenarios and biological interactions may influence the optimal silvicultural strategy for a mixed forest," Forest Policy and Economics, Elsevier, vol. 118(C).
    10. Viktoryia Buhayenko & Dick den Hertog, 2017. "Adjustable Robust Optimisation approach to optimise discounts for multi-period supply chain coordination under demand uncertainty," International Journal of Production Research, Taylor & Francis Journals, vol. 55(22), pages 6801-6823, November.
    11. Wu, Zhibin & Huang, Shuai & Xu, Jiuping, 2019. "Multi-stage optimization models for individual consistency and group consensus with preference relations," European Journal of Operational Research, Elsevier, vol. 275(1), pages 182-194.
    12. Jinzuo Guo & Tianyu Liu & Guopeng Song & Bo Guo, 2024. "Solving the Robust Shortest Path Problem with Multimodal Transportation," Mathematics, MDPI, vol. 12(19), pages 1-14, September.
    13. Xidonas, Panos & Hassapis, Christis & Soulis, John & Samitas, Aristeidis, 2017. "Robust minimum variance portfolio optimization modelling under scenario uncertainty," Economic Modelling, Elsevier, vol. 64(C), pages 60-71.
    14. Johannes Thürauf, 2022. "Deciding the feasibility of a booking in the European gas market is coNP-hard," Annals of Operations Research, Springer, vol. 318(1), pages 591-618, November.
    15. Chassein, André & Goerigk, Marc, 2018. "Variable-sized uncertainty and inverse problems in robust optimization," European Journal of Operational Research, Elsevier, vol. 264(1), pages 17-28.
    16. Darshan Chauhan & Avinash Unnikrishnan & Stephen D. Boyles & Priyadarshan N. Patil, 2024. "Robust maximum flow network interdiction considering uncertainties in arc capacity and resource consumption," Annals of Operations Research, Springer, vol. 335(2), pages 689-725, April.
    17. Bomze, Immanuel M. & Gabl, Markus, 2023. "Optimization under uncertainty and risk: Quadratic and copositive approaches," European Journal of Operational Research, Elsevier, vol. 310(2), pages 449-476.
    18. Ricardo M. Lima & Antonio J. Conejo & Loïc Giraldi & Olivier Le Maître & Ibrahim Hoteit & Omar M. Knio, 2022. "Risk-Averse Stochastic Programming vs. Adaptive Robust Optimization: A Virtual Power Plant Application," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1795-1818, May.
    19. Wang, Yu & Zhang, Yu & Tang, Jiafu, 2019. "A distributionally robust optimization approach for surgery block allocation," European Journal of Operational Research, Elsevier, vol. 273(2), pages 740-753.
    20. Shin, Youngchul & Moon, Ilkyeong, 2023. "Robust building evacuation planning in a dynamic network flow model under collapsible nodes and arcs," Socio-Economic Planning Sciences, Elsevier, vol. 86(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:1:p:171-181. 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.