TY - JOUR A1 - Turner, Mark A1 - Koch, Thorsten A1 - Serrano, Felipe A1 - Winkler, Michael T1 - Adaptive Cut Selection in Mixed-Integer Linear Programming JF - Open Journal of Mathematical Optimization N2 - Cutting plane selection is a subroutine used in all modern mixed-integer linear programming solvers with the goal of selecting a subset of generated cuts that induce optimal solver performance. These solvers have millions of parameter combinations, and so are excellent candidates for parameter tuning. Cut selection scoring rules are usually weighted sums of different measurements, where the weights are parameters. We present a parametric family of mixed-integer linear programs together with infinitely many family-wide valid cuts. Some of these cuts can induce integer optimal solutions directly after being applied, while others fail to do so even if an infinite amount are applied. We show for a specific cut selection rule, that any finite grid search of the parameter space will always miss all parameter values, which select integer optimal inducing cuts in an infinite amount of our problems. We propose a variation on the design of existing graph convolutional neural networks, adapting them to learn cut selection rule parameters. We present a reinforcement learning framework for selecting cuts, and train our design using said framework over MIPLIB 2017 and a neural network verification data set. Our framework and design show that adaptive cut selection does substantially improve performance over a diverse set of instances, but that finding a single function describing such a rule is difficult. Code for reproducing all experiments is available at https://github.com/Opt-Mucca/Adaptive-Cutsel-MILP. Y1 - 2023 U6 - https://doi.org/10.5802/ojmo.25 VL - 4 SP - 5 ER - TY - JOUR A1 - Turner, Mark A1 - Berthold, Timo A1 - Besançon, Mathieu A1 - Koch, Thorsten T1 - Branching via Cutting Plane Selection: Improving Hybrid Branching N2 - Cutting planes and branching are two of the most important algorithms for solving mixed-integer linear programs. For both algorithms, disjunctions play an important role, being used both as branching candidates and as the foundation for some cutting planes. We relate branching decisions and cutting planes to each other through the underlying disjunctions that they are based on, with a focus on Gomory mixed-integer cuts and their corresponding split disjunctions. We show that selecting branching decisions based on quality measures of Gomory mixed-integer cuts leads to relatively small branch-and-bound trees, and that the result improves when using cuts that more accurately represent the branching decisions. Finally, we show how the history of previously computed Gomory mixed-integer cuts can be used to improve the performance of the state-of-the-art hybrid branching rule of SCIP. Our results show a $4\%$ decrease in solve time, and an $8\%$ decrease in number of nodes over affected instances of MIPLIB 2017. Y1 - 2023 PB - Springer ER - TY - JOUR A1 - Anderson, Lovis A1 - Turner, Mark A1 - Koch, Thorsten T1 - Generative deep learning for decision making in gas networks JF - Mathematical Methods of Operations Research 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%. Y1 - 2022 U6 - https://doi.org/10.1007/s00186-022-00777-x VL - 95 SP - 503 EP - 532 PB - Springer Nature ER - TY - JOUR A1 - Hennings, Felix A1 - Anderson, Lovis A1 - Hoppmann-Baum, Kai A1 - Turner, Mark A1 - Koch, Thorsten T1 - Controlling transient gas flow in real-world pipeline intersection areas JF - Optimization and Engineering N2 - Compressor stations are the heart of every high-pressure gas transport network. Located at intersection areas of the network they are contained in huge complex plants, where they are in combination with valves and regulators responsible for routing and pushing the gas through the network. Due to their complexity and lack of data compressor stations are usually dealt with in the scientific literature in a highly simplified and idealized manner. As part of an ongoing project with one of Germany's largest Transmission System Operators to develop a decision support system for their dispatching center, we investigated how to automatize control of compressor stations. Each station has to be in a particular configuration, leading in combination with the other nearby elements to a discrete set of up to 2000 possible feasible operation modes in the intersection area. Since the desired performance of the station changes over time, the configuration of the station has to adapt. Our goal is to minimize the necessary changes in the overall operation modes and related elements over time, while fulfilling a preset performance envelope or demand scenario. This article describes the chosen model and the implemented mixed integer programming based algorithms to tackle this challenge. By presenting extensive computational results on real world data we demonstrate the performance of our approach. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1007/s11081-020-09559-y VL - 22 SP - 687 EP - 734 PB - Springer Nature ET - 2 ER -