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 - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Implications, conflicts, and reductions for Steiner trees T3 - ZIB-Report - 20-28 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-80039 SN - 1438-0064 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 - JOUR A1 - Griewank, Andreas A1 - Streubel, Tom A1 - Tischendorf, Caren T1 - On the abs-polynomial expansion of piecewise smooth functions JF - Optimization Methods and Software N2 - Tom Streubel has observed that for functions in abs-normal form, generalized Taylor expansions of arbitrary order $\bar d-1$ can be generated by algorithmic piecewise differentiation. Abs-normal form means that the real or vector valued function is defined by an evaluation procedure that involves the absolute value function $|...|$ apart from arithmetic operations and $\bar d$ times continuously differentiable univariate intrinsic functions. The additive terms in Streubel's expansion are abs-polynomial, i.e. involve neither divisions nor intrinsics. When and where no absolute values occur, Moore's recurrences can be used to propagate univariate Taylor polynomials through the evaluation procedure with a computational effort of $\mathcal O({\bar d}^2)$, provided all univariate intrinsics are defined as solutions of linear ODEs. This regularity assumption holds for all standard intrinsics, but for irregular elementaries one has to resort to Faa di Bruno's formula, which has exponential complexity in $\bar d$. As already conjectured we show that the Moore recurrences can be adapted for regular intrinsics to the abs-normal case. Finally, we observe that where the intrinsics are real analytic the expansions can be extended to infinite series that converge absolutely on spherical domains. Y1 - 2020 U6 - https://doi.org/10.1080/10556788.2020.1817448 PB - Taylor & Francis 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 - Prause, Felix A1 - Hoppmann-Baum, Kai A1 - Defourny, Boris A1 - Koch, Thorsten T1 - The maximum diversity assortment selection problem JF - Mathematical Methods of Operations Research N2 - In this article, we introduce the Maximum Diversity Assortment Selection Problem (MDASP), which is a generalization of the two-dimensional Knapsack Problem (2D-KP). Given a set of rectangles and a rectangular container, the goal of 2D-KP 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. MDASP is 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 the minimum or average normalized Hamming distance of all assortment pairs. MDASP was the topic of the 11th AIMMS-MOPTA Competition in 2019. The methods described in this article and the resulting 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 2D-KP literature. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1007/s00186-021-00740-2 VL - 93 SP - 521 EP - 554 PB - Mathematical Methods of Operations Research ER - TY - GEN A1 - Yueksel-Erguen, Inci A1 - Zittel, Janina A1 - Wang, Ying A1 - Hennings, Felix A1 - Koch, Thorsten T1 - Lessons learned from gas network data preprocessing N2 - The German high-pressure natural gas transport network consists of thousands of interconnected elements spread over more than 120,000 km of pipelines built during the last 100 years. During the last decade, we have spent many person-years to extract consistent data out of the available sources, both public and private. Based on two case studies, we present some of the challenges we encountered. Preparing consistent, high-quality data is surprisingly hard, and the effort necessary can hardly be overestimated. Thus, it is particularly important to decide which strategy regarding data curation to adopt. Which precision of the data is necessary? When is it more efficient to work with data that is just sufficiently correct on average? In the case studies we describe our experiences and the strategies we adopted to deal with the obstacles and to minimize future effort. Finally, we would like to emphasize that well-compiled data sets, publicly available for research purposes, provide the grounds for building innovative algorithmic solutions to the challenges of the future. T3 - ZIB-Report - 20-13 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78262 SN - 1438-0064 ER - TY - GEN A1 - Griewank, Andreas A1 - Streubel, Tom A1 - Tischendorf, Caren T1 - On the abs-polynomial expansion of piecewise smooth functions N2 - Tom Streubel has observed that for functions in abs-normal form, generalized Taylor expansions of arbitrary order $\bar d-1$ can be generated by algorithmic piecewise differentiation. Abs-normal form means that the real or vector valued function is defined by an evaluation procedure that involves the absolute value function $|...|$ apart from arithmetic operations and $\bar d$ times continuously differentiable univariate intrinsic functions. The additive terms in Streubel's expansion are abs-polynomial, i.e. involve neither divisions nor intrinsics. When and where no absolute values occur, Moore's recurrences can be used to propagate univariate Taylor polynomials through the evaluation procedure with a computational effort of $\mathcal O({\bar d}^2)$, provided all univariate intrinsics are defined as solutions of linear ODEs. This regularity assumption holds for all standard intrinsics, but for irregular elementaries one has to resort to Faa di Bruno's formula, which has exponential complexity in $\bar d$. As already conjectured we show that the Moore recurrences can be adapted for regular intrinsics to the abs-normal case. Finally, we observe that where the intrinsics are real analytic the expansions can be extended to infinite series that converge absolutely on spherical domains. T3 - ZIB-Report - 20-14 KW - Nonsmooth Taylor polynomial/series KW - forward mode propagation KW - abs-normal form KW - abs-linear form KW - absolute convergence KW - Moore recurrences KW - quadratic complexity Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78448 SN - 1438-0064 ER -