Outer Approximation for Global Optimization of Mixed-Integer Quadratic Bilevel Problems

  • Bilevel optimization problems have received a lot of attention in the last years and decades. Besides numerous theoretical developments there also evolved novel solution algorithms for mixed-integer linear bilevel problems and the most recent algorithms use branch-and-cut techniques from mixed-integer programming that are especially tailored for the bilevel context. In this paper, we consider MIQP-QP bilevel problems, i.e., models with a mixed-integer convex-quadratic upper level and a continuous convex-quadratic lower level. This setting allows for a strong-duality-based transformation of the lower level which yields, in general, an equivalent nonconvex single-level reformulation of the original bilevel problem. Under reasonable assumptions, we can derive both a multi- and a single-tree outer-approximation-based cutting-plane algorithm. We show finite termination and correctness of both methods and present extensive numerical results that illustrate the applicability of the approaches. It turns out that the proposed methods are capable of solving bilevel instances with several thousand variables and constraints and significantly outperform classical solution approaches.

Download full text files

Export metadata

Metadaten
Author:Thomas Kleinert, Veronika Grimm, Martin Schmidt
Parent Title (German):Mathematical Programming (Series B)
Document Type:Article
Language:English
Date of Publication (online):2019/12/23
Date of first Publication:2019/12/23
Release Date:2019/12/23
Tag:Bilevel optimization; Convex mixed-integer nonlinear optimization; Outer approximation; Quadratic programming
Page Number:28
Institutes:Friedrich-Alexander-Universität Erlangen-Nürnberg
Universität Trier
Subprojects:A05
B08
Licence (German):License LogoCreative Commons - CC BY - Namensnennung 4.0 International
Einverstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.