Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method

  • Bilevel problems are highly challenging optimization problems that appear in many applications of energy market design, critical infrastructure defense, transportation, pricing, etc. Often, these bilevel models are equipped with integer decisions, which makes the problems even harder to solve. Typically, in such a setting in mathematical optimization one develops primal heuristics in order to obtain feasible points of good quality quickly or to enhance the search process of exact global methods. However, there are comparably few heuristics for bilevel problems. In this paper, we develop such a primal heuristic for bilevel problems with mixed-integer linear or quadratic upper level and linear or quadratic lower level. The heuristic is based on a penalty alternating direction method, which allows for a theoretical analysis. We derive a convergence theory stating that the method converges to a stationary point of an equivalent single-level reformulation of the bilevel problem and extensively test the method on a test set of more than 2800 instances - which is one of the largest computational test sets ever used in bilevel programming. The study illustrates the very good performance of the proposed method, both in terms of running times and solution quality. This renders the method a suitable sub-routine in global bilevel solvers as well as a reasonable standalone approach.

Download full text files

Export metadata

Metadaten
Author:Thomas Kleinert, Martin Schmidt
DOI:https://doi.org/10.1287/ijoc.2019.0945
Parent Title (English):INFORMS Journal on Computing
Document Type:Article
Language:English
Date of Publication (online):2019/03/11
Date of first Publication:2019/03/14
Release Date:2019/03/14
Tag:Alternating direction methods; Bilevel optimization; Mixed-integer bilevel optimization; Penalty methods; Stationary points
Issue:33 (1)
First Page:198
Last Page:215
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.