@misc{BorndoerferBreuerGrimmetal.2017, author = {Bornd{\"o}rfer, Ralf and Breuer, Matthias and Grimm, Boris and Reuther, Markus and Schade, Stanley and Schlechte, Thomas}, title = {Timetable Sparsification by Rolling Stock Rotation Optimization}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-65948}, year = {2017}, abstract = {Rolling stock optimization is a task that naturally arises by operating a railway system. It could be seen with different level of details. From a strategic perspective to have a rough plan which types of fleets to be bought to a more operational perspective to decide which coaches have to be maintained first. This paper presents a new approach to deal with rolling stock optimisation in case of a (long term) strike. Instead of constructing a completely new timetable for the strike period, we propose a mixed integer programming model that is able to choose appropriate trips from a given timetable to construct efficient tours of railway vehicles covering an optimized subset of trips, in terms of deadhead kilometers and importance of the trips. The decision which trip is preferred over the other is made by a simple evaluation method that is deduced from the network and trip defining data.}, language = {en} } @misc{RehfeldtKoch2018, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {SCIP-Jack—a solver for STP and variants with parallelization extensions: An update}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-66416}, year = {2018}, abstract = {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.}, language = {en} } @misc{WaltherHillerSaitenmacher2017, author = {Walther, Tom and Hiller, Benjamin and Saitenmacher, Ren{\´e}}, title = {Polyhedral 3D Models for compressors in gas networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-65864}, year = {2017}, abstract = {Compressor machines are crucial elements in a gas transmission network, required to compensate for the pressure loss caused by friction in the pipes. Modelling all physical and technical details of a compressor machine involves a large amount of nonlinearity, which makes it hard to use such models in the optimization of large-scale gas networks. In this paper, we are going to describe a modelling approach for the operating range of a compressor machine, starting from a physical reference model and resulting in a polyhedral representation in the 3D space of mass flow throughput as well as in- and outlet pressure.}, language = {en} } @phdthesis{Schweiger2017, author = {Schweiger, Jonas}, title = {Exploiting structure in non-convex quadratic optimization and gas network planning under uncertainty}, pages = {411}, year = {2017}, abstract = {The amazing success of computational mathematical optimization over the last decades has been driven more by insights into mathematical structures than by the advance of computing technology. In this vein, we address applications, where nonconvexity in the model and uncertainty in the data pose principal difficulties. The first part of the thesis deals with non-convex quadratic programs. Branch\&Bound methods for this problem class depend on tight relaxations. We contribute in several ways: First, we establish a new way to handle missing linearization variables in the well-known Reformulation-Linearization-Technique (RLT). This is implemented into the commercial software CPLEX. Second, we study the optimization of a quadratic objective over the standard simplex or a knapsack constraint. These basic structures appear as part of many complex models. Exploiting connections to the maximum clique problem and RLT, we derive new valid inequalities. Using exact and heuristic separation methods, we demonstrate the impact of the new inequalities on the relaxation and the global optimization of these problems. Third, we strengthen the state-of-the-art relaxation for the pooling problem, a well-known non-convex quadratic problem, which is, for example, relevant in the petrochemical industry. We propose a novel relaxation that captures the essential non-convex structure of the problem but is small enough for an in-depth study. We provide a complete inner description in terms of the extreme points as well as an outer description in terms of inequalities defining its convex hull (which is not a polyhedron). We show that the resulting valid convex inequalities significantly strengthen the standard relaxation of the pooling problem. The second part of this thesis focuses on a common challenge in real world applications, namely, the uncertainty entailed in the input data. We study the extension of a gas transport network, e.g., from our project partner Open Grid Europe GmbH. For a single scenario this maps to a challenging non-convex MINLP. As the future transport patterns are highly uncertain, we propose a robust model to best prepare the network operator for an array of scenarios. We develop a custom decomposition approach that makes use of the hierarchical structure of network extensions and the loose coupling between the scenarios. The algorithm used the single-scenario problem as black-box subproblem allowing the generalization of our approach to problems with the same structure. The scenario-expanded version of this problem is out of reach for today's general-purpose MINLP solvers. Yet our approach provides primal and dual bounds for instances with up to 256 scenarios and solves many of them to optimality. Extensive computational studies show the impact of our work.}, language = {en} } @incollection{CaimiFischerSchlechte2018, author = {Caimi, Gabrio and Fischer, Frank and Schlechte, Thomas}, title = {Railway Track Allocation}, volume = {268}, booktitle = {Handbook of Optimization in the Railway Industry}, publisher = {Springer International Publishing}, isbn = {978-3-319-72152-1}, doi = {https://doi.org/10.1007/978-3-319-72153-8}, pages = {141 -- 160}, year = {2018}, abstract = {This chapter addresses the classical task to decide which train runs on which track in a railway network. In this context a track allocation defines the precise routing of trains through a railway network, which usually has only a limited capacity. Moreover, the departure and arrival times at the visited stations of each train must simultaneously meet several operational and safety requirements. The problem to find the 'best possible' allocation for all trains is called the track allocation problem (TTP). Railway systems can be modeled on a very detailed scale covering the behavior of individual trains and the safety system to a large extent. However, those microscopic models are too big and not scalable to large networks, which make them inappropriate for mathematical optimization on a network wide level. Hence, most network optimization approaches consider simplified, so called macroscopic, models. In the first part we take a look at the challenge to construct a reliable and condensed macroscopic model for the associated microscopic model and to facilitate the transition between both models of different scale. In the main part we focus on the optimization problem for macroscopic models of the railway system. Based on classical graph-theoretical tools the track allocation problem is formulated to determine conflict-free paths in corresponding time-expanded graphs. We present standard integer programming model formulations for the track allocation problem that model resource or block conflicts in terms of packing constraints. In addition, we discuss the role of maximal clique inequalities and the concept of configuration networks. We will also present classical decomposition approaches like Lagrangian relaxation and bundle methods. Furthermore, we will discuss recently developed techniques, e.g., dynamic graph generation. Finally, we will discuss the status quo and show a vision of mathematical optimization to support real world track allocation, i.e. integrated train routing and scheduling, in a data-dominated and digitized railway future.}, language = {en} } @article{BertholdHendelKoch2017, author = {Berthold, Timo and Hendel, Gregor and Koch, Thorsten}, title = {From feasibility to improvement to proof: three phases of solving mixed-integer programs}, volume = {33}, journal = {Optimization Methods and Software}, number = {3}, publisher = {Taylor \& Francis}, doi = {10.1080/10556788.2017.1392519}, pages = {499 -- 517}, year = {2017}, abstract = {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.}, language = {en} } @article{SchmidtAssmannBurlacuetal.2017, author = {Schmidt, Martin and Assmann, Denis and Burlacu, Robert and Humpola, Jesco and Joormann, Imke and Kanelakis, Nikolaos and Koch, Thorsten and Oucherif, Djamal and Pfetsch, Marc and Schewe, Lars and Schwarz, Robert and Sirvent, Matthias}, title = {GasLib - A Library of Gas Network Instances}, volume = {2}, journal = {Data}, number = {4}, doi = {10.3390/data2040040}, year = {2017}, language = {en} } @article{Koch2017, author = {Koch, Thorsten}, title = {The ZIMPL modeling language}, volume = {103}, journal = {Optima}, pages = {8 -- 9}, year = {2017}, language = {en} } @misc{RehfeldtKoch2017, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem}, issn = {1438-0064}, doi = {10.1137/17M1145963}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64699}, year = {2017}, abstract = {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.}, language = {en} } @misc{SchadeBorndoerferBreueretal.2017, author = {Schade, Stanley and Bornd{\"o}rfer, Ralf and Breuer, Matthias and Grimm, Boris and Reuther, Markus and Schlechte, Thomas and Siebeneicher, Patrick}, title = {Pattern Detection For Large-Scale Railway Timetables}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-63390}, year = {2017}, abstract = {We consider railway timetables of our industrial partner DB Fernverkehr AG that operates the ICE high speed trains in the long-distance passenger railway network of Germany. Such a timetable covers a whole year with 364 days and, typically, includes more than 45,000 trips. A rolling stock rotation plan is not created for the whole timetable at once. Instead the timetable is divided into regular invariant sections and irregular deviations (e.g. for public holidays). A separate rotation plan with a weekly period can then be provided for each of the different sections of the timetable. We present an algorithmic approach to automatically recognize these sections. Together with the supplementing visualisation of the timetable this method has shown to be very relevant for our industrial partner.}, language = {en} } @misc{GilgKlugMartienssenetal.2017, author = {Gilg, Brady and Klug, Torsten and Martienssen, Rosemarie and Paat, Joseph and Schlechte, Thomas and Schulz, Christof and Seymen, Sinan and Tesch, Alexander}, title = {Conflict-Free Railway Track Assignment at Depots}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-63843}, year = {2017}, abstract = {Managing rolling stock with no passengers aboard is a critical component of railway operations. In particular, one problem is to park the rolling stock on a given set of tracks at the end of a day or service. Depending on the parking assignment, shunting may be required in order for a parked train to depart or for an incoming train to park. Given a collection of tracks M and a collection of trains T with fixed arrival-departure timetable, the train assignment problem (TAP) is to determine the maximum number of trains from T that can be parked on M according to the timetable and without the use of shunting. Hence, efficiently solving the TAP allows to quickly compute feasible parking schedules that do not require further shunting adjustments. In this paper, we present two integer programming models for solving the TAP. To our knowledge, this is the first integrated approach that considers track lengths along with the three most common types of parking tracks. We compare these models on a theoretical level. We also prove that a decision version of the TAP is NP-complete, justifying the use of integer programming techniques. Using stochastic and robust modelling techniques, both models produce parking assignments that are optimized and robust according to random train delays. We conclude with computational results for both models, observing that they perform well on real timetables.}, language = {en} } @article{RehfeldtKochMaher2019, author = {Rehfeldt, Daniel and Koch, Thorsten and Maher, Stephen J.}, title = {Reduction Techniques for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem}, volume = {73}, journal = {Networks}, edition = {2}, publisher = {Wiley}, doi = {10.1002/net.21857}, pages = {206 -- 233}, year = {2019}, abstract = {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.}, language = {en} } @article{RehfeldtKoch2018, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP}, volume = {36}, journal = {Journal of Computational Mathematics}, number = {3}, doi = {10.4208/jcm.1709-m2017-0002}, pages = {459 -- 468}, year = {2018}, abstract = {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.}, language = {en} } @misc{Rehfeldt2015, type = {Master Thesis}, author = {Rehfeldt, Daniel}, title = {A Generic Approach to Solving the Steiner Tree Problem and Variants}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57817}, pages = {185}, year = {2015}, abstract = {Spawned by practical applications, numerous variations of the classical Steiner tree problem in graphs have been studied during the last decades. Despite the strong relationship between the different variants, solution approaches employed so far have been prevalently problem-specific. In contrast, we pursue a general-purpose strategy resulting in a solver able to solve both the classical Steiner tree problem and ten of its variants without modification. These variants include well-known problems such as the prize-collecting Steiner tree problem, the maximum-weight connected subgraph problem or the rectilinear minimum Steiner tree problem. Bolstered by a variety of new methods, most notably reduction techniques, our solver is not only of unprecedented versatility, but furthermore competitive or even superior to specialized state-of-the-art programs for several Steiner problem variants.}, language = {en} } @inproceedings{BorndoerferLamorgeseKlugetal.2015, author = {Bornd{\"o}rfer, Ralf and Lamorgese, Leonardo and Klug, Torsten and Mannino, Carlo and Reuther, Markus and Schlechte, Thomas}, title = {Recent Success Stories on Optimization of Railway Systems}, booktitle = {Proceedings of the IAROR conference RailTokyo}, year = {2015}, abstract = {Planning and operating railway transportation systems is an extremely hard task due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. Because of that, however, mathematical models and optimization techniques can result in large gains for both railway cus- tomers and operators, e.g., in terms of cost reductions or service quality improvements. In the last years a large and growing group of researchers in the OR community have devoted their attention to this domain devel- oping mathematical models and optimization approaches to tackle many of the relevant problems in the railway planning process. However, there is still a gap to bridge between theory and practice, with a few notable exceptions. In this paper we address three success stories, namely, long-term freight train routing (part I), mid-term rolling stock rotation planning (part II), and real-time train dispatching (part III). In each case, we describe real-life, successful implementations. We will dis- cuss the individual problem setting, survey the optimization literature, and focus on particular aspects addressed by the mathematical models. We demonstrate on concrete applications how mathematical optimization can support railway planning and operations. This gives proof that math- ematical optimization can support the planning of rolling stock resources. Thus, mathematical models and optimization can lead to a greater effi- ciency of railway operations and will serve as a powerful and innovative tool to meet recent challenges of the railway industry.}, language = {en} } @inproceedings{GamrathMelchioriBertholdetal.2015, author = {Gamrath, Gerald and Melchiori, Anna and Berthold, Timo and Gleixner, Ambros and Salvagnin, Domenico}, title = {Branching on Multi-aggregated Variables}, volume = {9075}, booktitle = {Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2015}, doi = {10.1007/978-3-319-18008-3_10}, pages = {141 -- 156}, year = {2015}, abstract = {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.}, language = {en} } @inproceedings{KlugJunoszaSzaniawskiKwasiborskietal.2015, author = {Klug, Torsten and Junosza-Szaniawski, Konstanty and Kwasiborski, Slawomir and F{\"u}genschuh, Armin and Schlechte, Thomas}, title = {Fastest, Average and Quantile Schedule}, booktitle = {SOFSEM 2015: Theory and Practice of Computer Science}, publisher = {Springer Berlin Heidelberg}, doi = {10.1007/978-3-662-46078-8_17}, pages = {201 -- 216}, year = {2015}, abstract = {We consider problems concerning the scheduling of a set of trains on a single track. For every pair of trains there is a minimum headway, which every train must wait before it enters the track after another train. The speed of each train is also given. Hence for every schedule - a sequence of trains - we may compute the time that is at least needed for all trains to travel along the track in the given order. We give the solution to three problems: the fastest schedule, the average schedule, and the problem of quantile schedules. The last problem is a question about the smallest upper bound on the time of a given fraction of all possible schedules. We show how these problems are related to the travelling salesman problem. We prove NP-completeness of the fastest schedule problem, NP-hardness of quantile of schedules problem, and polynomiality of the average schedule problem. We also describe some algorithms for all three problems. In the solution of the quantile problem we give an algorithm, based on a reverse search method, generating with polynomial delay all Eulerian multigraphs with the given degree sequence and a bound on the number of such multigraphs. A better bound is left as an open question.}, language = {en} } @inproceedings{FischerSchlechte2015, author = {Fischer, Frank and Schlechte, Thomas}, title = {Comparing two dual relaxations of large scale train timetabling problems}, booktitle = {Proceedings of Conference on Advanced Systems in Public Transport 2015}, year = {2015}, abstract = {Railway transportation and in particular train timetabling is one of the basic and source application areas of combinatorial optimization and integer programming. We will discuss two well established modeling techniques for the train timetabling problem. In this paper we focus on one major ingredient - the bounding by dual relaxations. We compare two classical dual relaxations of large scale time expanded train timetabling problems - the Lagrangean Dual and Lagrangean Decomposition. We discuss the convergence behavior and show limitations of the Lagrangean Decomposition approach for a configuration based model. We introduce a third dualization approach to overcome those limitations. Finally, we present promising preliminary computational experiments that show that our new approach indeed has superior convergence properties.}, language = {en} } @article{BertholdHendel2014, author = {Berthold, Timo and Hendel, Gregor}, title = {Shift-and-Propagate}, volume = {21}, journal = {Journal of Heuristics}, number = {1}, doi = {10.1007/s10732-014-9271-0}, pages = {73 -- 106}, year = {2014}, abstract = {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.}, language = {en} } @article{BorndoerferHeismann2015, author = {Bornd{\"o}rfer, Ralf and Heismann, Olga}, title = {The hypergraph assignment problem}, volume = {15}, journal = {Discrete Optimization}, doi = {10.1016/j.disopt.2014.11.002}, pages = {15 -- 25}, year = {2015}, language = {en} } @misc{GamrathKochRehfeldtetal.2014, author = {Gamrath, Gerald and Koch, Thorsten and Rehfeldt, Daniel and Shinano, Yuji}, title = {SCIP-Jack - A massively parallel STP solver}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-52293}, year = {2014}, abstract = {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.}, language = {en} } @misc{BorndoerferReutherSchlechte2014, author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas}, title = {A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-51009}, year = {2014}, abstract = {We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.}, language = {en} } @misc{BorndoerferKarbsteinMehrgardtetal.2014, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika and Mehrgardt, Julika and Reuther, Markus and Schlechte, Thomas}, title = {The Cycle Embedding Problem}, issn = {1438-0064}, doi = {10.1007/978-3-319-28697-6_65}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-52788}, year = {2014}, abstract = {Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach.}, language = {en} } @article{HumpolaLehmannFuegenschuh2015, author = {Humpola, Jesco and Lehmann, Thomas and F{\"u}genschuh, Armin}, title = {A primal heuristic for optimizing the topology of gas networks based on dual information}, volume = {3}, journal = {EURO Journal on Computational Optimization}, number = {1}, doi = {10.1007/s13675-014-0029-0}, pages = {53 -- 78}, year = {2015}, abstract = {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.}, language = {en} } @inproceedings{Reuther2014, author = {Reuther, Markus}, title = {Local Search for the Resource Constrained Assignment Problem}, volume = {42}, booktitle = {14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems}, doi = {10.4230/OASIcs.ATMOS.2014.62}, pages = {62 -- 78}, year = {2014}, abstract = {The resource constrained assignment problem (RCAP) is to find a minimal cost cycle partition in a directed graph such that a resource constraint is fulfilled. The RCAP has its roots in an application that deals with the covering of a railway timetable by rolling stock vehicles. Here, the resource constraint corresponds to maintenance constraints for rail vehicles. Moreover, the RCAP generalizes several variants of vehicle routing problems. We contribute a local search algorithm for this problem that is derived from an exact algorithm which is similar to the Hungarian method for the standard assignment problem. Our algorithm can be summarized as a k-OPT heuristic, exchanging k arcs of an alternating cycle of the incumbent solution in each improvement step. The alternating cycles are found by dual arguments from linear programming. We present computational results for instances from our railway application at Deutsche Bahn Fernverkehr AG as well as for instances of the vehicle routing problem from the literature.}, language = {en} } @misc{BeckenbachBorndoerfer2014, author = {Beckenbach, Isabel and Bornd{\"o}rfer, Ralf}, title = {An Approximation Result for Matchings in Partitioned Hypergraphs}, doi = {10.1007/978-3-319-28697-6_5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-51083}, year = {2014}, abstract = {We investigate the matching and perfect matching polytopes of hypergraphs having a special structure, which we call partitioned hypergraphs. We show that the integrality gap of the standard LP-relaxation is at most \$2\sqrt{d}\$ for partitioned hypergraphs with parts of size \$\leq d\$. Furthermore, we show that this bound cannot be improved to \$\mathcal{O}(d^{0.5-\epsilon})\$.}, language = {en} } @article{Maher2015, author = {Maher, Stephen J.}, title = {Solving the integrated airline recovery problem using column-and-row generation}, volume = {50}, journal = {Transportation Science}, number = {1}, doi = {10.1287/trsc.2014.0552}, pages = {216 -- 239}, year = {2015}, abstract = {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.}, language = {en} } @inproceedings{BorndoerferMehrgardtReutheretal.2014, author = {Bornd{\"o}rfer, Ralf and Mehrgardt, Julika and Reuther, Markus and Schlechte, Thomas and Waas, Kerstin}, title = {Re-Optimization of Rolling Stock Rotations}, edition = {Operations Research Proceedings 2013}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-07001-8_8}, pages = {49 -- 55}, year = {2014}, abstract = {The Rolling Stock Rotation Problem is to schedule rail vehicles in order to cover timetabled trips by a cost optimal set of vehicle rotations. The problem integrates several facets of railway optimization, such as vehicle composition, maintenance constraints, and regularity aspects. In industrial applications existing vehicle rotations often have to be re-optimized to deal with timetable changes or construction sites. We present an integrated modeling and algorithmic approach to this task as well as computational results for industrial problem instances of DB Fernverkehr AG.}, language = {en} } @misc{RalphsShinanoBertholdetal.2016, author = {Ralphs, Ted and Shinano, Yuji and Berthold, Timo and Koch, Thorsten}, title = {Parallel Solvers for Mixed Integer Linear Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-62239}, year = {2016}, abstract = {In this article, we introduce parallel mixed integer linear programming (MILP) solvers. MILP solving algorithms have been improved tremendously in the last two decades. Currently, commercial MILP solvers are known as a strong optimization tool. Parallel MILP solver development has started in 1990s. However, since the improvements of solving algorithms have much impact to solve MILP problems than application of parallel computing, there were not many visible successes. With the spread of multi-core CPUs, current state-of-the-art MILP solvers have parallel implementations and researches to apply parallelism in the solving algorithm also getting popular. We summarize current existing parallel MILP solver architectures.}, language = {en} } @misc{HillerWalther2018, author = {Hiller, Benjamin and Walther, Tom}, title = {Modelling compressor stations in gas networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-67443}, year = {2018}, abstract = {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.}, language = {en} } @inproceedings{WitzigBertholdHeinz2017, author = {Witzig, Jakob and Berthold, Timo and Heinz, Stefan}, title = {Experiments with Conflict Analysis in Mixed Integer Programming}, volume = {10335}, booktitle = {Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2017}, publisher = {Springer}, doi = {10.1007/978-3-319-59776-8_17}, pages = {211 -- 222}, year = {2017}, abstract = {The analysis of infeasible subproblems plays an import role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications obtained by domain propagation that led to infeasibility. The result of the analysis is one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept has its origin in solving satisfiability problems and is similarly used in constraint programming. The second concept is to analyze infeasible linear programming (LP) relaxations. The dual LP solution provides a set of multipliers that can be used to generate a single new globally valid linear constraint. The main contribution of this short paper is an empirical evaluation of two ways to combine both approaches. Experiments are carried out on general MIP instances from standard public test sets such as Miplib2010; the presented algorithms have been implemented within the non-commercial MIP solver SCIP. Moreover, we present a pool-based approach to manage conflicts which addresses the way a MIP solver traverses the search tree better than aging strategies known from SAT solving.}, language = {en} } @article{VigerskeGleixner2018, author = {Vigerske, Stefan and Gleixner, Ambros}, title = {SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework}, volume = {33}, journal = {Optimization Methods \& Software}, number = {3}, doi = {10.1080/10556788.2017.1335312}, pages = {563 -- 593}, year = {2018}, abstract = {This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality. SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An expression graph representation of nonlinear constraints allows for bound tightening, structure analysis, and reformulation. Primal heuristics are employed throughout the solving process to find feasible solutions early. We provide insights into the performance impact of individual MINLP solver components via a detailed computational study over a large and heterogeneous test set.}, language = {en} } @inproceedings{SchadeBorndoerferBreueretal.2017, author = {Schade, Stanley and Bornd{\"o}rfer, Ralf and Breuer, Matthias and Grimm, Boris and Reuther, Markus and Schlechte, Thomas and Siebeneicher, Patrick}, title = {Pattern Detection For Large-Scale Railway Timetables}, booktitle = {Proceedings of the IAROR conference RailLille}, year = {2017}, abstract = {We consider railway timetables of our industrial partner DB Fernverkehr AG that operates the ICE high speed trains in the long-distance passenger railway network of Germany. Such a timetable covers a whole year with 364 days and, typically, includes more than 45,000 trips. A rolling stock rotation plan is not created for the whole timetable at once. Instead the timetable is divided into regular invariant sections and irregular deviations (e.g. for public holidays). A separate rotation plan with a weekly period can then be provided for each of the different sections of the timetable. We present an algorithmic approach to automatically recognize these sections. Together with the supplementing visualisation of the timetable this method has shown to be very relevant for our industrial partner.}, language = {en} } @inproceedings{BorndoerferReutherSchlechteetal.2015, author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Schulz, Christof and Swarat, Elmar and Weider, Steffen}, title = {Duty Rostering in Public Transport - Facing Preferences, Fairness, and Fatigue}, booktitle = {Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)}, year = {2015}, abstract = {Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively.}, language = {en} } @inproceedings{BorndoerferHoppmannKarbstein2017, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Umsteigen ohne Warten}, booktitle = {HEUREKA 2017}, year = {2017}, abstract = {Wir stellen einen mathematischen Optimierungsansatz zur Berechnung von periodischen Taktfahrpl{\"a}nen vor, bei dem die Umsteigezeiten unter Ber{\"u}cksichtigung des Passagierverhaltens minimiert werden. Wir untersuchen damit den Einfluss wichtiger Systemparameter und Verhaltensmuster auf die Bef{\"o}rderungsqualit{\"a}t.}, language = {de} } @inproceedings{HillerSaitenmacherWalther2017, author = {Hiller, Benjamin and Saitenmacher, Ren{\´e} and Walther, Tom}, title = {Analysis of operating modes of complex compressor stations}, booktitle = {Proceedings of Operations Research 2016}, doi = {10.1007/978-3-319-55702-1_34}, pages = {251 -- 257}, year = {2017}, abstract = {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.}, language = {en} } @masterthesis{Viernickel2016, type = {Bachelor Thesis}, author = {Viernickel, Jan Merlin}, title = {Absch{\"a}tzung der Suchbaumgr{\"o}ße und Laufzeit f{\"u}r Branch-and-Bound Algorithmen}, year = {2016}, language = {de} } @misc{Gottwald2016, type = {Master Thesis}, author = {Gottwald, Robert Lion}, title = {Experiments with Concurrency and Heuristics in SCIP}, year = {2016}, language = {en} } @masterthesis{Roessig2016, type = {Bachelor Thesis}, author = {Roessig, Ansgar}, title = {Formulations and algorithms for the USCCSP}, year = {2016}, language = {en} } @misc{Teuchert2017, type = {Master Thesis}, author = {Teuchert, Andreas}, title = {Degeneriertheit im Simplexverfahren}, year = {2017}, language = {de} } @misc{Hendel2015, author = {Hendel, Gregor}, title = {Exploiting Solving Phases for Mixed-Integer Programs}, issn = {1438-0064}, doi = {10.1007/978-3-319-42902-1_1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57098}, year = {2015}, abstract = {Modern MIP solving software incorporates dozens of auxiliary algorithmic components for supporting the branch-and-bound search in finding and improving solutions and in strengthening the relaxation. Intuitively, a dynamic solving strategy with an appropriate emphasis on different solving components and strategies is desirable during the search process. We propose an adaptive solver behavior that dynamically reacts on transitions between the three typical phases of a MIP solving process: The first phase objective is to find a feasible solution. During the second phase, a sequence of incumbent solutions gets constructed until the incumbent is eventually optimal. Proving optimality is the central objective of the remaining third phase. Based on the MIP-solver SCIP, we demonstrate the usefulness of the phase concept both with an exact recognition of the optimality of a solution, and provide heuristic alternatives to make use of the concept in practice.}, language = {en} } @article{BorndoerferReutherSchlechteetal.2016, author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Waas, Kerstin and Weider, Steffen}, title = {Integrated Optimization of Rolling Stock Rotations for Intercity Railways}, volume = {50}, journal = {Transportation Science}, number = {3}, doi = {10.1287/trsc.2015.0633}, pages = {863 -- 877}, year = {2016}, abstract = {This paper proposes a highly integrated solution approach for rolling stock planning problems in the context of long distance passenger traffic between cities. The main contributions are a generic hypergraph-based mixed-integer programming model for the considered rolling stock rotation problem and an integrated algorithm for its solution. The newly developed algorithm is able to handle a large spectrum of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacities, and regularity aspects. We show that our approach has the power to produce rolling stock rotations that can be implemented in practice. In this way, the rolling stock rotations at the largest German long distance operator Deutsche Bahn Fernverkehr AG could be optimized by an automated system utilizing advanced mathematical programming techniques.}, language = {en} } @misc{YokoyamaShinanoTaniguchietal.2014, author = {Yokoyama, Ryohei and Shinano, Yuji and Taniguchi, Syusuke and Ohkura, Masashi and Wakui, Tetsuya}, title = {Optimization of energy supply systems by MILP branch and bound method in consideration of hierarchical relationship between design and operation}, issn = {1438-0064}, doi = {10.1016/j.enconman.2014.12.020}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-49413}, year = {2014}, abstract = {To attain the highest performance of energy supply systems, it is necessary to rationally determine types, capacities, and numbers of equipment in consideration of their operational strategies corresponding to seasonal and hourly variations in energy demands. In the combinatorial optimization method based on the mixed-integer linear programming (MILP), integer variables are used to express the selection, numbers, and on/off status of operation of equipment, and the number of these variables increases with those of equipment and periods for variations in energy demands, and affects the computation efficiency significantly. In this paper, a MILP method utilizing the hierarchical relationship between design and operation variables is proposed to solve the optimal design problem of energy supply systems efficiently: At the upper level, the optimal values of design variables are searched by the branch and bound method; At the lower level, the values of operation variables are optimized independently at each period by the branch and bound method under the values of design variables given tentatively during the search at the upper level; Lower bounds for the optimal value of the objective function are evaluated, and are utilized for the bounding operations at both the levels. This method is implemented into open and commercial MILP solvers. Illustrative and practical case studies on the optimal design of cogeneration systems are conducted, and the validity and effectiveness of the proposed method are clarified.}, language = {en} } @misc{GleixnerSteffyWolter2015, author = {Gleixner, Ambros and Steffy, Daniel and Wolter, Kati}, title = {Iterative Refinement for Linear Programming}, issn = {1438-0064}, doi = {10.1287/ijoc.2016.0692}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-55118}, year = {2015}, abstract = {We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved share the same constraint matrix as the original problem instance and are transformed only by modification of the objective function, right-hand side, and variable bounds. Exact computation is used to compute and store the exact representation of the transformed problems, while numeric computation is used for solving LPs. At all steps of the algorithm the LP bases encountered in the transformed problems correspond directly to LP bases in the original problem description. We show that this algorithm is effective in practice for computing extended precision solutions and that it leads to a direct improvement of the best known methods for solving LPs exactly over the rational numbers. Our implementation is publically available as an extension of the academic LP solver SoPlex.}, language = {en} } @misc{GamrathBertholdHeinzetal.2015, author = {Gamrath, Gerald and Berthold, Timo and Heinz, Stefan and Winkler, Michael}, title = {Structure-based primal heuristics for mixed integer programming}, issn = {1438-0064}, doi = {http://dx.doi.org/10.1007/978-4-431-55420-2_3}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-55518}, year = {2015}, abstract = {Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They help to reach optimality faster and provide good feasible solutions early in the solving process. In this paper, we present two new primal heuristics which take into account global structures available within MIP solvers to construct feasible solutions at the beginning of the solving process. These heuristics follow a large neighborhood search (LNS) approach and use global structures to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. The definition of the neighborhood is done by iteratively fixing variables and propagating these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. The neighborhood is solved as a sub-MIP and solutions are transferred back to the original problem. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about every third instance and therewith help to improve the average solving time.}, language = {en} } @article{MaherMurray2016, author = {Maher, Stephen J. and Murray, John M.}, title = {The unrooted set covering connected subgraph problem differentiating between HIV envelope sequences}, volume = {248}, journal = {European Journal of Operational Research}, number = {2}, doi = {doi:10.1016/j.ejor.2015.07.011}, pages = {668 -- 680}, year = {2016}, abstract = {This paper presents a novel application of operations research techniques to the analysis of HIV Env gene sequences, aiming to identify key features that are possible vaccine targets. These targets are identified as being critical to the transmission of HIV by being present in early transmitted (founder) sequences and absent in later chronic sequences. Identifying the key features of Env involves two steps: first, calculating the covariance of amino acid combinations and positions to form a network of related and compensatory mutations; and second, developing an integer program to identify the smallest connected subgraph of the constructed covariance network that exhibits a set covering property. The integer program developed for this analysis, labelled the unrooted set covering connected subgraph problem (USCCSP), integrates a set covering problem and connectivity evaluation, the latter formulated as a network flow problem. The resulting integer program is very large and complex, requiring the use of Benders' decomposition to develop an efficient solution approach. The results will demonstrate the necessity of applying acceleration techniques to the Benders' decomposition solution approach and the effectiveness of these techniques and heuristic approaches for solving the USCCSP.}, language = {en} } @inproceedings{GamrathHillerWitzig2015, author = {Gamrath, Gerald and Hiller, Benjamin and Witzig, Jakob}, title = {Reoptimization Techniques in MIP Solvers}, volume = {9125}, edition = {Experimental Algorithms, Lecture Notes in Computer Science}, publisher = {Springer}, isbn = {978-3-319-20086-6}, doi = {10.1007/978-3-319-20086-6_14}, pages = {181 -- 192}, year = {2015}, abstract = {Recently, there have been many successful applications of optimization algorithms that solve a sequence of quite similar mixed-integer programs (MIPs) as subproblems. Traditionally, each problem in the sequence is solved from scratch. In this paper we consider reoptimization techniques that try to benefit from information obtained by solving previous problems of the sequence. We focus on the case that subsequent MIPs differ only in the objective function or that the feasible region is reduced. We propose extensions of the very complex branch-and-bound algorithms employed by general MIP solvers based on the idea to ``warmstart'' using the final search frontier of the preceding solver run. We extend the academic MIP solver SCIP by these techniques to obtain a reoptimizing branch-and-bound solver and report computational results which show the effectiveness of the approach.}, language = {en} } @incollection{HillerHaynHeitschetal.2015, author = {Hiller, Benjamin and Hayn, Christine and Heitsch, Holger and Henrion, Ren{\´e} and Le{\"o}vey, Hernan and M{\"o}ller, Andris and R{\"o}misch, Werner}, title = {Methods for verifying booked capacities}, booktitle = {Evaluating gas network capacities}, publisher = {Society for Industrial and Applied Mathematics}, pages = {291 -- 315}, year = {2015}, language = {en} } @misc{GamrathBertholdHeinzetal.2017, author = {Gamrath, Gerald and Berthold, Timo and Heinz, Stefan and Winkler, Michael}, title = {Structure-driven fix-and-propagate heuristics for mixed integer programming}, issn = {1438-0064}, doi = {10.1007/s12532-019-00159-1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-65387}, year = {2017}, abstract = {Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early in the solving process and help to solve instances to optimality faster. In this paper, we present a scheme for primal start heuristics that can be executed without previous knowledge of an LP solution or a previously found integer feasible solution. It uses global structures available within MIP solvers to iteratively fix integer variables and propagate these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. If sufficiently many variables can be fixed that way, the resulting problem is solved as an LP and the solution is rounded. If the rounded solution did not provide a feasible solution already, a sub-MIP is solved for the neighborhood defined by the variable fixings performed in the first phase. The global structures help to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. We present three primal heuristics that use this scheme based on different global structures. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about three out of five instances and therewith help to improve several performance measures for MIP solvers, including the primal integral and the average solving time.}, language = {en} } @misc{BertholdHendelKoch2016, author = {Berthold, Timo and Hendel, Gregor and Koch, Thorsten}, title = {The Three Phases of MIP Solving}, issn = {1438-0064}, doi = {10.1080/10556788.2017.1392519}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61607}, year = {2016}, abstract = {Modern 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 different 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 behavior of the MIP solver SCIP at the predicted phase transition points.}, language = {en} }