Refine
Year of publication
Keywords
- Bilevel optimization (16)
- Gas networks (8)
- Optimal control (8)
- Robust optimization (8)
- Uniqueness (7)
- optimal control (7)
- Mixed-Integer Nonlinear Optimization (6)
- Mixed-integer optimization (6)
- Convergence (5)
- Gas Networks (5)
We investigate the problem of scheduling the maintenance
of edges in a network, motivated by the goal of minimizing outages in
transportation or telecommunication networks. We focus on maintaining
connectivity between two nodes over time; for the special case of path
networks, this is related to the problem of minimizing the busy time of
machines.
We show that the problem can be solved in polynomial time in arbitrary
networks if preemption is allowed. If preemption is restricted to integral
time points, the problem is NP-hard and in the non-preemptive case
we give strong non-approximability results. Furthermore, we give tight
bounds on the power of preemption, that is, the maximum ratio of the
values of non-preemptive and preemptive optimal solutions.
Interestingly, the preemptive and the non-preemptive problem can be
solved efficiently on paths, whereas we show that mixing both leads to a
weakly NP-hard problem that allows for a simple 2-approximation.
In this paper we investigate stochastic programs with joint chance constraints. We consider discrete scenario set and reformulate the problem by adding auxiliary variables. Since the resulting problem has a difficult feasible set, we regularize it. To decrease the dependence on the scenario number, we propose a numerical method by iteratively solving a master problem while adding Benders cuts. We find the solution of the slave problem (generating the Benders cuts) in a closed form and propose a heuristic method to decrease the number of cuts. We perform a numerical study by increasing the number of scenarios and compare our solution with a solution obtained by solving the same problem with continuous distribution.
Depending on whether a mathematical program with equilibrium constraints
(MPEC) is considered in its original or its enhanced (via KKT conditions) form, the assumed qualification
conditions as well as the derived necessary optimality conditions may differ significantly. In this paper, we
study this issue when imposing one of the weakest possible qualification conditions, namely the calmness of
the perturbation mapping associated with the respective generalized equations in both forms of the MPEC.
It is well known that the calmness property allows one to derive the so-called M-stationarity conditions. The
restrictiveness of assumptions and the strength of conclusions in the two forms of the MPEC is also strongly
related to the qualification conditions on the “lower level”. For instance, even under the Linear Independence
Constraint Qualification (LICQ) for a lower level feasible set described by C 1 functions, the calmness properties
of the original and the enhanced perturbation mapping are drastically different. When passing to C 1,1 data, this
difference still remains true under the weaker Mangasarian-Fromovitz Constraint Qualification, whereas under
LICQ both the calmness assumption and the derived optimality conditions are fully equivalent for the original
and the enhanced form of the MPEC. After clarifying these relations, we provide a compilation of practically
relevant consequences of our analysis in the derivation of necessary optimality conditions. The obtained results
are finally applied to MPECs with structured equilibria.
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.
Pareto efficiency for robust linear programs was introduced by
Iancu and Trichakis in [9]. We generalize their approach and theoretical results
to robust optimization problems in Euclidean spaces with linear uncertainty.
Additionally, we demonstrate the value of this approach in an exemplary
manner in the area of robust semidefinite programming (SDP). In particular,
we prove that computing a Pareto robustly optimal solution for a robust SDP
is tractable and illustrate the benefit of such solutions at the example of the
maximal eigenvalue problem. Furthermore, we modify the famous algorithm of
Goemans and Williamson [8] in order to compute cuts for the robust max cut
problem that yield an improved approximation guarantee in non-worst-case
scenarios.
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.
Stochastic Optimization (SO) is a classical approach for optimization under uncertainty that typically requires knowledge about the probability distribution of uncertain parameters. As the latter is often unknown, Distributionally Robust Optimization (DRO) provides a strong alternative that determines the best guaranteed solution over a set of distributions (ambiguity set). In this work, we present an approach for DRO over time that uses online learning and scenario observations arriving as a data stream to learn more about the uncertainty. Our robust solutions adapt over time and reduce the cost of protection with shrinking ambiguity. For various kinds of ambiguity sets, the robust solutions converge to the SO solution. Our algorithm achieves the optimization and learning goals without solving the DRO problem exactly at any step. We also provide a regret bound for the quality of the online strategy which converges at a rate of $ O(\log T / \sqrt{T})$, where $T$ is the number of iterations. Furthermore, we illustrate the effectiveness of our procedure by numerical experiments on mixed-integer optimization instances from popular benchmark libraries and give practical examples stemming from telecommunications and routing. Our algorithm is able to solve the DRO over time problem significantly faster than standard reformulations.
We propose a mathematical optimization model and its solution for joint chance constrained DC Optimal Power Flow. In this application, it is particularly important that there is a high probability of transmission limits being satisfied, even in the case of uncertain or fluctuating feed-in from renewable energy sources. In critical network situations where the network risks overload, renewable energy feed-in has to be curtailed by the transmission system operator (TSO). The TSO can reduce the feed-in in discrete steps at each network node. The proposed optimization model minimizes curtailment while ensuring that there is a high probability of transmission limits being maintained. The latter is modeled via (joint) chance constraints that are computationally challenging. Thus, we propose a solution approach based on the robust safe approximation of these constraints. Hereby, probabilistic constraints are replaced by robust constraints with suitably defined uncertainty sets constructed from historical data. The uncertainty sets are calculated by encompassing randomly drawn scenarios using the scenario approach proposed by Margellos et al. (IEEE Transactions on Automatic Control, 59 (2014)). The ability to discretely control the power feed-in then leads to a robust optimization problem with decision-dependent uncertainties, i.e. the uncertainty sets depend on decision variables. We propose an equivalent mixed-integer linear reformulation for box uncertainties with the exact linearization of bilinear terms. Finally, we present numerical results for different test cases from the Nesta archive, as well as for a real network. We consider the discrete curtailment of solar feed-in, for which we use real-world weather and network data. The experimental tests demonstrate the effectiveness of this method and run times are very fast. Moreover, on average the calculated robust solutions lead only to a small increase in curtailment, when compared to nominal solutions.
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.
The entropy-based moment method is a well-known discretization for the velocity variable in kinetic equations which has many desirable theoretical properties but is difficult to implement with high-order numerical methods. The regularized entropy-based moment method was recently introduced to remove one of the main challenges in the implementation of the entropy-based moment method, namely the requirement of the realizability of the numerical solution. In this work we use the method of relative entropy to prove the convergence of the regularized method to the original method as the regularization parameter goes to zero and give convergence rates. Our main assumptions are the boundedness of the velocity domain and that the original moment solution is Lipschitz continuous in space and bounded away from the boundary of realizability. We provide results from numerical simulations showing that the convergence rates we prove are optimal.