TY - CHAP A1 - Achterberg, Tobias A1 - Berthold, Timo ED - van Hoeve, Willem ED - Hooker, John T1 - Hybrid Branching T2 - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 6th International Conference, CPAIOR 2009 Y1 - 2009 VL - 5547 SP - 309 EP - 311 PB - Springer ER - TY - CHAP A1 - Berthold, Timo A1 - Pfetsch, Marc ED - Fleischmann, Bernhard ED - Borgwardt, Karl ED - Klein, Robert ED - Tuma, Axel T1 - Detecting Orbitopal Symmetries T2 - Operations Research Proceedings 2008 Y1 - 2009 SP - 433 EP - 438 PB - Springer-Verlag ER - TY - THES A1 - Gamrath, Gerald T1 - Generic Branch-Cut-and-Price N2 - In this thesis, we present the theoretical background, implementational details and computational results concerning the generic branch-cut-and-price solver GCG. KW - mixed-integer programming KW - column generation KW - branch-and-price Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57543 ER - TY - GEN A1 - Maher, Stephen J. A1 - Miltenberger, Matthias A1 - Pedroso, João Pedro A1 - Rehfeldt, Daniel A1 - Schwarz, Robert A1 - Serrano, Felipe T1 - PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite N2 - 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. T3 - ZIB-Report - 16-64 KW - SCIP, Mathematical optimization, Python, Modeling Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61348 SN - 1438-0064 ER - TY - JOUR A1 - Gleixner, Ambros A1 - Maher, Stephen A1 - Müller, Benjamin A1 - Pedroso, João Pedro T1 - Price-and-verify: a new algorithm for recursive circle packing using Dantzig–Wolfe decomposition JF - Annals of Operations Research N2 - Packing rings into a minimum number of rectangles is an optimization problem which appears naturally in the logistics operations of the tube industry. It encompasses two major difficulties, namely the positioning of rings in rectangles and the recursive packing of rings into other rings. This problem is known as the Recursive Circle Packing Problem (RCPP). We present the first dedicated method for solving RCPP that provides strong dual bounds based on an exact Dantzig–Wolfe reformulation of a nonconvex mixed-integer nonlinear programming formulation. The key idea of this reformulation is to break symmetry on each recursion level by enumerating one-level packings, i.e., packings of circles into other circles, and by dynamically generating packings of circles into rectangles. We use column generation techniques to design a “price-and-verify” algorithm that solves this reformulation to global optimality. Extensive computational experiments on a large test set show that our method not only computes tight dual bounds, but often produces primal solutions better than those computed by heuristics from the literature. Y1 - 2018 U6 - https://doi.org/10.1007/s10479-018-3115-5 VL - 284 IS - 2 SP - 527 EP - 555 PB - Springer US ER - TY - GEN A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Maher, Stephen J. A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - SCIP-Jack – A solver for STP and variants with parallelization extensions N2 - The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem-specific. In contrast, this paper introduces a general-purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. T3 - ZIB-Report - 16-41 KW - Steiner tree problem KW - SCIP-Jack KW - Steiner tree variants KW - maximum-weight connected subgraph KW - prize-collecting Steiner tree Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60170 SN - 1438-0064 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP N2 - Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this paper transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, we demonstrate the considerable implications for practical solving approaches, including the computation of strong upper and lower bounds. T3 - ZIB-Report - 16-36 KW - graph transformation KW - Steiner tree problems KW - prize-collecting Steiner tree problem KW - maximum-weight connected subgraph problem Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59777 SN - 1438-0064 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Schenker, Sebastian A1 - Skutella, Martin A1 - Strunk, Timo ED - Greuel, G.-M. ED - Koch, Thorsten ED - Paule, Peter ED - Sommese, Andrew T1 - PolySCIP T2 - Mathematical Software – ICMS 2016, 5th International Conference, Berlin, Germany, July 11-14, 2016, Proceedings N2 - PolySCIP is a new solver for multi-criteria integer and multi-criteria linear programs handling an arbitrary number of objectives. It is available as an official part of the non-commercial constraint integer programming framework SCIP. It utilizes a lifted weight space approach to compute the set of supported extreme non-dominated points and unbounded non-dominated rays, respectively. The algorithmic approach can be summarized as follows: At the beginning an arbitrary non-dominated point is computed (or it is determined that there is none) and a weight space polyhedron created. In every next iteration a vertex of the weight space polyhedron is selected whose entries give rise to a single-objective optimization problem via a combination of the original objectives. If the ptimization of this single-objective problem yields a new non-dominated point, the weight space polyhedron is updated. Otherwise another vertex of the weight space polyhedron is investigated. The algorithm finishes when all vertices of the weight space polyhedron have been investigated. The file format of PolySCIP is based on the widely used MPS format and allows a simple generation of multi-criteria models via an algebraic modelling language. Y1 - 2016 SN - 978-3-319-42431-6 U6 - https://doi.org/10.1007/978-3-319-42432-3_32 VL - 9725 SP - 259 EP - 264 PB - Springer International Publishing ET - Mathematical Software – ICMS 2016 ER - TY - JOUR A1 - Humpola, Jesco A1 - Serrano, Felipe T1 - Sufficient pruning conditions for MINLP in gas network design JF - EURO Journal on Computational Optimization N2 - One-quarter of Europe’s energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euros per kilometer the extension of the European pipeline network is already a multi-billion Euro business. Therefore, automatic planning tools that support the decision process are desired. We model the topology optimization problem in gas networks by a mixed-integer nonlinear program (MINLP). This gives rise to a so-called active transmission problem, a continuous nonlinear non-convex feasibility problem which emerges from the MINLP model by fixing all integral variables. We offer novel sufficient conditions for proving the infeasibility of this active transmission problem. These conditions can be expressed in the form of a mixed-integer program (MILP), i.e., the infeasibility of a non-convex continuous nonlinear program (NLP) can be certified by solving an MILP. This result provides an efficient pruning procedure in a branch-and-bound algorithm. Our computational results demonstrate a substantial speedup for the necessary computations. Y1 - 2017 U6 - https://doi.org/10.1007/s13675-016-0077-8 VL - 5 IS - 1-2 SP - 239 EP - 261 PB - Springer Berlin Heidelberg ER - TY - GEN A1 - Breuer, Thomas A1 - Bussieck, Michael A1 - Cao, Karl-Kien A1 - Cebulla, Felix A1 - Fiand, Frederik A1 - Gils, Hans Christian A1 - Gleixner, Ambros A1 - Khabi, Dmitry A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Wetzel, Manuel T1 - Optimizing Large-Scale Linear Energy System Problems with Block Diagonal Structure by Using Parallel Interior-Point Methods N2 - Current linear energy system models (ESM) acquiring to provide sufficient detail and reliability frequently bring along problems of both high intricacy and increasing scale. Unfortunately, the size and complexity of these problems often prove to be intractable even for commercial state-of-the-art linear programming solvers. This article describes an interdisciplinary approach to exploit the intrinsic structure of these large-scale linear problems to be able to solve them on massively parallel high-performance computers. A key aspect are extensions to the parallel interior-point solver PIPS-IPM originally developed for stochastic optimization problems. Furthermore, a newly developed GAMS interface to the solver as well as some GAMS language extensions to model block-structured problems will be described. T3 - ZIB-Report - 17-75 KW - energy system models KW - interior-point methods KW - high-performance computing Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66183 SN - 1438-0064 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - SCIP-Jack—a solver for STP and variants with parallelization extensions: An update N2 - The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. Although the different Steiner tree problem variants are usually strongly related, solution approaches employed so far have been prevalently problem-specific. Against this backdrop, the solver SCIP-Jack was created as a general-purpose framework that can be used to solve the classical Steiner tree problem and 11 of its variants. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. Furthermore, SCIP-Jack includes various newly developed algorithmic components such as preprocessing routines and heuristics. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. After the introduction of SCIP-Jack at the 2014 DIMACS Challenge on Steiner problems, the overall performance of the solver has considerably improved. This article provides an overview on the current state. T3 - ZIB-Report - 18-05 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66416 SN - 1438-0064 ER - TY - JOUR A1 - Berthold, Timo A1 - Hendel, Gregor A1 - Koch, Thorsten T1 - From feasibility to improvement to proof: three phases of solving mixed-integer programs JF - Optimization Methods and Software N2 - Modern mixed-integer programming (MIP) solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound. Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three distinct phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behaviour of the non-commercial MIP solver Scip at the predicted phase transition points. Y1 - 2017 U6 - https://doi.org/10.1080/10556788.2017.1392519 VL - 33 IS - 3 SP - 499 EP - 517 PB - Taylor & Francis ER - TY - JOUR A1 - Koch, Thorsten T1 - The ZIMPL modeling language JF - Optima Y1 - 2017 UR - http://www.mathopt.org/Optima-Issues/optima103.pdf VL - 103 SP - 8 EP - 9 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem N2 - Borne out of a surprising variety of practical applications, the maximum-weight connected subgraph problem has attracted considerable interest during the past years. This interest has not only led to notable research on theoretical properties, but has also brought about several (exact) solvers-with steadily increasing performance. Continuing along this path, the following article introduces several new algorithms such as reduction techniques and heuristics and describes their integration into an exact solver. The new methods are evaluated with respect to both their theoretical and practical properties. Notably, the new exact framework allows to solve common problem instances from the literature faster than all previous approaches. Moreover, one large-scale benchmark instance from the 11th DIMACS Challenge can be solved for the first time to optimality and the primal-dual gap for two other ones can be significantly reduced. T3 - ZIB-Report - 17-45 KW - maximum-weight connected subgraph Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64699 SN - 1438-0064 ER - TY - JOUR A1 - Rehfeldt, Daniel A1 - Koch, Thorsten A1 - Maher, Stephen J. T1 - Reduction Techniques for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem JF - Networks N2 - The concept of reduction has frequently distinguished itself as a pivotal ingredient of exact solving approaches for the Steiner tree problem in graphs. In this paper we broaden the focus and consider reduction techniques for three Steiner problem variants that have been extensively discussed in the literature and entail various practical applications: The prize-collecting Steiner tree problem, the rooted prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem. By introducing and subsequently deploying numerous new reduction methods, we are able to drastically decrease the size of a large number of benchmark instances, already solving more than 90 percent of them to optimality. Furthermore, we demonstrate the impact of these techniques on exact solving, using the example of the state-of-the-art Steiner problem solver SCIP-Jack. Y1 - 2019 U6 - https://doi.org/10.1002/net.21857 VL - 73 SP - 206 EP - 233 PB - Wiley ET - 2 ER - TY - JOUR A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP JF - Journal of Computational Mathematics N2 - Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this paper transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, we demonstrate the considerable implications for practical solving approaches, including the computation of strong upper and lower bounds. Y1 - 2018 U6 - https://doi.org/10.4208/jcm.1709-m2017-0002 VL - 36 IS - 3 SP - 459 EP - 468 ER - TY - CHAP A1 - Gamrath, Gerald A1 - Melchiori, Anna A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Salvagnin, Domenico T1 - Branching on Multi-aggregated Variables T2 - Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2015 N2 - In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly. Y1 - 2015 U6 - https://doi.org/10.1007/978-3-319-18008-3_10 VL - 9075 SP - 141 EP - 156 ER - TY - JOUR A1 - Berthold, Timo A1 - Hendel, Gregor T1 - Shift-and-Propagate JF - Journal of Heuristics N2 - In recent years, there has been a growing interest in the design of general purpose primal heuristics for use inside complete mixed integer programming solvers. Many of these heuristics rely on an optimal LP solution, which may take a significant amount of time to find. In this paper, we address this issue by introducing a pre-root primal heuristic that does not require a previously found LP solution. This heuristic, named Shift-and-Propagate , applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement to existing rounding and propagation heuristics. Y1 - 2014 U6 - https://doi.org/10.1007/s10732-014-9271-0 VL - 21 IS - 1 SP - 73 EP - 106 ER - TY - GEN A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - SCIP-Jack - A massively parallel STP solver N2 - In this article we describe the impact from embedding a 15 year old model for solving the Steiner tree problem in graphs in a state-of-the-art MIP-Framework, making the result run in a massively parallel environment and extending the model to solve as many variants as possible. We end up with a high-perfomance solver that is capable of solving previously unsolved instances and, in contrast to its predecessor, is freely available for academic research. T3 - ZIB-Report - 14-35 KW - Steiner Tree Problem KW - Mixed-Integer Programming KW - Branch-and-Cut KW - DIMACS Challenge Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52293 SN - 1438-0064 ER - TY - JOUR A1 - Humpola, Jesco A1 - Lehmann, Thomas A1 - Fügenschuh, Armin T1 - A primal heuristic for optimizing the topology of gas networks based on dual information JF - EURO Journal on Computational Optimization N2 - We present a novel heuristic to identify feasible solutions of a mixed-integer nonlinear programming problem arising in natural gas transportation: the selection of new pipelines to enhance the network's capacity to a desired level in a cost-efficient way. We solve this problem in a linear programming based branch-and-cut approach, where we deal with the nonlinearities by linear outer approximation and spatial branching. At certain nodes of the branching tree, we compute a KKT point of a nonlinear relaxation. Based on the information from the KKT point we alter some of the binary variables in a locally promising way exploiting our problem-specific structure. On a test set of real-world instances, we are able to increase the chance of identifying feasible solutions by some order of magnitude compared to standard MINLP heuristics that are already built in the general-purpose MINLP solver SCIP. Y1 - 2015 U6 - https://doi.org/10.1007/s13675-014-0029-0 VL - 3 IS - 1 SP - 53 EP - 78 ER - TY - CHAP A1 - Matuschke, Jannik A1 - Bley, Andreas A1 - Müller, Benjamin ED - Bodlaender, Hans L. ED - Italiano, Giuseppe F. T1 - Approximation Algorithms for Facility Location with Capacitated and Length-Bounded Tree Connections N2 - We consider a generalization of the uncapacitated facility location problem that occurs in planning of optical access networks in telecommunications. Clients are connected to open facilities via depth-bounded trees. The total demand of clients served by a tree must not exceed a given tree capacity. We investigate a framework for combining facility location algorithms with a tree-based clustering approach and derive approximation algorithms for several variants of the problem, using techniques for approximating shallow-light Steiner trees via layer graphs, simultaneous approximation of shortest paths and minimum spanning trees, and greedy coverings. Y1 - 2013 U6 - https://doi.org/10.1007/978-3-642-40450-4_60 VL - Algorithms -- ESA 2013 SP - 707 EP - 718 PB - Springer ER - TY - JOUR A1 - Maher, Stephen J. T1 - Solving the integrated airline recovery problem using column-and-row generation JF - Transportation Science N2 - Airline recovery presents very large and difficult problems requiring high quality solutions within very short time limits. To improve computational performance, the complete airline recovery problem is generally formulated as a series of sequential stages. While the sequential approach greatly simplifies the complete recovery problem, there is no guarantee of global optimality or solution quality. To address this, there has been increasing interest in the development of efficient solution techniques to solve an integrated recovery problem. In this paper, an integrated airline recovery problem is proposed by integrating the schedule, crew and aircraft recovery stages. To achieve short runtimes and high quality solutions, this problem is solved using column-and-row generation. Column-and-row generation achieves an improvement in solution runtimes by reducing the problem size and thereby achieving a faster execution of each LP solve. Further, the results demonstrate that a good upper bound achieved early in the solution process, indicating an improved solution quality with the early termination of the algorithm. This paper also details the integration of the row generation procedure with branch-and-price, which is used to achieve integral optimal solutions. The benefits of applying column-and-row generation to solve the integrated recovery problem are demonstrated with a comparison to a standard column generation technique. Y1 - 2015 U6 - https://doi.org/10.1287/trsc.2014.0552 VL - 50 IS - 1 SP - 216 EP - 239 ER -