@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} } @article{ŠofranacGleixnerPokutta2022, author = {Šofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {Accelerating domain propagation: An efficient GPU-parallel algorithm over sparse matrices}, volume = {109}, journal = {Parallel Computing}, doi = {10.1016/j.parco.2021.102874}, pages = {102874}, year = {2022}, abstract = {• Currently, domain propagation in state-of-the-art MIP solvers is single thread only. • The paper presents a novel, efficient GPU algorithm to perform domain propagation. • Challenges are dynamic algorithmic behavior, dependency structures, sparsity patterns. • The algorithm is capable of running entirely on the GPU with no CPU involvement. • We achieve speed-ups of around 10x to 20x, up to 180x on favorably-large instances.}, language = {en} } @article{PedersenSpreckelsenGotzesetal.2023, author = {Pedersen, Jaap and Spreckelsen, Klaus and Gotzes, Uwe and Zittel, Janina and Koch, Thorsten}, title = {Beimischung von Wasserstoff zum Erdgas: Eine Kapazit{\"a}tsstudie des deutschen Gasnetzes}, journal = {gwf Gas + Energie}, edition = {06/2023}, publisher = {Vulkan Verlag}, year = {2023}, abstract = {Die europaische Gasinfrastruktur wird disruptiv in ein zukunftiges dekarbonisiertes Energiesystem ver{\"a}ndert; ein Prozess, der angesichts der j{\"u}ngsten politischen Situation beschleunigt werden muss. Mit einem wachsenden Wasserstoffmarkt wird der pipelinebasierte Transport unter Nutzung der bestehenden Erdgasinfrastruktur wirtschaftlich sinnvoll, tr{\"a}gt zur Erh{\"o}hung der {\"o}ffentlichen Akzeptanz bei und beschleunigt den Umstellungsprozess. In diesem Beitrag wird die maximal technisch machbare Einspeisung von Wasserstoff in das bestehende deutsche Erdgastransportnetz hinsichtlich regulatorischer Grenzwerte der Gasqualit{\"a}t analysiert. Die Analyse erfolgt auf Basis eines transienten Tracking-Modells, das auf dem allgemeinen Pooling-Problem einschließlich Linepack aufbaut. Es zeigt sich, dass das Gasnetz auch bei strengen Grenzwerten gen ̈ugend Kapazit{\"a}t bietet, um f{\"u}r einen großen Teil der bis 2030 geplanten Erzeugungskapazit{\"a}t f{\"u}r gr{\"u}nen Wasserstoff als garantierter Abnehmer zu dienen.}, language = {de} } @article{LeKoch2023, author = {Le, Thi Thai and Koch, Thorsten}, title = {Effect of inertia force on the interface stability of a tangential-velocity discontinuity in porous media}, volume = {169}, journal = {International Journal of Multiphase Flow}, doi = {10.1016/j.ijmultiphaseflow.2023.104612}, year = {2023}, abstract = {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.}, language = {en} } @phdthesis{HoppmannBaum2022, author = {Hoppmann-Baum, Kai}, title = {Mathematical programming for stable control and safe operation of gas transport networks}, publisher = {TU Berlin}, doi = {10.14279/depositonce-15837}, year = {2022}, abstract = {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.}, language = {en} } @misc{PedersenWeinandSyranidouetal.2023, author = {Pedersen, Jaap and Weinand, Jann Michael and Syranidou, Chloi and Rehfeldt, Daniel}, title = {An efficient solver for multi-objective onshore wind farm siting and network integration}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-90590}, year = {2023}, abstract = {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.}, language = {en} } @phdthesis{Hennings2023, author = {Hennings, Felix}, title = {Modeling and solving real-world transient gas network transport problems using mathematical programming}, year = {2023}, abstract = {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.}, language = {en} } @article{HenningsPetkovicStreubel2024, 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}, volume = {25}, journal = {Optimization and Engineering}, publisher = {Springer Nature}, doi = {10.1007/s11081-023-09812-0}, pages = {491 -- 527}, year = {2024}, abstract = {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.}, language = {en} } @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} }