TY - JOUR A1 - Le, Thi Thai A1 - Koch, Thorsten T1 - Effect of inertia force on the interface stability of a tangential-velocity discontinuity in porous media JF - International Journal of Multiphase Flow N2 - The present study investigates the stability of a tangential-velocity discontinuity in porous media during the withdrawing and injecting processes of natural gases from and into an underground gas storage. The focus is placed on analyzing the impact of inertia forces on the interface stability using the Forchheimer equations. Other publications have relied primarily on Darcy's law to describe flow stability in porous media. However, Darcy's law only adequately describes flows in which viscous forces dominate over inertia forces. As the flow rate increases, the significance of inertia forces becomes more pronounced, and Darcy's law becomes insufficient for considering such flows. Our findings indicate that even a slight consideration of the inertia effect leads to permanent destabilization of the discontinuity interface, regardless of the fluid viscosity or the Mach number. In contrast, when the inertia effect is neglected, the interface is stabilized across the entire Mach number range if the fluid viscosity is strong enough. Y1 - 2023 U6 - https://doi.org/10.1016/j.ijmultiphaseflow.2023.104612 VL - 169 ER - TY - THES A1 - Hoppmann-Baum, Kai T1 - Mathematical programming for stable control and safe operation of gas transport networks N2 - The fight against climate change makes extreme but inevitable changes in the energy sector necessary. These in turn lead to novel and complex challenges for the transmission system operators (TSOs) of gas transport networks. In this thesis, we consider four different planning problems emerging from real-world operations and present mathematical programming models and solution approaches for all of them. Due to regulatory requirements and side effects of renewable energy production, controlling today's gas networks with their involved topologies is becoming increasingly difficult. Based on the network station modeling concept for approximating the technical capabilities of complex subnetworks, e.g., compressor stations, we introduce a tri-level MIP model to determine important global control decisions. Its goal is to avoid changes in the network elements' settings while deviations from future inflow pressures as well as supplies and demands are minimized. A sequential linear programming inspired post-processing routine is run to derive physically accurate solutions w.r.t. the transient gas flow in pipelines. Computational experiments based on real-world data show that meaningful solutions are quickly and reliably determined. Therefore, the algorithmic approach is used within KOMPASS, a decision support system for the transient network control that we developed together with the Open Grid Europe GmbH (OGE), one of Europe's largest natural gas TSOs. Anticipating future use cases, we adapt the aforementioned algorithmic approach for hydrogen transport. We investigate whether the natural gas infrastructure can be repurposed and how the network control changes when energy-equivalent amounts of hydrogen are transported. Besides proving the need for purpose-built compressors, we observe that, due to the reduced linepack, the network control becomes more dynamic, compression energy increases by 440% on average, and stricter regulatory rules regarding the balancing of supply and demand become necessary. Extreme load flows expose the technical limits of gas networks and are therefore of great importance to the TSOs. In this context, we introduce the Maximum Transportation Problem and the Maximum Potential Transport Moment Problem to determine severe transport scenarios. Both can be modeled as linear bilevel programs where the leader selects supplies and demands, maximizing the follower's transport effort. To solve them, we identify solution-equivalent instances with acyclic networks, provide variable bounds regarding their KKT reformulations, apply the big-M technique, and solve the resulting MIPs. A case study shows that the obtained scenarios exceed the maximum severity values of a provided test set by at least 23%. OGE's transmission system is 11,540km long. Monitoring it is crucial for safe operations. To this end, we discuss the idea of using uncrewed aerial vehicles and introduce the Length-Constrained Cycle Partition Problem to optimize their routing. Its goal is to find a smallest cycle partition satisfying vertex-induced length requirements. Besides a greedy-style heuristic, we propose two MIP models. Combining them with symmetry-breaking constraints as well as valid inequalities and lower bounds from conflict hypergraphs yields a highly performant solution algorithm for this class of problems. Y1 - 2022 UR - https://doi.org/10.14279/depositonce-15837 U6 - https://doi.org/10.14279/depositonce-15837 PB - TU Berlin ER - TY - GEN A1 - Pedersen, Jaap A1 - Weinand, Jann Michael A1 - Syranidou, Chloi A1 - Rehfeldt, Daniel T1 - An efficient solver for multi-objective onshore wind farm siting and network integration N2 - Existing planning approaches for onshore wind farm siting and network integration often do not meet minimum cost solutions or social and environmental considerations. In this paper, we develop an approach for the multi-objective optimization of turbine locations and their network connection using a Quota Steiner tree problem. Applying a novel transformation on a known directed cut formulation, reduction techniques, and heuristics, we design an exact solver that makes large problem instances solvable and outperforms generic MIP solvers. Although our case studies in selected regions of Germany show large trade-offs between the objective criteria of cost and landscape impact, small burdens on one criterion can significantly improve the other criteria. In addition, we demonstrate that contrary to many approaches for exclusive turbine siting, network integration must be simultaneously optimized in order to avoid excessive costs or landscape impacts in the course of a wind farm project. Our novel problem formulation and the developed solver can assist planners in decision making and help optimize wind farms in large regions in the future. T3 - ZIB-Report - 23-10 Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-90590 SN - 1438-0064 ER - TY - THES A1 - Hennings, Felix T1 - Modeling and solving real-world transient gas network transport problems using mathematical programming N2 - This thesis considers the transient gas network control optimization problem for on-shore pipeline-based transmission networks with numerous gas routing options. As input, the problem is given the network's topology, its initial state, and future demands at the boundaries of the network, which prescribe the gas flow exchange and potentially the pressure values. The task is to find a set of future control measures for all the active, i.e., controllable, elements in the network that minimizes a combination of different penalty functions. The problem is examined in the context of a decision support tool for gas network dispatchers. This results in detailed models featuring a diverse set of constraints, large and challenging real-world instances, and demanding time limit requirements. All these factors further complicate the problem, which is already difficult to solve in theory due to the inherent combination of non-linear and combinatorial aspects. Our contributions concern different steps of the process of solving the problem. Regarding the model formulation, we investigate the validity of two common approximations of the gas flow description in transport pipes: neglecting the inertia term and assuming a friction term that linearly depends on the gas flow and the pressure. For both, we examine if they can be applied under real-world conditions by evaluating a large amount of historical state data of the network of our project partner, the gas network operator Open Grid Europe. While we can confirm that it is reasonable to ignore the influence of the inertia term, the friction term linearization leads to significant errors and, as a consequence, cannot be used for describing the general gas flow behavior in transport pipes. As another topic of this thesis, we introduce the target value concept as a more realistic approach to express control actions of dispatchers regarding regulators and compressor stations. Here, we derive the mechanisms defined for target values based on the gas flow principles in pipes and develop a mixed-integer programming model capturing their behavior. The accuracy of this model is demonstrated in comparison to a target-value-based industry-standard simulator. Furthermore, we present two heuristics for the transient gas network control optimization problem featuring target values that are based on approximative models for the target-value-based control and determine the final decisions in a post-processing step. To compare the performance of the two heuristics with the approach of directly solving the corresponding model, we evaluate them on a set of artificially created test instances. Finally, we develop problem-specific algorithms for two variants of the described problem. One considers the control optimization for a single network station, which represents a local operation site featuring a large number of active elements. The used transient model is very detailed and includes a sophisticated representation of the compressor stations. Based on the shortness of the pipes in the station, the corresponding algorithm finds valid solutions by solving a series of stationary model variants as well as a transient rolling horizon approach. As the second variant, we consider the problem on the entire network but assume an approximative model representing the control capabilities of network stations. Aside from a new description of the compression capabilities, we introduce an algorithm that uses a combination of sequential mixed-integer programming, two heuristics based on reduced time horizons, and a specialized dynamic branch-and-bound node limit to determine promising values for the binary variables of the model. Complete solutions for the problem are obtained by fixing the binary values and solving the remaining non-linear program. Both algorithms are investigated in extensive empirical studies based on real-world instances of the corresponding model variants. N2 - Diese Arbeit behandelt das Optimierungsproblem der transienten Gasnetzwerksteuerung von Fernleitungsnetzen auf dem Festland mit einer großen Anzahl möglicher Gastransportrouten. Die Eingabedaten bestehen aus der Netzwerktopologie, dem Anfangszustand des Netzes und zukünftigen Vorgaben an den Randknoten des Netzes, welche den Gaseinfluss und Gasausfluss sowie eine potenzielle Vorgabe von Druckwerten umfassen. Gegeben diese Daten besteht die Aufgabe besteht darin, eine Menge an zukünftigen Steuerungsentscheidungen für alle aktiven, also steuerbaren, Elemente des Netzes zu finden, sodass eine Kombination von Straffunktionen minimiert wird. Das Problem wird in dieser Arbeit im Rahmen der Erstellung eines entscheidungsunterstützenden Systems für Dispatcher betrachtet, welche das Gasnetz steuern. Dies resultiert in einer detaillierten Modellierung mit einer Vielzahl von Nebenbedingungen, großen und herausfordernden realistischen Instanzen sowie anspruchsvollen Vorgaben zur maximalen Laufzeit. Diese Eigenschaften erhöhen die Komplexität des Problems, welches bereits in der Theorie auf Grund der inhärenten Kombination von nichtlinearen und kombinatorischen Aspekten schwierig zu lösen ist. Die Beiträge dieser Arbeit betreffen verschiedene Schritte des Prozesses zur Lösung des Problems. Bezüglich der Modellformulierung werden zwei übliche Approximationen der Gasflussbeschreibung in Fernleitungsrohren auf Validität überprüft: die Vernachlässigung des Trägheitsterms und die Annahme einer linearisierten Beschreibung des Reibungsterms. Für beide Approximationen wird untersucht, ob sie für reale Gasflussbedingungen zulässig sind. Dazu wird eine große Anzahl historischer Netzzustandsdaten des Gasnetzbetreibers Open Grid Europe ausgewertet. Während bestätigt werden kann, dass eine Vernachlässigung des Trägheitsterms unter Realbedingungen angemessen ist, führt die Linearisierung des Reibungsterms zu signifikanten Fehlern und kann daher nicht für die allgemeine Beschreibung des Gasflusses in Fernleitungsrohren verwendet werden. In einem weiteren Teil dieser Arbeit wird das Konzept der Sollwerte eingeführt. Mit diesen ist eine realistischere Beschreibung der Steuerungsbefehle möglich, welche den Dispatchern für Regler und Verdichterstationen zur Verfügung stehen. Der Sollwertmechanismus wird basierend auf den Gasflussprinzipien in Rohrleitungen hergeleitet, um anschließend ein gemischt-ganzzahliges Programm zu entwickeln, welches das entsprechende Verhalten erzeugt. Die Präzision dieses Modells wird durch einen Vergleich mit einem Simulator von Industriestandard sichergestellt, welcher auf Sollwerten basiert. Außerdem werden zwei Heuristiken für das Optimierungsproblem der transienten Gasnetzwerksteuerung mit Sollwertmodellierung vorgestellt. Diese basieren auf approximativen Modellen für die Sollwertsteuerung und ermitteln die letztendlichen Steuerungsentscheidungen in einer nachgelagerten Routine. Basierend auf künstlich erzeugten Testinstanzen werden die Heuristiken schließlich mit dem direkten Lösen des entsprechenden Modells verglichen. Zudem werden in dieser Arbeit problemspezifische Algorithmen für zwei Varianten des beschriebenen Optimierungsproblems entwickelt. Die erste Variante betrachtet das Gasnetzwerksteuerungsproblem beschränkt auf eine einzelne Netzstation, die lokale Betriebsstellen darstellen und über eine Vielzahl an aktiven Steuerungselementen verfügen. Das entsprechende transiente Modell ist sehr detailliert und beinhaltet eine differenzierte Beschreibung der Verdichterstationen. Der problemspezifische Algorithmus basiert auf der Kürze der Rohre innerhalb der Station und findet zulässige Lösungen durch das Lösen von stationären Varianten des Modells sowie der Nutzung eines transienten Rolling-Horizon Ansatzes. In der zweiten Problemvariante wird das gesamte Gasnetz betrachtet, wobei eine vereinfachte Modellierung der Steuerungsmöglichkeiten innerhalb von Netzstationen angenommen wird. Neben einer neuen Beschreibung der Verdichtungsmöglichkeiten einer Station wird ebenfalls ein problemspezifischer Algorithmus entwickelt. Dieser erstellt aussichtsreiche Werte für die Binärvariablen und nutzt dafür eine Kombination aus sequenzieller gemischt-ganzzahliger Programmierung, zwei auf verkürzten Zeithorizonten basierenden Heuristiken und eine spezialisierte dynamische Obergrenze für die Anzahl der Branch-and-Bound-Knoten. Diese Teillösungen werden durch eine Fixierung der binären Variablen und das anschließende Lösen des restlichen nichtlinearen Programms komplettiert. Die Güte beider Algorithmen wird in umfangreichen empirischen Experimenten untersucht, welche reale Instanzen der jeweiligen Problemvarianten betrachten. Y1 - 2023 ER - TY - JOUR A1 - Hennings, Felix A1 - Petkovic, Milena A1 - Streubel, Tom T1 - On the Numerical Treatment of Interlaced Target Values - Modeling, Optimization and Simulation of Regulating Valves in Gas Networks JF - Optimization and Engineering N2 - Due to the current and foreseeable shifts towards carbon dioxide neutral energy production, which will likely result in balancing fluctuating renewable energy generation by transforming power-to-gas-to-power as well as building a large-scale hydrogen transport infrastructure, the trading and transport operations of gas will become more dynamic, volatile, and hence also less predictable. Therefore, computer-aided support in terms of rapid simulation and control optimization will further broaden its importance for gas network dispatching. In this paper, we aim to contribute and openly publish two new mathematical models for regulators, also referred to as control valves, which together with compressors make up the most complex and involved types of active elements in gas network infrastructures. They provide direct control over gas networks but are in turn controlled via target values, also known as set-point values, themselves. Our models incorporate up to six dynamical target values to define desired transient states for the elements' local vicinity within the network. That is, each pair of every two target values defines a bounding box for the inlet pressure, outlet pressure as well as the passing mass flow of gas. In the proposed models, those target values are prioritized differently and are constantly in competition with each other, which can only be resolved dynamically at run-time of either a simulation or optimization process. Besides careful derivation, we compare simulation and optimization results with predictions of the widely adopted commercial simulation tool SIMONE, serving as our substitute for actual real-world transport operations. Y1 - 2024 U6 - https://doi.org/10.1007/s11081-023-09812-0 VL - 25 SP - 491 EP - 527 PB - Springer Nature ER - TY - GEN A1 - Prause, Felix A1 - Hoppmann-Baum, Kai A1 - Defourny, Boris A1 - Koch, Thorsten T1 - The Maximum Diversity Assortment Selection Problem N2 - In this paper, we introduce the Maximum Diversity Assortment Selection Problem (MADASS), which is a generalization of the 2-dimensional Cutting Stock Problem (2CSP). Given a set of rectangles and a rectangular container, the goal of 2CSP is to determine a subset of rectangles that can be placed in the container without overlapping, i.e., a feasible assortment, such that a maximum area is covered. In MADASS, we need to determine a set of feasible assortments, each of them covering a certain minimum threshold of the container, such that the diversity among them is maximized. Thereby, diversity is defined as minimum or average normalized Hamming-Distance of all assortment pairs. The MADASS Problem was used in the 11th AIMMS-MOPTA Competition in 2019. The methods we describe in this article and the computational results won the contest. In the following, we give a definition of the problem, introduce a mathematical model and solution approaches, determine upper bounds on the diversity, and conclude with computational experiments conducted on test instances derived from the 2CSP literature. T3 - ZIB-Report - 20-34 KW - Combinatorial Optimization KW - Mixed Integer Programming KW - 2-dim Cutting Stock Problem KW - Maximum Diversity Problem Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81039 SN - 1438-0064 ER - TY - GEN A1 - Anderson, Lovis A1 - Turner, Mark A1 - Koch, Thorsten T1 - Generative deep learning for decision making in gas networks N2 - A decision support system relies on frequent re-solving of similar problem instances. While the general structure remains the same in corresponding applications, the input parameters are updated on a regular basis. We propose a generative neural network design for learning integer decision variables of mixed-integer linear programming (MILP) formulations of these problems. We utilise a deep neural network discriminator and a MILP solver as our oracle to train our generative neural network. In this article, we present the results of our design applied to the transient gas optimisation problem. With the trained network we produce a feasible solution in 2.5s, use it as a warm-start solution, and thereby decrease global optimal solution solve time by 60.5%. T3 - ZIB-Report - 20-38 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81103 SN - 1438-0064 ER - TY - JOUR A1 - Hoppmann-Baum, Kai A1 - Hennings, Felix A1 - Zittel, Janina A1 - Gotzes, Uwe A1 - Spreckelsen, Eva-Maria A1 - Spreckelsen, Klaus A1 - Koch, Thorsten T1 - An Optimization Approach for the Transient Control of Hydrogen Transport Networks JF - Mathematical Methods of Operations Research Y1 - 2021 IS - Special Issue on Energy Networks ER - TY - GEN A1 - Hoppmann-Baum, Kai A1 - Mexi, Gioni A1 - Burdakov, Oleg A1 - Casselgren, Carl Johan A1 - Koch, Thorsten T1 - Length-Constrained Cycle Partition with an Application to UAV Routing N2 - In this article, we discuss the Length-Constrained Cycle Partition Problem (LCCP). Besides edge weights, the undirected graph in LCCP features an individual critical weight value for each vertex. A cycle partition, i.e., a vertex disjoint cycle cover, is a feasible solution if the length of each cycle is not greater than the critical weight of each of the vertices in the cycle. The goal is to find a feasible partition with the minimum number of cycles. In this article, we discuss theoretical properties, preprocessing techniques, and two mixed-integer programming models (MIP) for LCCP both inspired by formulations for the closely related Travelling Salesperson Problem (TSP). Further, we introduce conflict hypergraphs, whose cliques yield valid constraints for the MIP models. We conclude with a report on computational experiments conducted on (A)TSPLIB-based instances. As an example, we use a routing problem in which a fleet of uncrewed aerial vehicles (UAVs) patrols a set of areas. T3 - ZIB-Report - 20-30 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-80489 SN - 1438-0064 ER - TY - JOUR A1 - Gotzes, Uwe A1 - Hoppmann-Baum, Kai T1 - Bounding the final rank during a round robin tournament with integer programming JF - Operational Research N2 - This article is mainly motivated by the urge to answer two kinds of questions regarding the Bundesliga, which is Germany’s primary football (soccer) division having the highest average stadium attendance worldwide: “At any point in the season, what is the lowest final rank a certain team can achieve?” and “At any point in the season, what is the highest final rank a certain team can achieve?”. Although we focus on the Bundesliga in particular, the integer programming formulations we introduce to answer these questions can easily be adapted to a variety of other league systems and tournaments. Y1 - 2020 U6 - https://doi.org/https://doi.org/10.1007/s12351-020-00546-w VL - 1866-1505 ER - TY - JOUR A1 - Koch, Thorsten A1 - Schmidt, Martin A1 - Hiller, Benjamin 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 T1 - Capacity Evaluation for Large-Scale Gas Networks JF - German Success Stories in Industrial Mathematics Y1 - 2020 SN - 978-3-030-81454-0 U6 - https://doi.org/10.1007/978-3-030-81455-7 VL - 35 SP - 23 EP - 28 ER - TY - JOUR A1 - Chen, Ying A1 - Zakiyeva, Nazgul A1 - Zhu, Bangzhu A1 - Koch, Thorsten T1 - Modeling and Forecasting the Dynamics of the Natural Gas Transmission Network in Germany with the Demand and Supply Balance Constraint JF - Applied Energy Y1 - 2020 U6 - https://doi.org/10.1016/j.apenergy.2020.115597 N1 - https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3646636 IS - 278 ER - TY - JOUR A1 - Koch, Thorsten A1 - Chen, Ying A1 - Lim, Kian Guan A1 - Xu, Xiaofei A1 - Zakiyeva, Nazgul T1 - A review study of functional autoregressive models with application to energy forecasting JF - WIREs Computational Statistics Y1 - 2020 U6 - https://doi.org/10.1002/wics.1525 N1 - https://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=7693&context=lkcsb_research ER - TY - CHAP A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - An exact high performance solver for Steiner tree problems in graphs and related problems T2 - Modeling, Simulation and Optimization of Complex Processes HPSC 2018 Y1 - 2020 PB - Springer ER - TY - GEN A1 - Hoppmann-Baum, Kai A1 - Hennings, Felix A1 - Zittel, Janina A1 - Gotzes, Uwe A1 - Spreckelsen, Eva-Maria A1 - Spreckelsen, Klaus A1 - Koch, Thorsten T1 - From Natural Gas towards Hydrogen - A Feasibility Study on Current Transport Network Infrastructure and its Technical Control N2 - This study examines the usability of a real-world, large-scale natural gas transport infrastructure for hydrogen transport. We investigate whether a converted network can transport the amounts of hydrogen necessary to satisfy current energy demands. After introducing an optimization model for the robust transient control of hydrogen networks, we conduct computational experiments based on real-world demand scenarios. Using a representative network, we demonstrate that replacing each turbo compressor unit by four parallel hydrogen compressors, each of them comprising multiple serial compression stages, and imposing stricter rules regarding the balancing of in- and outflow suffices to realize transport in a majority of scenarios. However, due to the reduced linepack there is an increased need for technical and non-technical measures leading to a more dynamic network control. Furthermore, the amount of energy needed for compression increases by 364% on average. T3 - ZIB-Report - 20-27 KW - Hydrogen Transport KW - Hydrogen Infrastructure KW - Network Flows KW - Mixed Integer Programming KW - Energiewende Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-79901 SN - 1438-0064 ER - TY - JOUR A1 - Hoppmann-Baum, Kai A1 - Hennings, Felix A1 - Lenz, Ralf A1 - Gotzes, Uwe A1 - Heinecke, Nina A1 - Spreckelsen, Klaus A1 - Koch, Thorsten T1 - Optimal Operation of Transient Gas Transport Networks JF - Optimization and Engineering N2 - In this paper, we describe an algorithmic framework for the optimal operation of transient gas transport networks consisting of a hierarchical MILP formulation together with a sequential linear programming inspired post-processing routine. Its implementation is part of the KOMPASS decision support system, which is currently used in an industrial setting. Real-world gas transport networks are controlled by operating complex pipeline intersection areas, which comprise multiple compressor units, regulators, and valves. In the following, we introduce the concept of network stations to model them. Thereby, we represent the technical capabilities of a station by hand-tailored artificial arcs and add them to network. Furthermore, we choose from a predefined set of flow directions for each network station and time step, which determines where the gas enters and leaves the station. Additionally, we have to select a supported simple state, which consists of two subsets of artificial arcs: Arcs that must and arcs that cannot be used. The goal is to determine a stable control of the network satisfying all supplies and demands. The pipeline intersections, that are represented by the network stations, were initially built centuries ago. Subsequently, due to updates, changes, and extensions, they evolved into highly complex and involved topologies. To extract their basic properties and to model them using computer-readable and optimizable descriptions took several years of effort. To support the dispatchers in controlling the network, we need to compute a continuously updated list of recommended measures. Our motivation for the model presented here is to make fast decisions on important transient global control parameters, i.e., how to route the flow and where to compress the gas. Detailed continuous and discrete technical control measures realizing them, which take all hardware details into account, are determined in a subsequent step. In this paper, we present computational results from the KOMPASS project using detailed real-world data. Y1 - 2020 U6 - https://doi.org/10.1007/s11081-020-09584-x VL - 22 SP - 735 EP - 781 ER - TY - CHAP A1 - Hoppmann-Baum, Kai A1 - Mexi, Gioni A1 - Burdakov, Oleg A1 - Casselgren, Carl Johan A1 - Koch, Thorsten ED - Hebrard, Emmanuel ED - Musliu, Nysret T1 - Minimum Cycle Partition with Length Requirements T2 - Integration of Constraint Programming, Artificial Intelligence, and Operations Research N2 - In this article we introduce a Minimum Cycle Partition Problem with Length Requirements (CPLR). This generalization of the Travelling Salesman Problem (TSP) originates from routing Unmanned Aerial Vehicles (UAVs). Apart from nonnegative edge weights, CPLR has an individual critical weight value associated with each vertex. A cycle partition, i.e., a vertex disjoint cycle cover, is regarded as a feasible solution if the length of each cycle, which is the sum of the weights of its edges, is not greater than the critical weight of each of its vertices. The goal is to find a feasible partition, which minimizes the number of cycles. In this article, a heuristic algorithm is presented together with a Mixed Integer Programming (MIP) formulation of CPLR. We furthermore introduce a conflict graph, whose cliques yield valid constraints for the MIP model. Finally, we report on computational experiments conducted on TSPLIB-based test instances. Y1 - 2020 SN - 978-3-030-58941-7 U6 - https://doi.org/10.1007/978-3-030-58942-4_18 VL - 12296 SP - 273 EP - 282 PB - Springer International Publishing CY - Cham ER - TY - JOUR A1 - Ramin, Elham A1 - Bestuzheva, Ksenia A1 - Gargalo, Carina A1 - Ramin, Danial A1 - Schneider, Carina A1 - Ramin, Pedram A1 - Flores-Alsina, Xavier A1 - Andersen, Maj M. A1 - Gernaey, Krist V. T1 - Incremental design of water symbiosis networks with prior knowledge: The case of an industrial park in Kenya JF - Science of the Total Environment N2 - Industrial parks have a high potential for recycling and reusing resources such as water across companies by creating symbiosis networks. In this study, we introduce a mathematical optimization framework for the design of water network integration in industrial parks formulated as a large-scale standard mixed-integer non-linear programming (MINLP) problem. The novelty of our approach relies on i) developing a multi-level incremental optimization framework for water network synthesis, ii) including prior knowledge of demand growth and projected water scarcity to evaluate the significance of water-saving solutions, iii) incorporating a comprehensive formulation of water network synthesis problem including multiple pollutants and different treatment units and iv) performing a multi-objective optimization of the network including freshwater savings and relative cost of the network. The significance of the proposed optimization framework is illustrated by applying it to an existing industrial park in a water-scarce region in Kenya. Firstly, we illustrated the benefits of including prior knowledge to prevent an over-design of the network at the early stages. In the case study, we achieved a more flexible and expandable water network with 36% lower unit cost at the early stage and 15% lower unit cost at later stages for the overall maximum freshwater savings of 25%. Secondly, multi-objective analysis suggests an optimum freshwater savings of 14% to reduce the unit cost of network by half. Moreover, the significance of symbiosis networks is highlighted by showing that intra-company connections can only achieve a maximum freshwater savings of 17% with significantly higher unit cost (+45%). Finally, we showed that the values of symbiosis connectivity index in the Pareto front correspond to higher freshwater savings, indicating the significant role of the symbiosis network in the industrial park under study. This is the first study, where all the above elements have been taken into account simultaneously for the design of a water reuse network. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1016/j.scitotenv.2020.141706 VL - 751 ER - TY - BOOK A1 - Hadjidimitriou, Natalia Selini A1 - Frangioni, Antonio A1 - Lodi, Andrea A1 - Koch, Thorsten ED - Hadjidimitriou, Natalia Selini ED - Frangioni, Antonio ED - Lodi, Andrea ED - Koch, Thorsten T1 - Mathematical Optimization for Efficient and Robust Energy Networks Y1 - 2020 SN - 978-3-030-57441-3 U6 - https://doi.org/10.1007/978-3-030-57442-0 VL - 4 PB - Springer ER - TY - GEN A1 - Hennings, Felix A1 - Hoppmann-Baum, Kai A1 - Zittel, Janina T1 - Optimizing transient gas network control for challenging real-world instances using MIP-based heuristics N2 - Optimizing the transient control of gas networks is a highly challenging task. The corresponding model incorporates the combinatorial complexity of determining the settings for the many active elements as well as the non-linear and non-convex nature of the physical and technical principles of gas transport. In this paper, we present the latest improvements of our ongoing work to solve this problem for real-world, large-scale problem instances: By adjusting our mixed-integer non-linear programming model regarding the gas compression capabilities in the network, we reflect the technical limits of the underlying units more accurately while maintaining a similar overall model size. In addition, we introduce a new algorithmic approach that is based on splitting the complexity of the problem by first finding assignments for discrete variables and then determining the continuous variables as locally optimal solution of the corresponding non-linear program. For the first task, we design multiple different heuristics based on concepts for general time-expanded optimization problems that find solutions by solving a sequence of sub-problems defined on reduced time horizons. To demonstrate the competitiveness of our approach, we test our algorithm on particularly challenging historic demand scenarios. The results show that high-quality solutions are obtained reliably within short solving times, making the algorithm well-suited to be applied at the core of time-critical industrial applications. T3 - ZIB-Report - 22-08 Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-86842 SN - 1438-0064 ER - TY - GEN A1 - Pedersen, Jaap A1 - Le, Thi Thai A1 - Koch, Thorsten A1 - Zittel, Janina T1 - Optimal discrete pipe sizing for tree-shaped CO2 networks N2 - While energy-intensive industries like the steel industry plan to switch to renewable energy sources, other industries, such as the cement industry, have to rely on carbon capture storage and utilization technologies to reduce the inevitable carbon dioxide (CO2) emissions of their production processes. In this context, we investigate the problem of finding optimal pipeline diameters from a discrete set of diameters for a tree-shaped network transporting captured CO2 from multiple sources to a single sink. The general problem of optimizing arc capacities in potential-based fluid networks is a challenging mixed-integer nonlinear program. Additionally, the behaviour of CO2 is highly sensitive and nonlinear regarding temperature and pressure changes. We propose an iterative algorithm splitting the problem into two parts: a) the pipe-sizing problem under a fixed supply scenario and temperature distribution and b) the thermophysical modelling including mixing effects, the Joule-Thomson effect, and heat exchange with the surrounding environment. We show the effectiveness of our approach by applying our algorithm to a real-world network planning problem for a CO2 network in Western Germany. T3 - ZIB-Report - 22-15 KW - CO2 Transport KW - Network Design KW - Pipeline Sizing Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-87574 SN - 1438-0064 ER - TY - JOUR A1 - Hoppmann-Baum, Kai A1 - Burdakov, Oleg A1 - Mexi, Gioni A1 - Casselgren, Carl Johan A1 - Koch, Thorsten T1 - Length-Constrained Cycle Partition with an Application to UAV Routing JF - Optimization Methods and Software N2 - This article discusses the Length-Constrained Cycle Partition Problem (LCCP), which constitutes a new generalization of the Travelling Salesperson Problem (TSP). Apart from nonnegative edge weights, the undirected graph in LCCP features a nonnegative critical length parameter for each vertex. A cycle partition, i.e., a vertex-disjoint cycle cover, is a feasible solution for LCCP if the length of each cycle is not greater than the critical length of each vertex contained in it. The goal is to find a feasible partition having a minimum number of cycles. Besides analyzing theoretical properties and developing preprocessing techniques, we propose an elaborate heuristic algorithm that produces solutions of good quality even for large-size instances. Moreover, we present two exact mixed-integer programming formulations (MIPs) for LCCP, which are inspired by well-known modeling approaches for TSP. Further, we introduce the concept of conflict hypergraphs, whose cliques yield valid constraints for the MIP models. We conclude with a discussion on computational experiments that we conducted using (A)TSPLIB-based problem instances. As a motivating example application, we describe a routing problem where a fleet of uncrewed aerial vehicles (UAVs) must patrol a given set of areas. Y1 - 2022 U6 - https://doi.org/10.1080/10556788.2022.2053972 ER - TY - GEN A1 - Shinano, Yuji T1 - UG - Ubiquity Generator Framework v0.9.1 N2 - UG is a generic framework to parallelize branch-and-bound based solvers (e.g., MIP, MINLP, ExactIP) in a distributed or shared memory computing environment. It exploits the powerful performance of state-of-the-art "base solvers", such as SCIP, CPLEX, etc. without the need for base solver parallelization. UG framework, ParaSCIP(ug[SCIP,MPI]) and FiberSCIP (ug[SCIP,Pthreads]) are available as a beta version. For MIP solving, ParaSCIP and FiberSCIP are well debugged and should be stable. For MINLP solving, they are relatively stable, but not as thoroughly debugged. This release version should handle branch-and-cut approaches where subproblems are defined by variable bounds and also by constrains for ug[SCIP,*] ParaSCIP and FiberSCIP). Therefore, problem classes other than MIP or MINLP can be handled, but they have not been tested yet. v0.9.1: Update orbitope cip files. KW - parallelization framework KW - branch-and-bound parallelization KW - integer optimization Y1 - 2020 U6 - https://doi.org/10.12752/8508 ER - TY - CHAP A1 - Criado, Francisco A1 - Martínez-Rubio, David A1 - Pokutta, Sebastian T1 - Fast Algorithms for Packing Proportional Fairness and its Dual T2 - Proceedings of the Conference on Neural Information Processing Systems N2 - The proportional fair resource allocation problem is a major problem studied in flow control of networks, operations research, and economic theory, where it has found numerous applications. This problem, defined as the constrained maximization of sum_i log x_i, is known as the packing proportional fairness problem when the feasible set is defined by positive linear constraints and x ∈ R≥0. In this work, we present a distributed accelerated first-order method for this problem which improves upon previous approaches. We also design an algorithm for the optimization of its dual problem. Both algorithms are width-independent. Y1 - 2022 VL - 36 ER - TY - JOUR A1 - Kerdreux, Thomas A1 - d'Aspremont, Alexandre A1 - Pokutta, Sebastian T1 - Local and Global Uniform Convexity Conditions N2 - We review various characterizations of uniform convexity and smoothness on norm balls in finite-dimensional spaces and connect results stemming from the geometry of Banach spaces with scaling inequalities used in analysing the convergence of optimization methods. In particular, we establish local versions of these conditions to provide sharper insights on a recent body of complexity results in learning theory, online learning, or offline optimization, which rely on the strong convexity of the feasible set. While they have a significant impact on complexity, these strong convexity or uniform convexity properties of feasible sets are not exploited as thoroughly as their functional counterparts, and this work is an effort to correct this imbalance. We conclude with some practical examples in optimization and machine learning where leveraging these conditions and localized assumptions lead to new complexity results. Y1 - 2021 ER - TY - JOUR A1 - Schimunek, Johannes A1 - Seidl, Philipp A1 - Elez, Katarina A1 - Hempel, Tim A1 - Le, Tuan A1 - Noé, Frank A1 - Olsson, Simon A1 - Raich, Lluís A1 - Winter, Robin A1 - Gokcan, Hatice A1 - Gusev, Filipp A1 - Gutkin, Evgeny M. A1 - Isayev, Olexandr A1 - Kurnikova, Maria G. A1 - Narangoda, Chamali H. A1 - Zubatyuk, Roman A1 - Bosko, Ivan P. A1 - Furs, Konstantin V. A1 - Karpenko, Anna D. A1 - Kornoushenko, Yury V. A1 - Shuldau, Mikita A1 - Yushkevich, Artsemi A1 - Benabderrahmane, Mohammed B. A1 - Bousquet-Melou, Patrick A1 - Bureau, Ronan A1 - Charton, Beatrice A1 - Cirou, Bertrand C. A1 - Gil, Gérard A1 - Allen, William J. A1 - Sirimulla, Suman A1 - Watowich, Stanley A1 - Antonopoulos, Nick A1 - Epitropakis, Nikolaos A1 - Krasoulis, Agamemnon A1 - Itsikalis, Vassilis A1 - Theodorakis, Stavros A1 - Kozlovskii, Igor A1 - Maliutin, Anton A1 - Medvedev, Alexander A1 - Popov, Petr A1 - Zaretckii, Mark A1 - Eghbal-Zadeh, Hamid A1 - Halmich, Christina A1 - Hochreiter, Sepp A1 - Mayr, Andreas A1 - Ruch, Peter A1 - Widrich, Michael A1 - Berenger, Francois A1 - Kumar, Ashutosh A1 - Yamanishi, Yoshihiro A1 - Zhang, Kam Y. J. A1 - Bengio, Emmanuel A1 - Bengio, Yoshua A1 - Jain, Moksh J. A1 - Korablyov, Maksym A1 - Liu, Cheng-Hao A1 - Marcou, Gilles A1 - Glaab, Enrico A1 - Barnsley, Kelly A1 - Iyengar, Suhasini M. A1 - Ondrechen, Mary Jo A1 - Haupt, V. Joachim A1 - Kaiser, Florian A1 - Schroeder, Michael A1 - Pugliese, Luisa A1 - Albani, Simone A1 - Athanasiou, Christina A1 - Beccari, Andrea A1 - Carloni, Paolo A1 - D’Arrigo, Giulia A1 - Gianquinto, Eleonora A1 - Goßen, Jonas A1 - Hanke, Anton A1 - Joseph, Benjamin P. A1 - Kokh, Daria B. A1 - Kovachka, Sandra A1 - Manelfi, Candida A1 - Mukherjee, Goutam A1 - Muñiz-Chicharro, Abraham A1 - Musiani, Francesco A1 - Nunes-Alves, Ariane A1 - Paiardi, Giulia A1 - Rossetti, Giulia A1 - Sadiq, S. Kashif A1 - Spyrakis, Francesca A1 - Talarico, Carmine A1 - Tsengenes, Alexandros A1 - Wade, Rebecca C. A1 - Copeland, Conner A1 - Gaiser, Jeremiah A1 - Olson, Daniel R. A1 - Roy, Amitava A1 - Venkatraman, Vishwesh A1 - Wheeler, Travis J. A1 - Arthanari, Haribabu A1 - Blaschitz, Klara A1 - Cespugli, Marco A1 - Durmaz, Vedat A1 - Fackeldey, Konstantin A1 - Fischer, Patrick D. A1 - Gorgulla, Christoph A1 - Gruber, Christian A1 - Gruber, Karl A1 - Hetmann, Michael A1 - Kinney, Jamie E. A1 - Padmanabha Das, Krishna M. A1 - Pandita, Shreya A1 - Singh, Amit A1 - Steinkellner, Georg A1 - Tesseyre, Guilhem A1 - Wagner, Gerhard A1 - Wang, Zi-Fu A1 - Yust, Ryan J. A1 - Druzhilovskiy, Dmitry S. A1 - Filimonov, Dmitry A. A1 - Pogodin, Pavel V. A1 - Poroikov, Vladimir A1 - Rudik, Anastassia V. A1 - Stolbov, Leonid A. A1 - Veselovsky, Alexander V. A1 - De Rosa, Maria A1 - De Simone, Giada A1 - Gulotta, Maria R. A1 - Lombino, Jessica A1 - Mekni, Nedra A1 - Perricone, Ugo A1 - Casini, Arturo A1 - Embree, Amanda A1 - Gordon, D. Benjamin A1 - Lei, David A1 - Pratt, Katelin A1 - Voigt, Christopher A. A1 - Chen, Kuang-Yu A1 - Jacob, Yves A1 - Krischuns, Tim A1 - Lafaye, Pierre A1 - Zettor, Agnès A1 - Rodríguez, M. Luis A1 - White, Kris M. A1 - Fearon, Daren A1 - Von Delft, Frank A1 - Walsh, Martin A. A1 - Horvath, Dragos A1 - Brooks III, Charles L. A1 - Falsafi, Babak A1 - Ford, Bryan A1 - García-Sastre, Adolfo A1 - Yup Lee, Sang A1 - Naffakh, Nadia A1 - Varnek, Alexandre A1 - Klambauer, Günter A1 - Hermans, Thomas M. T1 - A community effort in SARS-CoV-2 drug discovery JF - Molecular Informatics KW - COVID-19 KW - drug discovery KW - machine learning KW - SARS-CoV-2 Y1 - 2023 U6 - https://doi.org/https://doi.org/10.1002/minf.202300262 VL - 43 IS - 1 SP - e202300262 ER - TY - JOUR A1 - Gorgulla, Christoph A1 - Nigam, AkshatKumar A1 - Koop, Matt A1 - Selim Çınaroğlu, Süleyman A1 - Secker, Christopher A1 - Haddadnia, Mohammad A1 - Kumar, Abhishek A1 - Malets, Yehor A1 - Hasson, Alexander A1 - Li, Minkai A1 - Tang, Ming A1 - Levin-Konigsberg, Roni A1 - Radchenko, Dmitry A1 - Kumar, Aditya A1 - Gehev, Minko A1 - Aquilanti, Pierre-Yves A1 - Gabb, Henry A1 - Alhossary, Amr A1 - Wagner, Gerhard A1 - Aspuru-Guzik, Alán A1 - Moroz, Yurii S. A1 - Fackeldey, Konstantin A1 - Arthanari, Haribabu T1 - VirtualFlow 2.0 - The Next Generation Drug Discovery Platform Enabling Adaptive Screens of 69 Billion Molecules JF - bioRxiv KW - preprint Y1 - 2023 U6 - https://doi.org/10.1101/2023.04.25.537981 ER - TY - JOUR A1 - Raharinirina, Nomenjanahary Alexia A1 - Sunkara, Vikram A1 - von Kleist, Max A1 - Fackeldey, Konstantin A1 - Weber, Marcus T1 - Multi-Input data ASsembly for joint Analysis (MIASA): A framework for the joint analysis of disjoint sets of variables JF - PLOS ONE Y1 - 2024 U6 - https://doi.org/10.1371/journal.pone.0302425 VL - 19 IS - 5 PB - Public Library of Science ER - TY - JOUR A1 - Trepte, Philipp A1 - Secker, Christopher A1 - Olivet, Julien A1 - Blavier, Jeremy A1 - Kostova, Simona A1 - Maseko, Sibusiso B A1 - Minia, Igor A1 - Silva Ramos, Eduardo A1 - Cassonnet, Patricia A1 - Golusik, Sabrina A1 - Zenkner, Martina A1 - Beetz, Stephanie A1 - Liebich, Mara J A1 - Scharek, Nadine A1 - Schütz, Anja A1 - Sperling, Marcel A1 - Lisurek, Michael A1 - Wang, Yang A1 - Spirohn, Kerstin A1 - Hao, Tong A1 - Calderwood, Michael A A1 - Hill, David E A1 - Landthaler, Markus A1 - Choi, Soon Gang A1 - Twizere, Jean-Claude A1 - Vidal, Marc A1 - Wanker, Erich E T1 - AI-guided pipeline for protein–protein interaction drug discovery identifies a SARS-CoV-2 inhibitor JF - Molecular Systems Biology N2 - Protein–protein interactions (PPIs) offer great opportunities to expand the druggable proteome and therapeutically tackle various diseases, but remain challenging targets for drug discovery. Here, we provide a comprehensive pipeline that combines experimental and computational tools to identify and validate PPI targets and perform early-stage drug discovery. We have developed a machine learning approach that prioritizes interactions by analyzing quantitative data from binary PPI assays or AlphaFold-Multimer predictions. Using the quantitative assay LuTHy together with our machine learning algorithm, we identified high-confidence interactions among SARS-CoV-2 proteins for which we predicted three-dimensional structures using AlphaFold-Multimer. We employed VirtualFlow to target the contact interface of the NSP10-NSP16 SARS-CoV-2 methyltransferase complex by ultra-large virtual drug screening. Thereby, we identified a compound that binds to NSP10 and inhibits its interaction with NSP16, while also disrupting the methyltransferase activity of the complex, and SARS-CoV-2 replication. Overall, this pipeline will help to prioritize PPI targets to accelerate the discovery of early-stage drug candidates targeting protein complexes and pathways. KW - Applied Mathematics KW - Computational Theory and Mathematics KW - General Agricultural and Biological Sciences KW - General Immunology and Microbiology KW - General Biochemistry, Genetics and Molecular Biology KW - Information Systems Y1 - 2024 U6 - https://doi.org/https://doi.org/10.1038/s44320-024-00019-8 SN - 1744-4292 VL - 20 IS - 4 SP - 428 EP - 457 PB - Springer Science and Business Media LLC ER - TY - JOUR A1 - Bärmann, Andreas A1 - Martin, Alexander A1 - Pokutta, Sebastian A1 - Schneider, Oskar T1 - An Online-Learning Approach to Inverse Optimization Y1 - 2018 ER - TY - JOUR A1 - Bienenstock, Daniel A1 - Muñoz, Gonzalo A1 - Pokutta, Sebastian T1 - Principled Deep Neural Network Training through Linear Programming N2 - Deep Learning has received significant attention due to its impressive performance in many state-of-the-art learning tasks. Unfortunately, while very powerful, Deep Learning is not well understood theoretically and in particular only recently results for the complexity of training deep neural networks have been obtained. In this work we show that large classes of deep neural networks with various architectures (e.g., DNNs, CNNs, Binary Neural Networks, and ResNets), activation functions (e.g., ReLUs and leaky ReLUs), and loss functions (e.g., Hinge loss, Euclidean loss, etc) can be trained to near optimality with desired target accuracy using linear programming in time that is exponential in the input data and parameter space dimension and polynomial in the size of the data set; improvements of the dependence in the input dimension are known to be unlikely assuming P≠NP, and improving the dependence on the parameter space dimension remains open. In particular, we obtain polynomial time algorithms for training for a given fixed network architecture. Our work applies more broadly to empirical risk minimization problems which allows us to generalize various previous results and obtain new complexity results for previously unstudied architectures in the proper learning setting. Y1 - 2018 ER - TY - CHAP A1 - Kerdreux, Thomas A1 - d'Aspremont, Alexandre A1 - Pokutta, Sebastian T1 - Projection-Free Optimization on Uniformly Convex Sets T2 - To Appear in Proceedings of AISTATS Y1 - 2020 ER - TY - JOUR A1 - Secker, Christopher A1 - Fackeldey, Konstantin A1 - Weber, Marcus A1 - Ray, Sourav A1 - Gorgulla, Christoph A1 - Schütte, Christof T1 - Novel multi-objective affinity approach allows to identify pH-specific μ-opioid receptor agonists JF - Journal of Cheminformatics N2 - Opioids are essential pharmaceuticals due to their analgesic properties, however, lethal side effects, addiction, and opioid tolerance are extremely challenging. The development of novel molecules targeting the μ-opioid receptor (MOR) in inflamed, but not in healthy tissue, could significantly reduce these unwanted effects. Finding such novel molecules can be achieved by maximizing the binding affinity to the MOR at acidic pH while minimizing it at neutral pH, thus combining two conflicting objectives. Here, this multi-objective optimal affinity approach is presented, together with a virtual drug discovery pipeline for its practical implementation. When applied to finding pH-specific drug candidates, it combines protonation state-dependent structure and ligand preparation with high-throughput virtual screening. We employ this pipeline to characterize a set of MOR agonists identifying a morphine-like opioid derivative with higher predicted binding affinities to the MOR at low pH compared to neutral pH. Our results also confirm existing experimental evidence that NFEPP, a previously described fentanyl derivative with reduced side effects, and recently reported β-fluorofentanyls and -morphines show an increased specificity for the MOR at acidic pH when compared to fentanyl and morphine. We further applied our approach to screen a >50K ligand library identifying novel molecules with pH-specific predicted binding affinities to the MOR. The presented differential docking pipeline can be applied to perform multi-objective affinity optimization to identify safer and more specific drug candidates at large scale. Y1 - 2023 U6 - https://doi.org/10.1186/s13321-023-00746-4 VL - 15 ER - TY - GEN A1 - Lenz, Ralf A1 - Serrano, Felipe T1 - Tight Convex Relaxations for the Expansion Planning Problem N2 - Secure energy transport is considered as highly relevant for the basic infrastructure of nowadays society and economy. To satisfy increasing demands and to handle more diverse transport situations, operators of energy networks regularly expand the capacity of their network by building new network elements, known as the expansion planning problem. A key constraint function in expansion planning problems is a nonlinear and nonconvex potential loss function. In order to improve the algorithmic performance of state-of-the-art MINLP solvers, this paper presents an algebraic description for the convex envelope of this function. Through a thorough computational study, we show that this tighter relaxation tremendously improve the performance of the MINLP solver SCIP on a large test set of practically relevant instances for the expansion planning problem. In particular, the results show that our achievements lead to an improvement of the solver performance for a development version by up to 58%. T3 - ZIB-Report - 21-05 KW - Convex envelopes KW - Mixed-Integer Nonlinear Programming KW - Expansion planning of energy networks Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81459 SN - 1438-0064 ER - TY - JOUR A1 - Pokutta, Sebastian A1 - Spiegel, Christoph A1 - Zimmer, Max T1 - Deep Neural Network Training with Frank-Wolfe N2 - This paper studies the empirical efficacy and benefits of using projection-free first-order methods in the form of Conditional Gradients, a.k.a. Frank-Wolfe methods, for training Neural Networks with constrained parameters. We draw comparisons both to current state-of-the-art stochastic Gradient Descent methods as well as across different variants of stochastic Conditional Gradients. In particular, we show the general feasibility of training Neural Networks whose parameters are constrained by a convex feasible region using Frank-Wolfe algorithms and compare different stochastic variants. We then show that, by choosing an appropriate region, one can achieve performance exceeding that of unconstrained stochastic Gradient Descent and matching state-of-the-art results relying on L2-regularization. Lastly, we also demonstrate that, besides impacting performance, the particular choice of constraints can have a drastic impact on the learned representations. Y1 - 2020 ER - TY - JOUR A1 - Cryille W., Combettes A1 - Spiegel, Christoph A1 - Pokutta, Sebastian T1 - Projection-Free Adaptive Gradients for Large-Scale Optimization N2 - The complexity in large-scale optimization can lie in both handling the objective function and handling the constraint set. In this respect, stochastic Frank-Wolfe algorithms occupy a unique position as they alleviate both computational burdens, by querying only approximate first-order information from the objective and by maintaining feasibility of the iterates without using projections. In this paper, we improve the quality of their first-order information by blending in adaptive gradients. We derive convergence rates and demonstrate the computational advantage of our method over the state-of-the-art stochastic Frank-Wolfe algorithms on both convex and nonconvex objectives. The experiments further show that our method can improve the performance of adaptive gradient algorithms for constrained optimization. Y1 - 2020 ER - TY - THES A1 - Pedersen, Jaap T1 - Multiperiod Optimal Power Flow Problem In Distribution System Planning N2 - Growing demand, distributed generation, such as renewable energy sources (RES), and the increasing role of storage systems to mitigate the volatility of RES on a medium voltage level, push existing distribution grids to their limits. Therefore, necessary network expansion needs to be evaluated to guarantee a safe and reliable electricity supply in the future taking these challenges into account. This problem is formulated as an optimal power flow (OPF) problem which combines network expansion, volatile generation and storage systems, minimizing network expansion and generation costs. As storage systems introduce a temporal coupling into the system, a multiperiod OPF problem is needed and analysed in this thesis. To reduce complexity, the network expansion problem is represented in a continuous nonlinear programming formulation by using fundamental properties of electrical engeneering. This formulation is validated succesfully against a common mixed integer programming approach on a 30 and 57 bus network with respect to solution and computing time. As the OPF problem is, in general, a nonconvex, nonlinear problem and, thus, hard to solve, convex relaxations of the power flow equations have gained increasing interest. Sufficient conditions are represented which guarantee exactness of a second-order cone (SOC) relaxation of an operational OPF in radial networks. In this thesis, these conditions are enhanced for the network expansion planning problem. Additionally, nonconvexities introduced by the choice of network expansion variables are relaxed by using McCormick envelopes. These relaxations are then applied on the multiperiod OPF and compared to the original problem on a 30 and a 57 bus network. In particular, the computational time is decreased by an order up to 10^2 by the SOC relaxation while it provides either an exact solution or a sufficient lower bound on the original problem. Finally, a sensitivity study is performed on weights of network expansion costs showing strong dependency of both the solution of performed expansion and solution time on the chosen weights. KW - multiperiod optimal power flow, distribution network planning, battery storage Y1 - 2020 ER - TY - GEN A1 - Bestuzheva, Ksenia A1 - Gleixner, Ambros A1 - Vigerske, Stefan T1 - A Computational Study of Perspective Cuts N2 - The benefits of cutting planes based on the perspective function are well known for many specific classes of mixed-integer nonlinear programs with on/off structures. However, we are not aware of any empirical studies that evaluate their applicability and computational impact over large, heterogeneous test sets in general-purpose solvers. This paper provides a detailed computational study of perspective cuts within a linear programming based branch-and-cut solver for general mixed-integer nonlinear programs. Within this study, we extend the applicability of perspective cuts from convex to nonconvex nonlinearities. This generalization is achieved by applying a perspective strengthening to valid linear inequalities which separate solutions of linear relaxations. The resulting method can be applied to any constraint where all variables appearing in nonlinear terms are semi-continuous and depend on at least one common indicator variable. Our computational experiments show that adding perspective cuts for convex constraints yields a consistent improvement of performance, and adding perspective cuts for nonconvex constraints reduces branch-and-bound tree sizes and strengthens the root node relaxation, but has no significant impact on the overall mean time. T3 - ZIB-Report - 21-07 KW - perspective cuts, mixed-integer nonlinear programming, nonconvex optimization, computational study Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81821 SN - 1438-0064 ER - TY - JOUR A1 - Csizmadia, Zsolt A1 - Berthold, Timo T1 - The confined primal integral: a measure to benchmark heuristic MINLP solvers against global MINLP solvers JF - Mathematical Programming N2 - It is a challenging task to fairly compare local solvers and heuristics against each other and against global solvers. How does one weigh a faster termination time against a better quality of the found solution? In this paper, we introduce the confined primal integral, a new performance measure that rewards a balance of speed and solution quality. It emphasizes the early part of the solution process by using an exponential decay. Thereby, it avoids that the order of solvers can be inverted by choosing an arbitrarily large time limit. We provide a closed analytic formula to compute the confined primal integral a posteriori and an incremental update formula to compute it during the run of an algorithm. For the latter, we show that we can drop one of the main assumptions of the primal integral, namely the knowledge of a fixed reference solution to compare against. Furthermore, we prove that the confined primal integral is a transitive measure when comparing local solves with different final solution values. Finally, we present a computational experiment where we compare a local MINLP solver that uses certain classes of cutting planes against a solver that does not. Both versions show very different tendencies w.r.t. average running time and solution quality, and we use the confined primal integral to argue which of the two is the preferred setting. Y1 - 2020 U6 - https://doi.org/10.1007/s10107-020-01547-5 ER - TY - JOUR A1 - Witzig, Jakob A1 - Berthold, Timo T1 - Conflict Analysis for MINLP JF - INFORMS Journal on Computing N2 - The generalization of MIP techniques to deal with nonlinear, potentially non-convex, constraints have been a fruitful direction of research for computational MINLP in the last decade. In this paper, we follow that path in order to extend another essential subroutine of modern MIP solvers towards the case of nonlinear optimization: the analysis of infeasible subproblems for learning additional valid constraints. To this end, we derive two different strategies, geared towards two different solution approaches. These are using local dual proofs of infeasibility for LP-based branch-and-bound and the creation of nonlinear dual proofs for NLP-based branch-and-bound, respectively. We discuss implementation details of both approaches and present an extensive computational study, showing that both techniques can significantly enhance performance when solving MINLPs to global optimality. Y1 - 2021 U6 - https://doi.org/10.1287/ijoc.2020.1050 VL - 33 IS - 2 SP - 421 EP - 435 ER - TY - JOUR A1 - Gamrath, Gerald A1 - Berthold, Timo A1 - Salvagnin, Domenico T1 - An exploratory computational analysis of dual degeneracy in mixed-integer programming JF - EURO Journal on Computational Optimization N2 - Dual degeneracy, i.e., the presence of multiple optimal bases to a linear programming (LP) problem, heavily affects the solution process of mixed integer programming (MIP) solvers. Different optimal bases lead to different cuts being generated, different branching decisions being taken and different solutions being found by primal heuristics. Nevertheless, only a few methods have been published that either avoid or exploit dual degeneracy. The aim of the present paper is to conduct a thorough computational study on the presence of dual degeneracy for the instances of well-known public MIP instance collections. How many instances are affected by dual degeneracy? How degenerate are the affected models? How does branching affect degeneracy: Does it increase or decrease by fixing variables? Can we identify different types of degenerate MIPs? As a tool to answer these questions, we introduce a new measure for dual degeneracy: the variable–constraint ratio of the optimal face. It provides an estimate for the likelihood that a basic variable can be pivoted out of the basis. Furthermore, we study how the so-called cloud intervals—the projections of the optimal face of the LP relaxations onto the individual variables—evolve during tree search and the implications for reducing the set of branching candidates. Y1 - 2020 U6 - https://doi.org/10.1007/s13675-020-00130-z IS - 8 SP - 241 EP - 246 ER - TY - JOUR A1 - Devriendt, Jo A1 - Gleixner, Ambros A1 - Nordström, Jakob T1 - Learn to Relax: Integrating 0-1 Integer Linear Programming with Pseudo-Boolean Conflict-Driven Search JF - Constraints N2 - Conflict-driven pseudo-Boolean solvers optimize 0-1 integer linear programs by extending the conflict-driven clause learning (CDCL) paradigm from SAT solving. Though pseudo-Boolean solvers have the potential to be exponentially more efficient than CDCL solvers in theory, in practice they can sometimes get hopelessly stuck even when the linear programming (LP) relaxation is infeasible over the reals. Inspired by mixed integer programming (MIP), we address this problem by interleaving incremental LP solving with cut generation within the conflict-driven pseudo-Boolean search. This hybrid approach, which for the first time combines MIP techniques with full-blown conflict analysis operating directly on linear inequalities using the cutting planes method, significantly improves performance on a wide range of benchmarks, approaching a "best-of-both-worlds" scenario between SAT-style conflict-driven search and MIP-style branch-and-cut. Y1 - 2021 U6 - https://doi.org/10.1007/s10601-020-09318-x VL - 26 SP - 26 EP - 55 ER - TY - CHAP A1 - Shinano, Yuji A1 - Tateiwa, N. A1 - Nakamura, S. A1 - Yoshida, A. A1 - Yasuda, M. A1 - Kaji, S. A1 - Fujisawa, K. T1 - Massive Parallelization for Finding Shortest Lattice Vectors Based on Ubiquity Generator Framework T2 - 2020 SC20: International Conference for High Performance Computing, Networking, Storage and Analysis (SC) N2 - Lattice-based cryptography has received attention as a next-generation encryption technique, because it is believed to be secure against attacks by classical and quantum computers. Its essential security depends on the hardness of solving the shortest vector problem (SVP). In the cryptography, to determine security levels, it is becoming significantly more important to estimate the hardness of the SVP by high-performance computing. In this study, we develop the world’s first distributed and asynchronous parallel SVP solver, the MAssively Parallel solver for SVP (MAP-SVP). It can parallelize algorithms for solving the SVP by applying the Ubiquity Generator framework, which is a generic framework for branch-and-bound algorithms. The MAP-SVP is suitable for massive-scale parallelization, owing to its small memory footprint, low communication overhead, and rapid checkpoint and restart mechanisms. We demonstrate its performance and scalability of the MAP-SVP by using up to 100,032 cores to solve instances of the Darmstadt SVP Challenge. Y1 - 2020 U6 - https://doi.org/10.1109/SC41405.2020.00064 SP - 834 EP - 848 ER - TY - JOUR A1 - Yokoyama, Ryohei A1 - Shinano, Yuji A1 - Wakayama, Yuki A1 - Wakui, Tetsuya T1 - Model reduction by time aggregation for optimal design of energy supply systems by an MILP hierarchical branch and bound method JF - Energy N2 - Mixed-integer linear programming (MILP) methods have been applied widely to optimal design of energy supply systems in consideration of multi-period operation. A hierarchical MILP method has been proposed to solve such optimal design problems efficiently. An original problem has been solved by dividing it into a relaxed optimal design problem at the upper level and optimal operation problems which are independent of one another at the lower level. In addition, some strategies have been proposed to enhance the computation efficiency furthermore. In this paper, a method of reducing model by time aggregation is proposed as a novel strategy to search design candidates efficiently in the relaxed optimal design problem at the upper level. In addition, the previous strategies are modified in accordance with the novel strategy. This method is realized only by clustering periods and averaging energy demands for clustered periods, while it guarantees to derive the optimal solution. Thus, it may decrease the computation time at the upper level. Through a case study on the optimal design of a gas turbine cogeneration system, it is clarified how the model reduction is effective to enhance the computation efficiency in comparison and combination with the modified previous strategies. Y1 - 2019 U6 - https://doi.org/https://doi.org/10.1016/j.energy.2019.04.066 VL - 181 SP - 782 EP - 792 ER - TY - CHAP A1 - Pfetsch, Marc A1 - Pokutta, Sebastian T1 - IPBoost – Non-Convex Boosting via Integer Programming T2 - Proceedings of ICML Y1 - 2020 N1 - URL of the Code: https://www2.mathematik.tu-darmstadt.de/~pfetsch/ipboost.html N1 - URL of the Slides: https://app.box.com/s/8dpvmls88suouy11bkpwufhu7iiz6dxl N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2020/02/13/ipboost-abstract.html ER - TY - CHAP A1 - Pokutta, Sebastian A1 - Singh, M. A1 - Torrico, A. T1 - On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness T2 - Proceedings of ICML Y1 - 2020 N1 - URL of the Poster: https://app.box.com/s/24vbh1s2vib11upqyepzen3lzdl13skr N1 - URL of the Slides: https://app.box.com/s/fmjxhfdpiqubm28upf563ohy8t8fgl3a N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2020/06/03/unreasonable-abstract.html N1 - https://www.youtube.com/watch?v=VB1e0HrDmVo ER - TY - CHAP A1 - Diakonikolas, Jelena A1 - Carderera, Alejandro A1 - Pokutta, Sebastian T1 - Locally Accelerated Conditional Gradients T2 - Proceedings of AISTATS Y1 - 2020 N1 - URL of the Code: https://colab.research.google.com/drive/1ejjfCan7xnEhWWJXCIzb03CwQRG9iW_O N1 - URL of the PDF: http://proceedings.mlr.press/v108/diakonikolas20a/diakonikolas20a.pdf N1 - URL of the Slides: https://app.box.com/s/gphkhapso7d1vrfnzqykkb3vx0agxh8w N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2019/07/04/LaCG-abstract.html N1 - https://slideslive.com/38930107/locally-accelerated-conditional-gradients?ref=account-folder-52123-folders ER - TY - JOUR A1 - Faenza, Yuri A1 - Muñoz, Gonzalo A1 - Pokutta, Sebastian T1 - New Limits of Treewidth-based tractability in Optimization JF - Mathematical Programming Y1 - 2020 U6 - https://doi.org/10.1007/s10107-020-01563-5 N1 - URL of the PDF: http://link.springer.com/article/10.1007/s10107-020-01563-5 N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2018/09/22/treewidth-abstract.html VL - 191 SP - 559 EP - 594 ER - TY - JOUR A1 - Anari, N. A1 - Haghtalab, N. A1 - Naor, S. A1 - Pokutta, Sebastian A1 - Singh, M. A1 - Torrico, A. T1 - Structured Robust Submodular Maximization: Offline and Online Algorithms JF - INFORMS Journal on Computing Y1 - 2020 ER - TY - CHAP A1 - Combettes, Cyrille W. A1 - Pokutta, Sebastian T1 - Boosting Frank-Wolfe by Chasing Gradients T2 - Proceedings of ICML Y1 - 2020 N1 - Additional Note: github code: https://github.com/cyrillewcombettes/boostfw N1 - URL of the Code: https://colab.research.google.com/drive/1TSOVjDFF1X2ADBo_adHLsUVrblSutRKw N1 - URL of the Slides: https://app.box.com/s/wwj247r5d456q0778p9b9y1jm6txuifb N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2020/03/16/boostFW.html N1 - https://www.youtube.com/watch?v=BfyV0C5FRbE ER -