Refine
Language
- English (8)
Has Fulltext
- yes (8)
Keywords
- AC Optimal Power Flow (1)
- Discrete Decisions (1)
- Mixed-Integer Nonlinear Programming (1)
- Piecewise Linear Relaxation (1)
- Potential-based flows, Gas networks, Computational complexity, European entry-exit market, Bookings (1)
- Robust Optimization, Mixed-integer programming, Uncertainty sets, Robust feasibility (1)
- Second-Order Cone Programming (1)
- chance constraints (1)
- decision trees (1)
- mixed-integer programming (1)
For a mixed-integer linear problem (MIP) with uncertain constraints, the radius of robust feasibility (RRF) determines a value for the maximal “size” of the uncertainty set such that robust feasibility of the MIP can be guaranteed. The approaches for the RRF in the literature are restricted to continuous optimization problems. We first analyze relations between the RRF of a MIP and its continuous linear (LP) relaxation. In particular, we derive conditions under which a MIP and its LP relaxation have the same RRF. Afterward, we extend the notion of the RRF such that it can be applied to a large variety of optimization problems and uncertainty sets. In contrast to the setting commonly used in the literature, we consider for every constraint a potentially different uncertainty set that is not necessarily full-dimensional. Thus, we generalize the RRF to MIPs as well as to include “safe” variables and constraints, i.e., where uncertainties do not affect certain variables or constraints. In the extended setting, we again analyze relations between the RRF for a MIP and its LP relaxation. Afterward, we present methods for computing the RRF of LPs as well as of MIPs with safe variables and constraints. Finally, we show that the new methodologies can be successfully applied to the instances in the MIPLIB 2017 for computing the RRF.
In this paper, we discuss optimality conditions for optimization problems {involving} random state constraints, which are modeled in probabilistic or almost sure form. While the latter can be understood as the limiting case of the former, the derivation of optimality conditions requires substantially different approaches. We apply them to a linear elliptic partial differential equation (PDE) with random inputs.
In the probabilistic case, we rely on the spherical-radial decomposition of Gaussian random vectors in order to formulate fully explicit optimality conditions involving a spherical integral. In the almost sure case, we derive optimality conditions and compare them to a model based on robust constraints with respect to the (compact) support of the given distribution.
We show that deciding the feasibility of a booking (FB) in the European entry-exit gas market is coNP-hard if a nonlinear potential-based flow model is used. The feasibility of a booking can be characterized by polynomially many load flow scenarios with maximum potential-difference, which are computed by solving nonlinear potential-based flow models. We use this existing characterization of the literature to prove that FB is coNP-hard by reducing Partition to the infeasibility of a booking. We further prove that computing a potential-difference maximizing load flow scenario is NP-hard even if we can determine the flow direction a priori. From the literature, it is known that FB can be decided in polynomial time on trees and a single cycle. Thus, our hardness result draws the first line that separates the easy from the hard variants of FB and finally answers that FB is hard in general.
The question for the capacity of a given gas network, i.e., determining the maximal amount of gas that can be transported by a given network, appears as an essential question that network operators and political administrations are regularly faced with.
In that context we present a novel mathematical approach in order to assist gas network operators in managing increasing uncertainty with respect to customers gas nominations and in exposing free network capacities while reliability of transmission and supply is taken into account. The approach is based on the rigorous examination of optimization
problems with nonlinear probabilistic constraints. As consequence we deal with solving
a problem belonging to the class of probabilistic/robust optimization problems, which can be formulated with some joint probabilistic constraint over an
infinite system of random inequalities. We will show that the inequality system
can be reduced to a finite one in the situation of considering a tree network topology.
A detailed study of the problem of maximizing bookable capacities in a stationary gas network is presented that comes up with an algebraic model involving Kirchhoff's first and second laws. The focus will be on both the theoretical and numerical side.
The analytical part consists in introducing and validating a generalized version of the known rank two constraint qualification implying the differentiability of the considered capacity problem. The results are important in order to solve the capacity problem numerically, where function and gradient evaluations of the probabilistic constraints are performed by an approach using spheric-radial decomposition applicable for multivariate Gaussian random variables and more general distributions.
In many real-world mixed-integer optimisation problems from engineering, the side
constraints can be subdivided into two categories: constraints which describe a certain logic to model a feasible allocation of resources (such as a maximal number of available assets, working time requirements, maintenance requirements, contractual obligations, etc.),
and constraints which model physical processes and the related quantities (such as current,
pressure, temperature, etc.). While the first type of constraints can often easily be stated in
terms of a mixed-integer program (MIP), the second part may involve the incorporation of
complex non-linearities, partial differential equations or even a black-box simulation of the
involved physical process. In this work, we propose the integration of a trained tree-based
classifier – a decision-tree or a random forest, into a mixed-integer optimization model as a
possible remedy. We assume that the classifier has been trained on data points produced
by a detailed simulation of a given complex process to represent the functional relationship
between the involved physical quantities. We then derive MIP-representable reformulations
of the trained classifier such that the resulting model can be solved using state-of-the-art
solvers. At the hand of several use cases in terms of possible optimisation goals, we show
the broad applicability of our framework that is easily extendable to other tasks beyond
engineering. In a detailed real-world computational study for the design of stable direct-
current power networks, we demonstrate that our approach yields high-quality solutions
in reasonable computation times.
Joint model of probabilistic/robust (probust) constraints applied to gas network optimization
(2017)
Optimization tasks under uncertain conditions abound in many
real-life applications. Whereas solution approaches for probabilistic constraints
are often developed in case the uncertainties can be assumed to follow a
certain probability distribution, robust approaches are usually used in case
solutions are sought that are feasible for all realizations of uncertainties within
some pre-defined uncertainty set. As many applications contain different types
of uncertainties that require robust as well as probabilistic treatments, we deal with a class of joint probabilistic/robust constraints as its appears in
optimization problems under uncertainty. Focusing on complex uncertain gas
network optimization problems, we show the relevance of this class of problems
for the task of maximizing free booked capacities in an algebraic model for a
stationary gas network. We furthermore present approaches for their solution.
Finally, we study the problem of controlling a transient system that is governed
by the wave equation. The task consists in determining controls such that a
certain robustness measure remains below some given upper bound, with high
probability.
Probability functions figure prominently in optimization problems
of engineering. They may be nonsmooth even if all input data are smooth.
This fact motivates the consideration of subdifferentials for such typically just
continuous functions. The aim of this paper is to provide subdifferential formulae
of such functions in the case of Gaussian distributions for possibly
infinite-dimensional decision variables and nonsmooth (locally Lipschitzian)
input data. These formulae are based on the spheric-radial decomposition of
Gaussian random vectors on the one hand and on a cone of directions of
moderate growth on the other. By successively adding additional hypotheses,
conditions are satisfied under which the probability function is locally Lipschitzian
or even differentiable.
We present a solution framework for general alternating current optimal power flow (AC OPF) problems that include discrete decisions.
The latter occur, for instance, in the context of the curtailment of renewables or the
switching of power generation units and transmission lines.
Our approach delivers globally optimal solutions and is provably convergent.
We model AC OPF problems with discrete decisions as mixed-integer nonlinear programs.
The solution method starts from a known framework that uses piecewise linear relaxations.
These relaxations are modeled as as mixed-integer linear programs and adaptively refined until some termination criterion is fulfilled.
In this work, we extend and complement this approach by problem-specific as well as very general algorithmic enhancements.
In particular, these are mixed-integer second-order cone programs as well as primal and dual cutting planes.
For example objective cuts and no-good-cuts help to compute good feasible solutions as where outer approximation constraints tighten the relaxations.
We present extensive numerical results for various AC OPF problems where discrete decisions play a major role.
Even for hard instances with a large proportion of discrete decisions, the method is able
to generate high quality solutions efficiently.
Furthermore, we compare our approach with state-of-the-art MINLP.
Our method outperforms all other algorithms.
