Complexity of near-optimal robust versions of multilevel optimization problems

DOI10.1007/S11590-021-01754-9zbMATH Open1477.90051arXiv2011.00824OpenAlexW3176021395MaRDI QIDQ2230787FDOQ2230787

Authors: Mathieu Besançon, Miguel F. Anjos, L. Brotcorne 

Publication date: 28 September 2021

Published in: Optimization Letters (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2011.00824

Recommendations

• Multilevel (Hierarchical) Optimization: Complexity Issues, Optimality Conditions, Algorithms
• Complexity of min-max-min robustness for combinatorial optimization under discrete uncertainty
• scientific article; zbMATH DE number 895368
• Decision uncertainty in multiobjective optimization
• Complexity and in-approximability of a selection problem in robust optimization

zbMATH Keywords

complexity theorymultilevel optimizationnear-optimal robustness

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Mixed integer programming (90C11) Robustness in mathematical programming (90C17)

Cites Work

• The polynomial hierarchy and a simple model for competitive analysis
• Pessimistic bilevel optimization
• Links between linear bilevel and mixed 0-1 programming problems
• Solving bilevel programs with the KKT-approach
• Bilevel programming problems. Theory, algorithms and applications to energy networks
• The polynomial-time hierarchy
• The Mixed Integer Linear Bilevel Programming Problem
• NP-completeness of the linear complementarity problem
• A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation
• A new general-purpose algorithm for mixed-integer bilevel linear programs
• Bilevel optimization: theory, algorithms, applications and a bibliography
• A study on the computational complexity of the bilevel knapsack problem
• On a class of bilevel linear mixed-integer programs in adversarial settings
• An enhanced branch-and-bound algorithm for bilevel integer linear programming
• On bilevel optimization with inexact follower
• Solution of bilevel optimization problems using the KKT approach
• A unified framework for multistage mixed integer linear optimization
• A survey on mixed-integer programming techniques in bilevel optimization
• A special three-level optimization problem

Cited In (11)

• On complexity of finding strong-weak solutions in bilevel linear programming
• MrDIRECT: a multilevel robust DIRECT algorithm for global optimization problems
• Multilevel (Hierarchical) Optimization: Complexity Issues, Optimality Conditions, Algorithms
• A survey on bilevel optimization under uncertainty
• Exact methods for discrete \({\varGamma}\)-robust interdiction problems with an application to the bilevel knapsack problem
• The robust bilevel continuous knapsack problem with uncertain coefficients in the follower's objective
• Shortest path network interdiction with asymmetric uncertainty
• Robust bilevel optimization for near-optimal lower-level solutions
• A survey on mixed-integer programming techniques in bilevel optimization
• Using neural networks to solve linear bilevel problems with unknown lower level
• Complexity and in-approximability of a selection problem in robust optimization

This page was built for publication: Complexity of near-optimal robust versions of multilevel optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2230787)