@misc{PrauseHoppmannBaumDefournyetal.2020, author = {Prause, Felix and Hoppmann-Baum, Kai and Defourny, Boris and Koch, Thorsten}, title = {The Maximum Diversity Assortment Selection Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81039}, year = {2020}, abstract = {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.}, language = {en} } @misc{AndersonTurnerKoch2020, author = {Anderson, Lovis and Turner, Mark and Koch, Thorsten}, title = {Generative deep learning for decision making in gas networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81103}, year = {2020}, abstract = {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\%.}, language = {en} } @article{StreubelTischendorfGriewank2020, author = {Streubel, Tom and Tischendorf, Caren and Griewank, Andreas}, title = {Piecewise Polynomial Taylor Expansions - The Generalization of Fa{\`a} di Bruno's Formula}, journal = {Modeling, Simulation and Optimization of Complex Processes HPSC 2018}, number = {Modeling, Simulation and Optimization of Complex Processes HPSC 2018}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-030-55240-4_3}, pages = {63 -- 82}, year = {2020}, abstract = {We present an extension of Taylor's Theorem for the piecewise polynomial expansion of non-smooth evaluation procedures involving absolute value operations. Evaluation procedures are computer programs of mathematical functions in closed form expression and allow a different treatment of smooth operations or calls to the absolute value function. The well known classical Theorem of Taylor defines polynomial approximations of sufficiently smooth functions and is widely used for the derivation and analysis of numerical integrators for systems of ordinary differential- or differential-algebraic equations, for the construction of solvers for continuous non-linear optimization of finite dimensional objective functions and for root solving of non-linear systems of equations. The long term goal is the stabilization and acceleration of already known methods and the derivation of new methods by incorporating piecewise polynomial Taylor expansions. The herein provided proof of the higher order approximation quality of the new generalized expansions is constructive and allows efficiently designed algorithms for the execution and computation of the piecewise polynomial expansions. As a demonstration towards the ultimate goal we will derive a prototype of a {\\$}{\\$}k{\\$}{\\$}k-step method on the basis of polynomial interpolation and the proposed generalized expansions.}, language = {en} } @article{HoppmannBaumHenningsZitteletal.2021, author = {Hoppmann-Baum, Kai and Hennings, Felix and Zittel, Janina and Gotzes, Uwe and Spreckelsen, Eva-Maria and Spreckelsen, Klaus and Koch, Thorsten}, title = {An Optimization Approach for the Transient Control of Hydrogen Transport Networks}, journal = {Mathematical Methods of Operations Research}, number = {Special Issue on Energy Networks}, year = {2021}, language = {en} } @misc{HoppmannBaumMexiBurdakovetal.2020, author = {Hoppmann-Baum, Kai and Mexi, Gioni and Burdakov, Oleg and Casselgren, Carl Johan and Koch, Thorsten}, title = {Length-Constrained Cycle Partition with an Application to UAV Routing}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-80489}, year = {2020}, abstract = {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.}, language = {en} } @article{GotzesHoppmannBaum2020, author = {Gotzes, Uwe and Hoppmann-Baum, Kai}, title = {Bounding the final rank during a round robin tournament with integer programming}, volume = {1866-1505}, journal = {Operational Research}, doi = {https://doi.org/10.1007/s12351-020-00546-w}, year = {2020}, abstract = {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.}, language = {en} } @misc{RehfeldtKoch2020, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {Implications, conflicts, and reductions for Steiner trees}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-80039}, year = {2020}, language = {en} } @misc{HoppmannBaumHenningsZitteletal.2020, author = {Hoppmann-Baum, Kai and Hennings, Felix and Zittel, Janina and Gotzes, Uwe and Spreckelsen, Eva-Maria and Spreckelsen, Klaus and Koch, Thorsten}, title = {From Natural Gas towards Hydrogen - A Feasibility Study on Current Transport Network Infrastructure and its Technical Control}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-79901}, year = {2020}, abstract = {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.}, language = {en} } @article{HoppmannBaumHenningsLenzetal.2021, author = {Hoppmann-Baum, Kai and Hennings, Felix and Lenz, Ralf and Gotzes, Uwe and Heinecke, Nina and Spreckelsen, Klaus and Koch, Thorsten}, title = {Optimal Operation of Transient Gas Transport Networks}, volume = {22}, journal = {Optimization and Engineering}, doi = {10.1007/s11081-020-09584-x}, pages = {735 -- 781}, year = {2021}, abstract = {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.}, language = {en} } @article{GriewankStreubelTischendorf2020, author = {Griewank, Andreas and Streubel, Tom and Tischendorf, Caren}, title = {On the abs-polynomial expansion of piecewise smooth functions}, journal = {Optimization Methods and Software}, publisher = {Taylor \& Francis}, doi = {10.1080/10556788.2020.1817448}, year = {2020}, abstract = {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.}, language = {en} } @incollection{HoppmannBaumMexiBurdakovetal.2020, author = {Hoppmann-Baum, Kai and Mexi, Gioni and Burdakov, Oleg and Casselgren, Carl Johan and Koch, Thorsten}, title = {Minimum Cycle Partition with Length Requirements}, volume = {12296}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research}, editor = {Hebrard, Emmanuel and Musliu, Nysret}, publisher = {Springer International Publishing}, address = {Cham}, isbn = {978-3-030-58941-7}, doi = {10.1007/978-3-030-58942-4_18}, pages = {273 -- 282}, year = {2020}, abstract = {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.}, language = {en} }