Mixed-Integer Bilevel Optimization with Nonconvex Quadratic Lower-Level Problems: Complexity and a Solution Method

Immanuel Bomze (), Andreas Horländer () and Martin Schmidt ()
Additional contact information
Immanuel Bomze: University of Vienna
Andreas Horländer: Trier University
Martin Schmidt: Trier University

Journal of Global Optimization, 2025, vol. 93, issue 1, No 1, 25 pages

Abstract: Abstract We study bilevel problems with a convex quadratic mixed-integer upper-level, integer linking variables, and a nonconvex quadratic, purely continuous lower-level problem. We prove $$\Sigma _2^p$$ Σ 2 p -hardness of this class of problems, derive an iterative lower- and upper-bounding scheme, and show its finiteness and correctness in the sense that it computes globally optimal points or proves infeasibility of the instance. To this end, we make use of the Karush–Kuhn–Tucker conditions of the lower-level problem for the lower-bounding step, since these conditions are only necessary but not sufficient in our setting. Moreover, integer no-good cuts as well as a simple optimality cut are used to obtain finiteness of the method. Finally, we illustrate the applicability of our approach by the first large-scale numerical experiment for this class of problems in the literature.

Keywords: Bilevel optimization; Nonconvex lower levels; Mixed-integer optimization; Complexity; 91A65; 90C11; 90C26; 68Q15 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-025-01522-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:93:y:2025:i:1:d:10.1007_s10898-025-01522-4

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-025-01522-4

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().