Complexity of near-optimal robust versions of multilevel optimization problems

Autor: Luce Brotcorne, Mathieu Besançon, Miguel F. Anjos
Přispěvatelé: Integrated Optimization with Complex Structure (INOCS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université libre de Bruxelles (ULB)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Zuse Institute Berlin (ZIB), University of Edinburgh
Rok vydání: 2020
Předmět:
FOS: Computer and information sciences
Mathematical optimization
021103 operations research
Control and Optimization
Computer science
complexity theory Mathematics Subject Classification (2010) 91A65
0211 other engineering and technologies
Computational intelligence
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
0102 computer and information sciences
02 engineering and technology
Computational Complexity (cs.CC)
01 natural sciences
Multilevel optimization
Computer Science - Computational Complexity
multilevel optimization
010201 computation theory & mathematics
Robustness (computer science)
Optimization and Control (math.OC)
Complexity class
FOS: Mathematics
near-optimality robustness
[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Mathematics - Optimization and Control
Zdroj: Besançon, M, Anjos, M F & Brotcorne, L 2021, ' Complexity of near-optimal robust versions of multilevel optimization problems ', Optimization letters . https://doi.org/10.1007/s11590-021-01754-9
Optimization Letters
Optimization Letters, 2021, 15 (8), pp.2597-2610. ⟨10.1007/s11590-021-01754-9⟩
ISSN: 1862-4472
1862-4480
DOI: 10.48550/arxiv.2011.00824
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: