90C27 Combinatorial optimization
Refine
Year of publication
Document Type
- ZIB-Report (89)
- Doctoral Thesis (5)
- Habilitation (3)
- Article (1)
- Master's Thesis (1)
Is part of the Bibliography
- no (99)
Keywords
- integer programming (8)
- line planning (8)
- polyhedral combinatorics (8)
- combinatorial optimization (7)
- Competitive Analysis (5)
- computational complexity (5)
- online optimization (5)
- column generation (4)
- competitive analysis (4)
- Ganzzahlige Programmierung (3)
- Heuristics (3)
- Online-Optimierung (3)
- Optimierung (3)
- Shortest Path Routing (3)
- branch-and-cut (3)
- elevator (3)
- kombinatorische Optimierung (3)
- mixed integer programming (3)
- polyhedra and polytopes (3)
- polynomial inequalities (3)
- shortest path (3)
- shortest path routing (3)
- Approximationsalgorithmen (2)
- Branch-And-Cut (2)
- Column Generation (2)
- Combinatorial Optimization (2)
- Constraint Programming (2)
- Echtzeit-Optimierung (2)
- Integer Programming (2)
- Linienplanung (2)
- Online Optimization (2)
- Optimierungssoftware (2)
- Optimization (2)
- Passenger routing (2)
- Periodic timetabling (2)
- Public transport (2)
- Railway Slot Allocation (2)
- Routing and Wavelength Allocation (2)
- Simulation (2)
- Train Timetabling Problem (2)
- approximation (2)
- approximation algorithm (2)
- approximation algorithms (2)
- constraint integer programming (2)
- cutting planes (2)
- direct connection (2)
- discrete optimization (2)
- discrete-continuous algorithm (2)
- flight planning (2)
- free flight (2)
- gemischt-ganzzahlige Programmierung (2)
- graph theory (2)
- hypergraph (2)
- kompetitive Analyse (2)
- kürzeste-Wege Routing (2)
- max-cut (2)
- metric inequalities (2)
- mixed-integer programming (2)
- network design (2)
- optimal control (2)
- optimization software (2)
- public transport (2)
- railway track allocation (2)
- semi-algebraic sets (2)
- set partitioning (2)
- stability index (2)
- stable multi-sets (2)
- unsplittable flow (2)
- (IIS) maximum feasible subsystem problem (1)
- Algorithmen (1)
- Approximation (1)
- Asymmetric Travelling Salesman Problem (1)
- Aufzugssteuerung (1)
- Aufzugsteuerung (1)
- Aufzüge (1)
- Bicriteria Optimization (1)
- Blocking Probability (1)
- Branch and Cut (1)
- Branch&Cut-Algorithm (1)
- Branch-and-Cut (1)
- Bundle Method (1)
- Call Admission (1)
- Cardinality Constraints (1)
- Cardinality Forcing Inequalities (1)
- Cardinality constraints (1)
- Chipverifikation (1)
- Colorability (1)
- Combinatorial Auctions (1)
- Comparative Analysis (1)
- Computational Complexity (1)
- Connectivity (1)
- Constraint Shortest Paths Problem (1)
- Control of Stacker Cranes (1)
- Cycles in Matroids (1)
- DIMACS Challenge (1)
- Data Library (1)
- Degree Property (1)
- Dial-a-Ride-Problem (1)
- Dienstplanung (1)
- Dispatching von Fahrzeugen (1)
- Duty Scheduling (1)
- Dynamic Network Configuration (1)
- Fahrplanung (1)
- Fallstudie (1)
- Gemischt-Ganzzahlige Programmierung (1)
- General Public (1)
- Generalization (1)
- Graphen (1)
- Hochregallagerbediengeräte (1)
- Hypergraph (1)
- IP Routing (1)
- Integer Programs (1)
- Integration (1)
- Internet routing (1)
- Inverse Shortest Paths (1)
- Kardinalitätsbeschränkung (1)
- Kommissioniermobile (1)
- Kompetitive Analyse (1)
- Komplexit{ä}t (1)
- Lagrangian relaxation (1)
- Latency (1)
- Line Planning, Extended Formulation, Public Transport (1)
- Linear and Integer Programming (1)
- Location Planning in Telecommunications (1)
- Logistik (1)
- Mathematical Programming Testdata Library (1)
- Matroid Polytope (1)
- Matroid-Polytop (1)
- Matroids (1)
- Mixed Integer Programming (1)
- Mixed-Integer Programming (1)
- Mixed-integer programming (1)
- Modelling Languages (1)
- Morse matching (1)
- Network Capacity Planning (1)
- Network Planning (1)
- Network design (1)
- Netzwerkaggregation (1)
- OSPF Routing (1)
- Online Algorithmen (1)
- Online Algorithms (1)
- Online Optimierung (1)
- Online-Algorithms (1)
- Optical Networks (1)
- Packing problems (1)
- Partition Inequalities (1)
- Paths (1)
- Preisplanung (1)
- Primal-Dual Approximation (1)
- Primalheuristiken (1)
- Problembibliothek (1)
- Proximale Bündelmethode (1)
- Pseudo-Boolean (1)
- Public Transport (1)
- Railway Track Allocation (1)
- Rapid Branching (1)
- Rapid-Branching-Heuristik (1)
- Realtime Optimization (1)
- Routing (1)
- Rundreisen (1)
- SCIP (1)
- Separation algorithm (1)
- Separationsalgorithmus (1)
- Shortest path routing (1)
- Simplon Korridor (1)
- Simplon corridor (1)
- Steiner Connectivity Problem (1)
- Steiner Tree (1)
- Steiner Tree Generalization (1)
- Steiner Tree Packing in Graphs (1)
- Steiner Tree Problem (1)
- Steiner Trees (1)
- Steiner tree packing (1)
- Sudoku (1)
- Survey (1)
- Survivable Networks (1)
- TSP (1)
- Telecommunication Network Design (1)
- Time Windows (1)
- Traffic enineering (1)
- Train Dispatching (1)
- Train Timetabling (1)
- Transparent Optical Networks (1)
- Trassenallokation (1)
- Trassenallokationsproblem (1)
- Traveling Repairman (1)
- Travelling-Salesman-Problem (1)
- UMTS (1)
- Umlaufplanung (1)
- Vehicle Routing (1)
- affine adjustable robust counterparts (1)
- affine routing (1)
- assignment (1)
- basis pursuit (1)
- bipartite (1)
- bisection (1)
- bisubmodular function (1)
- bisubmodular polyhedron (1)
- block structure (1)
- branch and cut (1)
- budgeted maximum coverage (1)
- cardinality homogeneous set systems (1)
- case study (1)
- chip verification (1)
- combinatorial packing (1)
- competitiveness (1)
- completeness (1)
- constraint programming (1)
- convex relaxation (1)
- cycles (1)
- discrete Morse function (1)
- discrete convex function (1)
- disjoint paths (1)
- duty scheduling (1)
- dynamic programming (1)
- elevator control (1)
- equicut (1)
- facet (1)
- facet classification (1)
- facets (1)
- greedy algorithm (1)
- hyperassignment (1)
- inequality (1)
- infeasible linear inequality system (1)
- integer characterizations (1)
- integration (1)
- irreducible infeasible subsystem (1)
- jump system (1)
- knapsack with integer capacity (1)
- length bounded paths (1)
- line planning, transfers,Steiner connectivity problem (1)
- linear Optimization (1)
- linear time algorithm (1)
- lineare Optimierung (1)
- matching (1)
- maximum feasible subsystem problem (1)
- minimum IIS-cover (1)
- mixed integer quadratically constrained programming (1)
- multi-commodity flow problem (1)
- multicast network design (1)
- network aggregation (1)
- nonconvex (1)
- online algorithm (1)
- optical networks (1)
- optimale Tour (1)
- orthogonal matching pursuit (1)
- passenger routing (1)
- path (1)
- perfect graphs (1)
- periodic event scheduling (1)
- polyhedral structure (1)
- polynomial-time algorithm (1)
- polytopes (1)
- positive semidefinite matrices (1)
- primal heuristics (1)
- public transport optimization (1)
- quadrati (1)
- quadratic 0-1 programming (1)
- real-world problems (1)
- recourse (1)
- reducibility (1)
- robust optimization (1)
- semialgebraic sets (1)
- semidefinite Programming (1)
- semidefinite cone (1)
- semidefinite duality (1)
- semidefinite programming (1)
- set packing (1)
- simulation studies (1)
- sparse representations (1)
- spectral bundle method (1)
- subgradient method (1)
- symmetry (1)
- timetabling (1)
- transfers (1)
- tropical geometry (1)
- vehicle dispatching (1)
- vehicle positioning (1)
- vehicle scheduling (1)
- wavelength assignment (1)
- zonotopal tilings (1)
- Öffentlicher Personennahverkehr (1)
Institute
- ZIB Allgemein (50)
- Mathematical Optimization (49)
- Mathematics of Transportation and Logistics (19)
- Network Optimization (3)
- Mathematical Algorithmic Intelligence (2)
- Mathematics for Life and Materials Science (2)
- Modeling and Simulation of Complex Processes (2)
- Computational Medicine (1)
- Mathematical Optimization Methods (1)
- Numerical Mathematics (1)
The Periodic Event Scheduling Problem (PESP) is the standard mathematical tool for optimizing periodic timetabling problems in public transport. A solution to PESP consists of three parts: a periodic timetable, a periodic tension, and integer periodic offset values. While the space of periodic tension has received much attention in the past, we explore geometric properties of the other two components, establishing novel connections between periodic timetabling and discrete geometry. Firstly, we study the space of feasible periodic timetables, and decompose it into polytropes, i.e., polytopes that are convex both classically and in the sense of tropical geometry. We then study this decomposition and use it to outline a new heuristic for PESP, based on the tropical neighbourhood of the polytropes. Secondly, we recognize that the space of fractional cycle offsets is in fact a zonotope. We relate its zonotopal tilings back to the hyperrectangle of fractional periodic tensions and to the tropical neighbourhood of the periodic timetable space. To conclude we also use this new understanding to give tight lower bounds on the minimum width of an integral cycle basis.
We propose a hybrid discrete-continuous algorithm for flight planning in free flight airspaces. In a first step, our DisCOptER method discrete-continuous optimization for enhanced resolution) computes a globally optimal approximate flight path on a discretization of the problem using the A* method. This route initializes a Newton method that converges rapidly to the smooth optimum in a second step. The correctness, accuracy, and complexity of the method are goverened by the choice of the crossover point that determines the coarseness of the discretization. We analyze the optimal choice of the crossover point and demonstrate the asymtotic superority of DisCOptER over a purely discrete approach.
We propose a hybrid discrete-continuous algorithm for flight planning in free flight airspaces. In a first step, our DisCOptER method discrete-continuous optimization for enhanced resolution) computes a globally optimal approximate flight path on a discretization of the problem using the A* method. This route initializes a Newton method that converges rapidly to the smooth optimum in a second step. The correctness, accuracy, and complexity of the method are goverened by the choice of the crossover point that determines the coarseness of the discretization. We analyze the optimal choice of the crossover point and demonstrate the asymtotic superority of DisCOptER over a purely discrete approach.
Umsteigen ohne Warten
(2017)
Wir stellen einen mathematischen Optimierungsansatz zur Berechnung von periodischen Taktfahrplänen vor, bei dem die Umsteigezeiten unter
Berücksichtigung des Passagierverhaltens minimiert werden. Wir untersuchen damit den Einfluss wichtiger Systemparameter und Verhaltensmuster auf die Beförderungsqualität.
In this paper we present a novel extended formulation for the line planning problem that is based on what we call “configurations” of lines and frequencies. Configurations account for all possible options to provide a required transportation capacity on an infrastructure edge. The proposed configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, MIR, and multicover inequalities. These theoretical findings can be confirmed in computational results. Further, we show how this concept can be generalized to define configurations for subsets of edges; the generalized model implies additional inequalities from the line planning literature.
The task of periodic timetabling is to schedule the trips in a public transport system by determining arrival and departure times at every station such that travel and transfer times are minimized. To date, the optimization literature generally assumes that passengers do not respond to changes in the timetable, i.e., the passenger routes are fixed. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We show that different routing models have a huge influence on the quality of the entire system: Whatever metric is applied, the performance ratios of timetables w.r.t. to different routing models can be arbitrarily large. Computations on a real-world instance for the city of Wuppertal substantiate the theoretical findings. These results indicate the existence of untapped optimization potentials that can be used to improve the efficiency of public transport systems.
The task of timetabling is to schedule the trips in a public transport system by determining periodic arrival and departure times at every station. The goal is to provide a service that is both attractive for passengers and can be operated economically. To date, timetable optimization is generally done with respect to fixed passenger routes, i.e., it is assumed that passengers do not respond to changes in the timetable. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We propose several models that differ in the allowed passenger paths and the objectives. We compare these models theoretically and report on computations on real-world instances for the city of Wuppertal.
We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We derive a feasibility condition for path capacities supporting such direct connection flows similar to the feasibility condition for arc capacities in ordinary multi-commodity flows.
The concept allows to solve large-scale real-world line planning problems in public transport including a novel passenger routing model that favors direct connections over connections with transfers.
The integrated line planning and passenger routing problem is an important planning problem in service design of public transport. A major challenge is the treatment of transfers. A main property of a line system is its connectivity.
In this paper we show that analysing the connecvitiy aspect of a line plan gives a new idea to handle the transfer aspect of the line planning problem.
In this article we describe the impact from embedding a 15 year old model for solving the Steiner tree problem in graphs in a state-of-the-art MIP-Framework, making the result run in a massively parallel environment and extending the model to solve as many variants as possible. We end up with a high-perfomance solver that is capable of solving previously unsolved instances and, in contrast to its predecessor, is freely available for academic research.