Optimization at the Second Level

A bilevel optimization problem consists in an optimization problem in which some of the constraints specify that a subset of variables must be an optimal solution to another optimization problem. This paradigm is particularly appropriate to model competition between agents, a leader and a follower, acting sequentially.

In this talk I focus on the simplest bilevel problems, those that are linear. I present the main characteristics, properties and algorithms for these problems. Then, I discuss some recent results showing that these problems are already extremely challenging. Finally, I show how linear bilevel optimisation may help to improve the resolution of stochastic optimisation problems whose objective involve the Value at Risk (VaR) or quantile.

Servitization markets that center their business around operationally connecting buyers and suppliers of goods, services, or capacities can be modeled as combinatorial exchanges. Usually, the markets employ a profit-oriented intermediary to coordinate the process. Particularities of the servitization market are that (I) potential buyers face budget constraints, which provide an incentive to overstate valuations, resulting in exchanges that are not welfare-maximizing and (II) core-stability of the market is essential to foster participation and, thus, the attractiveness of the heterogeneous exchange. However, it has been proven that no truthful mechanism exists under private budget constraints in combinatorial exchanges. We propose the introduction of a profit-oriented intermediary, which allows for the incentivization of truthfulness in these markets. We utilize the properties of Mixed Integer Bilevel Linear Problems to formulate the allocation and pricing problem for core-stable intermediated combinatorial exchanges under private budget constraints. We find that intermediated combinatorial exchanges with a profit-oriented intermediary lead to higher social welfare than truthful non-intermediated benchmarks while restricting the matching of untruthful buyers.

In this talk, I first reviewed robust convex optimization, focussing on duality-based reformulations of robust counterparts to finite and algorithmically tractable problems as well as cutting plane approaches. For constraints that are convex in the decisions and concave in the uncertainty, Fenchel duality can be used. For combinatorial optimization problems with nonlinear objective, I showed new reformulations that combine Gamma-robust counterparts with Fenchel duality (This part is joint work with Dennis Adelhütte, FAU). A novel approach (joint with Martina Kuchlbauer and Michael Stingl, both FAU) for mixed-integer nonlinear robust optimization was summarized. Here, an adaptive bundle method uses nonconvex adversarial problems that are solved up to any given error, e.g., via piecewise linear relaxations. For problems that are convex in the uncertainty and potentially nonconvex in the uncertainty, the bundle method is embedded in an outer approximation scheme. I then continued with reviewing distributional robustness, focussing on reformulations and the construction of ambiguity sets based on historical data. I concluded by pointing out current research questions.

We study a class of integer bilevel programs with second-order cone constraints at the upper level and a convex-quadratic objective function and linear constraints at the lower level. We develop disjunctive cuts (DCs) to separate bilevel-infeasible solutions using a second-order-cone-based cut-generating procedure. We propose DC separation strategies and consider several approaches for removing redundant disjunctions and normalization. Using these DCs, we propose a branch-and-cut algorithm for the problem class we study, and a cutting-plane method for the problem variant with only binary variables. We present an extensive computational study on a diverse set of instances, including instances with binary and with integer variables, and instances with a single and with multiple linking constraints. Our computational study demonstrates that the proposed enhancements of our solution approaches are effective for improving the performance. Moreover, both of our approaches outperform a state-of-the-art generic solver for mixed-integer bilevel linear programs that is able to solve a linearized version of our binary instances.

In this talk, we address multi-stage adjustable robust optimization with right-hand-side uncertainty. We consider both continuous cases and mixed integer cases. For continuous cases, we show that the problem can be solved by enumerating the vertices of the uncertainty set. So, for a polyhedral uncertainty set, we develop a simplex-type method that starts from a vertex and moves to an adjacent vertex with a worse objective value. For the mixed integer case, we developed an iterative approach that converges to the optimal solution. The algorithm is based on partitioning the uncertainty set into smaller sets and obtaining a lower and upper bound for each subset. Since the algorithm itself is an exhaustive search, we also developed a heuristic method based on the limited discrepancy search, where we develop a branching tree and construct waves to explore the tree. We show that both algorithms work in practical problems, as it is based on an oracle that solves the deterministic problem in each iteration.

Bilevel assignment problem is an example of bilevel optimization problems. In an instance of bilevel assignment problem, we are given a bipartite graph $G=(V,E)$, and the edge set $E$ is partitioned into two sets $E_{\mathrm{\ell }}$ and $E_f$. The set $E_{\mathrm{\ell }}$ is controlled by the leader and the set $E_f$ is controlled by the follower. Additionally, leader and follower have their own weight functions $w_{\mathrm{\ell }}$ and $w_f$ defined on the edge set $E$. Both decision makers have their own objective functions $c,d$ for the leader and the follower respectively. We consider the settings in which the objective functions of the leader and the follower can be of sum or bottleneck type. Moreover, the follower can behave according to the optimistic or pessimistic rule. The goal of the leader is to find $L\subseteq E_{\mathrm{\ell }}$ which minimizes her objective function subject to an optimal reaction of the follower $F\subseteq E_f$ such that $L\cup F$ forms a perfect matching in the graph $G$. We give a unified NP-hardness proof for the eight variants of bilevel assignment problem; the eight variants arise from the combinations of sum or bottleneck type of objective functions $c$ and $d$, and from the pessimistic or optimistic behavior of the follower. Consequently, we show non-existence of an approximation algorithm for this problem.

In this presentation I will give a broad introduction to stochastic optimization, focusing on static problems. I will start with the classic paradigm of minimizing expected costs, and then discuss why the inclusion of risk measures is desirable in many practical situations. I will exemplify the effect of risk aversion in the newsvendor problem, using the CVaR as the risk measure.

I will briefly introduce the dynamic setting, and the different algorithms to solve the problems in sequential decision-making. I will conclude with the current challenges in end-to-end learning, which consist of problems that integrate prediction and prescription. Bilevel optimization is an important tool in this integration, and I will define precisely how it can build the bridge between machine learning and optimization.

Product recommendation, matrix factorization, or Euclidean embedding can be formulated as optimization problems with a constraint on the rank of the decision variables (a matrix). These optimization problems constitute hard non-convex optimization problems that cannot be modeled via convex mixed-integer optimization. Alternatively, we propose to introduce projection matrices (i.e., matrices that satisfy $P^2=P$) to encode for the span of the decision variables and linearize the rank constraint. Projection matrices are not only a generalization of binary variables (i.e., scalar roots of the equation $z^2=2$) but we show that the resulting optimization framework, which we coin mixed-projection optimization, can effectively be used to solve low-rank optimization problems to provable optimality. In particular, some of the most successful ideas from mixed-integer optimization such as big-M formulations, perspective cuts, relax-then-round strategies generalize to low-rank problems by using projection matrices.

We present a variant of adaptive robust combinatorial optimization problems where the decision maker can prepare $K$ solutions and choose the best among them upon knowledge of the true data realizations. We suppose that the uncertainty may affect the objective and the constraints through functions that are not necessarily linear.

In the first part of the talk, we propose a new exact algorithm for solving these problems when the feasible set of the nominal optimization problem does not contain too many good solutions. Our algorithm enumerates these good solutions, generates dynamically a set of scenarios from the uncertainty set, and assigns the solutions to the generated scenarios using a vertex $p$-center formulation, solved by a binary search algorithm. Our numerical results on adaptive shortest path and knapsack with conflicts problems show that our algorithm compares favorably with the methods proposed in the literature. We additionally propose a heuristic extension of our method to handle problems where it is prohibitive to enumerate all good solutions. This heuristic is shown to provide good solutions within a reasonable solution time limit on the adaptive knapsack with conflicts problem. Finally, we illustrate how our approach handles non-linear functions on an all-or-nothing subset problem taken from the literature.

In the second part of the talk, we discuss extensions of these algorithms to $K$-adaptability, where the decision maker must set first-stage optimization variables in addition to the preparation of the $K$ second-stage solutions. We reformulate again the problem along the lines of $p$-center location problems, this time including additional coupling constraints. We discuss how subtle pricing and adversarial problems may lead to efficient branch-and-cut-price algorithms for solving the problem optimally.

In this talk, we consider the design choices one has to make when considering optimization under uncertainty. Expanding the model form useful for solving the deterministic problem into an uncertainty-including form is often hard. This calls, in line with the seminar description, for completely new ways of modelling ${\mathrm{\Sigma }}_2^p$ problems. We illustrate one heuristic idea (evaluating incumbent solutions of a deterministic MILP for a given problem with stochastic simulations and picking the best one among those) on the fleet assignment problem in airline optimization, which performs similarly to a massive, exact MILP reformulation of the stochastic problem.

Duality is a central concept in optimization from which optimality conditions arise, among other important implications. It is duality-based optimality conditions that enable the reformulations that are the basis for many algorithms for addressing multistage optimization problems in which the problem to be solved at each stage is parametric in the decisions and information revealed at previous stages. Examples include multilevel optimization, robust optimization, and multistage stochastic programming with recourse. By replacing later stage problems with their optimality conditions, it is possible to reformulate these multistage problems as traditional mathematical optimization problems, albeit ones involving complex value function. While it is often stated that there is no strong duality for nonconvex optimization problems, such as mixed integer linear optimization problems (MILPs), we discuss in this talk that this is indeed not the case. We describe a duality theory that generalizes the classical LP/convex duality theory to the MILP setting and show that it can be derived from first principles beginning from each of three seemingly disparate starting points. The first is the traditional notion based on bounding of the value function, the second is based on a generalized Farkas lemma that leads to a complexity-theoretic interpretation, and the third is based on reformulation via projection, which leads to a generalized Benders decomposition. The relationship between these three different derivations and the generalized notions that arise shed light on the nature of the duality relations at the core of optimization theory and enable duality principles to be applied to a much wider range of problems.

Bilevel optimization is a very active field of applied mathematics. The main reason is that bilevel optimization problems can serve as a powerful tool for modeling hierarchical decision making processes. This ability, however, also makes the resulting problems challenging to solve – both in theory and practice. In this talk, we focus on bilevel optimization problems under uncertainty. First, we give an overview about this rather young field. We particularly show that the sources of uncertainty are much richer in bilevel optimization when compared to “usual”, i.e., single-level, optimization. The reason is that, besides data uncertainty, one can also face uncertainties w.r.t. the decisions of the other player. Second, we briefly present two recent papers on uncertain bilevel optimization. One in which we develop a branch-and-cut framework for bilevel knapsack interdiction, where the lower-level is a Gamma-robustified model, and another one, in which we try to model the situation of a follower that is uncertain w.r.t. the leader’s decision. Third and finally, we sketch some open problems in the field of bilevel optimization under uncertainty to propel some further discussions during the seminar and beyond.

In the context of the massive penetration of renewables and the shift of the energy system operation towards more consumer-centric approaches, local energy markets are seen as a promising solution for prosumers’ empowerment. Various local market designs have been proposed that often ignore the laws of physics ruling the underlying distribution network’s power flows. This may compromise the power system’s security or lead to operational inefficiencies. Therefore, including the distribution network in clearing the local market arises as a challenge. We propose using grid usage prices (GUPs) as an incentive mechanism to drive the system towards an economically and operationally efficient market equilibrium, subject to security constraints. Our approach requires expressing the incentive policies as affine functions of the prosumers’ active and reactive power outputs. This setting falls into the category of reverse Stackelberg games, where we look for the optimal policy in the space of affine functions [2]. This approach takes advantage of controllability guarantees for the problem’s unconstrained setting, which hopefully will enable the DSO to influence the output of the market towards an optimally determined target point. Market-related properties of the policy, such as economic efficiency, individual rationality, incentive compatibility, and fairness, will be rigorously studied. Two alternative solution approaches are proposed: The first is based on reformulating the resulting bilevel problem into a single-level problem employing the KKT conditions of the underlying lower-level problem. Then, the resulting quadratically constrained quadratic problem is solved applying a trust-region method. The second solution approach is based on first obtaining a team-problem solution and solving a feasibility problem to induce it [1]. Finally, extensive computational experiments will be carried out on different IEEE test feeders to assess the performance of the proposed approach statistically.

In this work, we present a cloud sharing system that increases the utilization rate of public cloud resources. The system is modeled as a mixed integer bilevel problem with two independent follower lever problems. The leader interacts with the followers by (i) offering rewards to long-term consumers to lease their resources and (ii) setting prices to short-term consumers to access available resources. We solve the model using an optimal value function algorithm.