An Exact Projection-Based Algorithm for Bilevel Mixed-Integer Problems with Nonlinearities

Maximilian Merkert(maximilian.merkertovgu.de)
Galina Orlinskaya(galina.orlinskayafau.de)
Dieter Weninger(dieter.weningerfau.de)

Abstract: We aim at solving bilevel mixed-integer optimization problems with lower-level integer variables and including nonlinear terms such as, e.g., products of upper-level and lower-level variables. Problems of this type are extremely challenging as a single-level reformulation suitable for off-the-shelf solvers is not available in general. In order to solve these problems, we enhance an approximative projection-based algorithm for mixed-integer linear bilevel programming problems from the literature to become exact under one additional relatively mild assumption. This assumption still allows for discrete and continuous variables on both levels, but forbids continuous upper-level variables to appear in lower-level constraints and thus ensures that a bilevel optimum is attained. In addition, we extend the algorithm to make it applicable to a wider problem class and demonstrate which types of nonlinearities can be handled by our algorithm on each level. We also discuss computational experiments on modified library instances.

Keywords: Bilevel Optimization, Mixed-Integer Nonlinear Programming, Strong Duality, Projection, Global Optimization

Category 1: Global Optimization

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Other Topics (Game Theory )

Citation:

Download: [PDF]

Entry Submitted: 12/11/2020
Entry Accepted: 12/11/2020
Entry Last Modified: 12/11/2020

Modify/Update this entry