On linear bilevel optimization problems with complementarity-constrained lower levels

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.

Keywords:

• Bilevel optimization
• linear programs with complementarity constraints
• linear complementarity problems
• reformulations
• spatial price equilibria
• oligopoly models in energy

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 (2021).

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 $f_i(y_i)=-(p(y_1,\dots ,y_{N_F})y_i-{\gamma }_i{y}_i),$ the Hessian matrix ${\nabla }^2{f}_i(y_i)=2\beta >0$ so that $f_i(y_i)$ is strictly convex.

5 Without loss of generality, it is assumed that renewable production y_i, $i\in R,$ has zero emissions, i.e., ${\eta }_i=0$ for all $i\in R.$

Additional information

Funding

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.