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

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 Σ2p-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.