Robust and bilevel optimization share the common feature that they involve a certain multilevel structure. Hence, although they model something rather different when used in practice, they seem to have a similar mathematical structure. In this paper, we analyze the connections between different types of robust problems (static robust problems with and without decision-dependence of their uncertainty sets, worst-case regret problems, and two-stage robust problems) as well as of bilevel problems (optimistic problems, pessimistic problems, and robust bilevel problems). It turns out that bilevel optimization seems to be more general in the sense that for most types of robust problems, one can find proper reformulations as bilevel problems but not necessarily the other way around. We hope that these results pave the way for a stronger connection between the two fields - in particular to use both theory and algorithms from one field in the other and vice versa.
Developing solution methods for discrete bilevel problems is known to be a challenging task - even if all parameters of the problem are exactly known. Many real-world applications of bilevel optimization, however, involve data uncertainty. We study discrete min-max problems with a follower who faces uncertainties regarding the parameters of the lower-level problem. Adopting a Γ-robust approach, we present an extended formulation and a multi-follower formulation to model this type of problem. For both settings, we provide a generic branch-and-cut framework. Specifically, we investigate interdiction problems with a monotone Γ-robust follower and we derive problem-tailored cuts, which extend existing techniques that have been proposed for the deterministic case. For the Γ-robust knapsack interdiction problem, we computationally evaluate and compare the performance of the proposed algorithms for both modeling approaches.
Many applications of bilevel optimization contain a leader facing a follower whose reaction deviates from the one expected by the leader due to some kind of bounded rationality. We consider bilinear bilevel problems with follower's response uncertainty due to limited observability regarding the leader's decision and exploit robust optimization to model the decision making of the follower. We show that the robust counterpart of the lower level allows to tackle the problem via the lower level's KKT conditions.
We consider uncertain robust electricity market equilibrium problems including transmission and generation investments. Electricity market equilibrium modeling has a long tradition but is, in most of the cases, applied in a deterministic setting in which all data of the model are known. Whereas there exist some literature on stochastic equilibrium problems, the field of robust equilibrium models is still in its infancy. We contribute to this new field of research by considering Γ-robust electricity market equilibrium models on lossless DC networks with transmission and generation investments. We state the nominal market equilibrium problem as a mixed complementarity problem as well as its variational inequality and welfare optimization counterparts. For the latter, we then derive a Γ-robust formulation and show that it is indeed the counterpart of a market equilibrium problem with robustified player problems. Finally, we present two case studies to gain insights into the general effects of robustification on electricity market models. In particular, our case studies reveal that the transmission system operator tends to act more risk-neutral in the robust setting, whereas generating firms clearly behave more risk-averse.
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.
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.
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.
We consider the problem of discrete arc sizing for tree-shaped potential networks with respect to infinitely many demand scenarios. This means that the arc sizes need to be feasible for an infinite set of scenarios. The problem can be seen as a strictly robust counterpart of a single-scenario network design problem, which is shown to be NP-complete even on trees. In order to obtain a tractable problem, we introduce a method for generating a finite scenario set such that optimality of a sizing for this finite set implies the sizing's optimality for the originally given infinite set of scenarios. We further prove that the size of the finite scenario set is quadratically bounded above in the number of nodes of the underlying tree and that it can be computed in polynomial time. The resulting problem can then be solved as a standard mixed-integer linear optimization problem. Finally, we show the applicability of our theoretical results by computing globally optimal arc sizes for a realistic hydrogen transport network of Eastern Germany.