@misc{Shinano2021, author = {Shinano, Yuji}, title = {UG - Ubiquity Generator Framework v1.0.0beta}, doi = {10.12752/8521}, year = {2021}, abstract = {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. v1.0.0: new documentation and cmake, generalization of ug framework, implementation of selfsplitrampup for fiber- and parascip, better memory and time limit handling.}, language = {en} } @inproceedings{SofranacGleixnerPokutta2021, author = {Sofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {An Algorithm-Independent Measure of Progress for Linear Constraint Propagation}, volume = {210}, booktitle = {27th International Conference on Principles and Practice of Constraint Programming (CP 2021)}, doi = {10.4230/LIPIcs.CP.2021.52}, pages = {52:1 -- 52:17}, year = {2021}, abstract = {Propagation of linear constraints has become a crucial sub-routine in modern Mixed-Integer Programming (MIP) solvers. In practice, iterative algorithms with tolerance-based stopping criteria are used to avoid problems with slow or infinite convergence. However, these heuristic stopping criteria can pose difficulties for fairly comparing the efficiency of different implementations of iterative propagation algorithms in a real-world setting. Most significantly, the presence of unbounded variable domains in the problem formulation makes it difficult to quantify the relative size of reductions performed on them. In this work, we develop a method to measure -- independently of the algorithmic design -- the progress that a given iterative propagation procedure has made at a given point in time during its execution. Our measure makes it possible to study and better compare the behavior of bounds propagation algorithms for linear constraints. We apply the new measure to answer two questions of practical relevance: (i) We investigate to what extent heuristic stopping criteria can lead to premature termination on real-world MIP instances. (ii) We compare a GPU-parallel propagation algorithm against a sequential state-of-the-art implementation and show that the parallel version is even more competitive in a real-world setting than originally reported.}, language = {en} } @misc{KempkeRehfeldtKoch2024, author = {Kempke, Nils-Christian and Rehfeldt, Daniel and Koch, Thorsten}, title = {A Massively Parallel Interior-Point-Method for Arrowhead Linear Programs}, issn = {1438-0064}, arxiv = {http://arxiv.org/abs/2412.07731}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-98829}, year = {2024}, abstract = {In practice, non-specialized interior point algorithms often cannot utilize the massively parallel compute resources offered by modern many- and multi-core compute platforms. However, efficient distributed solution techniques are required, especially for large-scale linear programs. This article describes a new decomposition technique for systems of linear equations implemented in the parallel interior-point solver PIPS-IPM++. The algorithm exploits a matrix structure commonly found in optimization problems: a doubly-bordered block-diagonal or arrowhead structure. This structure is preserved in the linear KKT systems solved during each iteration of the interior-point method. We present a hierarchical Schur complement decomposition that distributes and solves the linear optimization problem; it is designed for high-performance architectures and scales well with the availability of additional computing resources. The decomposition approach uses the border constraints' locality to decouple the factorization process. Our approach is motivated by large-scale unit-commitment problems. We demonstrate the performance of our method on a set of mid-to large-scale instances, some of which have more than 10^9 nonzeros in their constraint matrix.}, language = {en} } @article{VanBulckGoossensClarneretal.2024, author = {Van Bulck, David and Goossens, Dries and Clarner, Jan-Patrick and Dimitsas, Angelos and Fonseca, Georg H. G. and Lamas-Fernandez, Carlos and Lester, Martin Mariusz and Pedersen, Jaap and Phillips, Antony E. and Rosati, Roberto Maria}, title = {Which algorithm to select in sports timetabling?}, volume = {318}, journal = {European Journal of Operational Research}, number = {2}, arxiv = {http://arxiv.org/abs/2309.03229}, doi = {10.1016/j.ejor.2024.06.005}, pages = {575 -- 591}, year = {2024}, abstract = {Any sports competition needs a timetable, specifying when and where teams meet each other. The recent International Timetabling Competition (ITC2021) on sports timetabling showed that, although it is possible to develop general algorithms, the performance of each algorithm varies considerably over the problem instances. This paper provides a problem type analysis for sports timetabling, resulting in powerful insights into the strengths and weaknesses of eight state-of-the-art algorithms. Based on machine learning techniques, we propose an algorithm selection system that predicts which algorithm is likely to perform best based on the type of competition and constraints being used (i.e., the problem type) in a given sports timetabling problem instance. Furthermore, we visualize how the problem type relates to algorithm performance, providing insights and possibilities to further enhance several algorithms. Finally, we assess the empirical hardness of the instances. Our results are based on large computational experiments involving about 50 years of CPU time on more than 500 newly generated problem instances.}, language = {en} } @inproceedings{PedersenHoppmannBaumZitteletal.2022, author = {Pedersen, Jaap and Hoppmann-Baum, Kai and Zittel, Janina and Koch, Thorsten}, title = {Blending hydrogen into natural gas: An assessment of the capacity of the German gas grid}, booktitle = {Operations Research Proceedings 2021}, doi = {https://doi.org/10.1007/978-3-031-08623-6_28}, pages = {182 -- 187}, year = {2022}, abstract = {In the transition towards a pure hydrogen infrastructure, repurposing the existing natural gas infrastructure is considered. In this study, the maximal technically feasible injection of hydrogen into the existing German natural gas transmission network is analysed with respect to regulatory limits regarding the gas quality. We propose a transient tracking model based on the general pooling problem including linepack. The analysis is conducted using real-world hourly gas flow data on a network of about 10,000 km length.}, language = {en} } @article{Hennings2021, author = {Hennings, Felix}, title = {Large-scale empirical study on the momentum equation's inertia term}, volume = {95}, journal = {Journal of Natural Gas Science and Engineering}, publisher = {Elsevier}, doi = {10.1016/j.jngse.2021.104153}, year = {2021}, abstract = {A common approach to reduce the Euler equations' complexity for the simulation and optimization of gas networks is to neglect small terms that contribute little to the overall equations. An example is the inertia term of the momentum equation, which is said to be of negligible size under real-world operating conditions. However, this justification has always only been based on experience or single sets of artificial data points. This study closes this gap by presenting a large-scale empirical evaluation of the absolute and relative size of the inertia term when operating a real-world gas network. Our data consists of three years of fine-granular state data of one of the largest gas networks in Europe, featuring over 6,000 pipes with a total length of over 10,000 km. We found that there are only 120 events in which a subnetwork consisting of multiple pipes has an inertia term of high significance for more than three minutes. On average, such an event occurs less often than once every ten days. Therefore, we conclude that the inertia term is indeed negligible for real-world transient gas network control problems.}, language = {en} } @article{HoppmannBaum2021, author = {Hoppmann-Baum, Kai}, title = {On the Complexity of Computing Maximum and Minimum Min-Cost-Flows}, journal = {Networks}, doi = {10.1002/net.22060}, year = {2021}, abstract = {Consider a flow network, i.e., a directed graph where each arc has a nonnegative capacity value and an associated length, together with nonempty supply intervals for the sources and nonempty demand intervals for the sinks. The Maximum Min-Cost-Flow Problem (MaxMCF) is to find fixed supply and demand values within these intervals such that the optimal objective value of the induced Min-Cost-Flow Problem (MCF) is maximized. In this paper, we show that MaxMCF as well as its uncapacitated variant, the Maximum Transportation Problem (MaxTP), are NP-hard. Further, we prove that MaxMCF is APX-hard if a connectedness-condition regarding the sources and the sinks of the flow network is dropped. Finally, we show how the Minimum Min-Cost-Flow Problem (MinMCF) can be solved in polynomial time.}, language = {en} } @misc{Hennings2021, author = {Hennings, Felix}, title = {Large-scale empirical study on the momentum equation's inertia term}, issn = {1438-0064}, doi = {10.1016/j.jngse.2021.104153}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81881}, year = {2021}, abstract = {A common approach to reduce the Euler equations' complexity for the simulation and optimization of gas networks is to neglect small terms that contribute little to the overall equations. An example is the inertia term of the momentum equation since it is said to be of negligible size under real-world operating conditions. However, this justification has always only been based on experience or single sets of artificial data points. This study closes this gap by presenting a large-scale empirical evaluation of the absolute and relative size of the inertia term when operating a real-world gas network. Our data consists of three years of fine-granular state data of one of the largest gas networks in Europe, featuring over 6,000 pipes with a total length of over 10,000 km. We found that there are only 120 events in which a subnetwork consisting of multiple pipes has an inertia term of high significance for more than three minutes. On average, such an event occurs less often than once every ten days. Therefore, we conclude that the inertia term is indeed negligible for real-world transient gas network control problems.}, language = {en} } @article{AndersonTurnerKoch2022, author = {Anderson, Lovis and Turner, Mark and Koch, Thorsten}, title = {Generative deep learning for decision making in gas networks}, volume = {95}, journal = {Mathematical Methods of Operations Research}, publisher = {Springer Nature}, doi = {10.1007/s00186-022-00777-x}, pages = {503 -- 532}, year = {2022}, 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} } @inproceedings{SofranacGleixnerPokutta2020, author = {Sofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices}, booktitle = {2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3)}, arxiv = {http://arxiv.org/abs/2009.07785}, doi = {10.1109/IA351965.2020.00007}, pages = {1 -- 11}, year = {2020}, abstract = {Fast domain propagation of linear constraints has become a crucial component of today's best algorithms and solvers for mixed integer programming and pseudo-boolean optimization to achieve peak solving performance. Irregularities in the form of dynamic algorithmic behaviour, dependency structures, and sparsity patterns in the input data make efficient implementations of domain propagation on GPUs and, more generally, on parallel architectures challenging. This is one of the main reasons why domain propagation in state-of-the-art solvers is single thread only. In this paper, we present a new algorithm for domain propagation which (a) avoids these problems and allows for an efficient implementation on GPUs, and is (b) capable of running propagation rounds entirely on the GPU, without any need for synchronization or communication with the CPU. We present extensive computational results which demonstrate the effectiveness of our approach and show that ample speedups are possible on practically relevant problems: on state-of-the-art GPUs, our geometric mean speed-up for reasonably-large instances is around 10x to 20x and can be as high as 195x on favorably-large instances.}, language = {en} } @misc{HenningsPetkovicStreubel2021, author = {Hennings, Felix and Petkovic, Milena and Streubel, Tom}, title = {On the Numerical Treatment of Interlaced Target Values - Modeling, Optimization and Simulation of Regulating Valves in Gas Networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-85359}, year = {2021}, abstract = {Due to the current and foreseeable shifts in energy production, 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 full 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 commercial simulation tool SIMONE.}, language = {en} }