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

Thomas Kleinert () and Martin Schmidt ()
Additional contact information
Thomas Kleinert: Department of Economics, Discrete Optimization, and Mathematics, Friedrich-Alexander-Universität Erlangen-Nürnberg, 91058 Erlangen, Germany; Energie Campus Nürnberg, Friedrich-Alexander-Universität, 90429 Nürnberg, Germany
Martin Schmidt: Energie Campus Nürnberg, Friedrich-Alexander-Universität, 90429 Nürnberg, Germany; Department of Mathematics, Trier University, 54296 Trier, Germany

INFORMS Journal on Computing, 2021, vol. 33, issue 1, 198-215

Abstract: Bilevel problems are highly challenging optimization problems that appear in many applications of energy market design, critical infrastructure defense, transportation, pricing, and so on. 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 a mixed-integer linear or quadratic upper level and a 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 2,800 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 in terms of both running times and solution quality. This renders the method a suitable subroutine in global bilevel solvers as well as a reasonable standalone approach. Summary of Contribution: Bilevel optimization problems form a very important class of optimization problems in the field of operations research, which is mainly due to their capability of modeling hierarchical decision processes. However, real-world bilevel problems are usually very hard to solve—especially in the case in which additional mixed-integer aspects are included in the modeling. Hence, the development of fast and reliable primal heuristics for this class of problems is very important. This paper presents such a method.

Keywords: bilevel optimization; mixed-integer bilevel optimization; stationary points; penalty methods; alternating direction methods (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2019.0945 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:1:p:198-215

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().