<  Back to the Polytechnique Montréal portal

Complexity of near-optimal robust versions of multilevel optimization problems

Mathieu Besançon, Miguel F. Anjos and Luce Brotcorne

Article (2021)

Published Version
Terms of Use: Creative Commons Attribution .
Download (459kB)
Cite this document: Besançon, M., Anjos, M. F. & Brotcorne, L. (2021). Complexity of near-optimal robust versions of multilevel optimization problems. Optimization Letters, 15(8), p. 2597-2610. doi:10.1007/s11590-021-01754-9
Show abstract Hide abstract


Near-optimality robustness extends multilevel optimization with a limited deviation of a lower level from its optimal solution, anticipated by higher levels. We analyze the complexity of near-optimal robust multilevel problems, where near-optimal robustness is modelled through additional adversarial decision-makers. Near-optimal robust versions of multilevel problems are shown to remain in the same complexity class as the problem without near-optimality robustness under general conditions.

Uncontrolled Keywords

Near-optimal robustness, Multilevel optimization, Complexity theory

Open Access document in PolyPublie
Department: Département de génie informatique et génie logiciel
Funders: Mermoz scholarship, Centre National de la Recherche Scientifique (CNRS) - Groupement de recherche - Recherche opérationnelle
Date Deposited: 19 Jan 2022 17:09
Last Modified: 20 Jan 2022 01:20
PolyPublie URL: https://publications.polymtl.ca/9261/
Document issued by the official publisher
Journal Title: Optimization Letters (vol. 15, no. 8)
Publisher: Springer Nature
Official URL: https://doi.org/10.1007/s11590-021-01754-9


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only