Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Complexity of near-optimal robust versions of multilevel optimization problems

Mathieu Besançon 1 Miguel Anjos 2 Luce Brotcorne 3
3 INOCS - Integrated Optimization with Complex Structure
ULB - Université libre de Bruxelles, Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
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 decisionmakers. 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Mathieu Besançon <>
Submitted on : Monday, February 22, 2021 - 5:16:36 PM
Last modification on : Wednesday, February 24, 2021 - 3:27:03 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License


  • HAL Id : hal-03149050, version 1
  • ARXIV : 2011.00824



Mathieu Besançon, Miguel Anjos, Luce Brotcorne. Complexity of near-optimal robust versions of multilevel optimization problems. 2021. ⟨hal-03149050⟩



Record views


Files downloads