B08
We propose an algorithm for solving bilevel problems with mixed-integer convex-quadratic upper level as well as convex-quadratic and continuous lower level. The method is based on a classic branch-and-bound procedure, where branching is performed on the integer constraints and on the complementarity constraints resulting from the KKT reformulation of the lower-level problem. However, instead of branching on constraints as usual, suitably chosen penalty terms are added to the objective function in order to create new subproblems in the tree. We prove the correctness of the method and present its applicability by some first numerical results.
Mixed complementarity problems are of great importance in practice since they appear in various fields of applications like energy markets, optimal stopping, or traffic equilibrium problems. However, they are also very challenging due to their inherent, nonconvex structure. In addition, recent applications require the incorporation of integrality constraints. Since complementarity problems often model some kind of equilibrium, these recent applications ask for equilibrium points that additionally satisfy certain integer conditions. Obviously, this makes the problem even harder to solve. The solution approach used most frequently in the literature is to recast the complementarity conditions as disjunctive constraints using additional binary variables and big-M constraints. However, both latter aspects create issues regarding the tractability and correctness of the reformulation. In this paper, we follow the opposite route and restate the integrality conditions as complementarity constraints, leading to purely continuous reformulations that can be tackled by local solvers. We study these reformulations theoretically and provide a numerical study that shows that continuous reformulations are useful in practice both in terms of solution times and solution quality.
We compare various flexible tariffs that have been proposed to cost-effectively govern a prosumer's electricity management - in particular time-of-use (TOU), critical-peak-pricing (CPP), and a real-time-pricing tariff (RTP). As the outside option, we consider a fixed-price tariff (FP) that restricts the specific characteristics of TOU, CPP, and RTP, so that the flexible tariffs are at least as profitable for the prosumer as the fixed-price tariff. We propose bilevel models to determine the optimal interplay between the retailer's tariff design and the prosumer's decisions on using the storage, on consumption, and on electricity purchases from as well as electricity sales to the grid. The single-level reformulations of the considered bilevel models are computationally highly challenging optimization problems since they, e.g., combine bilinearities and mixed-integer aspects for modeling certain tariff structures. Based on a computational study using real-world data, we find that RTP increases retailer profits, however, leads to the largest price volatility for the prosumer. TOU and CPP only yield mild additional retailer profits and, due to the multiplicity of optimal plans on the part of the prosumer, imply uncertain revenues for the retailer.
Portfolio optimization is an ongoing hot topic of mathematical optimization and management science. Due to the current financial market environment with low interest rates and volatile stock markets, it is getting more and more important to extend portfolio optimization models by other types of investments than classical assets. In this paper, we present a mixed-integer multistage stochastic model that includes investment opportunities in irreversible and long-term infrastructure projects in the context of renewable energies, which are also subject to policy risk. On realistic time scales for investment problems of this type, the resulting instances are by far too large to be solved with today's most evolved optimization software. Thus, we present a tailored moving-horizon approach together with suitable approximations and simplifications of the model. We evaluate these approximations and simplifications in a computational sensitivity analysis and derive a final model that can be tackled on a realistic instance by our moving-horizon approach.
We consider the combination of a network design and graph partitioning model in a multilevel framework for determining the optimal network expansion and the optimal zonal configuration of zonal pricing electricity markets, which is an extension of the model discussed in [25] that does not include a network design problem. The two classical discrete optimization problems of network design and graph partitioning together with nonlinearities due to economic modeling yield extremely challenging mixed-integer nonlinear multilevel models for which we develop two problem-tailored solution techniques. The first approach relies on an equivalent bilevel formulation and a standard KKT transformation thereof including novel primal-dual bound tightening techniques, whereas the second is a tailored generalized Benders decomposition. For the latter, we strengthen the Benders cuts of [25] by using the structure of the newly introduced network design subproblem. We prove for both methods that they yield global optimal solutions. Afterward, we compare the approaches in a numerical study and show that the tailored Benders approach clearly outperforms the standard KKT transformation. Finally, we present a case study that illustrates the economic effects that are captured in our model.