TY - INPR A1 - Gabriel, Steven A. A1 - Leal, Marina A1 - Schmidt, Martin T1 - On Linear Bilevel Optimization Problems with Complementarity-Constrained Lower Levels N2 - 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. KW - Bilevel optimization KW - Linear programs with complementarity constraints KW - Linear complementarity problems KW - Reformulations KW - Spatial price equilibria Y1 - 2020 ER - TY - JOUR A1 - Kramer, Anja A1 - Krebs, Vanessa A1 - Schmidt, Martin T1 - Strictly and Γ-Robust Counterparts of Electricity Market Models: Perfect Competition and Nash-Cournot Equilibria JF - Operations Research Perspectives N2 - This paper mainly studies two topics: linear complementarity problems for modeling electricity market equilibria and optimization under uncertainty. We consider both perfectly competitive and Nash–Cournot models of electricity markets and study their robustifications using strict robustness and the Γ-approach. For three out of the four combinations of economic competition and robustification, we derive algorithmically tractable convex optimization counterparts that have a clear-cut economic interpretation. In the case of perfect competition, this result corresponds to the two classical welfare theorems, which also apply in both considered robust cases that again yield convex robustified problems. Using the mentioned counterparts, we can also prove the existence and, in some cases, uniqueness of robust equilibria. Surprisingly, it turns out that there is no such economic sensible counterpart for the case of Γ-robustifications of Nash–Cournot models. Thus, an analogue of the welfare theorems does not hold in this case. Finally, we provide a computational case study that illustrates the different effects of the combination of economic competition and uncertainty modeling. KW - Robust optimization KW - Linear complementarity problems KW - Electricity market equilibrium models KW - Perfect competition KW - Nash-Cournot competition Y1 - 2018 IS - 89(2) SP - 100197 ER - TY - JOUR A1 - Krebs, Vanessa A1 - Schmidt, Martin T1 - Γ-Robust Linear Complementarity Problems JF - Optimization Methods and Software N2 - Complementarity problems are often used to compute equilibria made up of specifically coordinated solutions of different optimization problems. Specific examples are game-theoretic settings like the bimatrix game or energy market models like for electricity or natural gas. While optimization under uncertainties is rather well-developed, the field of equilibrium models represented by complementarity problems under uncertainty - especially using the concepts of robust optimization - is still in its infancy. In this paper, we extend the theory of strictly robust linear complementarity problems (LCPs) to Γ-robust settings, where existence of worst-case-hedged equilibria cannot be guaranteed. Thus, we study the minimization of the worst-case gap function of Γ-robust counterparts of LCPs. For box and l1-norm uncertainty sets we derive tractable convex counterparts for monotone LCPs and study their feasibility as well as the existence and uniqueness of solutions. To this end, we consider uncertainties in the vector and in the matrix defining the LCP. We additionally study so-called ρ-robust solutions, i.e., solutions of relaxed uncertain LCPs. Finally, we illustrate the Γ-robust concept applied to LCPs in the light of the above mentioned classical examples of bimatrix games and market equilibrium modeling. KW - Linear complementarity problems KW - Robust optimization KW - Optimization under uncertainty KW - Γ-robustness KW - Tractable counterparts Y1 - 2019 ER - TY - INPR A1 - Krebs, Vanessa A1 - Müller, Michael A1 - Schmidt, Martin T1 - Γ-Robust Linear Complementarity Problems with Ellipsoidal Uncertainty Sets T2 - International Transactions in Operational Research N2 - We study uncertain linear complementarity problems (LCPs), i.e., problems in which the LCP vector q or the LCP matrix M may contain uncertain parameters. To this end, we use the concept of Γ-robust optimization applied to the gap function formulation of the LCP. Thus, this work builds upon [16]. There, we studied Γ-robustified LCPs for l1- and box-uncertainty sets, whereas we now focus on ellipsoidal uncertainty set. For uncertainty in q or M, we derive conditions for the tractability of the robust counterparts. For these counterparts, we also give conditions for the existence and uniqueness of their solutions. Finally, a case study for the uncertain traffic equilibrium problem is considered, which illustrates the effects of the values of Γ on the feasibility and quality of the respective robustified solutions. KW - Robust optimization KW - Linear complementarity problems KW - Ellipsoidal uncertainty sets KW - Traffic equilibrium problems Y1 - 2019 IS - 29(1) SP - 417 EP - 441 ER - TY - JOUR A1 - Henrion, René A1 - Schmidt, Martin T1 - Chance-Constrained Linear Complementarity Problems N2 - We study linear complementarity problems (LCPs) under uncer- tainty, which we model using chance constraints. Since the complementarity condition of the LCP is an equality constraint, it is required to consider relax- ations, which naturally leads to optimization problems in which the relaxation parameters are minimized for given probability levels. We focus on these optimization problems and first study the continuity of the related probability functions and the compactness of the feasible sets. This leads to existence results for both types of models: one with a joint chance constraint and one with separate chance constraints for both uncertainty-affected conditions of the LCP. For both, we prove the differentiability of all probability functions and derive respective gradient formulae. For the separate case, we prove con- vexity of the respective optimization problem and use the gradient formulae to derive necessary and sufficient optimality conditions. In a small case study regarding a Cournot oligopoly among energy producers, we finally illustrate the applicability of our theoretical findings. KW - Linear complementarity problems KW - Chance constraints KW - Existence KW - Convexity KW - Optimality conditions Y1 - 2026 ER -