TY - GEN A1 - Petkovic, Milena A1 - Zakiyeva, Nazgul T1 - Mathematical Optimization for Analyzing and Forecasting Nonlinear Network Time Series N2 - This work presents an innovative short to mid-term forecasting model that analyzes nonlinear complex spatial and temporal dynamics in energy networks under demand and supply balance constraints using Network Nonlinear Time Series (TS) and Mathematical Programming (MP) approach. We address three challenges simultaneously, namely, the adjacency matrix is unknown; the total amount in the network has to be balanced; dependence is unnecessarily linear. We use a nonparametric approach to handle the nonlinearity and estimate the adjacency matrix under the sparsity assumption. The estimation is conducted with the Mathematical Optimisation method. We illustrate the accuracy and effectiveness of the model on the example of the natural gas transmission network of one of the largest transmission system operators (TSOs) in Germany, Open Grid Europe. The obtained results show that, especially for shorter forecasting horizons, the proposed method outperforms all considered benchmark models, improving the average nMAPE for 5.1% and average RMSE for 79.6% compared to the second-best model. The model is capable of capturing the nonlinear dependencies in the complex spatial-temporal network dynamics and benefits from both sparsity assumption and the demand and supply balance constraint. T3 - ZIB-Report - 22-19 KW - nonlinear time series KW - mathematical optimization KW - energy networks Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-88037 SN - 1438-0064 ER - TY - GEN A1 - Witzig, Jakob A1 - Berthold, Timo A1 - Heinz, Stefan T1 - Experiments with Conflict Analysis in Mixed Integer Programming N2 - 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. T3 - ZIB-Report - 16-63 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61087 SN - 1438-0064 ER - TY - GEN A1 - Cheung, Kevin K. H. A1 - Gleixner, Ambros A1 - Steffy, Daniel T1 - Verifying Integer Programming Results N2 - Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MILP solution algorithms, the ideal form of such a certificate is not entirely clear. This paper proposes such a certificate format, illustrating its capabilities and structure through examples. The certificate format is designed with simplicity in mind and is composed of a list of statements that can be sequentially verified using a limited number of simple yet powerful inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created. We report computational results on a selection of mixed-integer linear programming instances from the literature. To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates. T3 - ZIB-Report - 16-58 KW - correctness, verification, proof, certificate, optimality, infeasibility, mixed-integer linear programming Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61044 SN - 1438-0064 ER - TY - GEN A1 - Tesch, Alexander T1 - A Polyhedral Study of Event-Based Models for the Resource-Constrained Project Scheduling Problem N2 - 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). T3 - ZIB-Report - 17-79 KW - Scheduling KW - Mixed-Integer Programming Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-68485 SN - 1438-0064waoa ER - TY - GEN A1 - Tesch, Alexander T1 - Improving Energetic Propagations for Cumulative Scheduling N2 - 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. T3 - ZIB-Report - 18-29 KW - Cumulative Scheduling KW - Constraint Programming KW - Propagation Algorithm Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69331 SN - 1438-0064 ER - TY - GEN A1 - Hosoda, Junko A1 - Maher, Stephen J. A1 - Shinano, Yuji T1 - Combining Benders’ decomposition and parallelisation to solve large-scale adaptive network supply chain management problems N2 - Integrated supply chain network design—combining warehouse clustering with inter- and intra-cluster vehicle routing—is a fundamental feature of supply chain management problems. In this paper, a Benders’ decomposition-based parallel heuristic approach for the integrated long-haul and local vehicle routing problem is proposed. The proposed algorithm comprises lower- and upper-bound search algorithms running in parallel to find high-quality solutions for challenging supply chain management problems. A novel Benders’ decomposition approach is proposed to aid the improvement in the lower bound for large-scale problems. The results demonstrate that the Benders’ decomposition approach is effective in finding strong lower bounds and is beneficial for obtaining high-quality solutions. T3 - ZIB-Report - 24-12 Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-98744 SN - 1438-0064 ER - TY - GEN A1 - Fujii, Koichi A1 - Kim, Sunyoung A1 - Kojima, Masakazu A1 - Mittelmann, Hans D. A1 - Shinano, Yuji T1 - The Largest Unsolved QAP Instance Tai256c Can Be Converted into A 256-dimensional Simple BQOP with A Single Cardinality Constraint N2 - Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB; a 1.48% gap remains between the best known feasible objective value and lower bound of the unknown optimal value. This paper shows that the instance can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which requires the sum of the binary variables to be 92.The converted BQOP is much simpler than the original QAP tai256c and it also inherits some of the symmetry properties. However, it is still very difficult to solve. We present an efficient branch and bound method for improving the lower bound effectively. A new lower bound with 1.36% gap is also provided. T3 - ZIB-Report - 22-18 Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-88086 SN - 1438-0064 ER - TY - GEN A1 - Turner, Mark A1 - Koch, Thorsten A1 - Serrano, Felipe A1 - Winkler, Michael T1 - Adaptive Cut Selection in Mixed-Integer Linear Programming N2 - Cut selection is a subroutine used in all modern mixed-integer linear programming solvers with the goal of selecting a subset of generated cuts that induce optimal solver performance. These solvers have millions of parameter combinations, and so are excellent candidates for parameter tuning. Cut selection scoring rules are usually weighted sums of different measurements, where the weights are parameters. We present a parametric family of mixed-integer linear programs together with infinitely many family-wide valid cuts. Some of these cuts can induce integer optimal solutions directly after being applied, while others fail to do so even if an infinite amount are applied. We show for a specific cut selection rule, that any finite grid search of the parameter space will always miss all parameter values, which select integer optimal inducing cuts in an infinite amount of our problems. We propose a variation on the design of existing graph convolutional neural networks, adapting them to learn cut selection rule parameters. We present a reinforcement learning framework for selecting cuts, and train our design using said framework over MIPLIB 2017. Our framework and design show that adaptive cut selection does substantially improve performance over a diverse set of instances, but that finding a single function describing such a rule is difficult. Code for reproducing all experiments is available at https://github.com/Opt-Mucca/Adaptive-Cutsel-MILP. T3 - ZIB-Report - 22-04 KW - cut selection KW - mixed-integer linear programming KW - reinforcement learning Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-86055 SN - 1438-0064 ER - TY - GEN A1 - Lenz, Ralf A1 - Becker, Kai-Helge T1 - Optimization of Capacity Expansion in Potential-driven Networks including Multiple Looping - A comparison of modelling approaches N2 - 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. T3 - ZIB-Report - 18-44 KW - OR in energy KW - Network expansion KW - MINLP Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69726 SN - 1438-0064 ER - TY - GEN A1 - Ito, Satoshi A1 - Shinano, Yuji T1 - Calculation of clinch and elimination numbers for sports leagues with multiple tiebreaking criteria N2 - 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. T3 - ZIB-Report - 18-51 KW - Sports league KW - Round-robin tournament KW - Tiebreaking criteria KW - Clinch number KW - Elimination number KW - Combinatorial optimization KW - Integer programming Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-70591 SN - 1438-0064 ER - TY - GEN A1 - Becker, Kai-Helge A1 - Hiller, Benjamin T1 - ASTS Orientations on Undirected Graphs: Structural analysis and enumeration N2 - 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. T3 - ZIB-Report - 18-31 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69632 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika A1 - Lindner, Niels T1 - Separation of Cycle Inequalities in Periodic Timetabling N2 - 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. T3 - ZIB-Report - 18-16 KW - Periodic timetabling KW - Cycle inequality KW - Change-cycle inequality Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69746 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Becker, Kai-Helge T1 - Improving relaxations for potential-driven network flow problems via acyclic flow orientations N2 - 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. T3 - ZIB-Report - 18-30 KW - potential-driven network flows KW - acyclic orientations KW - flow orientations KW - MINLPs Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69622 SN - 1438-0064 ER - TY - GEN A1 - Gleixner, Ambros A1 - Bastubbe, Michael A1 - Eifler, Leon A1 - Gally, Tristan A1 - Gamrath, Gerald A1 - Gottwald, Robert Lion A1 - Hendel, Gregor A1 - Hojny, Christopher A1 - Koch, Thorsten A1 - Lübbecke, Marco A1 - Maher, Stephen J. A1 - Miltenberger, Matthias A1 - Müller, Benjamin A1 - Pfetsch, Marc A1 - Puchert, Christian A1 - Rehfeldt, Daniel A1 - Schlösser, Franziska A1 - Schubert, Christoph A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Viernickel, Jan Merlin A1 - Walter, Matthias A1 - Wegscheider, Fabian A1 - Witt, Jonas T. A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 6.0 N2 - 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. T3 - ZIB-Report - 18-26 KW - constraint integer programming KW - linear programming KW - mixed-integer linear programming KW - mixed-integer nonlinear programming KW - optimization solver KW - branch-and-cut KW - branch-and-price KW - column generation framework KW - parallelization KW - mixed-integer semidefinite programming KW - Steiner tree optimization Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69361 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Saitenmacher, René A1 - Walther, Tom T1 - Analysis of operating modes of complex compressor stations N2 - 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. T3 - ZIB-Report - 17-65 KW - bound tightening KW - flow patterns KW - model reformulation KW - multi-way compressor station Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-68179 SN - 1438-0064 ER - TY - GEN A1 - Wolf, Thomas T1 - A Study of Genetic Algorithms solving a combinatorial Puzzle N2 - The suitability of Genetic Algorithms (GAs) to solve a combinatorial problem with only one solution is investigated. The dependence of the performance is studied for GA-hard and GA-soft fitness functions, both with a range of different parameter values and different encodings. T3 - ZIB-Report - SC-98-01 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3445 ER - TY - GEN A1 - Lubkoll, Lars A1 - Schiela, Anton A1 - Weiser, Martin T1 - An affine covariant composite step method for optimization with PDEs as equality constraints N2 - We propose a composite step method, designed for equality constrained optimization with partial differential equations. Focus is laid on the construction of a globalization scheme, which is based on cubic regularization of the objective and an affine covariant damped Newton method for feasibility. We show finite termination of the inner loop and fast local convergence of the algorithm. We discuss preconditioning strategies for the iterative solution of the arising linear systems with projected conjugate gradient. Numerical results are shown for optimal control problems subject to a nonlinear heat equation and subject to nonlinear elastic equations arising from an implant design problem in craniofacial surgery. T3 - ZIB-Report - 15-09 KW - composite step methods KW - cubic regularization KW - affine covariant KW - optimization with PDEs Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53954 SN - 1438-0064 ER - TY - GEN A1 - Harks, Tobias A1 - Heinz, Stefan A1 - Pfetsch, Marc T1 - Competitive Online Multicommodity Routing N2 - We study online multicommodity minimum cost routing problems in networks, where commodities have to be routed sequentially. Arcs are equipped with load dependent price functions defining the routing weights. We discuss an online algorithm that routes each commodity by minimizing a convex cost function that depends on the demands that are previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is $4K/2+K$-competitive, where $K$ is the number of commodities. For the parallel arc case this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. Finally, we investigate a variant in which the demands have to be routed unsplittably. T3 - ZIB-Report - 06-27 KW - Online Optimization KW - Routing KW - Telecommunications Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9212 ER - TY - GEN A1 - Harks, Tobias A1 - Heinz, Stefan A1 - Pfetsch, Marc T1 - Competitive Online Multicommodity Routing N2 - In this paper we study online multicommodity routing problems in networks, in which commodities have to be routed sequentially. The flow of each commodity can be split on several paths. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes each commodity by minimizing a convex cost function that only depends on the demands previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is 4K2 (1+K)2 -competitive, where K is the number of commodities. For the single-source single-destination case, this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. Finally, we investigate a variant in which the demands have to be routed unsplittably. T3 - ZIB-Report - 07-16 KW - Online Optimization KW - Routing KW - Telecommunications Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9599 ER - TY - GEN A1 - Eifler, Leon A1 - Gleixner, Ambros A1 - Pulaj, Jonad T1 - A Safe Computational Framework for Integer Programming applied to Chvátal's Conjecture N2 - We describe a general and safe computational framework that provides integer programming results with the degree of certainty that is required for machine-assisted proofs of mathematical theorems. At its core, the framework relies on a rational branch-and-bound certificate produced by an exact integer programming solver, SCIP, in order to circumvent floating-point roundoff errors present in most state-of-the-art solvers for mixed-integer programs. The resulting certificates are self-contained and checker software exists that can verify their correctness independently of the integer programming solver used to produce the certificate. This acts as a safeguard against programming errors that may be present in complex solver software. The viability of this approach is tested by applying it to finite cases of Chvátal's conjecture, a long-standing open question in extremal combinatorics. We take particular care to verify also the correctness of the input for this specific problem, using the Coq formal proof assistant. As a result we are able to provide a first machine-assisted proof that Chvátal's conjecture holds for all downsets whose union of sets contains seven elements or less. T3 - ZIB-Report - 21-35 KW - exact rational mixed integer programming KW - extremal combinatorics Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-84444 SN - 1438-0064 ER - TY - GEN A1 - Eifler, Leon A1 - Gleixner, Ambros T1 - Safe and Verified Gomory Mixed Integer Cuts in a Rational MIP Framework N2 - This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one computational bottleneck that should be avoided whenever possible is to employ large-scale symbolic computations. Instead it is often possible to use safe directed rounding methods, e.g., to generate provably correct dual bounds. In this work, we continue to leverage this paradigm and extend an exact branch-and-bound framework by separation routines for safe cutting planes, based on the approach first introduced by Cook, Dash, Fukasawa, and Goycoolea in 2009. Constraints are aggregated safely using approximate dual multipliers from an LP solve, followed by mixed-integer rounding to generate provably valid, although slightly weaker inequalities. We generalize this approach to problem data that is not representable in floating-point arithmetic, add routines for controlling the encoding length of the resulting cutting planes, and show how these cutting planes can be verified according to the VIPR certificate standard. Furthermore, we analyze the performance impact of these cutting planes in the context of an exact MIP framework, showing that we can solve 21.5% more instances and reduce solving times by 26.8% on the MIPLIB 2017 benchmark test set. T3 - ZIB-Report - 23-09 KW - Mixed integer programming, Exact computation, Rational arithmetic, Cutting Planes, Symbolic Computations, Certificate of correctness Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-90159 SN - 1438-0064 ER - TY - GEN A1 - Lenz, Ralf A1 - Serrano, Felipe T1 - Tight Convex Relaxations for the Expansion Planning Problem N2 - Secure energy transport is considered as highly relevant for the basic infrastructure of nowadays society and economy. To satisfy increasing demands and to handle more diverse transport situations, operators of energy networks regularly expand the capacity of their network by building new network elements, known as the expansion planning problem. A key constraint function in expansion planning problems is a nonlinear and nonconvex potential loss function. In order to improve the algorithmic performance of state-of-the-art MINLP solvers, this paper presents an algebraic description for the convex envelope of this function. Through a thorough computational study, we show that this tighter relaxation tremendously improve the performance of the MINLP solver SCIP on a large test set of practically relevant instances for the expansion planning problem. In particular, the results show that our achievements lead to an improvement of the solver performance for a development version by up to 58%. T3 - ZIB-Report - 21-05 KW - Convex envelopes KW - Mixed-Integer Nonlinear Programming KW - Expansion planning of energy networks Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81459 SN - 1438-0064 ER - TY - GEN A1 - Ebert, Patricia A1 - Schlechte, Thomas A1 - Schwartz, Stephan T1 - Scheduling for German Road Inspectors N2 - For the yearly over 500,000 vehicle inspections of the German Federal Logistics and Mobility Office (BALM), crew rosters must be scheduled to efficiently achieve Germany's road inspection control targets. For that, we present a model to solve the respective duty scheduling and crew rostering problem in order to obtain duty rosters that comply with numerous legal regulations while maximizing the 'control success' to achieve the control targets. We formulate the Template Assignment Problem, which can be modelled as a large scale mixed-integer linear program. Here, feasible combinations of control topics are assigned to the duties using a hypergraph approach. The model is used in production by BALM, and we prove its effectiveness on a number of real-world instances. T3 - ZIB-Report - 25-13 KW - scheduling KW - rostering KW - mixed-integer linear program KW - crew scheduling KW - hypergraph Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-101999 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schwartz, Stephan A1 - Surau, William T1 - Rooted Maximum Weight Connected Subgraphs with Balancing and Capacity Constraints T3 - ZIB-Report - 21-34 Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-84427 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Danecker, Fabian A1 - Weiser, Martin T1 - Convergence Properties of Newton's Method for Globally Optimal Free Flight Trajectory Optimization N2 - The algorithmic efficiency of Newton-based methods for Free Flight Trajectory Optimization is heavily influenced by the size of the domain of convergence. We provide numerical evidence that the convergence radius is much larger in practice than what the theoretical worst case bounds suggest. The algorithm can be further improved by a convergence-enhancing domain decomposition. T3 - ZIB-Report - 23-19 KW - shortest path KW - flight planning KW - free flight KW - optimal control KW - global optimization KW - Newton's method Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-91309 SN - 1438-0064 ER - TY - GEN A1 - Reuther, Markus A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - Integrated Optimization of Rolling Stock Rotations for Intercity Railways N2 - This paper provides a highly integrated solution approach for rolling stock planning problems in the context of intercity passenger traffic. The main contributions are a generic hypergraph based mixed integer programming model and an integrated algorithm for the considered rolling stock rotation planning problem. The new developed approach is able to handle a very large set of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacity, and regularity aspects. By the integration of this large bundle of technical railway aspects, we show that our approach has the power to produce implementable rolling stock rotations for our industrial cooperation partner DB Fernverkehr. This is the first time that the rolling stock rotations at DB Fernverkehr could be optimized by an automated system utilizing advanced mathematical programming techniques. T3 - ZIB-Report - 12-39 KW - Mixed Integer Programming KW - Railway Optimization KW - Rolling Stock Rostering Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16424 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Fügenschuh, Armin A1 - Klug, Torsten A1 - Schang, Thilo A1 - Schlechte, Thomas A1 - Schülldorf, Hanno T1 - The Freight Train Routing Problem N2 - We consider the following freight train routing problem (FTRP). Given is a transportation network with fixed routes for passenger trains and a set of freight trains (requests), each defined by an origin and destination station pair. The objective is to calculate a feasible route for each freight train such that a sum of all expected delays and all running times is minimal. Previous research concentrated on microscopic train routings for junctions or inside major stations. Only recently approaches were developed to tackle larger corridors or even networks. We investigate the routing problem from a strategic perspective, calculating the routes in a macroscopic transportation network of Deutsche Bahn AG. Here macroscopic refers to an aggregation of complex real-world structures are into fewer network elements. Moreover, the departure and arrival times of freight trains are approximated. The problem has a strategic character since it asks only for a coarse routing through the network without the precise timings. We give a mixed-integer nonlinear programming~(MINLP) formulation for FTRP, which is a multi-commodity flow model on a time-expanded graph with additional routing constraints. The model's nonlinearities are due to an algebraic approximation of the delays of the trains on the arcs of the network by capacity restraint functions. The MINLP is reduced to a mixed-integer linear model~(MILP) by piecewise linear approximation. The latter is solved by a state of the art MILP solver for various real-world test instances. T3 - ZIB-Report - 13-36 KW - Mixed-Integer Nonlinear Programming KW - multi-commodity flows KW - freight train routing Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18991 ER - TY - GEN A1 - Hiller, Benjamin A1 - Vredeveld, Tjark T1 - Probabilistic alternatives for competitive analysis N2 - In the last 20 years competitive analysis has become the main tool for analyzing the quality of online algorithms. Despite of this, competitive analysis has also been criticized: It sometimes cannot discriminate between algorithms that exhibit significantly different empirical behavior, or it even favors an algorithm that is worse from an empirical point of view. Therefore, there have been several approaches to circumvent these drawbacks. In this survey, we discuss probabilistic alternatives for competitive analysis. T3 - ZIB-Report - 11-55 KW - online algorithms KW - probabilistic analysis KW - competitive analysis KW - survey Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15131 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Masing, Berenike T1 - SAT-Generated Initial Solutions for Integrated Line Planning and Turn-Sensitive Periodic Timetabling with Track Choice N2 - Periodic timetabling is a challenging planning task in public transport. As safety requirements are crucial, track allocation is indispensable for validating the practical feasibility of a railway timetable. For busy stations with limited capacities, this requires a detailed planning of turnarounds. It is therefore desirable to integrate timetabling not only with track allocation, but also with vehicle scheduling and line planning. This is captured by the Integrated Line Planning and Turn-Sensitive Periodic Timetabling Problem with Track Choice, whose MIP formulation has been demonstrated to be effective for construction site railway rescheduling, as long as a good quality initial solution is available. In this paper, we discuss how to generate such a solution by extending the SAT formulation of the Periodic Event Scheduling Problem with track choice, track occupation, and minimum service frequency components. The SAT approach is superior to pure MIP on real-world instances of the S-Bahn Berlin network. T3 - ZIB-Report - 24-01 KW - Periodic Timetabling KW - Railway Timetabling KW - Railway Track Allocation KW - Boolean Satisfiability Problem KW - Rescheduling KW - Line Planning Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-94644 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schwartz, Stephan A1 - Surau, William T1 - Vertex Covering with Capacitated Trees N2 - The covering of a graph with (possibly disjoint) connected subgraphs is a fundamental problem in graph theory. In this paper, we study a version to cover a graph's vertices by connected subgraphs subject to lower and upper weight bounds, and propose a column generation approach to dynamically generate feasible and promising subgraphs. Our focus is on the solution of the pricing problem which turns out to be a variant of the NP-hard Maximum Weight Connected Subgraph Problem. We compare different formulations to handle connectivity, and find that a single-commodity flow formulation performs best. This is notable since the respective literature seems to have dismissed this formulation. We improve it to a new coarse-to-fine flow formulation that is theoretically and computationally superior, especially for large instances with many vertices of degree 2 like highway networks, where it provides a speed-up factor of 10 over the non-flow-based formulations. We also propose a preprocessing method that exploits a median property of weight constrained subgraphs, a primal heuristic, and a local search heuristic. In an extensive computational study we evaluate the presented connectivity formulations on different classes of instances, and demonstrate the effectiveness of the proposed enhancements. Their speed-ups essentially multiply to an overall factor of 20. Overall, our approach allows the reliabe solution of instances with several hundreds of nodes in a few minutes. These findings are further corroborated in a comparison to existing districting models on a set of test instances from the literature. T3 - ZIB-Report - 21-14 Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-82616 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Denißen, Jonas A1 - Heller, Simon A1 - Klug, Torsten A1 - Küpper, Michael A1 - Lindner, Niels A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Söhlke, Andreas A1 - Steadman, William T1 - Microscopic Timetable Optimization for a Moving Block System N2 - We present an optimization model which is capable of routing and ordering trains on a microscopic level under a moving block regime. Based on a general timetabling definition (GTTP) that allows the plug in of arbitrarily detailed methods to compute running and headway times, we describe a layered graph approach using velocity expansion, and develop a mixed integer linear programming formulation. Finally, we present promising results for a German corridor scenario with mixed traffic, indicating that applying branch-and-cut to our model is able to solve reasonably sized instances with up to hundred trains to optimality. T3 - ZIB-Report - 21-13 KW - Moving Block KW - Railway Track Allocation KW - Railway Timetabling KW - Train Routing Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-82547 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Liebchen, Christian T1 - Determining all integer vertices of the PESP polytope by flipping arcs N2 - We investigate polyhedral aspects of the Periodic Event Scheduling Problem (PESP), the mathematical basis for periodic timetabling problems in public transport. Flipping the orientation of arcs, we obtain a new class of valid inequalities, the flip inequalities, comprising both the known cycle and change-cycle inequalities. For a point of the LP relaxation, a violated flip inequality can be found in pseudo-polynomial time, and even in linear time for a spanning tree solution. Our main result is that the integer vertices of the polytope described by the flip inequalities are exactly the vertices of the PESP polytope, i.e., the convex hull of all feasible periodic slacks with corresponding modulo parameters. Moreover, we show that this flip polytope equals the PESP polytope in some special cases. On the computational side, we devise several heuristic approaches concerning the separation of cutting planes from flip inequalities. These produce better dual bounds for the smallest and largest instance of the benchmarking library PESPlib. T3 - ZIB-Report - 20-19 KW - Periodic Event Scheduling Problem KW - Periodic Timetabling KW - Mixed Integer Programming Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78793 SN - 1438-0064 ER - TY - GEN A1 - Brose, Achim A1 - Fügenschuh, Armin A1 - Gausemeier, Pia A1 - Vierhaus, Ingmar A1 - Seliger, Günther T1 - A System Dynamic Enhancement for the Scenario Technique N2 - The Scenario Technique is a strategic planning method that aims to describe and analyze potential developments of a considered system in the future. Its application consists of several steps, from an initial problem analysis over an influence analysis to projections of key factors and a definition of the scenarios to a final interpretation of the results. The technique itself combines qualitative and quantitative methods and is an enhancement of the standard Scenario Technique. We use the numerical values gathered during the influence analysis, and embed them in a System Dynamics framework. This yields a mathematically rigorous way to achieve predictions of the system‘s future behavior from an initial impulse and the feedback structure of the factors. The outcome of our new method is a further way of projecting the present into the future, which enables the user of the Scenario Technique to obtain a validation of the results achieved by the standard method. T3 - ZIB-Report - 13-24 KW - Scenario Technique; System Dynamics Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18150 UR - http://opus4.kobv.de/opus4-tuberlin/frontdoor/index/index/docId/4026 SN - 1438-0064 ER - TY - GEN A1 - Euler, Ricardo A1 - Borndörfer, Ralf A1 - Strunk, Timo A1 - Takkula, Tuomo T1 - ULD Build-Up Scheduling with Dynamic Batching in an Air Freight Hub N2 - Air freight is usually shipped in standardized unit load devices (ULDs). The planning process for the consolidation of transit cargo from inbound flights or locally emerging shipments into ULDs for outbound flights is called build-up scheduling. More specifically, outbound ULDs must be assigned a time and a workstation subject to both workstation capacity constraints and the availability of shipments which in turn depends on break-down decisions for incoming ULDs. ULDs scheduled for the same outbound flight should be built up in temporal and spatial proximity. This serves both to minimize overhead in transportation times and to allow workers to move freight between ULDs. We propose to address this requirement by processing ULDs for the same outbound flight in batches. For the above build-up scheduling problem, we introduce a multi-commodity network design model. Outbound flights are modeled as commodities; transit cargo is represented by cargo flow volume and unpack and batch decisions are represented as design variables. The model is solved with standard MIP solvers on a set of benchmark data. For instances with a limited number of resource conflicts, near-optimal solutions are found in under two hours for a whole week of operations. T3 - ZIB-Report - 21-31 KW - Logistics KW - Airline Applications Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-83482 SN - 1438-0064 ER - TY - GEN A1 - Heinz, Stefan A1 - Schlechte, Thomas A1 - Stephan, Rüdiger A1 - Winkler, Michael T1 - Solving steel mill slab design problems N2 - The steel mill slab design problem from the CSPLIB is a combinatorial optimization problem motivated by an application of the steel industry. It has been widely studied in the constraint programming community. Several methods were proposed to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called the multiple knapsack problem with color constraints, originated from the same industrial problem, was discussed in the integer programming community. In particular, a simple integer program for this problem has been given by Forrest et al. The aim of this paper is to bring these different studies together. Moreover, we adapt the model of Forrest et al. for the steel mill slab design problem. Using this model and a state-of-the-art integer program solver all instances of the steel mill slab library can be solved efficiently to optimality. We improved, thereby, the solution values of 76 instances compared to previous results. Finally, we consider a recently introduced variant of the steel mill slab design problem, where within all solutions which minimize the leftover one is interested in a solution which requires a minimum number of slabs. For that variant we introduce two approaches and solve all instances of the steel mill slab library with this slightly changed objective function to optimality. T3 - ZIB-Report - 11-38 KW - steel mill slab design problem KW - multiple knapsack problem with color constraints KW - integer programming KW - set partitioning KW - binpacking with side constraints Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14089 SN - 1438-0064 ER - TY - GEN A1 - Harrod, Steven A1 - Schlechte, Thomas T1 - A Direct Comparison of Physical Block Occupancy Versus Timed Block Occupancy in Train Timetabling Formulations N2 - Two fundamental mathematical formulations for railway timetabling are compared on a common set of sample problems, representing both multiple track high density services in Europe and single track bidirectional operations in North America. One formulation, ACP, enforces against conflicts by constraining time intervals between trains, while the other formulation, HGF, monitors physical occupation of controlled track segments. The results demonstrate that both ACP and HGF return comparable solutions in the aggregate, with some significant differences in select instances, and a pattern of significant differences in performance and constraint enforcement overall. T3 - ZIB-Report - 13-18 KW - Railway Scheduling KW - Train Timetabling KW - Track Allocation Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17946 SN - 1438-0064 ER - TY - GEN A1 - Schlechte, Thomas T1 - Railway Track Allocation - Simulation and Optimization N2 - Today the railway timetabling process and the track allocation is one of the most challenging problems to solve by a railway infrastructure provider. Especially due to the deregulation of the transport market in the recent years several suppliers of railway traffic have entered the market. This leads to an increase of slot requests and then it is natural that conflicts occur among them. Furthermore, railway infrastructure networks consist of very expensive assets, even more they are rigid due to the long-term upgrade process. In order to make best use of these valuable infrastructure and to ensure economic operation, efficient planning of the railway operation is indispensable. Mathematical optimization models and algorithmic methodology can help to automatize and tackle these challenges. Our contribution in this paper is to present a renewed planning process due to the liberalization in Europe and a general framework to support the integration of simulation and optimization for railway capacity allocation. T3 - ZIB-Report - 11-32 KW - railway models KW - railway capacity KW - track allocation framework Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-13632 SN - 1438-0064 ER - TY - GEN A1 - Raack, Christian A1 - Raymond, Annie A1 - Werner, Axel A1 - Schlechte, Thomas T1 - Integer Programming and Sports Rankings N2 - Sports rankings are obtained by applying a system of rules to evaluate the performance of the participants in a competition. We consider rankings that result from assigning an ordinal rank to each competitor according to their performance. We develop an integer programming model for rankings that allows us to calculate the number of points needed to guarantee a team the ith position, as well as the minimum number of points that could yield the ith place. The model is very general and can thus be applied to many types of sports. We discuss examples coming from football (soccer), ice hockey, and Formula~1. We answer various questions and debunk a few myths along the way. Are 40 points enough to avoid relegation in the Bundesliga? Do 95 points guarantee the participation of a team in the NHL playoffs? Moreover, in the season restructuration currently under consideration in the NHL, will it be easier or harder to access the playoffs? Is it possible to win the Formula~1 World Championship without winning at least one race or without even climbing once on the podium? Finally, we observe that the optimal solutions of the aforementioned model are associated to extreme situations which are unlikely to happen. Thus, to get closer to realistic scenarios, we enhance the model by adding some constraints inferred from the results of the previous years. T3 - ZIB-Report - 13-19 KW - sport ranking KW - integer programming Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18068 SN - 1438-0064 ER - TY - GEN A1 - Schlechte, Thomas T1 - Railway Track Allocation N2 - This article gives an overview of the results of the author's PhD thesis. The thesis deals with the mathematical optimization for the efficient use of railway infrastructure. We address the optimal allocation of the available railway track capacity - the track allocation problem. This track allocation problem is a major challenge for a railway company, independent of whether a free market, a private monopoly, or a public monopoly is given. Planning and operating railway transportation systems is extremely hard due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense sizes of the problem instances. Mathematical models and optimization techniques can result in huge gains for both railway customers and operators, e.g., in terms of cost reductions or service quality improvements. We tackle this challenge by developing novel mathematical models and associated innovative algorithmic solution methods for large scale instances. We made considerable progress on solving track allocation problems by two main features - a novel modeling approach for the macroscopic track allocation problem and algorithmic improvements based on the utilization of the bundle method. This allows us to produce for the first time reliable solutions for a real world instance, i.e., the Simplon corridor in Switzerland. T3 - ZIB-Report - 12-38 KW - large-scale integer programming KW - network aggregation KW - configuration models KW - rapid branching Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16402 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Masing, Berenike T1 - On the Split Closure of the Periodic Timetabling Polytope N2 - The Periodic Event Scheduling Problem (PESP) is the central mathematical tool for periodic timetable optimization in public transport. PESP can be formulated in several ways as a mixed-integer linear program with typically general integer variables. We investigate the split closure of these formulations and show that split inequalities are identical with the recently introduced flip inequalities. While split inequalities are a general mixed-integer programming technique, flip inequalities are defined in purely combinatorial terms, namely cycles and arc sets of the digraph underlying the PESP instance. It is known that flip inequalities can be separated in pseudo-polynomial time. We prove that this is best possible unless P $=$ NP, but also observe that the complexity becomes linear-time if the cycle defining the flip inequality is fixed. Moreover, introducing mixed-integer-compatible maps, we compare the split closures of different formulations, and show that reformulation or binarization by subdivision do not lead to stronger split closures. Finally, we estimate computationally how much of the optimality gap of the instances of the benchmark library PESPlib can be closed exclusively by split cuts, and provide better dual bounds for five instances. T3 - ZIB-Report - 23-16 KW - Periodic Event Scheduling Problem KW - Periodic Timetabling KW - Split Closure KW - Mixed-Integer Programming Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-91156 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Liebchen, Christian T1 - Incremental Heuristics for Periodic Timetabling N2 - We present incremental heuristics for the Periodic Event Scheduling Problem (PESP), the standard mathematical tool to optimize periodic timetables in public transport. The core of our method is to solve successively larger subinstances making use of previously found solutions. Introducing the technical notion of free stratifications, we formulate a general scheme for incremental heuristics for PESP. More practically, we use line and station information to create heuristics that add lines or stations one by one, and we evaluate these heuristics on instances of the benchmarking library PESPlib. This approach is indeed viable, and leads to new incumbent solutions for six PESPlib instances. T3 - ZIB-Report - 23-22 KW - Timetabling KW - Mixed-Integer Programming KW - Public Transport Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-92309 SN - 1438-0064 ER - TY - GEN A1 - Bortoletto, Enrico A1 - Lindner, Niels T1 - Scaling and Rounding Periodic Event Scheduling Instances to Different Period Times N2 - The Periodic Event Scheduling Problem (PESP) is a notoriously hard combinatorial optimization problem, essential for the design of periodic timetables in public transportation. The coefficients of the integer variables in the standard mixed integer linear programming formulations of PESP are the period time, e.g., 60 for a horizon of one hour with a resolution of one minute. In many application scenarios, lines with different frequencies have to be scheduled, leading to period times with many divisors. It then seems natural to consider derived instances, where the period time is a divisor of the original one, thereby smaller, and bounds are scaled and rounded accordingly. To this end, we identify two rounding schemes: wide and tight. We then discuss the approximation performance of both strategies, in theory and practice. T3 - ZIB-Report - 23-23 KW - Timetabling KW - Mixed-Integer Programming KW - Public Transport Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-92315 SN - 1438-0064 ER - TY - GEN A1 - D'Andreagiovanni, Fabio A1 - Krolikowski, Jonatan A1 - Pulaj, Jonad T1 - A hybrid primal heuristic for Robust Multiperiod Network Design N2 - We investigate the Robust Multiperiod Network Design Problem, a generalization of the classical Capacitated Network Design Problem that additionally considers multiple design periods and provides solutions protected against traffic uncertainty. Given the intrinsic difficulty of the problem, which proves challenging even for state-of-the art commercial solvers, we propose a hybrid primal heuristic based on the combination of ant colony optimization and an exact large neighborhood search. Computational experiments on a set of realistic instances from the SNDlib show that our heuristic can find solutions of extremely good quality with low optimality gap. T3 - ZIB-Report - 13-78 KW - Multiperiod Network Design, Traffic Uncertainty, Robust Optimization, Multiband Robustness, Hybrid Heuristics Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-44081 SN - 1438-0064 ER - TY - GEN A1 - D'Andreagiovanni, Fabio A1 - Raymond, Annie T1 - Multiband Robust Optimization and its Adoption in Harvest Scheduling N2 - A central assumption in classical optimization is that all the input data of a problem are exact. However, in many real-world problems, the input data are subject to uncertainty. In such situations, neglecting uncertainty may lead to nominally optimal solutions that are actually suboptimal or even infeasible. Robust optimization offers a remedy for optimization under uncertainty by considering only the subset of solutions protected against the data deviations. In this paper, we provide an overview of the main theoretical results of multiband robustness, a new robust optimization model that extends and refines the classical theory introduced by Bertsimas and Sim. After introducing some new results for the special case of pure binary programs, we focus on the harvest scheduling problem and show how multiband robustness can be adopted to tackle the uncertainty affecting the volume of produced timber and grant a reduction in the price of robustness. T3 - ZIB-Report - 13-76 KW - Data Uncertainty KW - Robust Optimization KW - Multiband Robustness KW - Harvest Scheduling Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-43380 SN - 1438-0064 ER - TY - GEN A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio A1 - Raymond, Annie T1 - 0-1 Multiband Robust Optimization N2 - We provide an overview of new theoretical results that we obtained while further investigating multiband robust optimization, a new model for robust optimization that we recently proposed to tackle uncertainty in mixed-integer linear programming. This new model extends and refines the classical Gamma-robustness model of Bertsimas and Sim and is particularly useful in the common case of arbitrary asymmetric distributions of the uncertainty. Here, we focus on uncertain 0-1 programs and we analyze their robust counterparts when the uncertainty is represented through a multiband set. Our investigations were inspired by the needs of our industrial partners in the research project ROBUKOM. T3 - ZIB-Report - 13-77 KW - Combinatorial Optimization, Robust Optimization, Multiband Robustness, Network Design Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-44093 SN - 1438-0064 ER - TY - GEN A1 - Vierhaus, Ingmar A1 - Fügenschuh, Armin A1 - Gottwald, Robert Lion A1 - Grösser, Stefan N. T1 - Modern Nonlinear Optimization Techniques for an Optimal Control of System Dynamics Models N2 - We study System Dynamics models with several free parameters that can be altered by the user. We assume that the user's goal is to achieve a certain dynamic behavior of the model by varying these parameters. In order to the find best possible combination of parameter settings, several automatic parameter tuning methods are described in the literature and readily available within existing System Dynamic software packages. We give a survey on the available techniques in the market and describe their theoretical background. Some of these methods are already six decades old, and meanwhile newer and more powerful optimization methods have emerged in the mathematical literature. One major obstacle for their direct use are tabled data in System Dynamics models, which are usually interpreted as piecewise linear functions. However, modern optimization methods usually require smooth functions which are twice continuously differentiable. We overcome this problem by a smooth spline interpolation of the tabled data. We use a test set of three complex System Dynamic models from the literature, describe their individual transition into optimization problems, and demonstrate the applicability of modern optimization algorithms to these System Dynamics Optimization problems. T3 - ZIB-Report - 14-08 KW - System Dynamics KW - Optimal Control KW - Nonlinear Optimization KW - Spline Interpolation Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-48159 SN - 1438-0064 ER - TY - GEN A1 - Humpola, Jesco A1 - Fügenschuh, Armin A1 - Lehmann, Thomas T1 - A Primal Heuristic for MINLP based on Dual Information N2 - We present a novel heuristic algorithm 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 for a nonlinear relaxation. Based on the information from the KKT point we alter some of the integer variables in a locally promising way. We describe this heuristic for general MINLPs and then show how to tailor the heuristic to exploit 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. T3 - ZIB-Report - 13-49 KW - Mixed-Integer Nonlinear Programming KW - Relaxations KW - Heuristics KW - Duality KW - Nonlinear Network Design Applications Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-43110 SN - 1438-0064 ER - TY - GEN A1 - Fügenschuh, Armin A1 - Grösser, Stefan N. A1 - Vierhaus, Ingmar T1 - A Global Approach to the Control of an Industry Structure System Dynamics Model N2 - We consider a system dynamics model that describes the effect of human activity on natural resources. The central stocks are the accumulated profit, the industry structures, and the water resources. The model can be controlled through two time-dependent parameters. The goal in this paper is to find a parameter setting that leads to a maximization of a performance index, which reflects both environmental and economic aspects. Thus, the goal is to identify the most sustainable stock of industry structures within the model's constraints and assumptions. In order to find a proven global optimal parameter set, we formulate the System Dynamics Optimization model as a mixed-integer nonlinear problem that is accessible for numerical solvers. Due to the dynamic structure of the model, certain steps of the solution process must be handled with greater care, compared to standard non-dynamic problems. We describe our approach of solving the industry structure model and present computational results. In addition, we discuss the limitations of the approach and next steps. T3 - ZIB-Report - 13-67 KW - System Dynamics; Mixed-Integer Nonlinear Optimization Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42932 SN - 1438-0064 ER - TY - GEN A1 - Bley, Andreas A1 - D'Andreagiovanni, Fabio A1 - Karch, Daniel T1 - Scheduling technology migration in WDM Networks N2 - The rapid technological evolution of telecommunication networks demands service providers to regularly update their technology, with the aim of remaining competitive in the marketplace. However, upgrading the technology in a network is not a trivial task. New hardware components need to be installed in the network and during the installation network connectivity may be temporarily compromised. The Wavelength Division Multiplexing (WDM) technology, whose upgrade is considered in here, shares fiber links among several optical connections and tearing down a single link may disrupt several optical connections at once. When the upgrades involve large parts of a network, typically not all links can be upgraded in parallel, which may lead to an unavoidable longer disruption of some connections. A bad scheduling of the overall endeavor, however, can dramatically increase the disconnection time of parts of the networks, causing extended service disruption. In this contribution, we study the problem of finding a schedule of the fiber link upgrades that minimizes the total service disruption time. To the best of our knowledge, this problem has not yet been formalized and investigated. The aim of our work is to close this gap by presenting a mathematical optimization model for the problem and an innovative solution algorithm that tackles the intrinsic difficulties of the problem. Computational experience on realistic instances completes our study. Our original investigations have been driven by real needs of DFN, operator of the German National Research and Education Network and our partner in the BMBF research project ROBUKOM (http://www.robukom.de/). T3 - ZIB-Report - 13-62 KW - Scheduling, Extended Formulations, Network Migration, WDM Networks Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42654 UR - http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6507677&isnumber=6507670 SN - 1438-0064 ER - TY - GEN A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio T1 - A new theoretical framework for Robust Optimization under multi-band uncertainty N2 - We provide an overview of our main results about studying Linear Programming Problems whose coefficient matrix is subject to uncertainty and the uncertainty is modeled through a multi-band set. Such an uncertainty set generalizes the classical one proposed by Bertsimas and Sim and is particularly suitable in the common case of arbitrary non-symmetric distributions of the parameters. Our investigations were inspired by practical needs of our industrial partner in ongoing projects with focus on the design of robust telecommunications networks. T3 - ZIB-Report - 13-61 KW - Robust Optimization, Uncertainty Set, Multiband Robustness, Network Design Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42644 UR - http://www.springer.com/business+%26+management/operations+research/book/978-3-319-00794-6 SN - 1438-0064 ER - TY - GEN A1 - Blanco, Marco A1 - Schlechte, Thomas T1 - Analysis of Micro-Macro Transformations of Railway Networks N2 - A common technique in the solution of large or complex optimization problems is the use of micro-macro transformations. In this paper, we carry out a theoretical analysis of such transformations for the track allocation problem in railway networks. We prove that the cumulative rounding technique of Schlechte et al. satisfies two of three natural optimality criteria and that this performance cannot be improved. We also show that under extreme circumstances, this technique can perform inconvieniently by underestimating the global optimal value. T3 - ZIB-Report - 13-65 Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42710 ER - TY - GEN A1 - Zakrzewska, Anna A1 - D'Andreagiovanni, Fabio A1 - Ruepp, Sarah A1 - Berger, Michael S. T1 - Biobjective Optimization of Radio Access Technology Selection and Resource Allocation in Heterogeneous Wireless Networks N2 - We propose a novel optimization model for resource assignment in heterogeneous wireless network. The model adopts two objective functions maximizing the number of served users and the minimum granted utility at once. A distinctive feature of our new model is to consider two consecutive time slots, in order to include handover as an additional decision dimension. Furthermore, the solution algorithm that we propose refines a heuristic solution approach recently proposed in literature, by considering a real joint optimization of the considered resources. The simulation study shows that the new model leads to a significant reduction in handover frequency, when compared to a traditional scheme based on maximum SNR. T3 - ZIB-Report - 13-63 KW - Heterogeneous Wireless Networks, Biobjective Optimization, Mixed Integer Linear Programming, Simulation Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42675 UR - http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6576416&isnumber=6576384 SN - 1438-0064 ER - TY - GEN A1 - Bauschert, Thomas A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio A1 - Koster, Arie M.C.A. A1 - Kutschka, Manuel A1 - Steglich, Uwe T1 - Network Planning under Demand Uncertainty with Robust Optimization N2 - The planning of a communication network is inevitably depending on the quality of both the planning tool and the demand forecast used. In this article, we show exemplarily how the emerging area of Robust Optimization can advance the network planning by a more accurate mathematical description of the demand uncertainty. After a general introduction of the concept and its application to a basic network design problem, we present two applications: multi-layer and mixed-line-rate network design. We conclude with a discussion of extensions of the robustness concept to increase the accuracy of handling uncertainties. T3 - ZIB-Report - 13-59 KW - Network Design, Demand Uncertainty, Robust Optimization, Telecommunications Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42557 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Mehrgardt, Julika A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Waas, Kerstin T1 - Re-optimization of Rolling Stock Rotations N2 - 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, i.e., vehicle composition, maintenance constraints, and regularity aspects. In industrial applications existing schedules often have to be re-optimized to integrate timetable changes or construction sites. We present an integrated modeling and algorithmic approach for this task as well as computational results for industrial problem instances of DB Fernverkehr AG. T3 - ZIB-Report - 13-60 Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42569 SN - 1438-0064 ER - TY - GEN A1 - Shinano, Yuji A1 - Heinz, Stefan A1 - Vigerske, Stefan A1 - Winkler, Michael T1 - FiberSCIP - A shared memory parallelization of SCIP N2 - Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a MIP solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, the basic concept of having two parallel extensions and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator) is presented, including an implementation of deterministic parallelization. Second, the difficulties to achieve a good performance that utilizes all resources on an actual computing environment and the difficulties of performance evaluation of the parallel solvers are discussed. Third, a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions is presented. Finally, current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer non-linear programs (MINLPs) in parallel is demonstrated. T3 - ZIB-Report - 13-55 KW - parallel KW - branch-and-bound KW - deterministic parallelism KW - constraint integer programming KW - mixed integer programming KW - mixed integer nonlinear programming KW - SCIP KW - MIP KW - MINLP Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42595 SN - 1438-0064 ER - TY - GEN A1 - Masing, Berenike A1 - Lindner, Niels A1 - Ebert, Patricia T1 - Forward and Line-Based Cycle Bases for Periodic Timetabling N2 - The optimization of periodic timetables is an indispensable planning task in public transport. Although the periodic event scheduling problem (PESP) provides an elegant mathematical formulation of the periodic timetabling problem that led to many insights for primal heuristics, it is notoriously hard to solve to optimality. One reason is that for the standard mixed-integer linear programming formulations, linear programming relaxations are weak and the integer variables are of pure technical nature and in general do not correlate with the objective value. While the first problem has been addressed by developing several families of cutting planes, we focus on the second aspect. We discuss integral forward cycle bases as a concept to compute improved dual bounds for PESP instances. To this end, we develop the theory of forward cycle bases on general digraphs. Specifically for the application of timetabling, we devise a generic procedure to construct line-based event-activity networks, and give a simple recipe for an integral forward cycle basis on such networks. Finally, we analyze the 16 railway instances of the benchmark library PESPlib, match them to the line-based structure and use forward cycle bases to compute better dual bounds for 14 out of the 16 instances. T3 - ZIB-Report - 23-05 Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-89731 SN - 1438-0064 ER - TY - GEN A1 - Witzig, Jakob A1 - Gamrath, Gerald A1 - Hiller, Benjamin T1 - Reoptimization Techniques in MIP Solvers N2 - 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. T3 - ZIB-Report - 15-24 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54375 SN - 1438-0064 ER - TY - GEN A1 - Uslu, Svenja A1 - Werner, Axel T1 - A Two-Phase Method for the Biobjective k-Architecture Connected Facility Location Problem and Hypervolume Computation N2 - We apply customized versions of the ε-constraint Method and the Two-Phase Method to a problem originating in access network planning. We introduce various notions of quality measures for approximated/partial sets of nondominated points, utilizing the concept of hypervolume for biobjective problems. We report on computations to assess the performance of the two methods in terms of these measures. T3 - ZIB-Report - 15-08 KW - Biobjective Optimization KW - Connected Facility Location KW - Hypervolume Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53753 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Mehl, Lukas A1 - Bartoszuk, Karolina A1 - Berendes, Sarah A1 - Zittel, Janina T1 - Demand Uncertainty in Energy Systems: Scenario Catalogs vs. Integrated Robust Optimization N2 - Designing efficient energy systems is indispensable for shaping a more sustainable society. This involves making infrastructure investment decisions that must be valid for a long-term time horizon. While energy system optimization models constitute a powerful technique to support planning decisions, they need to cope with inherent uncertainty. For example, predicting future demand on a scale of decades is not only an intricate challenge in itself, but small fluctuations in such a forecast might also largely impact the layout of a complex energy system. In this paper, we compare two methodologies of capturing demand uncertainty for linear-programming based energy system optimization models. On one hand, we generate and analyze catalogs of varying demand scenarios, where each individual scenario is considered independently, so that the optimization produces scenario-specific investment pathways. On the other hand, we make use of robust linear programming to meet the demand of all scenarios at once. Since including a multitude of scenarios increases the size and complexity of the optimization model, we will show how to use warm-starting approaches to accelerate the computation process, by exploiting the similar structure of the linear program across different demand inputs. This allows to integrate a meaningful number of demand scenarios with fully-fledged energy system models. We demonstrate the practical use of our methods in a case study of the Berlin-Brandenburg area in Germany, a region that contains both a metropolitan area and its rural surroundings. As a backbone, we use the open-source framework oemof to create a sector-coupled optimization model for planning an energy system with up to 100% reduction of greenhouse gas emissions. This model features a fine-grained temporal resolution of one hour for the full year 2050. We consider uncertainty in demand for electricity, hydrogen, natural gas, central, and decentral heat. Based on our computations, we analyze the trade-offs in terms of quality and computation time for scenario catalogs and the robust optimization approach. We further demonstrate that our procedure provides a valuable strategy for decision makers to gain insight on the robustness and sensitivity of solutions regarding demand variability. T3 - ZIB-Report - 25-19 Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-102404 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels T1 - A Multi-Commodity Flow Heuristic for Integrated Periodic Timetabling for Railway Construction Sites N2 - Rescheduling a railway system comprises many aspects, such as line planning, timetabling, track allocation, and vehicle scheduling. For periodic timetables, these features can be integrated into a single mixed-integer program extending the Periodic Event Scheduling Problem (PESP) with a routing component. We develop a multi-commodity-flow-based heuristic that allows to compute better solutions faster than a black-box MIP approach on real construction site scenarios on the S-Bahn Berlin network. T3 - ZIB-Report - 25-02 KW - Railway Timetabling KW - Periodic Timetabling KW - Rescheduling KW - Railway Track Allocation Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-99449 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Liebchen, Christian T1 - A two-stage model for periodic timetabling with fixed line activities N2 - The timetable is a central pillar of any public transportation system. Constructing and optimizing periodic timetables in terms of passenger comfort and operational efficiency leads to NP-hard optimization problems that are also computationally challenging in applications. The Periodic Event Scheduling Problem (PESP) as standard mathematical tool benefits from its succinct formulation and rich combinatorial structure, but suffers from poor linear programming relaxations and weak dual bounds. These difficulties persist in a reduced version, where driving and dwelling activities of the lines are assumed to be fixed. In this case, fixing the initial departure time of each line fully determines the timetable, and for each pair of lines, the resulting (weighted) transfer durations can be expressed in terms of a piecewise linear non-convex function in terms of the difference of the initial times. When the number of activities between two lines is bounded, this function can be computed in polynomial time. By inserting precomputed piecewise linear functions into a mixed-integer program with the initial departure times as variables, we introduce an equivalent formulation for reduced PESP instances. The model bears analogies with quadratic semi-assignment approaches and offers alternative ways to compute primal and dual bounds. We evaluate the computational behavior of our approach on realistic benchmarking instances. T3 - ZIB-Report - 25-14 Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-101234 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume T1 - Picos Documentation. Release 0.1.1. N2 - PICOS is a user friendly interface to several conic and integer programming solvers, very much like YALMIP under MATLAB. The main motivation for PICOS is to have the possibility to enter an optimization problem as a high level model, and to be able to solve it with several different solvers. Multidimensional and matrix variables are handled in a natural fashion, which makes it painless to formulate a SDP or a SOCP. This is very useful for educational purposes, and to quickly implement some models and test their validity on simple examples. Furthermore, with PICOS you can take advantage of the python programming language to read and write data, construct a list of constraints by using python list comprehensions, take slices of multidimensional variables, etc. T3 - ZIB-Report - 12-48 KW - mathematical programming KW - SDP KW - SOCP KW - python Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17396 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume T1 - On the semidefinite representations of real functions applied to symmetric matrices N2 - We present a new semidefinite representation for the trace of a real function f applied to symmetric matrices, when a semidefinite representation of the convex function f is known. Our construction is intuitive, and yields a representation that is more compact than the previously known one. We also show with the help of matrix geometric means and the Riemannian metric of the set of positive definite matrices that for a rational number p in the interval (0,1], the matrix X raised to the exponent p is the largest element of a set represented by linear matrix inequalities. We give numerical results for a problem inspired from the theory of experimental designs, which show that the new semidefinite programming formulation yields a speed-up factor in the order of 10. T3 - ZIB-Report - 12-50 KW - semidefinite representability KW - optimal experimental designs KW - SDP KW - matrix geometric mean Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17511 SN - 1438-0064 VL - 439 SP - 2829 EP - 2843 ER - TY - GEN A1 - Gamrath, Gerald T1 - Improving strong branching by propagation N2 - Strong branching is an important component of most variable selection rules in branch-and-bound based mixed-integer linear programming solvers. It predicts the dual bounds of potential child nodes by solving auxiliary LPs and thereby helps to keep the branch-and-bound tree small. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Computational experiments on standard MIP instances indicate that this is beneficial in three aspects: It helps to reduce the average number of LP iterations per strong branching call, the number of branch-and-bound nodes, and the overall solving time. T3 - ZIB-Report - 12-46 KW - mixed-integer programming KW - branch-and-bound KW - branching rule KW - strong branching KW - domain propagation Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17701 SN - 1438-0064 ER - TY - GEN A1 - Schwartz, Stephan A1 - Borndörfer, Ralf A1 - Bartz, Gerald T1 - The Graph Segmentation Problem N2 - We investigate a graph theoretical problem arising in the automatic billing of a network toll. Given a network and a family of user paths, we study the graph segmentation problem (GSP) to cover parts of the user paths by a set of disjoint segments. The GSP is shown to be NP-hard but for special cases it can be solved in polynomial time. We also show that the marginal utility of a segment is bounded. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest. T3 - ZIB-Report - 16-53 KW - toll billing KW - graph segmentation KW - combinatorial optimization Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60750 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Walther, Tom T1 - Improving branching for disjunctive polyhedral models using approximate convex decompositions N2 - 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. T3 - ZIB-Report - 17-68 KW - approximate convex decomposition KW - branch-and-bound KW - convex hull reformulation KW - disjunctive set Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-67462 SN - 1438-0064 ER - TY - GEN A1 - Shinano, Yuji T1 - The Ubiquity Generator Framework: 7 Years of Progress in Parallelizing Branch-and-Bound N2 - Mixed integer linear programming (MIP) is a general form to model combinatorial optimization problems and has many industrial applications. The performance of MIP solvers has improved tremendously in the last two decades and these solvers have been used to solve many real-word problems. However, against the backdrop of modern computer technology, parallelization is of pivotal importance. In this way, ParaSCIP is the most successful parallel MIP solver in terms of solving previously unsolvable instances from the well-known benchmark instance set MIPLIB by using supercomputers. It solved two instances from MIPLIB2003 and 12 from MIPLIB2010 for the first time to optimality by using up to 80,000 cores on supercomputers. ParaSCIP has been developed by using the Ubiquity Generator (UG) framework, which is a general software package to parallelize any state-of-the-art branch-and-bound based solver. This paper discusses 7 years of progress in parallelizing branch-and-bound solvers with UG. T3 - ZIB-Report - 17-60 KW - Parallelization, Branch-and-bound, Mixed Integer Programming, UG, ParaSCIP, FiberSCIP, ParaXpress, FiberXpress, SCIP-Jack Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65545 SN - 1438-0064 ER - TY - GEN A1 - Lenz, Ralf A1 - Schwarz, Robert T1 - Optimal Looping of Pipelines in Gas Networks N2 - In this paper, we compare several approaches for the problem of gas network expansions using loops, that is, to build new pipelines in parallel to existing ones. We present different model formulations for the problem of continuous loop expansions as well as discrete loop expansions. We then analyze problem properties, such as the structure and convexity of the underlying feasible regions. The paper concludes with a computational study comparing the continuous and the discrete formulations. T3 - ZIB-Report - 16-67 KW - Mixed Integer Nonlinear Programming KW - Gas Network Applications KW - Expansion Planning Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61564 SN - 1438-0064 ER - TY - GEN A1 - Blanco, Marco A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung A1 - Kaier, Anton A1 - Schlechte, Thomas A1 - Schlobach, Swen T1 - The Shortest Path Problem with Crossing Costs N2 - We introduce the shortest path problem with crossing costs (SPPCC), a shortest path problem in a directed graph, in which the objective function is the sum of arc weights and crossing costs. The former are independently paid for each arc used by the path, the latter need to be paid every time the path intersects certain sets of arcs, which we call regions. The SPPCC generalizes not only the classical shortest path problem but also variants such as the resource constrained shortest path problem and the minimum label path problem. We use the SPPCC to model the flight trajectory optimization problem with overflight costs. In this paper, we provide a comprehensive analysis of the problem. In particular, we identify efficient exact and approximation algorithms for the cases that are most relevant in practice. T3 - ZIB-Report - 16-70 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61240 SN - 1438-0064 ER - TY - GEN A1 - Hennig, Kai A1 - Schwarz, Robert T1 - Using Bilevel Optimization to find Severe Transport Situations in Gas Transmission Networks N2 - In the context of gas transmission in decoupled entry-exit systems, many approaches to determine the network capacity are based on the evaluation of realistic and severe transport situations. In this paper, we review the Reference Point Method, which is an algorithm used in practice to generate a set of scenarios using the so-called transport moment as a measure for severity. We introduce a new algorithm for finding severe transport situations that considers an actual routing of the flow through the network and is designed to handle issues arising from cyclic structures in a more dynamical manner. Further, in order to better approximate the physics of gas, an alternative, potential based flow formulation is proposed. The report concludes with a case study based on data from the benchmark library GasLib. T3 - ZIB-Report - 16-68 KW - bilevel optimization KW - gas networks KW - network flow Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61519 SN - 1438-0064 ER - TY - GEN A1 - Gottwald, Robert Lion A1 - Maher, Stephen J. A1 - Shinano, Yuji T1 - Distributed domain propagation N2 - Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite it's simplicity portfolio parallelization has been shown to perform well for modern mixed-integer programming (MIP) and boolean satisfiability problem (SAT) solvers. Domain propagation has also been shown to be a simple technique in modern MIP and SAT solvers that effectively finds additional domain reductions after a variables domain has been reduced. This paper investigates the impact of distributed domain propagation in modern MIP solvers that employ portfolio parallelization. Computational experiments were conducted for two implementations of this parallelization approach. While both share global variable bounds and solutions they communicate differently. In one implementation the communication is performed only at designated points in the solving process and in the other it is performed completely asynchronously. Computational experiments show a positive performance impact of communicating global variable bounds and provide valuable insights in communication strategies for parallel solvers. T3 - ZIB-Report - 16-71 KW - mixed integer programming KW - parallelization KW - domain propagation KW - portfolio solvers Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61380 SN - 1438-0064 ER - TY - GEN A1 - Hendel, Gregor T1 - Enhancing MIP branching decisions by using the sample variance of pseudo-costs N2 - The selection of a good branching variable is crucial for small search trees in Mixed Integer Programming. Most modern solvers employ a strategy guided by history information, mainly the variable pseudo-costs, which are used to estimate the objective gain. At the beginning of the search, such information is usually collected via an expensive look-ahead strategy called strong-branching until variables are considered reliable. The reliability notion is thereby mostly based on fixed-number thresholds, which may lead to ineffective branching decisions on problems with highly varying objective gains. We suggest two new notions of reliability motivated by mathematical statistics that take into account the sample variance of the past observations on each variable individually. The first method prioritizes additional strong-branching look-aheads on variables whose pseudo-costs show a large variance by measuring the relative error of a pseudo-cost confidence interval. The second method performs a two-sample Student-t test for filtering branching candidates with a high probability to be better than the best history candidate. Both methods were implemented in the MIP-solver SCIP and computational results on standard MIP test sets are presented. T3 - ZIB-Report - 15-28 KW - mixed-integer programming KW - reliability branching Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54591 SN - 1438-0064 ER - TY - GEN A1 - Grötschel, Martin A1 - Stephan, Rüdiger T1 - Characterization of Facets of the Hop Constrained Chain Polytope via Dynamic Programming N2 - In this paper, we study the hop constrained chain polytope, that is, the convex hull of the incidence vectors of (s,t)-chains using at most k arcs of a given digraph, and its dominant. We use extended formulations (implied by the inherent structure of the Moore-Bellman-Ford algorithm) to derive facet defining inequalities for these polyhedra via projection. Our findings result into characterizations of all facet defining {0,+1,-1}-inequalities for the hop constrained chain polytope and all facet defining {0,1}-inequalities for its dominant. Although the derived inequalities are already known, such classifications were not previously given to the best of our knowledge. Moreover, we use this approach to generalize so called jump inequalities, which have been introduced in a paper of Dahl and Gouveia in 2004. T3 - ZIB-Report - 11-54 KW - hop constraints KW - chains KW - dynamic programming KW - facets Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14914 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume T1 - Approximation of a Maximum-Submodular-Coverage problem involving spectral functions, with application to Experimental Design N2 - We study a family of combinatorial optimization problems defined by a parameter $p\in[0,1]$, which involves spectral functions applied to positive semidefinite matrices, and has some application in the theory of optimal experimental design. This family of problems tends to a generalization of the classical maximum coverage problem as $p$ goes to $0$, and to a trivial instance of the knapsack problem as $p$ goes to $1$. In this article, we establish a matrix inequality which shows that the objective function is submodular for all $p\in[0,1]$, from which it follows that the greedy approach, which has often been used for this problem, always gives a design within $1-1/e$ of the optimum. We next study the design found by rounding the solution of the continuous relaxed problem, an approach which has been applied by several authors. We prove an inequality which generalizes a classical result from the theory of optimal designs, and allows us to give a rounding procedure with an approximation factor which tends to $1$ as $p$ goes to $1$. T3 - ZIB-Report - 11-53 KW - Maximum Coverage KW - Optimal Experimental Design KW - Polynomial Time Approximability KW - Kiefer's p-criterion Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14956 SN - 1438-0064 VL - 151 IS - 1--2 SP - 258 EP - 276 ER - TY - GEN A1 - Sagnol, Guillaume T1 - A Class of Semidefinite Programs with rank-one solutions N2 - We show that a class of semidefinite programs (SDP) admits a solution that is a positive semidefinite matrix of rank at most $r$, where $r$ is the rank of the matrix involved in the objective function of the SDP. The optimization problems of this class are semidefinite packing problems, which are the SDP analogs to vector packing problems. Of particular interest is the case in which our result guarantees the existence of a solution of rank one: we show that the computation of this solution actually reduces to a Second Order Cone Program (SOCP). We point out an application in statistics, in the optimal design of experiments. T3 - ZIB-Report - 11-51 KW - SDP KW - Semidefinite Packing Problem KW - rank 1-solution KW - Low-rank solutions KW - SOCP KW - Optimal Experimental Design KW - Multiresponse experiments Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14933 SN - 1438-0064 ER - TY - GEN A1 - Szabó, Jácint T1 - The set of solutions to nomination validation in passive gas transportation networks with a generalized flow formula N2 - In this paper we give an analytical description on the structure of solutions to the gas nomination validation problem in gas transportation networks. These networks are assumed to contain no active devices, only certain hypothetical pipelines, where the flow of gas is modeled by a generalized version of the quadratic Weymouth's equation. The purpose of considering generalized flow formulas is to be able to adapt our results to various gas network optimization problems involving gas flow formulas beyond Weymouth's equation. Such formulas can appear in leaves of branch and bound trees, or they can stem from discretization and linearization carried out at active devices. We call a balanced supply-demand vector a nomination, and the passive nomination validation problem is to decide whether there exist pressures at the nodes generating a given nomination. We prove that in our setup the pressure square vectors generating a given nomination form a one-dimensional connected and continuous curve in the pressure square space, and this curve is a line for the classical Weymouth's equation. We also present a visual approach for the easy comprehension of how this solution curve arises; we give a short investigation of the set of feasible nominations; and finally we give a proof that the nomination validation problem in gas networks with active devices is NP-complete. T3 - ZIB-Report - 11-44 KW - pressure drop equation KW - gas networks KW - generalized flow formula Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15151 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume T1 - Network-related problems in Optimal Experimental Design and Second Order Cone Programming N2 - In the past few years several applications of optimal experimental designs have emerged to optimize the measurements in communication networks. The optimal design problems arising from this kind of applications share three interesting properties: (i) measurements are only available at a small number of locations of the network; (ii) each monitor can simultaneously measure several quantities, which can be modeled by ``multiresponse experiments"; (iii) the observation matrices depend on the topology of the network. In this paper, we give an overview of these experimental design problems and recall recent results for the computation of optimal designs by Second Order Cone Programming (SOCP). New results for the network-monitoring of a discrete time process are presented. In particular, we show that the optimal design problem for the monitoring of an AR1 process can be reduced to the standard form and we give experimental results. T3 - ZIB-Report - 11-52 KW - Optimal Experimental Design KW - Second Order Cone Programming KW - Network measurements Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14942 SN - 1438-0064 VL - 51 IS - 51 SP - 161 EP - 171 ER - TY - GEN A1 - Martin, Alexander A1 - Geißler, Björn A1 - Hayn, Christine A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Morsi, Antonio A1 - Pfetsch, Marc A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schultz, Rüdiger A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Steinbach, Marc A1 - Willert, Bernhard T1 - Optimierung Technischer Kapazitäten in Gasnetzen N2 - Die mittel- und längerfristige Planung für den Gastransport hat sich durch Änderungen in den regulatorischen Rahmenbedingungen stark verkompliziert. Kernpunkt ist die Trennung von Gashandel und -transport. Dieser Artikel diskutiert die hieraus resultierenden mathematischen Planungsprobleme, welche als Validierung von Nominierungen und Buchungen, Bestimmung der technischen Kapazität und Topologieplanung bezeichnet werden. Diese mathematischen Optimierungsprobleme werden vorgestellt und Lösungsansätze skizziert. T3 - ZIB-Report - 11-56 KW - Gasnetzplanung KW - Technische Kapazitäten KW - Nominierungsvalidierung KW - Buchungsvalidierung KW - Topologieplanung Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15121 SN - 1438-0064 ER - TY - GEN A1 - Grimm, Boris A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schade, Stanley A1 - Schlechte, Thomas T1 - A Propagation Approach to Acyclic Rolling Stock Rotation Optimization N2 - The rolling stock, i.e., railway vehicles, are one of the key ingredients of a running railway system. As it is well known, the offer of a railway company to their customers, i.e., the railway timetable, changes from time to time. Typical reasons for that are different timetables associated with different seasons, maintenance periods or holidays. Therefore, the regular lifetime of a timetable is split into (more or less) irregular periods where parts of the timetable are changed. In order to operate a railway timetable most railway companies set up sequences that define the operation of timetabled trips by a single physical railway vehicle called (rolling stock) rotations. Not surprisingly, the individual parts of a timetable also affect the rotations. More precisely, each of the parts brings up an acyclic rolling stock rotation problem with start and end conditions associated with the beginning and ending of the corresponding period. In this paper, we propose a propagation approach to deal with large planning horizons that are composed of many timetables with shorter individual lifetimes. The approach is based on an integer linear programming formulation that propagates rolling stock rotations through the irregular parts of the timetable while taking a large variety of operational requirements into account. This approach is implemented within the rolling stock rotation optimization framework ROTOR used by DB Fernverkehr AG, one of the leading railway operators in Europe. Computational results for real world scenarios are presented to evaluate the approach. T3 - ZIB-Report - 17-24 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-63930 SN - 1438-0064 ER - TY - GEN A1 - Fischer, Frank A1 - Schlechte, Thomas T1 - Strong Relaxations for the Train Timetabling Problem using Connected Configurations N2 - The task of the train timetabling problem or track allocation problem is to find conflict free schedules for a set of trains with predefined routes in a railway network. Especially for non-periodic instances models based on time expanded networks are often used. Unfortunately, the linear programming relaxation of these models is often extremely weak because these models do not describe combinatorial relations like overtaking possibilities very well. In this paper we extend the model by so called connected configuration subproblems. These subproblems perfectly describe feasible schedules of a small subset of trains (2-3) on consecutive track segments. In a Lagrangian relaxation approach we solve several of these subproblems together in order to produce solutions which consist of combinatorially compatible schedules along the track segments. The computational results on a mostly single track corridor taken from the INFORMS RAS Problem Solving Competition 2012 data indicate that our new solution approach is rather strong. Indeed, for this instance the solution of the Lagrangian relaxation is already integral. T3 - ZIB-Report - 17-46 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64743 SN - 1438-0064 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Generalized preprocessing techniques for Steiner tree and maximum-weight connected subgraph problems N2 - This article introduces new preprocessing techniques for the Steiner tree problem in graphs and one of its most popular relatives, the maximum-weight connected subgraph problem. Several of the techniques generalize previous results from the literature. The correctness of the new methods is shown, but also their NP-hardness is demonstrated. Despite this pessimistic worst-case complexity, several relaxations are discussed that are expected to allow for a strong practical efficiency of these techniques in strengthening both exact and heuristic solving approaches. T3 - ZIB-Report - 17-57 KW - Steiner tree KW - maximum-weight connected subgraph Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65439 SN - 1438-0064 ER - TY - GEN A1 - Miltenberger, Matthias A1 - Ralphs, Ted A1 - Steffy, Daniel T1 - Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization T2 - Operations Research Proceedings 2017 N2 - We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether such predictions can be used to make better algorithmic choices. In a first step towards this goal, we discuss here the numerical behavior of an existing solver in order to determine whether our intuitive understanding of this behavior is correct. T3 - ZIB-Report - 17-43 KW - Mixed Integer Programming KW - Linear Programming KW - Algorithm Analysis Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64645 SN - 1438-0064 ER - TY - GEN A1 - Renken, Malte A1 - Ahmadi, Amin A1 - Borndörfer, Ralf A1 - Sahin, Guvenc A1 - Schlechte, Thomas T1 - Demand-Driven Line Planning with Selfish Routing N2 - Bus rapid transit systems in developing and newly industrialized countries are often operated at the limits of passenger capacity. In particular, demand during morning and afternoon peaks is hardly or even not covered with available line plans. In order to develop demand-driven line plans, we use two mathematical models in the form of integer programming problem formulations. While the actual demand data is specified with origin-destination pairs, the arc-based model considers the demand over the arcs derived from the origin-destination demand. In order to test the accuracy of the models in terms of demand satisfaction, we simulate the optimal solutions and compare number of transfers and travel times. We also question the effect of a selfish route choice behavior which in theory results in a Braess-like paradox by increasing the number of transfers when system capacity is increased with additional lines. T3 - ZIB-Report - 17-38 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64547 SN - 1438-0064 ER - TY - GEN A1 - Humpola, Jesco T1 - Sufficient Pruning Conditions for MINLP in Gas Network Design N2 - One quarter of Europe’s energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euros per kilometer the extension of the European pipeline network is already a multi billion Euro business. Therefore, automatic planning tools that support the decision process are desired. We model the topology extension problem in gas networks by a mixed-integer nonlinear program (MINLP). This gives rise to a so-called active transmission problem, a continuous nonlinear non-convex feasibility problem which emerges from the MINLP model by fixing all integral variables. In this article we offer novel sufficient conditions for proving the infeasibility of this active transmission problem. These conditions can be expressed in the form of a mixed-integer program (MILP), i.e., the infeasibility of a non-convex NLP can be certified by solving an MILP. These results provide an efficient bounding procedure in a branch-and-bound algorithm. Our computational results demonstrate a substantial speed-up for the necessary computations. T3 - ZIB-Report - 15-04 KW - Network Design KW - Mixed-Integer Nonlinear Programming KW - Infeasibility Detection Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53489 ER - TY - GEN A1 - Brett, Charles A1 - Hoberg, Rebecca A1 - Pacheco, Meritxell A1 - Smith, Kyle A1 - Borndörfer, Ralf A1 - Euler, Ricardo A1 - Gamrath, Gerwin A1 - Grimm, Boris A1 - Heismann, Olga A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Tesch, Alexander T1 - G-RIPS 2014 RailLab - Towards robust rolling stock rotations N2 - The Graduate-Level Research in Industrial Projects (G-RIPS) Program provides an opportunity for high-achieving graduate-level students to work in teams on a real-world research project proposed by a sponsor from industry or the public sector. Each G-RIPS team consists of four international students (two from the US and two from European universities), an academic mentor, and an industrial sponsor. This is the report of the Rail-Lab project on the definition and integration of robustness aspects into optimizing rolling stock schedules. In general, there is a trade-off for complex systems between robustness and efficiency. The ambitious goal was to explore this trade-off by implementing numerical simulations and developing analytic models. In rolling stock planning a very large set of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacity, and regularity aspects, have to be considered in an integrated model. General hypergraphs provide the modeling power to tackle those requirements. Furthermore, integer programming approaches are able to produce high quality solutions for the deterministic problem. When stochastic time delays are considered, the mathematical programming problem is much more complex and presents additional challenges. Thus, we started with a basic variant of the deterministic case, i.e., we are only considering hypergraphs representing vehicle composition and regularity. We transfered solution approaches for robust optimization from the airline industry to the setting of railways and attained a reasonable measure of robustness. Finally, we present and discuss different methods to optimize this robustness measure. T3 - ZIB-Report - 14-34 KW - robust optimization, rolling stock planning Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53475 SN - 1438-0064 N1 - ZIB-Report 14-34 ER - TY - GEN A1 - Witzig, Jakob T1 - Conflict Driven Diving for Mixed Integer Programming N2 - The analysis of infeasibility plays an important role in solving satisfiability problems (SAT) and mixed integer programs (MIPs). In mixed integer programming, this procedure is called conflict analysis. So far, modern MIP solvers use conflict analysis only for propagation and improving the dual bound, i.e., fathoming nodes that cannot contain feasible solutions. In this short paper, we present a new approach which uses conflict information to improve the primal bound during a MIP solve. To derive new improving primal solutions we use a conflict driven diving heuristic called conflict diving that uses the information obtained by conflict analysis. Conflict diving pursues a twofold strategy. By using conflict information the new diving approach is guided into parts of the search space that are usually not explored by other diving heuristics. At the same time, conflict diving has a fail-fast-strategy to reduce the time spent if it cannot find a new primal solution. As a byproduct, additional valid conflict constraints can be derived, from which a MIP solver can gain benefit to improve the dual bound as well. To show the added-value of conflict diving within a MIP solver, conflict diving has been implemented within the non-commercial MIP solver SCIP. Experiments are carried out on general MIP instances from standard public test sets, like MIPLIB2010 or Cor@l. T3 - ZIB-Report - 17-69 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66116 SN - 1438-0064 ER - TY - GEN 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 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. T3 - ZIB-Report - 16-47 KW - Steiner tree problems KW - reduction techniques KW - prize-collecting Steiner tree problem KW - maximum-weight connected subgraph problem Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60420 SN - 1438-0064 ER - TY - GEN A1 - Witzig, Jakob A1 - Beckenbach, Isabel A1 - Eifler, Leon A1 - Fackeldey, Konstantin A1 - Gleixner, Ambros A1 - Grever, Andreas A1 - Weber, Marcus T1 - Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes N2 - In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst. T3 - ZIB-Report - 16-39 KW - Non-reversible Markov Processes KW - NESS KW - Mixed-Integer Programming KW - Markov State Models Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60353 SN - 1438-0064 ER - TY - GEN A1 - Fischer, Frank A1 - Grimm, Boris A1 - Klug, Torsten A1 - Schlechte, Thomas T1 - A Re-optimization Approach for Train Dispatching N2 - The Train Dispatching Problem (TDP) is to schedule trains through a network in a cost optimal way. Due to disturbances during operation existing track allocations often have to be re-scheduled and integrated into the timetable. This has to be done in seconds and with minimal timetable changes to guarantee smooth and conflict free operation. We present an integrated modeling approach for the re-optimization task using Mixed Integer Programming. Finally, we provide computational results for scenarios provided by the INFORMS RAS Problem Soling Competition 2012. T3 - ZIB-Report - 16-49 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60493 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Klug, Torsten A1 - Lamorgese, Leonardo A1 - Mannino, Carlo A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Recent Success Stories on Optimization of Railway Systems N2 - 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. T3 - ZIB-Report - 14-47 KW - railway planning KW - railway operations KW - capacity optimization Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53726 SN - 1438-0064 ER - TY - GEN A1 - Draegert, Andreas A1 - Eisenblätter, Andreas A1 - Gamrath, Inken A1 - Werner, Axel T1 - Optimal Battery Controlling for Smart Grid Nodes N2 - Energy storages can be of great value when added to power grids. They introduce the possibility to store and release energy whenever this is favorable. This is particularly relevant, for example, if power supply is volatile (as is the case with renewable energy) and the network is small (so that there are few other nodes that might balance fluctuations in consumption or production). We present models and methods from mathematical optimization for computing an optimized storage schedule for this purpose. We look at alternative optimization objectives, such as smallest possible peak load, low energy costs, or the close approximation of a prescribed load curve. The optimization needs to respect general operational and economic constraints as well as limitations in the use of storage, which are imposed by the chosen storage technology. We therefore introduce alternative approaches for modeling the non-linear properties of energy storages and study their impact on the efficiency of the optimization process. Finally, we present a computational study with batteries as storage devices. We use this to highlight the trade-off between solution quality and computational tractability. A version of the model for the purpose of leveling peaks and instabilities has been implemented into a control system for an office-building smart grid scenario. T3 - ZIB-Report - 15-06 KW - energy optimization, non-linear optimization, smart grid Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53550 SN - 1438-0064 ER - TY - GEN A1 - Harman, Radoslav A1 - Sagnol, Guillaume T1 - Computing D-optimal experimental designs for estimating treatment contrasts under the presence of a nuisance time trend N2 - We prove a mathematical programming characterisation of approximate partial D-optimality under general linear constraints. We use this characterisation with a branch-and-bound method to compute a list of all exact D-optimal designs for estimating a pair of treatment contrasts in the presence of a nuisance time trend up to the size of 24 consecutive trials. T3 - ZIB-Report - 15-02 KW - optimal design of experiments KW - nuisance trend KW - branch and bound Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53640 SN - 1438-0064 ER - TY - GEN A1 - Orlowski, Sebastian A1 - Werner, Axel A1 - Wessäly, Roland T1 - Estimating trenching costs in FTTx network planning N2 - In this paper we assess to which extent trenching costs of an FTTx network are unavoidable, even if technical side constraints are neglected. For that purpose we present an extended Steiner tree model. Using a variety of realistic problem instances we demonstrate that the total trenching cost can only be reduced by about 5 percent in realistic scenarios. This work has been funded by BMBF (German Federal Ministry of Education and Research) within the program "KMU-innovativ". T3 - ZIB-Report - 11-49 KW - Optical access networks KW - Optimization KW - Steiner trees Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14884 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Pfetsch, Marc A1 - Vigerske, Stefan T1 - Large Neighborhood Search beyond MIP N2 - Large neighborhood search (LNS) heuristics are an important component of modern branch-and-cut algorithms for solving mixed-integer linear programs (MIPs). Most of these LNS heuristics use the LP relaxation as the basis for their search, which is a reasonable choice in case of MIPs. However, for more general problem classes, the LP relaxation alone may not contain enough information about the original problem to find feasible solutions with these heuristics, e.g., if the problem is nonlinear or not all constraints are present in the current relaxation. In this paper, we discuss a generic way to extend LNS heuristics that have been developed for MIP to constraint integer programming (CIP), which is a generalization of MIP in the direction of constraint programming (CP). We present computational results of LNS heuristics for three problem classes: mixed-integer quadratically constrained programs, nonlinear pseudo-Boolean optimization instances, and resource-constrained project scheduling problems. Therefore, we have implemented extended versions of the following LNS heuristics in the constraint integer programming framework SCIP: Local Branching, RINS, RENS, Crossover, and DINS. Our results indicate that a generic generalization of LNS heuristics to CIP considerably improves the success rate of these heuristics. T3 - ZIB-Report - 11-21 KW - Large Neighborhood Search KW - Primal Heuristic KW - MIP KW - MIQCP KW - Pseudo-Boolean Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12989 ER - TY - GEN A1 - Fügenschuh, Armin A1 - Humpola, Jesco T1 - A Unified View on Relaxations for a Nonlinear Network Flow Problem N2 - We consider a nonlinear nonconvex network flow problem that arises, for example, in natural gas or water transmission networks. Given is such network with active and passive components, that is, valves, compressors, pressure regulators (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes of the network. Besides flow conservation constraints in the nodes the flow must fulfill nonlinear nonconvex pressure loss constraints on the arcs subject to potential values (i.e., pressure levels) in both end nodes of each arc. The problem is how to numerically compute this flow and pressures. We review an existing approach of Maugis (1977) and extend it to the case of networks with active elements (for example, compressors). We further examine different ways of relaxations for the nonlinear network flow model. We compare different approaches based on nonlinear optimization numerically on a set of test instances. T3 - ZIB-Report - 13-31 KW - Nonlinear Network Flow KW - Mixed-Integer Nonlinear Programming KW - Relaxations Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18857 ER - TY - GEN A1 - Fügenschuh, Armin A1 - Vierhaus, Ingmar T1 - A Global Approach to the Optimal Control of System Dynamics Models N2 - The System Dynamics (SD) methodology is a framework for modeling and simulating the dynamic behavior of socioeconomic systems. Characteristic for the description of such systems is the occurrence of feedback loops together with stocks and flows. The mathematical equations that describe the system are usually ordinary differential equations and nonlinear algebraic constraints. Therefore seemingly simple systems can show a nonintuitive, unpredictable behavior over time. Controlling a dynamical system means to specify potential interventions from outside that should keep the system on the desired track, and to define an evaluation schema to compare different controls among each other, so that a "best" control can be defined in a meaningful way. The central question is how to compute such globally optimal control for a given SD model, that allows the transition of the system into a desired state with minimum effort. We propose a mixed-integer nonlinear programming (MINLP) reformulation of the System Dynamics Optimization (SDO) problem. MINLP problems can be solved by linear programming based branch-and-bound approach. We demonstrate that standard MINLP solvers are not able to solve SDO problem. To overcome this obstacle, we introduce a special-tailored bound propagation method. We apply our new method to a predator-prey model with additional hunting activity as control, and to a mini-world model with the consumption level as control. Numerical results for these test cases are presented. T3 - ZIB-Report - 13-28 KW - System Dynamics KW - Global Optimal Control KW - Mixed-Integer Nonlinear Optimization KW - Bounds Strengthening Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18600 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Liebchen, Christian T1 - Timetable Merging for the Periodic Event Scheduling Problem N2 - We propose a new mixed integer programming based heuristic for computing new benchmark primal solutions for instances of the PESPlib. The PESPlib is a collection of instances for the Periodic Event Scheduling Problem (PESP), comprising periodic timetabling problems inspired by real-world railway timetabling settings, and attracting several international research teams during the last years. We describe two strategies to merge a set of good periodic timetables. These make use of the instance structure and minimum weight cycle bases, finally leading to restricted mixed integer programming formulations with tighter variable bounds. Implementing this timetable merging approach in a concurrent solver, we improve the objective values of the best known solutions for the smallest and largest PESPlib instances by 1.7 and 4.3 percent, respectively. T3 - ZIB-Report - 21-06 KW - Periodic Event Scheduling Problem KW - Periodic Timetabling KW - Railway Timetabling KW - PESPlib KW - Benchmark Solutions KW - Mixed Integer Programming Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81587 SN - 1438-0064 ER - TY - GEN A1 - Leitner, Markus A1 - Ljubic, Ivana A1 - Sinnl, Markus A1 - Werner, Axel T1 - On the Two-Architecture Connected Facility Location Problem N2 - We introduce a new variant of the connected facility location problem that allows for modeling mixed deployment strategies (FTTC/FTTB/FTTH) in the design of local access telecommunication networks. Several mixed integer programming models and valid inequalities are presented. Computational studies on realistic instances from three towns in Germany are provided. T3 - ZIB-Report - 13-29 KW - Connected Facility Location, Branch-and-Cut, FTTx Deployment Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18610 SN - 1438-0064 ER - TY - GEN A1 - Humpola, Jesco A1 - Fügenschuh, Armin T1 - A New Class of Valid Inequalities for Nonlinear Network Design Problems N2 - We consider a nonlinear nonconvex network design problem that arises in the extension of natural gas transmission networks. Given is such network with active and passive components, that is, valves, compressors, pressure regulators (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes of the network. Besides flow conservation constraints in the nodes the flow must fulfill nonlinear nonconvex pressure loss constraints on the arcs subject to potential values (i.e., pressure levels) in both end nodes of each arc. Assume that there does not exist a feasible flow that fulfills all physical constraints and meets the desired entry and exit amounts. Then a natural question is where to extend the network by adding pipes in the most economic way such that this flow becomes feasible. Answering this question is computationally demanding because of the difficult problem structure. We use mixed-integer nonlinear programming techniques that rely on an outer approximation of the overall problem, and a branching on decision variables. We formulate a new class of valid inequalities (or cutting planes) which reduce the overall solution time when added to the formulation. We demonstrate the computational merits of our approach on test instances. T3 - ZIB-Report - 13-06 KW - Network Design KW - Mixed-Integer Nonlinear Programming KW - Cutting Planes Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17771 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Liebchen, Christian A1 - Masing, Berenike T1 - Forward Cycle Bases and Periodic Timetabling N2 - Periodic timetable optimization problems in public transport can be modeled as mixed-integer linear programs by means of the Periodic Event Scheduling Problem (PESP). In order to keep the branch-and-bound tree small, minimum integral cycle bases have been proven successful. We examine forward cycle bases, where no cycle is allowed to contain a backward arc. After reviewing the theory of these bases, we describe the construction of an integral forward cycle basis on a line-based event-activity network. Adding turnarounds to the instance \texttt{R1L1} of the benchmark library PESPlib, we computationally evaluate three types of forward cycle bases in the Pareto sense, and come up with significant improvements concerning dual bounds. T3 - ZIB-Report - 21-18 KW - Periodic Timetabling KW - Cycle Bases KW - Mixed Integer Programming Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-82756 SN - 1438-0064 ER -