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 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Winkler, Michael T1 - Solving hard MIPLIB2003 problems with ParaSCIP on Supercomputers: An update N2 - Contemporary supercomputers can easily provide years of CPU time per wall-clock hour. One challenge of today's software development is how to harness this wast computing power in order to solve really hard mixed integer programming instances. In 2010, two out of six open MIPLIB2003 instances could be solved by ParaSCIP in more than ten consecutive runs, restarting from checkpointing files. The contribution of this paper is threefold: For the first time, we present computational results of single runs for those two instances. Secondly, we provide new improved upper and lower bounds for all of the remaining four open MIPLIB2003 instances. Finally, we explain which new developments led to these results and discuss the current progress of ParaSCIP. Experiments were conducted on HLRNII, on HLRN III, and on the Titan supercomputer, using up to 35,200 cores. T3 - ZIB-Report - 13-66 KW - Mixed Integer Programming KW - MIPLIB2003 KW - ParaSCIP KW - Ubiquity Generator Framework KW - Supercomputer Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42888 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 - THES A1 - Buwaya, Julia T1 - Optimizing control in a transportation network when users may choose their OD-path N2 - This thesis represents a game-theoretic investigation of the allocation of inspectors in a transportation network, comparing Nash and Stackelberg equilibrium strategies to a strategy in which inspections are conducted proportionally to the traffic volume. It contains specifications for the integration of space and time dependencies and extensive experimental tests for the application on the transportation network of German motorways using real data. Main results are that - although the formulated spot-checking game is not zero-sum - we are able to compute a Nash equilibrium using linear programming and secondly, that experimental results yield that a Nash equilibrium strategy represents a good trade-off for the Stackelberg equilibrium strategy between efficiency of controls and computation time. KW - Optimization KW - Transportation Network KW - Game Theory KW - Stackelberg Equilibrium KW - Mixed Integer Programming KW - Security Game KW - Linear Programming KW - Nash Equilibrium Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42330 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 - 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 - 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 - 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 - 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 - 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 - TY - GEN A1 - Lindner, Niels A1 - Maristany de las Casas, Pedro A1 - Schiewe, Philine T1 - Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data N2 - We investigate preprocessing for single-source shortest path queries in digraphs, where arc costs are only known to lie in an interval. More precisely, we want to decide for each arc whether it is part of some shortest path tree for some realization of costs. We show that this problem is solvable in polynomial time by giving a combinatorial algorithm, using optimal structures that we call forks. Our algorithm turns out to be very efficient in practice, and is sometimes even superior in quality to a heuristic developed for the one-to-one shortest path problem in the context of passenger routing in public transport. T3 - ZIB-Report - 21-17 KW - Preprocessing Shortest Path Problems KW - Interval Data KW - Graph Algorithms Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-82716 SN - 1438-0064 ER - TY - GEN A1 - Scheumann, Rene A1 - Fügenschuh, Armin A1 - Schenker, Sebastian A1 - Vierhaus, Ingmar A1 - Borndörfer, Ralf A1 - Finkbeiner, Matthias T1 - Global Manufacturing: How to Use Mathematical Optimisation Methods to Transform to Sustainable Value Creation N2 - It is clear that a transformation to sustainable value creation is needed, because business as usual is not an option for preserving competitive advantages of leading industries. What does that mean? This contribution proposes possible approaches for a shift in existing manufacturing paradigms. In a first step, sustainability aspects from the German Sustainability Strategy and from the tools of life cycle sustainability assessment are chosen to match areas of a value creation process. Within these aspects are indicators, which can be measured within a manufacturing process. Once these data are obtained they can be used to set up a mathematical linear pulse model of manufacturing in order to analyse the evolution of the system over time, that is the transition process, by using a system dynamics approach. An increase of technology development by a factor of 2 leads to an increase of manufacturing but also to an increase of climate change. Compensation measures need to be taken. This can be done by e.g. taking money from the GDP (as an indicator of the aspect ``macroeconomic performance''). The value of the arc from that building block towards climate change must then be increased by a factor of 10. The choice of independent and representative indicators or aspects shall be validated and double-checked for their significance with the help of multi-criteria mixed-integer programming optimisation methods. T3 - ZIB-Report - 12-28 KW - Multi-Criteria Optimisation KW - Sustainability Indicator KW - System Dynamics KW - Value Creation Process Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15703 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem N2 - We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems. T3 - ZIB-Report - 14-26 KW - column generation KW - coarse-to-fine approach KW - multi-layer approach KW - rolling stock rotation problem Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-51009 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Hendel, Gregor A1 - Koch, Thorsten T1 - The Three Phases of MIP Solving N2 - Modern MIP solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound. Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three different phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behavior of the MIP solver SCIP at the predicted phase transition points. T3 - ZIB-Report - 16-78 KW - optimization software KW - mixed-integer programming KW - branch-and-bound KW - adaptive search behavior KW - optimality prediction Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61607 SN - 1438-0064 ER - TY - GEN A1 - Griewank, Andreas A1 - Streubel, Tom A1 - Lehmann, Lutz A1 - Hasenfelder, Richard A1 - Radons, Manuel T1 - Piecewise linear secant approximation via Algorithmic Piecewise Differentiation N2 - It is shown how piecewise differentiable functions \(F: R^n → R^m\) that are defined by evaluation programs can be approximated locally by a piecewise linear model based on a pair of sample points x̌ and x̂. We show that the discrepancy between function and model at any point x is of the bilinear order O(||x − x̌|| ||x − x̂||). This is a little surprising since x ∈ R^n may vary over the whole Euclidean space, and we utilize only two function samples F̌ = F(x̌) and F̂ = F(x̂), as well as the intermediates computed during their evaluation. As an application of the piecewise linearization procedure we devise a generalized Newton’s method based on successive piecewise linearization and prove for it sufficient conditions for convergence and convergence rates equaling those of semismooth Newton. We conclude with the derivation of formulas for the numerically stable implementation of the aforedeveloped piecewise linearization methods. T3 - ZIB-Report - 16-54 KW - Automatic differentiation KW - Computational graph KW - Lipschitz continuity KW - Generalized Hermite interpolation KW - ADOL-C Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61642 SN - 1438-0064 ER - TY - CHAP A1 - Kunt, Tim T1 - Solving the n-Queens Problem in Higher Dimensions T2 - Operations Research Proceedings 2024. OR 2024 N2 - How many mutually non-attacking queens can be placed on a d-dimensional chessboard of size n? The n-queens problem in higher dimensions is a generalization of the well-known n-queens problem. We present an integer programming formulation of the n-queens problem in higher dimensions and several strengthenings through additional valid inequalities. Compared to recent benchmarks, we achieve a speedup in computational time between 15–70x over all instances of the integer programs. Our computational results prove optimality of certificates for several large instances. Breaking additional, previously unsolved instances with the proposed methods is likely possible. On the primal side, we further discuss heuristic approaches to constructing solutions that turn out to be optimal when compared to the IP. KW - Integer Programming KW - Maximum Independent Set KW - n-Queens Y1 - 2025 U6 - https://doi.org/10.1007/978-3-031-92575-7_29 SP - 205 EP - 211 ER -