https://opus4.kobv.de/opus4-zibOPUS documents
https://opus4.kobv.de/opus4-zib/index/index/
Tue, 18 Dec 2018 12:29:07 +0100Tue, 18 Dec 2018 12:29:07 +0100Adaptive Large Neighborhood Search for Mixed Integer Programming
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7116
Large Neighborhood Search (LNS) heuristics are among the most powerful but also most expensive heuristics for mixed integer programs (MIP). Ideally, a solver learns adaptively which LNS heuristics work best for the MIP problem at hand in order to concentrate its limited computational budget.
To this end, this work introduces Adaptive Large Neighborhood Search (ALNS) for MIP, a primal heuristic that acts a framework for eight popular LNS heuristics such as Local Branching and Relaxation Induced Neighborhood Search (RINS). We distinguish the available LNS heuristics by their individual search domains, which we call neighborhoods. The decision which neighborhood should be executed is guided by selection strategies for the multi armed bandit problem, a related optimization problem during which suitable actions have to be chosen to maximize a reward function. In this paper, we propose an LNS-specific reward function to learn to distinguish between the available neighborhoods based on successful calls and failures. A second, algorithmic enhancement is a generic variable fixing priorization, which ALNS employs to adjust the subproblem complexity as needed. This is particularly useful for some neighborhoods which do not fix variables by themselves. The proposed primal heuristic has been implemented
within the MIP solver SCIP. An extensive computational study is conducted to compare different LNS strategies within our ALNS framework on a large set of publicly available MIP instances from the MIPLIB and Coral benchmark sets. The results of this simulation are used to calibrate the parameters of the bandit selection strategies. A second computational experiment shows the computational benefits of the proposed ALNS framework within the MIP solver SCIP.Gregor Hendelreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7116Tue, 18 Dec 2018 12:29:07 +0100Intersection cuts for factorable MINLP
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7110
Given a factorable function f, we propose a procedure that constructs a concave underestimor of f that is tight at a given point. These underestimators can be used to generate intersection cuts. A peculiarity of these underestimators is that they do not rely on a bounded domain. We propose a strengthening procedure for the intersection cuts that exploits the bounds of the domain. Finally, we propose an extension of monoidal strengthening to take advantage of the integrality of the non-basic variables.Felipe Serranoreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7110Fri, 07 Dec 2018 14:53:12 +0100Building Optimal Steiner Trees on Supercomputers by using up to 43,000 Cores
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7111
SCIP-JACK is a customized, branch-and-cut based solver for Steiner tree and related problems. ug [SCIP-JACK, MPI] extends SCIP-JACK to a massively par- allel solver by using the Ubiquity Generator (UG) framework. ug [SCIP-JACK, MPI] was the only solver that could run on a distributed environment at the (latest) 11th DIMACS Challenge in 2014. Furthermore, it could solve three well-known open instances and updated 14 best known solutions to instances from the bench- mark libary STEINLIB. After the DIMACS Challenge, SCIP-JACK has been con- siderably improved. However, the improvements were not reflected on ug [SCIP- JACK, MPI]. This paper describes an updated version of ug [SCIP-JACK, MPI], especially branching on constrains and a customized racing ramp-up. Furthermore, the different stages of the solution process on a supercomputer are described in detail. We also show the latest results on open instances from the STEINLIB.Yuji Shinano; Daniel Rehfeldt; Thorsten Kochreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7111Fri, 07 Dec 2018 13:23:47 +0100Reduction-based exact solution of prize-collecting Steiner tree problems
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7095
Daniel Rehfeldt; Thorsten Kochreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7095Wed, 21 Nov 2018 21:48:21 +0100Kombilösung: Optimierung des Liniennetzes in Karlsruhe
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6967
Wir beschreiben die Optimierung des Nahverkehrsnetzes der Stadt Karlsruhe im Zusammmenhang mit den Baumaßnahmen der sogenannten Kombilösung.Ralf Borndörfer; Ascan Egerer; Marika Karbstein; Ralf Messerschmidt; Marc Perez; Steven Pfisterer; Petra Straußreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6967Mon, 12 Nov 2018 22:57:35 +0100Calculation of clinch and elimination numbers for sports leagues with multiple tiebreaking criteria
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7059
The clinch (elimination) number is a minimal number of future wins (losses) needed to clinch (to be eliminated from) a specified place in a sports league. Several optimization models and computational results are shown in this paper for calculating clinch and elimination numbers in the presence of predefined multiple tiebreaking criteria. The main subject of this paper is to provide a general algorithmic framework based on integer programming with utilizing possibly multilayered upper and lower bounds.Satoshi Ito; Yuji Shinanoreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7059Thu, 27 Sep 2018 10:52:48 +0200Chvátal’s Conjecture Holds for Ground Sets of Seven Elements
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7024
We establish a general computational framework for Chvátal’s conjecture based on exact rational integer programming. As a result we prove Chvátal’s conjecture holds for all downsets whose union of sets contains seven elements or less. The computational proof relies on an exact branch-and-bound certificate that allows for elementary verification and is independent of the integer programming solver used.Leon Eifler; Ambros Gleixner; Jonad Pulajreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7024Tue, 28 Aug 2018 09:26:42 +0200Optimization of a Master Surgery Schedule
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6999
During the past years hospitals saw themselves confronted with increasing economical pressure (WB06, p. V). Therefore, optimizing the general operational procedures has gained in importance. The revenue of a hospital depends on the kinds and quantity of treatments performed and on the effcient use and utilization of the corresponding resources. About 25 − 50% of the treatment costs of a patient needing surgery incurs in the operating rooms (WB06, p. 58). Hence skillful management of the operating rooms can have a large impact on the overall revenue of a hospital. Belien and Demeulemeester (BD07) describe the planning of operating room (OR) schedules as a multi-stage process. In the first stage OR time is allocated to the hospitals specialties and capacities and resources are adjusted. In the second stage a master surgery schedule (MSS) is developed, that is a timetable for D days that specifies the amount of OR time assigned to the specialties on every individual day. After D days this schedule will be repeated without any changes. Hence, developing an MSS is a long-term problem. Finally, specialties will schedule specific surgeries within their assigned OR time. In this work we will focus on the development of the MSS that maximizes the revenue of the hospital. Our main focus will be to ensure that the capacities of the downstream resources, i.e. the bed capacities in the ICU and ward, will not be exceeded. Additionally, we hope that our formulation of the problem will lead to a leveled bed demand without significant peaks. We will incorporate the uncertainty of patient demand and case mix in our model. There have been several approaches on this subject, for example in (Fü15) and (BD07) and this work is in part in� uenced by these advances.Lisa Mattrischmasterthesishttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6999Tue, 14 Aug 2018 15:08:13 +0200ASTS Orientations on Undirected Graphs: Structural analysis and enumeration
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6963
All feasible flows in potential-driven networks
induce an orientation on the undirected graph underlying the network.
Clearly, these orientations must satisfy two conditions: they are acyclic and there are no "dead ends" in the network, i.e. each source requires outgoing flows, each sink requires incoming flows, and each transhipment vertex requires both an incoming and an outgoing flow. In this paper we will call orientations that satisfy these conditions acyclic source-transhipment-sink orientations (ASTS-orientation) and study their structure. In particular, we characterize graphs that allow for such an orientation, describe a way to enumerate all possible ASTS-orientations of a given graph, present an algorithm to simplify and decompose a graph before such an enumeration and shed light on the role of zero flows in the context of ASTS-orientations.Kai Helge Becker; Benjamin Hillerreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6963Tue, 31 Jul 2018 23:57:17 +0200Improving relaxations for potential-driven network flow problems via acyclic flow orientations
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6962
The class of potential-driven network flow problems provides important models for a range of infrastructure networks. For real-world applications, they need to be combined with integer
models for switching certain network elements, giving rise to hard-to-solve MINLPs. We observe that on large-scale real-world meshed networks the usually employed relaxations are rather weak due to cycles in the network.
We propose acyclic flow orientations as a combinatorial relaxation of feasible solutions of potential-driven flow problems and show how they can be used to strengthen existing relaxations. First computational results indicate that the strengthend model is much tighter than the original relaxation, thus promising a computational advantage.Benjamin Hiller; Kai Helge Beckerreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6962Tue, 31 Jul 2018 20:26:57 +0200Separation of Cycle Inequalities in Periodic Timetabling
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6974
Cycle inequalities play an important role in the polyhedral study of the periodic
timetabling problem. We give the first pseudo-polynomial time separation algo-
rithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial
time separability of the change-cycle inequalities. Moreover, we provide several
NP-completeness results, indicating that pseudo-polynomial time is best possible.
The efficiency of these cutting planes is demonstrated on real-world instances of the
periodic timetabling problem.Ralf Borndörfer; Heide Hoppmann; Marika Karbstein; Niels Lindnerreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6974Tue, 31 Jul 2018 20:09:08 +0200Optimization of Capacity Expansion in Potential-driven Networks including Multiple Looping - A comparison of modelling approaches
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6972
In commodity transport networks such as natural gas, hydrogen and water networks, flows arise from nonlinear potential differences between the nodes, which can be represented by so-called "potential-driven" network models. When operators of these networks face increasing demand or the need to handle more diverse transport situations, they regularly seek to expand the capacity of their network by building new pipelines parallel to existing ones ("looping").
The paper introduces a new mixed-integer non-linear programming (MINLP) model and a new non-linear programming (NLP) model and compares these with existing models for the looping problem and related problems in the literature, both theoretically and experimentally.
On this basis, we give recommendations about the circumstances under which a certain model should be used. In particular, it turns out that one of our novel models outperforms the existing models.
Moreover, the paper is the first to include the practically relevant option that a particular pipeline may be looped several times.Ralf Lenz; Kai Helge Beckerreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6972Tue, 31 Jul 2018 16:24:49 +0200A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6968
We consider the following planning problem in public transportation: Given a
periodic timetable, how many vehicles are required to operate it?
In [9], for this sequential approach, it is proposed to first expand the periodic
timetable over time, and then answer the above question by solving a flow-based
aperiodic optimization problem.
In this contribution we propose to keep the compact periodic representation of
the timetable and simply solve a particular perfect matching problem. For practical
networks, it is very much likely that the matching problem decomposes into several
connected components. Our key observation is that there is no need to change any
turnaround decision for the vehicles of a line during the day, as long as the timetable
stays exactly the same.Ralf Borndörfer; Marika Karbstein; Christian Liebchen; Niels Lindnerreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6968Mon, 30 Jul 2018 21:46:29 +0200Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6956
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.Gregor Hendel; Matthias Miltenberger; Jakob Witzigreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6956Fri, 20 Jul 2018 12:08:09 +0200The SCIP Optimization Suite 6.0
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6936
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.Ambros Gleixner; Michael Bastubbe; Leon Eifler; Tristan Gally; Gerald Gamrath; Robert Lion Gottwald; Gregor Hendel; Christopher Hojny; Thorsten Koch; Marco E. Lübbecke; Stephen J. Maher; Matthias Miltenberger; Benjamin Müller; Marc E. Pfetsch; Christian Puchert; Daniel Rehfeldt; Franziska Schlösser; Christoph Schubert; Felipe Serrano; Yuji Shinano; Jan Merlin Viernickel; Matthias Walter; Fabian Wegscheider; Jonas T. Witt; Jakob Witzigreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6936Mon, 02 Jul 2018 12:11:52 +0200Improving Energetic Propagations for Cumulative Scheduling
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6933
We consider the Cumulative Scheduling Problem (CuSP) in which a set of $n$ jobs must be scheduled according to release dates, due dates and cumulative resource constraints. In constraint programming, the CuSP is modeled as the cumulative constraint. Among the most common propagation algorithms for the CuSP there is energetic reasoning (Baptiste et al., 1999) with a complexity of O(n^3) and edge-finding (Vilim, 2009) with O(kn log n) where k <= n is the number of different resource demands. We consider the complete versions of the propagators that perform all deductions in one call of the algorithm. In this paper, we introduce the energetic edge-finding rule that is a generalization of both energetic reasoning and edge-finding. Our main result is a complete energetic edge-finding algorithm with a complexity of O(n^2 log n) which improves upon the complexity of energetic reasoning. Moreover, we show that a relaxation of energetic edge-finding with a complexity of O(n^2) subsumes edge-finding while performing stronger propagations from energetic reasoning. A further result shows that energetic edge-finding reaches its fixpoint in strongly polynomial time. Our main insight is that energetic schedules can be interpreted as a single machine scheduling problem from which we deduce a monotonicity property that is exploited in the algorithms. Hence, our algorithms improve upon the strength and the complexity of energetic reasoning and edge-finding whose complexity status seemed widely untouchable for the last decades.Alexander Teschreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6933Tue, 26 Jun 2018 15:05:42 +0200A Polyhedral Study of Event-Based Models for the Resource-Constrained Project Scheduling Problem
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6848
We consider event-based Mixed-Integer Programming (MIP) models for the Resource-Constrained Project Scheduling Problem (RCPSP) that represent an alternative to the common time-indexed model (DDT) of Pritsker et al. (1969) for the case where the underlying time horizon is large or job processing times are subject to huge variations. In contrast to the time-indexed model, the size of event-based models does not depend on the time horizon. For two event-based formulations OOE and SEE of Koné et al. (2011) we present new valid inequalities that dominate the original formulation. Additionally, we introduce a new event-based model: the Interval Event-Based Model (IEE). We deduce linear transformations between all three models that yield the strict domination order IEE > SEE > OOE for their linear programming (LP) relaxations, meaning that IEE has the strongest linear relaxation among the event-based models. We further show that the popular DDT formulation can be retrieved from IEE by certain polyhedral operations, thus giving a unifying view on a complete branch of MIP formulations for the RCPSP. In addition, we analyze the computational performance of all presented models on test instances of the PSPLIB (Kolisch and Sprecher 1997).Alexander Teschreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6848Fri, 27 Apr 2018 12:50:15 +0200Feature-Based Algorithm Selection for Mixed Integer Programming
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6836
Mixed integer programming is a versatile and valuable optimization tool. However, solving specific problem instances can be computationally demanding even for cutting-edge solvers. Such long running times are often significantly reduced by an appropriate change of the solver's parameters. In this paper we investigate "algorithm selection", the task of choosing among a set of algorithms the ones that are likely to perform best for a particular instance.
In our case, we treat different parameter settings of the MIP solver SCIP as different algorithms to choose from. Two peculiarities of the MIP solving process have our special attention. We address the well-known problem of performance variability by using multiple random seeds. Besides solving time, primal dual integrals are recorded as a second performance measure in order to distinguish solvers that timed out.
We collected feature and performance data for a large set of publicly available MIP instances. The algorithm selection problem is addressed by several popular, feature-based methods, which have been partly extended for our purpose. Finally, an analysis of the feature space and performance results of the selected algorithms are presented.Alexander Georges; Ambros Gleixner; Gorana Gojic; Robert Lion Gottwald; David Haley; Gregor Hendel; Bartlomiej Matejczykreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6836Tue, 10 Apr 2018 15:44:52 +0200Mathematical Optimization of Rolling Stock Rotations
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6823
We show how to optimize rolling stock rotations that are required for the operation of a passenger timetable. The underlying mathematical ptimization problem is called rolling stock rotation problem (RSRP) and the leitmotiv of the thesis is RotOR, i.e., a highly integrated optimization algorithm for the RSRP. RotOR is used by DB Fernverkehr AG (DBF) in order to optimize intercity express (ICE) rotations for the European high-speed network. In this application, RSRPs have to be solved which (A) require many different aspects to be simultaneously considered, (B) are typically of large scale, and (C) include constraints that have a difficult combinatorial structure. This thesis suggests answers to these issues via the following concepts.
(A) The main model, which RotOR uses, relies on a hypergraph. The hypergraph provides an easy way to model manifold industrial railway requirements in great detail. This includes well known vehicle composition requirements as well as relatively unexplored regularity stipulations. At the same time, the hypergraph directly leads to a mixed-integer programming (MIP) model for the RSRP.
(B) The main algorithmic ingredient to solve industrial instances of the RSRP is a coarse-to-fine (C2F) column generation procedure. In this approach, the hypergraph is layered into coarse and fine layers that distinguish different levels of detail of the RSRP. The coarse layers are algorithmically utilized while pricing fine columns until proven optimality. Initially, the C2F approach is presented in terms of pure linear programming in order to provide an interface for other applications.
(C) Rolling stock rotations have to comply to resource constraints in order to ensure, e.g., enough maintenance inspections along the rotations. These constraints are computationally hard, but are well known in the literature on the vehicle routing problem (VRP). We define an interface problem in order to bridge between the RSRP and the VRP and derive a straightforward algorithmic concept, namely regional search (RS), from their common features and, moreover, differences. Our RS algorithms show promising results for classical VRPs and RSRPs.
In the first part of the thesis we present these concepts, which encompass its main mathematical contribution. The second part explains all modeling and solving components of RotOR that turn out to be essential in its industrial application. The thesis concludes with a solution to a complex re-optimization RSRP that RotOR has computed successfully for DBF. In this application all ICE vehicles of the ICE-W fleets of DBF had to be redirected past a construction site on a high-speed line in the heart of Germany.Markus Reutherdoctoralthesishttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6823Fri, 23 Mar 2018 09:42:03 +0100Analysis of operating modes of complex compressor stations
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6817
We consider the modeling of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. In particular, we propose a refined model that allows to precompute tighter relaxations for each operation mode. These relaxations may be used to strengthen the compressor station submodels in gas network optimization problems. We provide a procedure to obtain the refined model from the input data for the original model. This procedure is based on a nontrivial reduction of the graph representing the gas flow through the compressor station in an operation mode.Benjamin Hiller; René Saitenmacher; Tom Waltherreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6817Tue, 20 Mar 2018 21:06:31 +0100Cutting Planes for Union-Closed Families
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6760
Frankl’s (union-closed sets) conjecture states that for any nonempty finite union-closed (UC) family of distinct sets there exists an element in at least half of the sets. Poonen’s Theorem characterizes the existence of weights which determine
whether a given UC family ensures Frankl’s conjecture holds for all UC families which contain it. The weight systems are nontrivial to identify for a given UC family, and methods to determine such weight systems have led to several other open questions and conjectures regarding structures in UC families.
We design a cutting-plane method that computes the explicit weights which imply the existence conditions of Poonen’s Theorem using computational integer programming coupled with redundant verification routines that ensure correctness. We find over one hundred previously unknown families of sets which ensure Frankl’s conjecture holds for all families that contain any of them. This improves significantly on all previous results of the kind.
Our framework allows us to answer several open questions and conjectures regarding structural properties of UC families, including proving the 3-sets conjecture of Morris from 2006 which characterizes the minimum number of 3-sets that ensure Frankl’s conjecture holds for all families that contain them. Furthermore, our method provides a general algorithmic road-map for improving other known results and uncovering structures in UC families.Jonad Pulajdoctoralthesishttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6760Mon, 05 Mar 2018 00:23:20 +0100Improving branching for disjunctive polyhedral models using approximate convex decompositions
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6746
Disjunctive sets arise in a variety of optimization models and much esearch has been devoted to obtain strong relaxations for them. This paper focuses on the evaluation of the relaxation during the branch-and-bound search process. We argue that the branching possibilities (\ie binary variables) of the usual formulations are unsuitable to obtain strong bounds early in the search process as they do not capture the overall shape of the the entire disjunctive set. To analyze and exploit the shape of the disjunctive set we propose to compute a hierarchy of approximate convex decompositions and show how to extend the known formulations to obtain improved branching behavior.Benjamin Hiller; Tom Waltherreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6746Thu, 01 Mar 2018 17:22:29 +0100Modelling compressor stations in gas networks
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6744
Gas networks are an important application area for optimization. When considering long-range transmission, compressor stations play a crucial role in these applications. The purpose of this report is to collect and systematize the models used for compressor stations in the literature. The emphasis is on recent work on simple yet accurate polyhedral models that may replace more simplified traditional models without increasing model complexity. The report also describes an extension of the compressor station data available in GasLib (http://gaslib.zib.de/) with the parameters of these models.Benjamin Hiller; Tom Waltherreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6744Thu, 01 Mar 2018 14:38:42 +0100Mixed-Integer Programming for Clustering in Non-reversible Markov Processes
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6648
The topic of this thesis is the examination of an optimization model
which stems from the clustering process of non-reversible markov processes.
We introduce the cycle clustering problem und formulate it as a mixed
integer program (MIP).
We prove that this problem is N P-hard and discuss polytopal aspects
such as facets and dimension. The focus of this thesis is the development of
solving methods for this clustering problem. We develop problem specific
primal heuristics, as well as separation methods and an approximation
algorithm. These techniques are implemented in practice as an application
for the MIP solver SCIP.
Our computational experiments show that these solving methods result
in an average speedup of ×4 compared to generic solvers and that our
application is able to solve more instances to optimality within the given
time limit of one hour.Leon Eiflermasterthesishttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6648Fri, 19 Jan 2018 14:01:46 +0100SCIP-Jack—a solver for STP and variants with parallelization extensions: An update
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6641
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.Daniel Rehfeldt; Thorsten Kochreportzibhttps://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6641Thu, 18 Jan 2018 19:19:22 +0100