Thomas Kleinert

Thomas Kleinert

Auto-generated profile, based on publicly available information

Thomas Kleinert

Quantagonia GmbH, Bad Homburg, Germany

Research Focus & Metrics

Academic Career Length

8Years (2019-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
28 October 2024 in Nature Reviews Physics
Verified
Journal Article
Closed access
PDF file
AAAmira Abbas
Amira Abbas
AAAndris Ambainis
Andris Ambainis
BABrandon Augustino
Brandon Augustino
ABAndreas Bärtschi
Andreas Bärtschi
HBHarry Buhrman
Harry Buhrman
CZChrista Zoufal
Christa Zoufal

1 November 2020 in Operations Research
Verified
Journal Article
Closed access
TKThomas Kleinert
Thomas Kleinert
MLMartine Labbé
Martine Labbé
FPFr¨ank Plein
Fr¨ank Plein
MSMartin Schmidt
Martin Schmidt
There's No Free Lunch in Bilevel Optimization

1 January 2021 in INFORMS Journal on Computing
Verified
Journal Article
Closed access
TKThomas Kleinert
Thomas Kleinert
MSMartin Schmidt
Martin Schmidt
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.

7 February 2023 in Computational Management Science
Verified
Journal Article
Open access
PDF file
TKThomas Kleinert
Thomas Kleinert
MSMartin Schmidt
Martin Schmidt
Linear bilevel optimization problems have gained increasing attention both in theory as well as in practical applications of Operations Research (OR) during the last years and decades. The latter is mainly due to the ability of this class of problems to model hierarchical decision processes. However, this ability makes bilevel problems also very hard to solve. Since no general-purpose solvers are available, a “best-practice” has developed in the applied OR community, in which not all people want to develop tailored algorithms but “just use” bilevel optimization as a modeling tool for practice. This best-practice is the big-M reformulation of the Karush–Kuhn–Tucker (KKT) conditions of the lower-level problem—an approach that has been shown to be highly problematic by Pineda and Morales (2019). Choosing invalid values for M yields solutions that may be arbitrarily bad. Checking the validity of the big-Ms is however shown to be as hard as solving the original bilevel problem in Kleinert et al. (2019). Nevertheless, due to its appealing simplicity, especially w.r.t. the required implementation effort, this ready-to-use approach still is the most popular method. Until now, there has been a lack of approaches that are competitive both in terms of implementation effort and computational cost. In this note we demonstrate that there is indeed another competitive ready-to-use approach: If the SOS-1 technique is applied to the KKT complementarity conditions, adding the simple additional root-node inequality developed by Kleinert et al. (2020) leads to a competitive performance—without having all the possible theoretical disadvantages of the big-M approach.

11 November 2020 in Optimization Letters
Verified
Journal Article
Open access
PDF file
TKThomas Kleinert
Thomas Kleinert
MLMartine Labbé
Martine Labbé
FPFränk Plein
Fränk Plein
MSMartin Schmidt
Martin Schmidt
Linear bilevel optimization problems are often tackled by replacing the linear lower-level problem with its Karush–Kuhn–Tucker conditions. The resulting single-level problem can be solved in a branch-and-bound fashion by branching on the complementarity constraints of the lower-level problem’s optimality conditions. While in mixed-integer single-level optimization branch-and-cut has proven to be a powerful extension of branch-and-bound, in linear bilevel optimization not too many bilevel-tailored valid inequalities exist. In this paper, we briefly review existing cuts for linear bilevel problems and introduce a new valid inequality that exploits the strong duality condition of the lower level. We further discuss strengthened variants of the inequality that can be derived from McCormick envelopes. In a computational study, we show that the new valid inequalities can help to close the optimality gap very effectively on a large test set of linear bilevel instances.

8 February 2021 in Mathematical Programming
Verified
Journal Article
Open access
PDF file
TKThomas Kleinert
Thomas Kleinert
VGVeronika Grimm
Veronika Grimm
MSMartin Schmidt
Martin Schmidt
Bilevel optimization problems have received a lot of attention in the last years and decades. Besides numerous theoretical developments there also evolved novel solution algorithms for mixed-integer linear bilevel problems and the most recent algorithms use branch-and-cut techniques from mixed-integer programming that are especially tailored for the bilevel context. In this paper, we consider MIQP-QP bilevel problems, i.e., models with a mixed-integer convex-quadratic upper level and a continuous convex-quadratic lower level. This setting allows for a strong-duality-based transformation of the lower level which yields, in general, an equivalent nonconvex single-level reformulation of the original bilevel problem. Under reasonable assumptions, we can derive both a multi- and a single-tree outer-approximation-based cutting-plane algorithm. We show finite termination and correctness of both methods and present extensive numerical results that illustrate the applicability of the approaches. It turns out that the proposed methods are capable of solving bilevel instances with several thousand variables and constraints and significantly outperform classical solution approaches.