TY - INPR A1 - Aßmann, Denis A1 - Liers, Frauke A1 - Stingl, Michael T1 - Decomposable Robust Two-Stage Optimization: An Application to Gas Network Operations Under Uncertainty N2 - We study gas network problems with compressors and control valves under uncertainty that can be formulated as two-stage robust optimization problems. Uncertain data are present in the physical parameters of the pipes as well as in the overall demand. We show how to exploit the special decomposable structure of the problem in order to reformulate the two-stage robust problem as a standard single-stage optimization problem. Since this structure is present in similar problems on e.g., water or direct current electricity networks, we investigate the consequences of the decomposable structure in an abstract setting: The right-hand side of the single-stage problem can be precomputed by solving a series of optimization problems and multiple elements of the right-hand side can be combined into one optimization task. In order to apply our results to gas network problems, we extend piecewise relaxations and preprocessing techniques to incorporate uncertain input data. The practical feasibility and effectiveness of our approach is demonstrated with benchmarks on realistic gas network instances. We observe large speedups due to the described aggregation method together with the developed preprocessing strategies. Furthermore, we are able to solve even comparably large gas network instances quickly for the price of slightly more conservative solutions. KW - robust optimization KW - gas networks KW - relaxations Y1 - 2017 ER - TY - JOUR A1 - Bärmann, Andreas A1 - Liers, Frauke A1 - Martin, Alexander A1 - Merkert, Maximilian A1 - Thurner, Christoph A1 - Weninger, Dieter T1 - Solving network design problems via iterative aggregation JF - Mathematical Programming Computation N2 - In this work, we present an exact approach for solving network design problems that is based on an iterative graph aggregation procedure. The scheme allows existing preinstalled capacities. Starting with an initial aggregation, we solve a sequence of network design master problems over increasingly fine-grained representations of the original network. In each step, a subproblem is solved that either proves optimality of the solution or gives a directive where to refine the representation of the network in the subsequent iteration. The algorithm terminates with a globally optimal solution to the original problem. Our implementation uses a standard integer programming solver for solving the master problems as well as the subproblems. The computational results on random and realistic instances confirm the profitable use of the iterative aggregation technique. The computing time often reduces drastically when our method is compared to solving the original problem from scratch. KW - Aggregation KW - Network design KW - Combinatorial optimization KW - Mixed-integer programming KW - Branch-and-cut Y1 - 2015 U6 - https://doi.org/10.1007/s12532-015-0079-1 VL - 7 IS - 2 SP - 189 EP - 217 ER - TY - JOUR A1 - Liers, Frauke A1 - Merkert, Maximilian T1 - Structural Investigation of Piecewise Linearized Network Flow Problems N2 - In this work we study polyhedra in the context of network flow problems, where the flow value on each arc lies in one of several predefined intervals. This is motivated by nonlinear problems on transportation networks, where nonlinearities are handled by piecewise linear approximation or relaxation - a common and established approach in many applications. Several methods for modeling piecewise linear functions are known which provide a complete description for a single network arc. However, in general this property is lost when considering multiple arcs. We show how to strengthen the formulation for specific substructures consisting of multiple arcs by linear inequalities. For the case of paths of degree-two-nodes we give a complete description of the polyhedron projected to the integer variables. Our model is based on - but not limited to - the multiple choice method; we also show how to transfer our results to a formulation based on the incremental method. Computational results show that a state-of-the-art MIP-solver greatly benefits from using our cutting planes for random and realistic network topologies. KW - Combinatorial optimization KW - Complete description KW - Network flow problems KW - Piecewise linear functions Y1 - 2016 U6 - https://doi.org/10.1137/15M1006751 VL - 26 SP - 2863 EP - 2886 ER - TY - JOUR A1 - Cacchiani, Valentina A1 - Jünger, Michael A1 - Liers, Frauke A1 - Lodi, Andrea A1 - Schmidt, Daniel T1 - Single-commodity robust network design with finite and Hose demand sets JF - Mathematical Programming N2 - We study a single-commodity robust network design problem (sRND) defined on an undirected graph. Our goal is to determine minimum cost capacities such that any traffic demand from a given uncertainty set can be satisfied by a feasible single-commodity flow. We consider two ways of representing the uncertainty set, either as a finite list of scenarios or as a polytope. We propose a branch-and-cut algorithm to derive optimal solutions to sRND, built on a capacity-based integer linear programming formulation. It is strengthened with valid inequalities derived as {0, 1/2}-Chvátal–Gomory cuts. Since the formulation contains exponentially many constraints, we provide practical separation algorithms. Extensive computational experiments show that our approach is effective, in comparison to existing approaches from the literature as well as to solving a flow based formulation by a general purpose solver. KW - Robust network design KW - Branch-and-cut KW - Cut-set inequalities KW - Polyhedral demand uncertainty KW - Separation under uncertainty Y1 - 2016 U6 - https://doi.org/10.1007/s10107-016-0991-9 VL - 157 IS - 1 SP - 297 EP - 342 ER - TY - JOUR A1 - Gottschalk, Corinna A1 - Koster, Arie M.C.A. A1 - Liers, Frauke A1 - Peis, Britta A1 - Schmand, Daniel A1 - Wierz, Andreas T1 - Robust Flows over Time: Models and Complexity Results N2 - We study dynamic network flows with uncertain input data under a robust optimization perspective. In the dynamic maximum flow problem, the goal is to maximize the flow reaching the sink within a given time horizon T, while flow requires a certain travel time to traverse an arc. In our setting, we account for uncertain travel times of flow. We investigate maximum flows over time under the assumption that at most Γ travel times may be prolonged simultaneously due to delay. We develop and study a mathematical model for this problem. As the dynamic robust flow problem generalizes the static version, it is NP-hard to compute an optimal flow. However, our dynamic version is considerably more complex than the static version. We show that it is NP-hard to verify feasibility of a given candidate solution. Furthermore, we investigate temporally repeated flows and show that in contrast to the non-robust case (i.e., without uncertainties) they no longer provide optimal solutions for the robust problem, but rather yield a worst case optimality gap of at least T. We finally show that for infinite delays, the optimality gap is at most O(k log T), where k is a newly introduced instance characteristic. The results obtained in this paper yield a first step towards understanding robust dynamic flow problems with uncertain travel times. KW - Dynamic Network Flows KW - Uncertain Travel Times KW - Dynamic Robust Flow Y1 - 2017 U6 - https://doi.org/10.1007/s10107-017-1170-3 ER - TY - JOUR A1 - Schweiger, Jonas A1 - Liers, Frauke T1 - A Decomposition Approach for Optimum Gas Network Extension with a Finite Set of Demand Scenarios N2 - Today's gas markets demand more flexibility from the network operators which in turn have to invest into their network infrastructure. As these investments are very cost-intensive and long-living, network extensions should not only focus on a single bottleneck scenario, but should increase the flexibility to fulfill different demand scenarios. In this work, we formulate a model for the network extension problem for multiple demand scenarios and propose a scenario decomposition in order to solve the arising challenging optimization tasks. In fact, euch subproblem consists of a mixed-integer nonlinear optimization problem (MINLP). Valid bounds are derived even without solving the subproblems to optimality. Furthermore, we develop heuristics that prove capable of improving the initial solutions substantially. Results of computational experiments on realistic network topologies are presented. It turns out that our method is able to solve these challenging instances to optimality within a reasonable amount of time. Y1 - 2016 ER - TY - INPR A1 - Gutina, Daria A1 - Bärmann, Andreas A1 - Roeder, Georg A1 - Schellenberger, Martin A1 - Liers, Frauke T1 - Optimisation over Decision Trees – A Case Study for the Design of Stable Direct-Current Electricity Networks N2 - 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. KW - decision trees KW - random forests KW - mixed-integer programming KW - power networks Y1 - 2022 ER - TY - INPR A1 - Aigner, Kevin-Martin A1 - Bärmann, Andreas A1 - Braun, Kristin A1 - Liers, Frauke A1 - Pokutta, Sebastian A1 - Schneider, Oskar A1 - Sharma, Kartikey A1 - Tschuppik, Sebastian T1 - Data-driven Distributionally Robust Optimization over Time N2 - 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. KW - distributionally robust optimization KW - learning over time KW - gradient descent Y1 - 2023 ER - TY - JOUR A1 - Kreimeier, Timo A1 - Kuchlbauer, Martina A1 - Liers, Frauke A1 - Stingl, Michael A1 - Walther, Andrea T1 - Towards the Solution of Robust Gas Network Optimization Problems Using the Constrained Active Signature Method N2 - This work studies robust gas network optimization under uncertainties in demand and in the physical parameters. The corresponding optimization problems are nonconvex in node pressures and flows along the pipes. They are thus very difficult to solve for realistic instance sizes. In recent approaches, an adaptive bundle method has been developed, where one solves the occurring adversarial problems via iteratively refined piecewise linear relaxations. These subproblems need to be solved always from scratch using mixed-integer linear programming (MIP). As alternative to the MIP solver, we employ here a nonsmooth optimization approach that allows a warm start strategy such that it can profit from the results obtained for coarser relaxations. We evaluate the approach for realistic gas network topologies and outline possibilities for future research. Y1 - 2022 ER - TY - INPR A1 - Aigner, Kevin-Martin A1 - Schaumann, Peter A1 - von Loeper, Freimut A1 - Martin, Alexander A1 - Schmidt, Volker A1 - Liers, Frauke T1 - Robust DC Optimal Power Flow with Modeling of Solar Power Supply Uncertainty via R-Vine Copulas N2 - 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. KW - chance constrained programming KW - optimal power flow KW - robust optimization KW - conditional uncertainty set KW - R-vine copula Y1 - ER - TY - INPR A1 - Bernhard, Daniela A1 - Liers, Frauke A1 - Stingl, Michael A1 - Uihlein, Andrian T1 - A Gradient-Based Method for Joint Chance-Constrained Optimization with Continuous Distributions N2 - The input parameters of an optimization problem are often affected by uncertainties. Chance constraints are a common way to model stochastic uncertainties in the constraints. Typically, algorithms for solving chance-constrained problems require convex functions or discrete probability distributions. In this work, we go one step further and allow non-convexities as well as continuous distributions. We propose a gradient-based approach to approximately solve joint chance-constrained models. We approximate the original problem by smoothing indicator functions. Then, the smoothed chance constraints are relaxed by penalizing their violation in the objective function. The approximation problem is solved with the Continuous Stochastic Gradient method that is an enhanced version of the stochastic gradient descent and has recently been introduced in the literature. We present a convergence theory for the smoothing and penalty approximations. Under very mild assumptions, our approach is applicable to a wide range of chance-constrained optimization problems. As an example, we illustrate its computational efficiency on difficult practical problems arising in the operation of gas networks. The numerical experiments demonstrate that the approach quickly finds nearly feasible solutions for joint chance-constrained problems with non-convex constraint functions and continuous distributions, even for realistically-sized instances. Y1 - ER - TY - INPR A1 - Bernhard, Daniela A1 - Liers, Frauke A1 - Stingl, Michael T1 - Robust chance-constrained optimization with discrete distributions N2 - Typically, probability distributions that generate uncertain parameters cannot be measured exactly in practice. As a remedy, distributional robustness determines optimized decisions that are protected in a robust fashion against all probability distributions in some appropriately chosen ambiguity set. In this work, we consider robust joint chance-constrained optimization problems and focus on discrete probability distributions. Many methods for this kind of problems study convex or even linear constraint functions. In contrast, we introduce a practically efficient scenario-based bundle method without convexity assumptions on the constraint functions. We start by deriving an approximation problem to the original robust chance-constrained version by using smoothing and penalization techniques that build on our former work on chance-constrained optimization. Our convergence results with respect to the smoothing approximation and well-known results for penalty approximations suggest replacing the original problem with the approximation problem for large smoothing and penalty parameters. Our scenario-based bundle method starts by solving the approximation problem with a bundle method, and then uses the bundle solution to decide which scenarios to include in a scenario-expanded formulation. This formulation is a standard nonlinear optimization problem. Our approach is guaranteed to find feasible solutions. Furthermore, in the numerical experiments on real-world gas transport problems with uncertain demands, we mostly find globally optimal solutions. Comparing these results to the classical robust reformulations for ambiguity sets consisting of confidence intervals and Wasserstein balls, we observe that the scenario-based bundle method typically outperforms solving the classical reformulation directly. Y1 - 2024 ER - TY - INPR A1 - Aigner, Kevin-Martin A1 - Goerigk, Marc A1 - Hartisch, Michael A1 - Liers, Frauke A1 - Miehlich, Arthur A1 - Rösel, Florian T1 - Feature Selection for Data-Driven Explainable Optimization N2 - Mathematical optimization, although often leading to NP-hard models, is now capable of solving even large-scale instances within reasonable time. However, the primary focus is often placed solely on optimality. This implies that while obtained solutions are globally optimal, they are frequently not comprehensible to humans, in particular when obtained by black-box routines. In contrast, explainability is a standard requirement for results in Artificial Intelligence, but it is rarely considered in optimization yet. There are only a few studies that aim to find solutions that are both of high quality and explainable. In recent work, explainability for optimization was defined in a data-driven manner: a solution is considered explainable if it closely resembles solutions that have been used in the past under similar circumstances. To this end, it is crucial to identify a preferably small subset of features from a presumably large set that can be used to explain a solution. In mathematical optimization, feature selection has received little attention yet. In this work, we formally define the feature selection problem for explainable optimization and prove that its decision version is NP-complete. We introduce mathematical models for optimized feature selection. As their global solution requires significant computation time with modern mixed-integer linear solvers, we employ local heuristics. Our computational study using data that reflect real-world scenarios demonstrates that the problem can be solved practically efficiently for instances of reasonable size. KW - Feature selection KW - Explainable optimization KW - Data-driven optimization Y1 - 2025 ER - TY - INPR A1 - Bernhard, Daniela A1 - Stingl, Michael A1 - Liers, Frauke T1 - Algorithms for robust chance-constrained optimization with mixture ambiguity N2 - Constructing ambiguity sets in distributionally robust optimization is difficult and currently receives increased attention. In this paper, we focus on mixture models with finitely many reference distributions. We present two different solution concepts for robust joint chance-constrained optimization problems with these ambiguity sets and non-convex constraint functions. Both concepts rely on solving an approximation problem that is based on well-known smoothing and penalization techniques. On the one side, we consider a classical bundle method together with an approach for finding good starting points. On the other side, we integrate the Continuous Stochastic Gradient method, a variant of the stochastic gradient descent that is able to exploit regularity in the data. On the example of gas networks we compare the two algorithmic concepts for different topologies and two types of mixture ambiguity sets with Gaussian reference distributions and polyhedral and ϕ-divergence based feasible sets for the mixing coefficients. The results show that both solution approaches are well-suited to solve this difficult problem class. Based on the numerical results we provide some general advices for choosing the more efficient algorithm depending on the main challenges of the considered optimization problem. We give an outlook for the applicability of the method in a wider context. Y1 - ER - TY - INPR A1 - Bernhard, Daniela A1 - Liers, Frauke A1 - Stingl, Michael T1 - Branch-and-cut for mixed-integer robust chance-constrained optimization with discrete distributions N2 - We study robust chance-constrained problems with mixed-integer design variables and ambiguity sets consisting of discrete probability distributions. Allowing general non-convex constraint functions, we develop a branch-and-cut framework using scenario-based cutting planes to generate lower bounds. The cutting planes are obtained by exploiting the classical big-M reformulation of the chance-constrained problem in the case of discrete distributions. Furthermore, we include the calculation of initial feasible solutions based on a bundle method applied to an approximation of the original problem into the branch-and-cut procedure. We conclude with a detailed discussion about the practical performance of the branch-and-cut framework with and without initial feasible solutions. In our experiments we focus on gas transport problems under uncertainty and provide a comparison of our method with solving the classical reformulation directly for various real-world sized instances. Y1 - ER - TY - JOUR A1 - Bernhard, Daniela A1 - Heitsch, Holger A1 - Henrion, René A1 - Liers, Frauke A1 - Stingl, Michael A1 - Uihlein, Andrian A1 - Zipf, Viktor T1 - Continuous stochastic gradient and spherical radial decomposition N2 - In this paper, a new method is presented for solving chance-constrained optimization problems. The method combines the well-established Spherical-Radial Decomposition approach with the Continuous Stochastic Gradient method. While the Continuous Stochastic Gradient method has been successfully applied to chance-constrained problems in the past, only the combination with the Spherical-Radial Decomposition allows to avoid smoothing of the integrand. In this chapter, we prove this fact for a relevant class of chance-constrained problems and apply the resulting method to the capacity maximization problem for gas networks. KW - chance constraints KW - continuous stochastic gradient KW - spheric-radial decomposition Y1 - ER - TY - INPR A1 - Denzler, Sebastian A1 - Aigner, Kevin-Martin A1 - Lüer, Larry A1 - Brabec, Christoph A1 - Liers, Frauke T1 - Robust Bayesian Optimization with an Application to Material Science N2 - We propose a novel online learning framework for robust Bayesian optimization of uncertain black-box functions. While Bayesian optimization is well-suited for data-efficient optimization of expensive objectives, its standard form can be sensitive to hidden or varying parameters. To address this issue, we consider a min–max robust counterpart of the optimization problem and develop a practically efficient solution algorithm, BROVER (Bayesian Robust Optimization via Exploration with Regret minimization). Our method combines Gaussian process regression with a decomposition approach: the minimax structure is split into a non-convex online learner based on the Follow-the-Perturbed-Leader algorithm together with a subsequent minimization step in the decision variables. We prove that the theoretical regret bound converges under mild assumptions, ensuring asymptotic convergence to robust solutions. Numerical experiments on synthetic data validate the regret guarantees and demonstrate fast convergence to the robust optimum. Furthermore, we apply our method to the robust optimization of organic solar cell performance, where hidden process parameters and experimental variability naturally induce uncertainty. Our results on real-world datae show that BROVER identifies solutions with strong robustness properties within relatively few iterations, thereby offering a modern and practical approach for data-driven black-box optimization under uncertainty. KW - robust optimization KW - Bayesian optimization KW - online learning KW - solar cell performance Y1 - 2025 ER - TY - JOUR A1 - Aigner, Kevin-Martin A1 - Denzler, Sebastian A1 - Liers, Frauke A1 - Pokutta, Sebastian A1 - Sharma, Kartikey T1 - Scenario Reduction for Distributionally Robust Optimization N2 - Stochastic and (distributionally) robust optimization problems often become computationally challenging as the number of scenarios increases. Scenario reduction is therefore a key technique for improving tractability. We introduce a general scenario reduction method for distributionally robust optimization (DRO), which includes stochastic and robust optimization as special cases. Our approach constructs the reduced DRO problem by projecting the original ambiguity set onto a reduced set of scenarios. Under mild conditions, we establish bounds on the relative quality of the reduction. The methodology is applicable to random variables following either discrete or continuous probability distributions, with representative scenarios appropriately selected in both cases. Given the relevance of optimization problems with linear and quadratic objectives, we further refine our approach for these settings. Finally, we demonstrate its effectiveness through numerical experiments on mixed-integer benchmark instances from MIPLIB and portfolio optimization problems. Our results show that the oroposed approximation significantly reduces solution time while maintaining high solution quality with only minor errors. KW - distributionally robust optimization KW - scenario reduction KW - scenario clustering KW - approximation bounds KW - mixed-integer programming Y1 - 2025 ER -