Abstract
We consider a novel class of linear bilevel optimization models with a lower level that is a linear program with complementarity constraints (LPCC). We present different single-level reformulations depending on whether the linear complementarity problem (LCP) as part of the lower-level constraint set depends on the upper-level decisions or not as well as on whether the LCP matrix is positive definite or positive semidefinite. Moreover, we illustrate the connection to linear trilevel models that can be reduced to bilevel problems with LPCC lower levels having positive (semi)definite matrices. Finally, we provide two generic and illustrative bilevel models from the fields of transportation and energy to show the practical relevance of the newly introduced class of bilevel problems and show related theoretical results.
Acknowledgements
The second author thanks the DFG for their support within RTG 2126 “Algorithmic Optimization”. The third author thanks the DFG for their support within project A05 and B08 in CRC TRR 154. The second author has also been partially supported by Spanish Ministry of Science and Innovation grant number PID2020-114594GB-C21, project Junta de Andalucía P18-FR-1422, Project I+D+i FEDER Andalucía US-1256951.
Correction Statement
This article has been republished with minor changes. These changes do not impact the academic content of the article.
Notes
1 See https://biopt.github.io/solvers/ and the papers referred to in the technical report Zhou and Zemkoho (Citation2021).
2 Note that if the LCP(q, M) is not feasible, neither is the lower-level problem.
3 It is implicitly assumed that costs and other factors may differ by index i representing different fuel-firm combinations. For example, an energy company that uses both coal and natural gas for power production would then be split into two separate firms using this notation.
4 With the Hessian matrix so that is strictly convex.
5 Without loss of generality, it is assumed that renewable production yi, has zero emissions, i.e., for all