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

Weninger D, Orlinskaya G, Merkert M (2022)

Publication Language: English

Publication Status: Submitted

Publication Type: Journal article, Review article

Future Publication Type: Journal article

Publication year: 2022

Journal

Journal of Global Optimization Springer Verlag (Germany)

URI: http://www.optimization-online.org/DB_FILE/2020/12/8153.pdf

DOI: 10.1007/s10898-022-01172-w

Open Access Link: https://link.springer.com/content/pdf/10.1007/s10898-022-01172-w.pdf

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.

Authors with CRIS profile

Dieter Weninger Economics - Discrete Optimization - Mathematics (EDOM) Galina Orlinskaya Economics - Discrete Optimization - Mathematics (EDOM)

Involved external institutions

Otto-von-Guericke-Universität Magdeburg DE Germany (DE)

How to cite

APA:

Weninger, D., Orlinskaya, G., & Merkert, M. (2022). An Exact Projection-Based Algorithm for Bilevel Mixed-Integer Problems with Nonlinearities. Journal of Global Optimization. https://doi.org/10.1007/s10898-022-01172-w

MLA:

Weninger, Dieter, Galina Orlinskaya, and Maximilian Merkert. "An Exact Projection-Based Algorithm for Bilevel Mixed-Integer Problems with Nonlinearities." Journal of Global Optimization (2022).

BibTeX: Download