90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Refine
Year of publication
Document Type
- ZIB-Report (175)
- Master's Thesis (5)
- Bachelor's Thesis (3)
- Doctoral Thesis (2)
- In Proceedings (1)
Has Fulltext
- yes (186) (remove)
Keywords
Institute
- Mathematical Optimization (143)
- Mathematical Optimization Methods (32)
- Network Optimization (20)
- Applied Algorithmic Intelligence Methods (13)
- AI in Society, Science, and Technology (8)
- Mathematics of Telecommunication (7)
- Mathematics of Transportation and Logistics (6)
- ZIB Allgemein (4)
- Mathematical Algorithmic Intelligence (3)
- Numerical Mathematics (3)
The operation of a railway network as large as Deutsche Bahn's Intercity Express (ICE) hinges on a number of factors, such as the availability of personnel and the assignment of physical vehicles to a timetable schedule, a problem known as the rolling stock rotation problem (RSRP). In this paper, we consider the problem of creating an alternative timetable in the case that there is a long-term disruption, such as a strike, and the effects that this alternative timetable has on the resulting vehicle rotation plan. We define a priority measure via the Analytic Hierarchy Process (AHP) to determine the importance of each trip in the timetable and therefore which trips to cancel or retain. We then compare our results with those of a limited timetable manually designed by Deutsche Bahn (DB). We find that while our timetable results in a more expensive rotation plan, its flexibility lends itself to a number of simple improvements. Furthermore, our priority measure has the potential to be integrated into the rolling stock rotation optimization process, in particular, the Rotation Optimizer for Railways (ROTOR) software, via the cost function. Ultimately, our method provides the foundation for an automated way of creating a new timetable quickly, and potentially in conjunction with a new rotation plan, in the case of a limited scenario.
Mit dem Voranschreiten der Technologie erhalten die öffentlichen Verkehrsmittel eine größere Bedeutung. Die Beförderung mehrerer Personen eröffnet der Gesellschaft viele Möglichkeiten, unter Anderem den Vorteil der Zeitersparnis. Die Dauer des Verkehrswegs mit öffentlichen Verkehrsmitteln ist häufig geringer, als die mit individuellen Verkehrsmitteln. Jedes öffentliche Transportmittel ist mit einem Fahrplan versehen. Dieser bietet Passagieren, die öffentliche Verkehrsmittel öfter nutzen, eine Strukturierung und Planung ihrer Zeit. Dabei lassen sich Taktfahrpläne aufgrund ihres periodischen Verhaltens leicht einprägen. Dieses periodische Verhalten ist durch mathematische Modellierungen darstellbar. Das persönliche Nutzverhalten vieler Bürger im Personenverkehr ist auf die öffentlichen Verkehrsmittel beschränkt. Diese beinhalten im Gegensatz zum individuellen Verkehrsmittel eine Wartezeit. Dabei stellt sich die Frage, ob man anhand mathematischer Modelle diese Wartezeit minimieren kann. Eine bekannte mathematische Modellierung dieses Problems ist das Periodic Event Scheduling Problem (PESP). Die optimale Planung eines periodischen Taktfahrplanes steht im Vordergrund.
Während ich dieses Problem betrachtet habe, wurde ich auf das Rechnen mit linearen Gleichungssystemen modulo T aufmerksam. Bei periodischen Taktfahrplänen wird ein einheitliches zeitliches Muster, welches sich nach T Minuten wiederholt, betrachtet. Das dabei zu betrachtende Lösungsproblem eröffnet ein Teilgebiet der Mathematik, welches bislang nicht im Vordergrund stand: Das Lösen linearer Gleichungen modulo T, wobei T für die Zeit in Minuten steht und somit 60 ist. Da 60 keine Primzahl ist, kann – wie im Laufe der Arbeit präsentiert – das lineare Gleichungssystem nicht mehr über einen Körper gelöst werden. Lineare Gleichungssysteme werden nun über Nicht-Körpern betrachtet. Die Literatur weist sowohl im deutschsprachigem als auch im englischsprachigen Raum wenig Umfang bezüglich linearer Gleichungssysteme über Nicht-Körper auf. Der Bestand an Fachliteratur bezüglich den Themen lineare diophantische Gleichungssysteme, Hermite-
Normalform und Smith-Normalform ist zurzeit gering, dennoch erreichbar, beispielsweise in [1], welches in dieser Bachelorarbeit genutzt wurde. Insbesondere wurde ich bei der Suche nach geeigneter Literatur zu linearen Gleichungssystemen über Restklassenringe, die keinen Körper bilden, nicht fündig. Dabei recherchierte ich sowohl in den Universitätsbibliotheken als auch in webbasierenden Suchmaschinen.
Aufgrund dem geringen Bestand an Fachliteratur in diesem Kontext, war ich gezwungen, an vielen Stellen eigene logische Verknüpfungen zu konzipieren und zu beweisen. Dies brachte viele Schwierigkeiten mit sich, die mit bestmöglichem Verständnis bearbeitet wurden.
Abseits der Zugänglichkeit der Literatur, finde ich es sehr überraschend, dass sich viele Professoren der Mathematik mit diesem Themenbereich nicht beschäftigten. Insbesondere gingen von den Dozenten, die ich um Literaturempfehlung bat, kein Werk aus. Damit
wurde das Thema "Lineare Gleichungssysteme Modulo T" einerseits eine große Herausforderung, andererseits eine große Motivation, da ich mit dieser Bachelorarbeit vielen Interessenten der Mathematik als Sekundärliteratur dienen kann.
We propose a simple and general online method to measure the search progress within the Branch-and-Bound algorithm, from which we estimate the size of the remaining search tree. We then show how this information can help solvers algorithmically at runtime by designing a restart strategy for Mixed-Integer Programming (MIP) solvers that decides whether to restart the search based on the current estimate of the number of remaining nodes in the tree. We refer to this type of algorithm as clairvoyant.
Our clairvoyant restart strategy outperforms a state-of-the-art solver on a large set of publicly available MIP benchmark instances.
It is implemented in the MIP solver SCIP and will be available in future releases.
A decision support system relies on frequent re-solving of similar problem instances. While the general structure remains the same in corresponding applications, the input parameters are updated on a regular basis. We propose a generative neural network design for learning integer decision variables of mixed-integer linear programming (MILP) formulations of these problems. We utilise a deep neural network discriminator and a MILP solver as our oracle to train our generative neural network. In this article, we present the results of our design applied to the transient gas optimisation problem. With the trained network we produce a feasible solution in 2.5s, use it as a warm-start solution, and thereby decrease global optimal solution solve time by 60.5%.
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.
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.
In a recent paper, Conte et al. [CGMR2017] presented an algorithm for enumerating all acyclic orientations of a graph G=(V,E) with a single source (and related orientations) with delay O(|V||E|). In this paper we revisit the problem by going back to an early paper by de Fraysseix et al. [FMR1995], who proposed an algorithm for enumerating all bipolar orientations of a graph based on a recursion formula. We first formalize de Fraysseix et al.'s algorithm for bipolar orientations and determine that its delay is also O(|V||E|). We then apply their recursion formula to the case of Conte et al.'s enumeration problem and show that this yields a more efficient enumeration algorithm with delay O(\sqrt(|V|)|E|). Finally, a way to further streamline the algorithm that leads to a particularly simple implementation is suggested.
Improved optimization models for potential-driven network flow problems via ASTS orientations
(2019)
The class of potential-driven network flow problems provides important models for a range of infrastructure networks that lead to hard-to-solve MINLPs in real-world applications. On large-scale meshed networks the relaxations usually employed are rather weak due to cycles in the network. To address this situation, we introduce the concept of ASTS orientations, a generalization of bipolar orientations, as a combinatorial relaxation of feasible solutions of potential-driven flow problems, study their structure, and show how they can be used to strengthen existing relaxations and thus provide improved optimization models. Our computational results indicate that ASTS orientations can be used to derive much stronger bounds on the flow variables than existing bound tightening methods and to yield significant performance improvements for an existing state-of-the-art MILP model for large-scale gas networks.
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.
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.
Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that approximates crossing costs by shadow costs on individual arcs, thus reducing the SPPCC to a standard shortest path problem. We evaluate all algorithms’ performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds.
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.
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.
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/).
Bus rapid transit systems in developing and newly
industrialized countries often consist of a trunk with a path
topology. On this trunk, several overlapping lines are operated
which provide direct connections. The demand varies heavily over the
day, with morning and afternoon peaks typically in reverse
directions. We propose an integer programming
model for this problem, derive a structural property of line plans
in the static (or single period) ``unimodal demand'' case, and
consider approaches to the solution of the multi-period version that
rely on clustering the demand into peak and off-peak service
periods. An application to the Metrobüs system of Istanbul is
discussed.
Convergence Properties of Newton's Method for Globally Optimal Free Flight Trajectory Optimization
(2023)
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.
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.
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.
A railway operator creates (rolling stock) rotations in order to have a precise master plan for the
operation of a timetable by railway vehicles. A rotation is considered as a cycle that multiply
traverses a set of operational days while covering trips of the timetable. As it is well known,
the proper creation of rolling stock rotations by, e.g., optimization algorithms is challenging
and still a topical research subject. Nevertheless, we study a completely different but strongly
related question in this paper, i.e.: How to visualize a rotation? For this purpose, we introduce
a basic handout concept, which directly leads to the visualization, i.e., handout of a rotation. In
our industrial application at DB Fernverkehr AG, the handout is exactly as important as the
rotation itself. Moreover, it turns out that also other European railway operators use exactly the
same methodology (but not terminology). Since a rotation can have many handouts of different
quality, we show how to compute optimal ones through an integer program (IP) by standard
software. In addition, a construction as well as an improvement heuristic are presented. Our
computational results show that the heuristics are a very reliable standalone approach to quickly
find near-optimal and even optimal handouts. The efficiency of the heuristics is shown via a
computational comparison to the IP approach.