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

Kleinert T, Schmidt M (2020)


Publication Language: English

Publication Status: Accepted

Publication Type: Journal article, Original article

Future Publication Type: Journal article

Publication year: 2020

Journal

URI: https://pubsonline.informs.org/doi/10.1287/ijoc.2019.0945

DOI: 10.1287/ijoc.2019.0945

Abstract

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.

Authors with CRIS profile

Related research project(s)

How to cite

APA:

Kleinert, T., & Schmidt, M. (2020). Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method. Informs Journal on Computing. https://dx.doi.org/10.1287/ijoc.2019.0945

MLA:

Kleinert, Thomas, and Martin Schmidt. "Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method." Informs Journal on Computing (2020).

BibTeX: Download