Dokument-ID Dokumenttyp Verfasser/Autoren Herausgeber Haupttitel Abstract Auflage Verlagsort Verlag Erscheinungsjahr Seitenzahl Schriftenreihe Titel Schriftenreihe Bandzahl ISBN Quelle der Hochschulschrift Konferenzname Quelle:Titel Quelle:Jahrgang Quelle:Heftnummer Quelle:Erste Seite Quelle:Letzte Seite URN DOI Abteilungen OPUS4-6936 misc Gleixner, Ambros; Bastubbe, Michael; Eifler, Leon; Gally, Tristan; Gamrath, Gerald; Gottwald, Robert Lion; Hendel, Gregor; Hojny, Christopher; Koch, Thorsten; Lübbecke, Marco; Maher, Stephen J.; Miltenberger, Matthias; Müller, Benjamin; Pfetsch, Marc; Puchert, Christian; Rehfeldt, Daniel; Schlösser, Franziska; Schubert, Christoph; Serrano, Felipe; Shinano, Yuji; Viernickel, Jan Merlin; Walter, Matthias; Wegscheider, Fabian; Witt, Jonas T.; Witzig, Jakob The SCIP Optimization Suite 6.0 The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion for cutting planes, one focus of this release are decomposition algorithms. Both SCIP and the automatic decomposition solver GCG now include advanced functionality for performing Benders' decomposition in a generic framework. GCG's detection loop for structured matrices and the coordination of pricing routines for Dantzig-Wolfe decomposition has been significantly revised for greater flexibility. Two SCIP extensions have been added to solve the recursive circle packing problem by a problem-specific column generation scheme and to demonstrate the use of the new Benders' framework for stochastic capacitated facility location. Last, not least, the report presents updates and additions to the other components and extensions of the SCIP Optimization Suite: the LP solver SoPlex, the modeling language Zimpl, the parallelization framework UG, the Steiner tree solver SCIP-Jack, and the mixed-integer semidefinite programming solver SCIP-SDP. 2018 urn:nbn:de:0297-zib-69361 Mathematical Optimization OPUS4-6460 Konferenzveröffentlichung Miltenberger, Matthias; Ralphs, Ted; Steffy, Daniel Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether such predictions can be used to make better algorithmic choices. In a first step towards this goal, we discuss here the numerical behavior of an existing solver in order to determine whether our intuitive understanding of this behavior is correct. Springer International Publishing 2018 6 Operations Research Proceedings 2017 151 157 10.1007/978-3-319-89920-6 Mathematical Optimization OPUS4-6464 misc Miltenberger, Matthias; Ralphs, Ted; Steffy, Daniel Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether such predictions can be used to make better algorithmic choices. In a first step towards this goal, we discuss here the numerical behavior of an existing solver in order to determine whether our intuitive understanding of this behavior is correct. 2017 Operations Research Proceedings 2017 urn:nbn:de:0297-zib-64645 Mathematical Optimization OPUS4-5771 Konferenzveröffentlichung Cao, Karl-Kiên; Gleixner, Ambros; Miltenberger, Matthias Methoden zur Reduktion der Rechenzeit linearer Optimierungsmodelle in der Energiewirtschaft - Eine Performance-Analyse Dieser Beitrag stellt mögliche Ansätze zur Reduktion der Rechenzeit von linearen Optimierungsproblemen mit energiewirtschaftlichem Anwendungshintergrund vor. Diese Ansätze bilden im Allgemeinen die Grundlage für konzeptionelle Strategien zur Beschleunigung von Energiesystemmodellen. Zu den einfachsten Beschleunigungsstrategien zählt die Verkleinerung der Modelldimensionen, was beispielsweise durch Ändern der zeitlichen, räumlichen oder technologischen Auflösung eines Energiesystemmodells erreicht werden kann. Diese Strategien sind zwar häufig ein Teil der Methodik in der Energiesystemanalyse, systematische Benchmarks zur Bewertung ihrer Effektivität werden jedoch meist nicht durchgeführt. Die vorliegende Arbeit adressiert genau diesen Sachverhalt. Hierzu werden Modellinstanzen des Modells REMix in verschiedenen Größenordnungen mittels einer Performance-Benchmark-Analyse untersucht. Die Ergebnisse legen zum einen den Schluss nahe, dass verkürzte Betrachtungszeiträume das größte Potential unter den hier analysierten Strategien zur Reduktion von Rechenzeit bieten. Zum anderen empfiehlt sich die Verwendung des Barrier-Lösungsverfahrens mit multiplen Threads unter Vernachlässigung des Cross-Over. 2016 EnInnov 2016: 14. Symposium Energieinnovation 2016 Mathematical Optimization OPUS4-6110 misc Gamrath, Gerald; Gleixner, Ambros; Koch, Thorsten; Miltenberger, Matthias; Kniasew, Dimitri; Schlögel, Dominik; Martin, Alexander; Weninger, Dieter Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming SAP's decision support systems for optimized supply network planning rely on mixed-integer programming as the core engine to compute optimal or near-optimal solutions. The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of a robust and future-proof decision support system for a large and diverse customer base. In this paper we describe our coordinated efforts to ensure that the performance of the underlying solution algorithms matches the complexity of the large supply chain problems and tight time limits encountered in practice. 2016 urn:nbn:de:0297-zib-61107 10.4208/jcm.1905-m2019-0055 Mathematical Optimization OPUS4-3290 Masterarbeit / Diplomarbeit Miltenberger, Matthias Die IDR(s)-Methode zur Lösung von parametrisierten Gleichungssystemen 2009 Mathematical Optimization OPUS4-5668 Wissenschaftlicher Artikel Gamrath, Gerald; Koch, Thorsten; Martin, Alexander; Miltenberger, Matthias; Weninger, Dieter Progress in presolving for mixed integer programming This paper describes three presolving techniques for solving mixed integer programming problems (MIPs) that were implemented in the academic MIP solver SCIP. The task of presolving is to reduce the problem size and strengthen the formulation, mainly by eliminating redundant information and exploiting problem structures. The first method fixes continuous singleton columns and extends results known from duality fixing. The second analyzes and exploits pairwise dominance relations between variables, whereas the third detects isolated subproblems and solves them independently. The performance of the presented techniques is demonstrated on two MIP test sets. One contains all benchmark instances from the last three MIPLIB versions, while the other consists of real-world supply chain management problems. The computational results show that the combination of all three presolving techniques almost halves the solving time for the considered supply chain management problems. For the MIPLIB instances we obtain a speedup of 20 % on affected instances while not degrading the performance on the remaining problems. 2015 31 Mathematical Programming Computation 7 4 367 398 10.1007/s12532-015-0083-5 Mathematical Optimization OPUS4-7806 Wissenschaftlicher Artikel Gamrath, Gerald; Gleixner, Ambros; Koch, Thorsten; Miltenberger, Matthias; Kniasew, Dimitri; Schlögel, Dominik; Martin, Alexander; Weninger, Dieter Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of robust and future-proof decision support systems. The complexity of industrial-scale supply chain optimization, however, often poses limits to the application of general mixed-integer programming solvers. In this paper we describe algorithmic innovations that help to ensure that MIP solver performance matches the complexity of the large supply chain problems and tight time limits encountered in practice. Our computational evaluation is based on a diverse set, modeling real-world scenarios supplied by our industry partner SAP. 2019 22 Journal of Computational Mathematics 37 866 888 10.4208/jcm.1905-m2019-0055 Mathematical Optimization OPUS4-4253 misc Gamrath, Gerald; Koch, Thorsten; Martin, Alexander; Miltenberger, Matthias; Weninger, Dieter Progress in Presolving for Mixed Integer Programming Presolving attempts to eliminate redundant information from the problem formulation and simultaneously tries to strengthen the formulation. It can be very effective and is often essential for solving instances. Especially for mixed integer programming problems, fast and effective presolving algorithms are very important. In this paper, we report on three new presolving techniques. The first method searches for singleton continuous columns and tries to fix the corresponding variables. Then we present a presolving technique which exploits a partial order of the variables to induce fixings. Finally, we show an approach based on connected components in graphs. Our computational results confirm the profitable use of the algorithms in practice. 2013 urn:nbn:de:0297-zib-42530 10.1007/s12532-015-0083-5 Mathematical Optimization OPUS4-6134 misc Maher, Stephen J.; Miltenberger, Matthias; Pedroso, João Pedro; Rehfeldt, Daniel; Schwarz, Robert; Serrano, Felipe PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite SCIP is a solver for a wide variety of mathematical optimization problems. It is written in C and extendable due to its plug-in based design. However, dealing with all C specifics when extending SCIP can be detrimental to development and testing of new ideas. This paper attempts to provide a remedy by introducing PySCIPOpt, a Python interface to SCIP that enables users to write new SCIP code entirely in Python. We demonstrate how to intuitively model mixed-integer linear and quadratic optimization problems and moreover provide examples on how new Python plug-ins can be added to SCIP. 2016 urn:nbn:de:0297-zib-61348 10.1007/978-3-319-42432-3_37 Mathematical Optimization OPUS4-6045 Konferenzveröffentlichung Maher, Stephen J.; Miltenberger, Matthias; Pedroso, João Pedro; Rehfeldt, Daniel; Schwarz, Robert; Serrano, Felipe PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite SCIP is a solver for a wide variety of mathematical optimization problems. It is written in C and extendable due to its plug-in based design. However, dealing with all C specifics when extending SCIP can be detrimental to development and testing of new ideas. This paper attempts to provide a remedy by introducing PySCIPOpt, a Python interface to SCIP that enables users to write new SCIP code entirely in Python. We demonstrate how to intuitively model mixed-integer linear and quadratic optimization problems and moreover provide examples on how new Python plug-ins can be added to SCIP. Springer 2016 6 Mathematical Software – ICMS 2016 9725 301 307 10.1007/978-3-319-42432-3_37 Mathematical Optimization OPUS4-6956 misc Hendel, Gregor; Miltenberger, Matthias; Witzig, Jakob Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms State-of-the-art solvers for mixed integer programs (MIP) govern a variety of algorithmic components. Ideally, the solver adaptively learns to concentrate its computational budget on those components that perform well on a particular problem, especially if they are time consuming. We focus on three such algorithms, namely the classes of large neighborhood search and diving heuristics as well as Simplex pricing strategies. For each class we propose a selection strategy that is updated based on the observed runtime behavior, aiming to ultimately select only the best algorithms for a given instance. We review several common strategies for such a selection scenario under uncertainty, also known as Multi Armed Bandit Problem. In order to apply those bandit strategies, we carefully design reward functions to rank and compare each individual heuristic or pricing algorithm within its respective class. Finally, we discuss the computational benefits of using the proposed adaptive selection within the \scip Optimization Suite on publicly available MIP instances. 2018 urn:nbn:de:0297-zib-69563 Mathematical Optimization OPUS4-7113 Konferenzveröffentlichung Hendel, Gregor; Miltenberger, Matthias; Witzig, Jakob Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms State-of-the-art solvers for mixed integer programs (MIP) govern a variety of algorithmic components. Ideally, the solver adaptively learns to concentrate its computational budget on those components that perform well on a particular problem, especially if they are time consuming. We focus on three such algorithms, namely the classes of large neighborhood search and diving heuristics as well as Simplex pricing strategies. For each class we propose a selection strategy that is updated based on the observed runtime behavior, aiming to ultimately select only the best algorithms for a given instance. We review several common strategies for such a selection scenario under uncertainty, also known as Multi Armed Bandit Problem. In order to apply those bandit strategies, we carefully design reward functions to rank and compare each individual heuristic or pricing algorithm within its respective class. Finally, we discuss the computational benefits of using the proposed adaptive selection within the SCIP Optimization Suite on publicly available MIP instances. 2018 OR 2018: International Conference on Operations Research Mathematical Optimization OPUS4-9187 Dissertation Miltenberger, Matthias Linear Programming in MILP Solving - A Computational Perspective Mixed-integer linear programming (MILP) plays a crucial role in the field of mathematical optimization and is especially relevant for practical applications due to the broad range of problems that can be modeled in that fashion. The vast majority of MILP solvers employ the LP-based branch-and-cut approach. As the name suggests, the linear programming (LP) subproblems that need to be solved therein influence their behavior and performance significantly. This thesis explores the impact of various LP solvers as well as LP solving techniques on the constraint integer programming framework SCIP Optimization Suite. SCIP allows for comparisons between academic and open-source LP solvers like Clp and SoPlex, as well as commercially developed, high-end codes like CPLEX, Gurobi, and Xpress. We investigate how the overall performance and stability of an MILP solver can be improved by new algorithmic enhancements like LP solution polishing and persistent scaling that we have implemented in the LP solver SoPlex. The former decreases the fractionality of LP solutions by selecting another vertex on the optimal hyperplane of the LP relaxation, exploiting degeneracy. The latter provides better numerical properties for the LP solver throughout the MILP solving process by preserving and extending the initial scaling factors, effectively also improving the overall performance of SCIP. Both enhancement techniques are activated by default in the SCIP Optimization Suite. Additionally, we provide an analysis of numerical conditions in SCIP through the lens of the LP solver by comparing different measures and how these evolve during the different stages of the solving process. A side effect of our work on this topic was the development of TreeD: a new and convenient way of presenting the search tree interactively and animated in the three-dimensional space. This visualization technique facilitates a better understanding of the MILP solving process of SCIP. Furthermore, this thesis presents the various algorithmic techniques like the row representation and iterative refinement that are implemented in SoPlex and that distinguish the solver from other simplex-based codes. Although it is often not as performant as its competitors, SoPlex demonstrates the ongoing research efforts in the field of linear programming with the simplex method. Aside from that, we demonstrate the rapid prototyping of algorithmic ideas and modeling approaches via PySCIPOpt, the Python interface to the SCIP Optimization Suite. This tool allows for convenient access to SCIP's internal data structures from the user-friendly Python programming language to implement custom algorithms and extensions without any prior knowledge of SCIP's programming language C. TreeD is one such example, demonstrating the use of several Python libraries on top of SCIP. PySCIPOpt also provides an intuitive modeling layer to formulate problems directly in the code without having to utilize another modeling language or framework. All contributions presented in this thesis are readily accessible in source code in SCIP Optimization Suite or as separate projects on the public code-sharing platform GitHub. Verlag Dr. Hut GmbH 2023 237 9783843953238 urn:nbn:de:0297-zib-91873 Mathematical Optimization OPUS4-6217 misc Maher, Stephen J.; Fischer, Tobias; Gally, Tristan; Gamrath, Gerald; Gleixner, Ambros; Gottwald, Robert Lion; Hendel, Gregor; Koch, Thorsten; Lübbecke, Marco; Miltenberger, Matthias; Müller, Benjamin; Pfetsch, Marc; Puchert, Christian; Rehfeldt, Daniel; Schenker, Sebastian; Schwarz, Robert; Serrano, Felipe; Shinano, Yuji; Weninger, Dieter; Witt, Jonas T.; Witzig, Jakob The SCIP Optimization Suite 4.0 The SCIP Optimization Suite is a powerful collection of optimization software that consists of the branch-cut-and-price framework and mixed-integer programming solver SCIP, the linear programming solver SoPlex, the modeling language Zimpl, the parallelization framework UG, and the generic branch-cut-and-price solver GCG. Additionally, it features the extensions SCIP-Jack for solving Steiner tree problems, PolySCIP for solving multi-objective problems, and SCIP-SDP for solving mixed-integer semidefinite programs. The SCIP Optimization Suite has been continuously developed and has now reached version 4.0. The goal of this report is to present the recent changes to the collection. We not only describe the theoretical basis, but focus on implementation aspects and their computational consequences. 2017 urn:nbn:de:0297-zib-62170 Mathematical Optimization OPUS4-5767 misc Gamrath, Gerald; Fischer, Tobias; Gally, Tristan; Gleixner, Ambros; Hendel, Gregor; Koch, Thorsten; Maher, Stephen J.; Miltenberger, Matthias; Müller, Benjamin; Pfetsch, Marc; Puchert, Christian; Rehfeldt, Daniel; Schenker, Sebastian; Schwarz, Robert; Serrano, Felipe; Shinano, Yuji; Vigerske, Stefan; Weninger, Dieter; Winkler, Michael; Witt, Jonas T.; Witzig, Jakob The SCIP Optimization Suite 3.2 The SCIP Optimization Suite is a software toolbox for generating and solving various classes of mathematical optimization problems. Its major components are the modeling language ZIMPL, the linear programming solver SoPlex, the constraint integer programming framework and mixed-integer linear and nonlinear programming solver SCIP, the UG framework for parallelization of branch-and-bound-based solvers, and the generic branch-cut-and-price solver GCG. It has been used in many applications from both academia and industry and is one of the leading non-commercial solvers. This paper highlights the new features of version 3.2 of the SCIP Optimization Suite. Version 3.2 was released in July 2015. This release comes with new presolving steps, primal heuristics, and branching rules within SCIP. In addition, version 3.2 includes a reoptimization feature and improved handling of quadratic constraints and special ordered sets. SoPlex can now solve LPs exactly over the rational number and performance improvements have been achieved by exploiting sparsity in more situations. UG has been tested successfully on 80,000 cores. A major new feature of UG is the functionality to parallelize a customized SCIP solver. GCG has been enhanced with a new separator, new primal heuristics, and improved column management. Finally, new and improved extensions of SCIP are presented, namely solvers for multi-criteria optimization, Steiner tree problems, and mixed-integer semidefinite programs. 2016 urn:nbn:de:0297-zib-57675 Mathematical Optimization OPUS4-7802 misc Gamrath, Gerald; Anderson, Daniel; Bestuzheva, Ksenia; Chen, Wei-Kun; Eifler, Leon; Gasse, Maxime; Gemander, Patrick; Gleixner, Ambros; Gottwald, Leona; Halbig, Katrin; Hendel, Gregor; Hojny, Christopher; Koch, Thorsten; Le Bodic, Pierre; Maher, Stephen J.; Matter, Frederic; Miltenberger, Matthias; Mühmer, Erik; Müller, Benjamin; Pfetsch, Marc; Schlösser, Franziska; Serrano, Felipe; Shinano, Yuji; Tawfik, Christine; Vigerske, Stefan; Wegscheider, Fabian; Weninger, Dieter; Witzig, Jakob The SCIP Optimization Suite 7.0 The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming frame- work SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies mixed-integer linear op- timization problems and can be used stand-alone or integrated into SCIP via a presolver plugin. SCIP 7.0 provides additional support for decomposition algorithms. Besides im- provements in the Benders' decomposition solver of SCIP, user-defined decomposition structures can be read, which are used by the automated Benders' decomposition solver and two primal heuristics. Additionally, SCIP 7.0 comes with a tree size estimation that is used to predict the completion of the overall solving process and potentially trigger restarts. Moreover, substantial performance improvements of the MIP core were achieved by new developments in presolving, primal heuristics, branching rules, conflict analysis, and symmetry handling. Last, not least, the report presents updates to other components and extensions of the SCIP Optimization Suite, in particular, the LP solver SoPlex and the mixed-integer semidefinite programming solver SCIP-SDP. 2020 urn:nbn:de:0297-zib-78023 Mathematical Optimization OPUS4-6629 misc Gleixner, Ambros; Eifler, Leon; Gally, Tristan; Gamrath, Gerald; Gemander, Patrick; Gottwald, Robert Lion; Hendel, Gregor; Hojny, Christopher; Koch, Thorsten; Miltenberger, Matthias; Müller, Benjamin; Pfetsch, Marc; Puchert, Christian; Rehfeldt, Daniel; Schlösser, Franziska; Serrano, Felipe; Shinano, Yuji; Viernickel, Jan Merlin; Vigerske, Stefan; Weninger, Dieter; Witt, Jonas T.; Witzig, Jakob The SCIP Optimization Suite 5.0 This article describes new features and enhanced algorithms made available in version 5.0 of the SCIP Optimization Suite. In its central component, the constraint integer programming solver SCIP, remarkable performance improvements have been achieved for solving mixed-integer linear and nonlinear programs. On MIPs, SCIP 5.0 is about 41 % faster than SCIP 4.0 and over twice as fast on instances that take at least 100 seconds to solve. For MINLP, SCIP 5.0 is about 17 % faster overall and 23 % faster on instances that take at least 100 seconds to solve. This boost is due to algorithmic advances in several parts of the solver such as cutting plane generation and management, a new adaptive coordination of large neighborhood search heuristics, symmetry handling, and strengthened McCormick relaxations for bilinear terms in MINLPs. Besides discussing the theoretical background and the implementational aspects of these developments, the report describes recent additions for the other software packages connected to SCIP, in particular for the LP solver SoPlex, the Steiner tree solver SCIP-Jack, the MISDP solver SCIP-SDP, and the parallelization framework UG. 2017 urn:nbn:de:0297-zib-66297 Mathematical Optimization