TY - INPR A1 - Grübel, Julia A1 - Huber, Olivier A1 - Hümbs, Lukas A1 - Klimm, Max A1 - Schmidt, Martin A1 - Schwartz, Alexandra T1 - Nonconvex Equilibrium Models for Energy Markets: Exploiting Price Information to Determine the Existence of an Equilibrium N2 - 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. KW - Energy markets KW - Nonconvex games KW - Existence KW - Equilibrium computation KW - Perfect competition Y1 - 2021 ER - TY - JOUR A1 - Groß, Martin A1 - Marc E., Pfetsch A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Skutella, Martin T1 - Algorithmic Results for Potential-Based Flows: Easy and Hard Cases N2 - Potential-based flows are an extension of classical network flows in which the flow on an arc is determined by the difference of the potentials of its incident nodes. Such flows are unique and arise, for example, in energy networks. Two important algorithmic problems are to determine whether there exists a feasible flow and to maximize the flow between two designated nodes. We show that these problems can be solved for the single source and sink case by reducing the network to a single arc. However, if we additionally consider switches that allow to force the flow to 0 and decouple the potentials, these problems are NP-hard. Nevertheless, for particular series-parallel networks, one can use algorithms for the subset sum problem. Moreover, applying network presolving based on generalized series-parallel structures allows to significantly reduce the size of realistic energy networks. KW - Potential networks KW - Potential-based flows KW - Maximum flow problem KW - Series-parallel graphs KW - Network reduction Y1 - 2017 U6 - https://doi.org/10.1002/net.21865 VL - 73 IS - 3 SP - 303 EP - 324 ET - Networks ER - TY - JOUR A1 - Abed, Fidaa A1 - Chen, Lin A1 - Disser, Yann A1 - Groß, Martin A1 - Megow, Nicole A1 - Meißner, Julie A1 - Richter, Alexander T. A1 - Rischke, Roman T1 - Scheduling Maintenance Jobs in Networks N2 - 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. Y1 - 2017 ER - TY - INPR A1 - Groß, Martin A1 - Gupta, Anupam A1 - Kumar, Amit A1 - Matuschke, Jannik A1 - Schmidt, Daniel R. A1 - Schmidt, Melanie A1 - Verschae, José T1 - A Local-Search Algorithm for Steiner Forest N2 - In the Steiner Forest problem, we are given a graph and a collection of source-sink pairs, and the goal is to find a subgraph of minimum total length such that all pairs are connected. The problem is APX-Hard and can be 2 -approximated by, e.g., the elegant primal-dual algorithm of Agrawal, Klein, and Ravi from 1995. We give a local-search-based constant-factor approximati on for the problem. Local search brings in new techniques to an area that has for long not seen any improv ements and might be a step towards a combinatorial algorithm for the more general survivable n etwork design problem. Moreover, local search was an essential tool to tackle the dynamic MST/Stein er Tree problem, whereas dynamic Steiner Forest is still wide open. It is easy to see that any constant factor local search algori thm requires steps that add/drop many edges together. We propose natural local moves which, at each step , either (a) add a shortest path in the current graph and then drop a bunch of inessential edges, or (b) add a s et of edges to the current solution. This second type of moves is motivated by the potential function w e use to measure progress, combining the cost of the solution with a penalty for each connected compon ent. Our carefully-chosen local moves and potential function work in tandem to eliminate bad local min ima that arise when using more traditional local moves. Our analysis first considers the case where the local optimum is a single tree, and shows optimality w.r.t. moves that add a single edge (and drop a set of edges) is enough to bound the locality gap. For the general case, we show how to “project” the optimal solution o nto the different trees of the local optimum without incurring too much cost (and this argument uses opti mality w.r.t. both kinds of moves), followed by a tree-by-tree argument. We hope both the potential funct ion, and our analysis techniques will be useful to develop and analyze local-search algorithms in ot her contexts. Y1 - 2017 ER - TY - JOUR A1 - Bernstein, Aaron A1 - Disser, Yann A1 - Groß, Martin T1 - General Bounds for Incremental Maximization N2 - We propose a theoretical framework to capture incremental s olutions to cardinality con- strained maximization problems. The defining characterist ic of our framework is that the cardinality/support of the solution is bounded by a value k ∈ N that grows over time, and we allow the solution to be extended one element at a time. We i nvestigate the best-possible competitive ratio of such an incremental solution, i.e., th e worst ratio over all k between the incremental solution after k steps and an optimum solution of cardinality k . We define a large class of problems that contains many important cardin ality constrained maximization problems like maximum matching, knapsack, and packing/cov ering problems. We provide a general 2 . 618-competitive incremental algorithm for this class of pr oblems, and show that no algorithm can have competitive ratio below 2 . 18 in general. In the second part of the paper, we focus on the inherently inc remental greedy algorithm that increases the objective value as much as possible in eac h step. This algorithm is known to be 1 . 58-competitive for submodular objective functions, but it has unbounded competitive ratio for the class of incremental problems mentioned above . We define a relaxed submod- ularity condition for the objective function, capturing pr oblems like maximum (weighted) ( b -)matching and a variant of the maximum flow problem. We show t hat the greedy algo- rithm has competitive ratio (exactly) 2 . 313 for the class of problems that satisfy this relaxed submodularity condition. Note that our upper bounds on the competitive ratios transla te to approximation ratios for the underlying cardinality constrained problems. Y1 - 2017 ER - TY - JOUR A1 - Groß, Martin A1 - Pfetsch, Marc E. A1 - Skutella, Martin T1 - On the Complexity of Instationary Gas Flows N2 - We study a simplistic model of instationary gas flows consisting of a sequence of k stationary gas flows. We present efficiently solvable cases and NP-hardness results, establishing complexity gaps between stationary and instationary gas flows (already for k=2) as well as between instationary gas s-t-flows and instationary gas b-flows. Y1 - 2017 U6 - https://doi.org/10.1016/j.orl.2018.01.007 VL - 46 IS - 3 SP - 286 EP - 290 ET - Operations Research Letters ER - TY - JOUR A1 - Schmidt, Martin A1 - Aßmann, Denis A1 - Burlacu, Robert A1 - Humpola, Jesco A1 - Joormann, Imke A1 - Kanelakis, Nikolaos A1 - Koch, Thorsten A1 - Oucherif, Djamal A1 - Pfetsch, Marc E. A1 - Schewe, Lars A1 - Schwarz, Robert A1 - Sirvent, Mathias T1 - GasLib – A Library of Gas Network Instances JF - Data N2 - The development of mathematical simulation and optimization models and algorithms for solving gas transport problems is an active field of research. In order to test and compare these models and algorithms, gas network instances together with demand data are needed. The goal of GasLib is to provide a set of publicly available gas network instances that can be used by researchers in the field of gas transport. The advantages are that researchers save time by using these instances and that different models and algorithms can be compared on the same specified test sets. The library instances are encoded in an XML format. In this paper, we explain this format and present the instances that are available in the library. KW - Gas Transport KW - Networks KW - Problem Instances KW - Mixed-Integer Nonlinear Optimization KW - GasLib Y1 - 2017 U6 - https://doi.org/10.3390/data2040040 VL - 4 IS - 2 ER - TY - RPRT A1 - Arulselvan, Ashwin A1 - Cseh, Ágnes A1 - Groß, Martin A1 - Manlove, David F. A1 - Matuschke, Jannik T1 - Matchings with lower quotas: Algorithms and complexity N2 - We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph G = (A∪P,E) with weights on the edges in E, and with lower and upper quotas on the vertices in P. We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in P are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (wmlq), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of wmlq from the viewpoints of classical polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between NP-hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota u_max as basis, and we prove that this dependence is necessary unless FPT = W[1]. The approximability of wmlq is also discussed: we present an approximation algorithm for the general case with performance guarantee umax + 1, which is asymptotically best possible unless P = NP. Finally, we elaborate on how most of our positive results carry over to matchings in arbitrary graphs with lower quotas. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-662-48971-0_16 ER - TY - JOUR A1 - Domschke, Pia A1 - Groß, Martin A1 - Hiller, Benjamin A1 - Hante, Falk A1 - Schewe, Lars A1 - Schmidt, Martin T1 - Mathematische Modellierung, Simulation und Optimierung von Gastransportnetzwerken JF - gwf-gas/erdgas Y1 - 2015 VL - 11 SP - 880 EP - 885 ER - TY - INPR A1 - Klimm, Max A1 - Pfetsch, Marc A1 - Raber, Rico A1 - Skutella, Martin T1 - Approximation of Binary Second Order Cone Programs of Packing Type N2 - This paper considers binary second order cone programs of packing type where a linear objective is optimized under m second order cone packing constraints and all decision variables are binary. We show that when m is part of the input, these problems cannot be approximated within a factor of 1/(m + 1)^(1−ε) for any ε > 0, unless P = NP. We then propose approximation algorithms based on different algorithmic principles that almost match this approximation factor: a pipage rounding technique that solves fractional relaxations of the problems and modifies the solutions so that few fractional variables remain, a greedy approach, and a randomized rounding technique. While all algorithms have similar theoretical approximation guarantees in the order of 1/m, we also test the algorithms on realistic instances that arise in the context of gas transportation networks. This empirical study reveals in particular that taking the best of the proposed algorithms produces highly competitive solutions that yield on average 96 % of the value of an optimal solution. Y1 - 2021 ER - TY - JOUR A1 - Klimm, Max A1 - Warode, Philipp T1 - Parametric computation of minimum cost flows with piecewise quadratic costs JF - Mathematics of Operations Research N2 - We develop algorithms solving parametric flow problems with separable, continuous, piecewise quadratic, and strictly convex cost functions. The parameter to be considered is a common multiplier on the demand of all nodes. Our algorithms compute a family of flows that are each feasible for the respective demand and minimize the costs among the feasible flows for that demand. For single commodity networks with homogenous cost functions, our algorithm requires one matrix multiplication for the initialization, a rank 1 update for each nondegenerate step and the solution of a convex quadratic program for each degenerate step. For nonhomogeneous cost functions, the initialization requires the solution of a convex quadratic program instead. For multi-commodity networks, both the initialization and every step of the algorithm require the solution of a convex program. As each step is mirrored by a breakpoint in the output this yields output-polynomial algorithms in every case. Y1 - 2021 U6 - https://doi.org/10.1287/moor.2021.1151 ER - TY - INPR A1 - Klimm, Max A1 - Pfetsch, Marc A1 - Raber, Rico A1 - Skutella, Martin T1 - Reduction of Potential-Based Flow Networks N2 - We consider potential-based flow networks with terminal nodes at which flow can enter or leave the network and physical properties such as voltages or pressures are measured and controlled. We study conditions under which such a network can be reduced to a smaller, equivalent network with the same behavior at the terminal nodes. Potential-based flow networks are widely used to model infrastructure networks such as electricity, gas, or water networks. In contrast to Kron's reduction for electrical networks, we prove that, in general, potential-based flow networks with at least three terminals cannot be reduced to smaller networks whose size only depends on the number of terminals. On the other hand, we show that it is possible to represent a special class of potential-based flow networks by a complete graph on the terminals, and we establish a characterization of networks that can be reduced to a path network. Our results build on fundamental properties of effective resistances proved in this paper, including explicit formulae for their dependence on edge resistances of the network and their metric properties. Y1 - 2021 ER - TY - INPR A1 - Schmidt, Martin A1 - Hiller, Benjamin A1 - Koch, Thorsten A1 - Pfetsch, Marc A1 - Geißler, Björn A1 - Henrion, René A1 - Joormann, Imke A1 - Martin, Alexander A1 - Morsi, Antonio A1 - Römisch, Werner A1 - Schewe, Lars A1 - Schultz, Rüdiger A1 - Steinbach, Marc C. T1 - Capacity Evaluation for Large-Scale Gas Networks N2 - Natural gas is important for the energy turnaround in many countries like in Germany, where it serves as a "bridging energy" towards a fossil-free energy supply in the future. About 20% of the total German energy demand is provided by natural gas, which is transported through a complex pipeline network with a total length of about 30000 km and the efficient use of the given transport infrastructure for natural gas is of political, economic, and societal importance. As a consequence of the liberalization of the European gas market in the last decades, gas trading and transport have been decoupled. This has led to new challenges for gas transport companies, and mathematical optimization is perfectly suited for tackling many of these challenges. However, the underlying mathematical problems are by far too hard to be solved by today's general-purpose software so that novel mathematical theory and algorithms are needed. The industrial research project "ForNe: Research Cooperation Network Optimization" has been initiated and funded by Open Grid Europe in 2009 and brought together experts in mathematical optimization from seven German universities and research institutes, which cover almost the entire range of mathematical optimization: integer and nonlinear optimization as well as optimization under uncertainty. The mathematical research results have been put together in a software package that has been delivered to Open Grid Europe at the end of the project. Moreover, the research is still continuing - e.g., in the Collaborative Research Center/Transregio 154 "Mathematical Modelling, Simulation and Optimization using the Example of Gas Networks" funded by the German Research Foundation. Y1 - 2019 ER - TY - INPR A1 - Klimm, Max A1 - Pfetsch, Marc E. A1 - Raber, Rico A1 - Skutella, Martin T1 - Packing under Convex Quadratic Constraints N2 - We consider a general class of binary packing problems with a convex quadratic knapsack constraint. We prove that these problems are APX-hard to approximate and present constant-factor approximation algorithms based upon three different algorithmic techniques: (1) a rounding technique tailored to a convex relaxation in conjunction with a non-convex relaxation whose approximation ratio equals the golden ratio; (2) a greedy strategy; (3) a randomized rounding method leading to an approximation algorithm for the more general case with multiple convex quadratic constraints. We further show that a combination of the first two strategies can be used to yield a monotone algorithm leading to a strategyproof mechanism for a game-theoretic variant of the problem. Finally, we present a computational study of the empirical approximation of the three algorithms for problem instances arising in the context of real-world gas transport networks. Y1 - 2019 ER - TY - INPR A1 - Klimm, Max A1 - Pfetsch, Marc A1 - Raber, Rico A1 - Skutella, Martin T1 - On the Robustness of Potential-Based Flow Networks N2 - Potential-based flows provide a simple yet realistic mathematical model of transport in many real-world infrastructure networks such as, e.g., electricity, gas, or water networks, where the flow along each edge is controlled via the (difference of) potentials at its end nodes. A potential-based flow network is robust if the maximal difference of node potentials needed to satisfy a set of demands cannot increase if demands are decreased. This notion of robustness is motivated by infrastructure networks where users first make reservations for certain demands that may be larger than the actual amounts sent later on. Here node potentials correspond to physical quantities such as the pressures or the voltages and must be guaranteed to lie within a fixed range, even if the actual amounts are smaller than the previously reserved demands. Our main results are a precise characterization of such robust networks for the case of point-to-point demands via forbidden node-labeled graph minors, as well as an efficient algorithm for testing robustness. Y1 - 2019 ER - TY - JOUR A1 - Burlacu, Robert A1 - Egger, Herbert A1 - Groß, Martin A1 - Martin, Alexander A1 - Pfetsch, Marc A1 - Schewe, Lars A1 - Sirvent, Mathias A1 - Skutella, Martin T1 - Maximizing the storage capacity of gas networks: a global MINLP approach N2 - In this paper, we study the transient optimization of gas networks, focusing in particular on maximizing the storage capacity of the network. We include nonlinear gas physics and active elements such as valves and compressors, which due to their switching lead to discrete decisions. The former is described by a model derived from the Euler equations that is given by a coupled system of nonlinear parabolic partial differential equations (PDEs). We tackle the resulting mathematical optimization problem by a first-discretize-then-optimize approach. To this end, we introduce a new discretization of the underlying system of parabolic PDEs and prove well-posedness for the resulting nonlinear discretized system. Endowed with this discretization, we model the problem of maximizing the storage capacity as a non-convex mixed-integer nonlinear problem (MINLP). For the numerical solution of the MINLP, we algorithmically extend a well-known relaxation approach that has already been used very successfully in the field of stationary gas network optimization. This method allows us to solve the problem to global optimality by iteratively solving a series of mixed-integer problems (MIPs). Finally, we present two case studies that illustrate the applicability of our approach. KW - Mixed-Integer Nonlinear Programming KW - Transient Gas Transport Optimization KW - Storage Capacity Maximization KW - Power-to-Gas KW - First-Discretize-Then-Optimize Y1 - 2019 U6 - https://doi.org/10.1007/s11081-018-9414-5 VL - 20 SP - 543 EP - 573 ET - Optimization and Engineering ER -