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 - TY - GEN A1 - Arnold, Thomas A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Vigerske, Stefan A1 - Henrion, René A1 - Grötschel, Martin A1 - Koch, Thorsten A1 - Tischendorf, Caren A1 - Römisch, Werner ED - Deuflhard, Peter ED - Grötschel, Martin ED - Hömberg, Dietmar ED - Horst, Ulrich ED - Kramer, Jürg ED - Mehrmann, Volker ED - Polthier, Konrad ED - Schmidt, Frank ED - Schütte, Christof ED - Skutella, Martin ED - Sprekels, Jürgen T1 - A Jack of all Trades? Solving stochastic mixed-integer nonlinear constraint programs T2 - MATHEON - Mathematics for Key Technologies N2 - Natural gas is one of the most important energy sources in Germany and Europe. In recent years, political regulations have led to a strict separation of gas trading and gas transport, thereby assigning a central role in energy politics to the transportation and distribution of gas. These newly imposed political requirements influenced the technical processes of gas transport in such a way that the complex task of planning and operating gas networks has become even more intricate. Mathematically, the combination of discrete decisions on the configuration of a gas transport network, the nonlinear equations describing the physics of gas, and the uncertainty in demand and supply yield large-scale and highly complex stochastic mixed-integer nonlinear optimization problems. The Matheon project "Optimization of Gas Transport" takes the key role of making available the necessary core technology to solve the mathematical optimization problems which model the topology planning and the operation of gas networks. An important aspect of the academic impact is the free availability of our framework. As a result of several years of research and development, it is now possible to download a complete state-of-the-art framework for mixed-integer linear and nonlinear programming in source code at http://scip.zib.de Y1 - 2014 U6 - https://doi.org/10.4171/137 VL - 1 SP - 135 EP - 146 PB - European Mathematical Society ER -