@misc{TurnerKochSerranoetal., author = {Turner, Mark and Koch, Thorsten and Serrano, Felipe and Winkler, Michael}, title = {Adaptive Cut Selection in Mixed-Integer Linear Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-86055}, abstract = {Cut 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. 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.}, language = {en} } @misc{KochBertholdPedersenetal., author = {Koch, Thorsten and Berthold, Timo and Pedersen, Jaap and Vanaret, Charlie}, title = {Progress in Mathematical Programming Solvers from 2001 to 2020}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82779}, abstract = {This study investigates the progress made in LP and MILP solver performance during the last two decades by comparing the solver software from the beginning of the millennium with the codes available today. On average, we found out that for solving LP/MILP, computer hardware got about 20 times faster, and the algorithms improved by a factor of about nine for LP and around 50 for MILP, which gives a total speed-up of about 180 and 1,000 times, respectively. However, these numbers have a very high variance and they considerably underestimate the progress made on the algorithmic side: many problem instances can nowadays be solved within seconds, which the old codes are not able to solve within any reasonable time.}, language = {en} } @article{KochBertholdPedersenetal., author = {Koch, Thorsten and Berthold, Timo and Pedersen, Jaap and Vanaret, Charlie}, title = {Progress in mathematical programming solvers from 2001 to 2020}, series = {EURO Journal on Computational Optimization}, volume = {10}, journal = {EURO Journal on Computational Optimization}, doi = {10.1016/j.ejco.2022.100031}, pages = {100031}, abstract = {This study investigates the progress made in lp and milp solver performance during the last two decades by comparing the solver software from the beginning of the millennium with the codes available today. On average, we found out that for solving lp/milp, computer hardware got about 20 times faster, and the algorithms improved by a factor of about nine for lp and around 50 for milp, which gives a total speed-up of about 180 and 1,000 times, respectively. However, these numbers have a very high variance and they considerably underestimate the progress made on the algorithmic side: many problem instances can nowadays be solved within seconds, which the old codes are not able to solve within any reasonable time.}, language = {en} } @article{TurnerKochSerranoetal., author = {Turner, Mark and Koch, Thorsten and Serrano, Felipe and Winkler, Michael}, title = {Adaptive Cut Selection in Mixed-Integer Linear Programming}, series = {Open Journal of Mathematical Optimization}, volume = {4}, journal = {Open Journal of Mathematical Optimization}, doi = {10.5802/ojmo.25}, pages = {5}, abstract = {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.}, language = {en} } @article{AndersonTurnerKoch2022, author = {Anderson, Lovis and Turner, Mark and Koch, Thorsten}, title = {Generative deep learning for decision making in gas networks}, series = {Mathematical Methods of Operations Research}, 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} } @misc{AndersonTurnerKoch, 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}, 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} } @misc{TurnerBertholdBesancon, author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu}, title = {A Context-Aware Cutting Plane Selection Algorithm for Mixed-Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91691}, abstract = {The current cut selection algorithm used in mixed-integer programming solvers has remained largely unchanged since its creation. In this paper, we propose a set of new cut scoring measures, cut filtering techniques, and stopping criteria, extending the current state-of-the-art algorithm and obtaining a 5\\% performance improvement for SCIP over the MIPLIB 2017 benchmark set.}, language = {en} } @phdthesis{Turner, author = {Turner, Mark}, title = {Cutting Plane Selection for Mixed-Integer Linear Programming}, abstract = {Mixed-Integer Linear Programming (MILP) is a ubiquitous and practical modelling paradigm that is essential for optimising a broad range of real-world systems. The backbone of all modern MILP solvers is the branch-and-cut algorithm, which is a hybrid of the branch-and-bound and cutting planes algorithms. Cutting planes (cuts) are linear inequalities that tighten the relaxation of a MILP. While a lot of research has gone into deriving valid cuts for MILPs, less emphasis has been put on determining which cuts to select. Cuts in general are generated in rounds, and a subset of the generated cuts must be added to the relaxation. The decision on which subset of cuts to add is called cut selection. This is a crucial task since adding too many cuts makes the relaxation large and slow to optimise over. Conversely, adding too few cuts results in an insufficiently tightened relaxation, and more relaxations need to be enumerated. To further emphasise the difficulty, the effectiveness of an applied cut is both dependent on the other applied cuts, and the state of the MILP solver. In this thesis, we present theoretical results on the importance and difficulty of cut selection, as well as practical results that use cut selection to improve general MILP solver performance. Improving general MILP solver performance is of great importance for practitioners and has many runoff effects. Reducing the solve time of currently solved systems can directly improve efficiency within the application area. In addition, improved performance enables larger systems to be modelled and optimised, and MILP to be used in areas where it was previously impractical due to time restrictions. Each chapter of this thesis corresponds to a publication on cut selection, where the contributions of this thesis can naturally be divided into four components. The first two components are motivated by instance-dependent performance. In practice, for each subroutine, including cut selection, MILP solvers have adjustable parameters with hard-coded default values. It is ultimately unrealistic to expect these default values to perform well for every instance. Rather, it would be ideal if the parameters were dependent on the given instance. To show this motivation is well founded, we first introduce a family of parametric MILP instances and cuts to showcase worst-case performance of cut selection for any fixed parameter value. We then introduce a graph neural network architecture and reinforcement learning framework for learning instance-dependent cut scoring parameters. In the following component, we formalise language for determining if a cut has theoretical usefulness from a polyhedral point of view in relation to other cuts. In addition, to overcome issues of infeasible projections and dual degeneracy, we introduce analytic center based distance measures. We then construct a lightweight multi-output regression model that predicts relative solver performance of an instance for a set of distance measures. The final two components are motivated by general MILP solver improvement via cut selection. Such improvement was shown to be possible, albeit difficult to achieve, by the first half of this thesis. We relate branch-and-bound and cuts through their underlying disjunctions. Using a history of previously computed Gomory mixed-integer cuts, we reduce the solve time of SCIP over the 67\% of affected MIPLIB 2017 instances by 4\%. In the final component, we introduce new cut scoring measures and filtering methods based on information from other MILP solving processes. The new cut selection techniques reduce the solve time of SCIP over the 97\% of affected MIPLIB 2017 instances by 5\%.}, language = {en} } @misc{TurnerBertholdBesanconetal., author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu and Koch, Thorsten}, title = {Cutting Plane Selection with Analytic Centers and Multiregression}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89065}, abstract = {Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method.}, language = {en} } @misc{TurnerBertholdBesanconetal., author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu and Koch, Thorsten}, title = {Branching via Cutting Plane Selection: Improving Hybrid Branching}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91120}, abstract = {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.}, language = {en} } @misc{TjusilaBesanconTurneretal., author = {Tjusila, Gennesaret and Besancon, Mathieu and Turner, Mark and Koch, Thorsten}, title = {How Many Clues To Give? A Bilevel Formulation For The Minimum Sudoku Clue Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-90902}, abstract = {It has been shown that any 9 by 9 Sudoku puzzle must contain at least 17 clues to have a unique solution. This paper investigates the more specific question: given a particular completed Sudoku grid, what is the minimum number of clues in any puzzle whose unique solution is the given grid? We call this problem the Minimum Sudoku Clue Problem (MSCP). We formulate MSCP as a binary bilevel linear program, present a class of globally valid inequalities, and provide a computational study on 50 MSCP instances of 9 by 9 Sudoku grids. Using a general bilevel solver, we solve 95\\% of instances to optimality, and show that the solution process benefits from the addition of a moderate amount of inequalities. Finally, we extend the proposed model to other combinatorial problems in which uniqueness of the solution is of interest.}, language = {en} } @article{TurnerBertholdBesanconetal., author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu and Koch, Thorsten}, title = {Branching via Cutting Plane Selection: Improving Hybrid Branching}, publisher = {Springer}, abstract = {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.}, language = {en} } @inproceedings{TurnerBertholdBesancon, author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu}, title = {A Context-Aware Cutting Plane Selection Algorithm for Mixed-Integer Programming}, abstract = {The current cut selection algorithm used in mixed-integer programming solvers has remained largely unchanged since its creation. In this paper, we propose a set of new cut scoring measures, cut filtering techniques, and stopping criteria, extending the current state-of-the-art algorithm and obtaining a 5\\% performance improvement for SCIP over the MIPLIB 2017 benchmark set.}, language = {en} } @misc{CaoAndersonBoehmeetal., author = {Cao, Karl-Kien and Anderson, Lovis and B{\"o}hme, Aileen and Breuer, Thomas and Buschmann, Jan and Fiand, Frederick and Frey, Ulrich and Fuchs, Benjamin and Kempe, Nils-Christian and von Krbek, Kai and Medjroubi, Wided and Riehm, Judith and Sasanpour, Shima and Simon, Sonja and Vanaret, Charlie and Wetzel, Manuel and Xiao, Mengzhu and Zittel, Janina}, title = {Evaluation of Uncertainties in Linear-Optimizing Energy System Models - Compendium}, series = {DLR-Forschungsbericht}, journal = {DLR-Forschungsbericht}, number = {DLR-FB-2023-15}, doi = {10.57676/w2rq-bj85}, pages = {95}, abstract = {F{\"u}r die Energiesystemforschung sind Software-Modelle ein Kernelement zur Analyse von Szenarien. Das Forschungsprojekt UNSEEN hatte das Ziel eine bisher unerreichte Anzahl an modellbasierten Energieszenarien zu berechnen, um Unsicherheiten - vor allem unter Nutzung linear optimierender Energiesystem-Modelle - besser bewerten zu k{\"o}nnen. Hierf{\"u}r wurden umfangreiche Parametervariationen auf Energieszenarien angewendet und das wesentliche methodische Hindernis in diesem Zusammenhang adressiert: die rechnerische Beherrschbarkeit der zu l{\"o}senden mathematischen Optimierungsprobleme. Im Vorl{\"a}uferprojekt BEAM-ME wurde mit der Entwicklung und Anwendung des Open-Source-L{\"o}sers PIPS-IPM++ die Grundlage f{\"u}r den Einsatz von High-Performance-Computing (HPC) zur L{\"o}sung dieser Modelle gelegt. In UNSEEN war dieser L{\"o}ser die zentrale Komponente eines Workflows, welcher zur Generierung, L{\"o}sung und multi-kriteriellen Bewertung von Energieszenarien auf dem Hochleistungscomputer JUWELS am Forschungszentrum J{\"u}lich implementiert wurde. Zur effizienten Generierung und Kommunikation von Modellinstanzen f{\"u}r Methoden der mathematischen Optimierung auf HPC wurde eine weitere Workflow-Komponente von der GAMS Software GmbH entwickelt: der Szenariogenerator. Bei der Weiterentwicklung von L{\"o}sungsalgorithmen f{\"u}r linear optimierende Energie-Systemmodelle standen gemischt-ganzzahlige Optimierungsprobleme im Fokus, welche f{\"u}r die Modellierung konkreter Infrastrukturen und Maßnahmen zur Umsetzung der Energiewende gel{\"o}st werden m{\"u}ssen. Die in diesem Zusammenhang stehenden Arbeiten zur Entwicklung von Algorithmen wurden von der Technischen Universit{\"a}t Berlin verantwortet. Bei Design und Implementierung dieser Methoden wurde sie vom Zuse Instituts Berlin unterst{\"u}tzt.}, language = {en} } @inproceedings{TurnerBertholdBesanconetal., author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu and Koch, Thorsten}, title = {Cutting Plane Selection with Analytic Centers and Multiregression}, series = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2023.}, volume = {13884}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2023.}, publisher = {Springer}, doi = {10.1007/978-3-031-33271-5_4}, pages = {52 -- 68}, abstract = {Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method.}, language = {en} } @article{Vanaret, author = {Vanaret, Charlie}, title = {Interval constraint programming for globally solving catalog-based categorical optimization}, series = {Journal of Global Optimization}, volume = {89}, journal = {Journal of Global Optimization}, doi = {10.1007/s10898-023-01362-0}, pages = {457 -- 476}, abstract = {In this article, we propose an interval constraint programming method for globally solving catalog-based categorical optimization problems. It supports catalogs of arbitrary size and properties of arbitrary dimension, and does not require any modeling effort from the user. A novel catalog-based contractor (or filtering operator) guarantees consistency between the categorical properties and the existing catalog items. This results in an intuitive and generic approach that is exact, rigorous (robust to roundoff errors) and can be easily implemented in an off-the-shelf interval-based continuous solver that interleaves branching and constraint propagation. We demonstrate the validity of the approach on a numerical problem in which a categorical variable is described by a two-dimensional property space. A Julia prototype is available as open-source software under the MIT license.}, language = {en} }