B07
Refine
Keywords
- Gas networks (4)
- Mixed-Integer Nonlinear Programming (4)
- Networks (4)
- Mixed-integer optimization (3)
- Pricing (3)
- Uniqueness (3)
- Bilevel optimization (2)
- Bookings (2)
- Combinatorial optimization (2)
- Convergence (2)
We study the classic single-item auction setting of Myerson, but under the assumption that the buyers' values for the item are distributed over "finite" supports. Using strong LP duality and polyhedral theory, we rederive various key results regarding the revenue-maximizing auction, including the characterization through virtual welfare maximization and the optimality of deterministic mechanisms, as well as a novel, generic equivalence between dominant-strategy and Bayesian incentive compatibility.
Inspired by this, we abstract our approach to handle more general auction settings, where the feasibility space can be given by arbitrary convex constraints, and the objective is a linear combination of revenue and social welfare. We characterize the optimal auctions of such systems as generalized virtual welfare maximizers, by making use of their KKT conditions, and we present an analogue of Myerson's payment formula for general discrete single-parameter auction settings. Additionally, we prove that total unimodularity of the feasibility space is a sufficient condition to guarantee the optimality of auctions with integral allocation rules.
Finally, we demonstrate this KKT approach by applying it to a setting where bidders are interested in buying feasible flows on trees with capacity constraints, and provide a combinatorial description of the (randomized, in general) optimal auction.
Robust DC Optimal Power Flow with Modeling of Solar Power Supply Uncertainty via R-Vine Copulas
(2021)
We present a robust approximation of joint chance constrained DC Optimal Power Flow in combination with a model-based prediction of uncertain power supply via R-vine copulas.
It is applied to optimize the discrete curtailment of solar feed-in in an electrical distribution network and guarantees network stability under fluctuating feed-in.
This is modeled by a two-stage mixed-integer stochastic optimization problem proposed by Aigner et al. (European Journal of Operational Research, (2021)).
The solution approach is based on the approximation of chance constraints via robust constraints using suitable uncertainty sets.
The resulting robust optimization problem has a known equivalent tractable reformulation.
To compute uncertainty sets that lead to an inner approximation of the stochastic problem, an R-vine copula model is fitted to the distribution of the multi-dimensional power forecast error, i.e., the difference between the forecasted solar power and the measured feed-in at several network nodes.
The uncertainty sets are determined by encompassing a sufficient number of samples drawn from the R-vine copula model.
Furthermore, an enhanced algorithm is proposed to fit R-vine copulas which can be used to draw conditional samples for given solar radiation forecasts.
The experimental results obtained for real-world weather and network data demonstrate the effectiveness of the combination of stochastic programming and model-based prediction of uncertainty via copulas.
We improve the outcomes of previous work by showing that the resulting uncertainty sets are much smaller and lead to less conservative solutions while maintaining the same probabilistic guarantees.
Every optimization problem has a corresponding verification problem which verifies whether a given optimal solution is in fact optimal. In the literature there are a lot of such ways to verify optimality for a given solution, e.g., the branch-and-bound tree. To simplify this task, Baes et al. introduced optimality certificates for convex mixed-integer nonlinear programs and proved that these are bounded in the number of integer variables. We introduce an algorithm to compute the certificates and conduct computational experiments. Through the experiments we show that the optimality certificates can be surprisingly small.
A PDE-Constrained Generalized Nash Equilibrium Approach for Modeling Gas Markets with Transport
(2021)
We investigate a class of generalized Nash equilibrium problems (GNEPs) in which the objectives of the individuals are interdependent and the shared constraint consists of a system of partial differential equations. This setup is motivated by the modeling of strategic interactions of competing firms, which explicitly take into account the dynamics of transporting a commodity, such as natural gas, through a network. We establish the existence of a variational equilibrium of the GNEP. In the case of symmetric firms, we identify an equivalent optimization problem. We use this model to numerically explore the impact of linepacking, that is the use of the network as a temporary storage device. In particular, we study the firms' decisions under various linepacking abilities and analyze which market participants benefit from it.
Common energy system models that integrate hydrogen transport in pipelines typically simplify fluid flow models and reduce the network size in order to achieve solutions quickly. This contribution analyzes two different types of pipeline network topologies (namely, star and tree networks) and two different fluid flow models (linear and nonlinear) for a given hydrogen capacity scenario of electrical reconversion in Germany to analyze the impact of these simplifications. For each network topology, robust demand and supply scenarios are generated. The results show that a simplified topology, as well as the consideration of detailed fluid flow, could heavily influence the total pipeline investment costs. For the given capacity scenario, an overall cost reduction of the pipeline costs of 37% is observed for the star network with linear cost compared to the tree network with nonlinear fluid flow. The impact of these improvements regarding the total electricity reconversion costs has led to a cost reduction of 1.4%, which is fairly small. Therefore, the integration of nonlinearities into energy system optimization models is not recommended due to their high computational burden. However, the applied method for generating robust demand and supply scenarios improved the credibility and robustness of the network topology, while the simplified fluid flow consideration can lead to infeasibilities. Thus, we suggest the utilization of the nonlinear model for post- processing to prove the feasibility of the results and strengthen their credibility, while retaining the computational performance of linear modeling.
The operation of gas pipeline flow with high pressure and small Mach numbers allows to model the flow by a semilinear hyperbolic system of partial differential equations. In this paper we present a number of transient and stationary analytical solutions of this model. They are used to discuss and clarify why a pde model is necessary to handle certain dynamic situations in the operation of gas transportation networks. We show that adequate numerical discretizations can capture the dynamical behavior sufficiently accurate. We also present examples that show that in certain cases an optimization approach that is based upon multi-period optimization of steady states does not lead to approximations that converge to the optimal state.
We consider equilibrium problems under uncertainty where firms
maximize their profits in a robust way when selling their output. Robust
optimization plays an increasingly important role when best guaranteed objective
values are to be determined, independently of the specific distributional
assumptions regarding uncertainty. In particular, solutions are to be determined
that are feasible regardless of how the uncertainty manifests itself within
some predefined uncertainty set. Our analysis adopts the robust optimization
perspective in the context of equilibrium problems. First, we consider a singlestage,
nonadjustable robust setting. We then go one step further and study the
more complex two-stage or adjustable case where a part of the variables can
adjust to the realization of the uncertainty. We compare equilibrium outcomes
with the corresponding centralized robust optimization problem where the
sum of all profits are maximized. As we find, the market equilibrium for
the perfectly competitive firms differs from the solution of the robust central
planner, which is in stark contrast to classical results regarding the efficiency of
market equilibria with perfectly competitive firms. For the different scenarios
considered, we furthermore are able to determine the resulting price of anarchy.
In the case of non-adjustable robustness, for fixed demand in every time step
the price of anarchy is bounded whereas it is unbounded if the buyers are
modeled by elastic demand functions. For the two-stage adjustable setting,
we show how to compute subsidies for the firms that lead to robust welfare
optimal equilibria.
In this article, we continue our work (Krug et al., 2021) on time-domain decomposition of optimal control problems for systems of semilinear hyperbolic equations in that we now consider mixed two-point boundary value problems and provide an in-depth well-posedness analysis. The more general boundary conditions significantly enlarge the scope of applications, e.g., to hyperbolic problems on metric graphs with cycles. We design an iterative method based on the optimality systems that can be interpreted as a decomposition method for the original optimal control problem into virtual control problems on smaller time domains.
Motivated by examples from the energy sector, we consider market equilibrium problems (MEPs) involving players with nonconvex strategy spaces or objective functions, where the latter are assumed to be linear in market prices. We propose an algorithm that determines if an equilibrium of such an MEP exists and that computes an equilibrium in case of existence. Three key prerequisites have to be met. First, appropriate bounds on market prices have to be derived from necessary optimality conditions of some players. Second, a technical assumption is required for those prices that are not uniquely determined by the derived bounds. Third, nonconvex optimization problems have to be solved to global optimality. We test the algorithm on well-known instances from the power and gas literature that meet these three prerequisites. There, nonconvexities arise from considering the transmission system operator as an additional player besides producers and consumers who, e.g., switches lines or faces nonlinear physical laws. Our numerical results indicate that equilibria often exist, especially for the case of continuous nonconvexities in the context of gas market problems.
A Bilevel Optimization Approach to Decide the Feasibility of Bookings in the European Gas Market
(2021)
The European gas market is organized as a so-called entry-exit system with the main goal to decouple transport and trading. To this end, gas traders and the transmission system operator (TSO) sign so-called booking contracts that grant capacity rights to traders to inject or withdraw gas at certain nodes up to this capacity. On a day-ahead basis, traders then nominate the actual amount of gas within the previously booked capacities. By signing a booking contract, the TSO guarantees that all nominations within the booking bounds can be transported through the network. This results in a highly challenging mathematical problem. Using potential-based flows to model stationary gas physics, feasible bookings on passive networks, i.e., networks without controllable elements, have been characterized in the recent literature. In this paper, we consider networks with linearly modeled active elements such as compressors or control valves. Since these active elements allow the TSO to control the gas flow, the single-level approaches for passive networks from the literature are no longer applicable. We thus present a bilevel model to decide the feasibility of bookings in networks with active elements. While this model is well-defined for general active networks, we focus on the class of networks for which active elements do not lie on cycles. This assumption allows us to reformulate the original bilevel model such that the lower-level problem is linear for every given upper-level decision. Consequently, we derive several single-level reformulations for this case. Besides the classic Karush-Kuhn-Tucker reformulation, we obtain three problem-specific optimal-value-function reformulations. The latter also lead to novel characterizations of feasible bookings in networks with active elements that do not lie on cycles. We compare the performance of our methods by a case study based on data from the GasLib.
