Refine
Year of publication
Document Type
- ZIB-Report (33)
- In Proceedings (12)
- Article (11)
- Book chapter (5)
- Book (1)
- In Collection (1)
Language
- English (63) (remove)
Is part of the Bibliography
- no (63)
Keywords
- line planning (6)
- integer programming (5)
- branch-and-cut (4)
- constraint integer programming (4)
- Online Optimization (3)
- Pseudo-Boolean (3)
- Routing (3)
- Telecommunications (3)
- column generation (3)
- computational complexity (3)
- linear programming (3)
- mixed-integer semidefinite programming (3)
- symmetry breaking (3)
- Branch-and-cut (2)
- Branch-and-price (2)
- Column generation (2)
- Constraint integer programming (2)
- Ganzzahlige Programmierung (2)
- Linear programming (2)
- Mixed-integer linear programming (2)
- Mixed-integer nonlinear programming (2)
- Mixed-integer semidefinite programming (2)
- Optimization solver (2)
- Parallelization (2)
- Steiner tree optimization (2)
- branch-and-price (2)
- column generation framework (2)
- demand function (2)
- discrete choice model (2)
- fare planning (2)
- mixed-integer linear programming (2)
- mixed-integer nonlinear programming (2)
- optimization solver (2)
- orbitopes (2)
- parallelization (2)
- public transport (2)
- (IIS) maximum feasible subsystem problem (1)
- Branch-And-Cut (1)
- Connectivity (1)
- Constraint Programming (1)
- Generalization (1)
- Graphenisomorphie (1)
- LP solver (1)
- Large Neighborhood Search (1)
- MINLP solver (1)
- MIP (1)
- MIP solver (1)
- MIQCP (1)
- Morse matching (1)
- Nachfragefunktion (1)
- Nahverkehr (1)
- Optimierung (1)
- Optimierungssoftware (1)
- Orbitope (1)
- Partition Inequalities (1)
- Paths (1)
- Preisplanung (1)
- Primal Heuristic (1)
- Public transport (1)
- Steiner Tree (1)
- Steiner Tree Generalization (1)
- Steiner tree solver (1)
- Symmetrie-Brechung (1)
- Symmetrie-Erkennung (1)
- basis pursuit (1)
- branch and bound (1)
- branch-cut-and-price framework (1)
- discrete Morse function (1)
- domain propagation (1)
- duty scheduling (1)
- forecasting (1)
- generic column generation (1)
- graph ismorphism (1)
- infeasible linear inequality system (1)
- irreducible infeasible subsystem (1)
- lexicographic representatives (1)
- linear relaxation (1)
- machine learning (1)
- maximum feasible subsystem problem (1)
- minimum IIS-cover (1)
- mixed integer programming (1)
- mixed-integer linear and nonlinear programming (1)
- modeling (1)
- multi-criteria optimization (1)
- optimization software (1)
- orthogonal matching pursuit (1)
- parallel branch-and-bound (1)
- passenger routing (1)
- public transport optimization (1)
- separation algorithm (1)
- simplex method (1)
- sparse representations (1)
- symmetry detection (1)
- variable fixing (1)
- vehicle scheduling (1)
The line planning problem is one of the fundamental problems in strategic planning of public and rail transport. It consists in finding lines and corresponding frequencies in a network such that a giv en demand can be satisfied. There are two objectives. Passengers want to minimize travel times, the transport company wishes to minimize operating costs. We investigate three variants of a multi-commo dity flow model for line planning that differ with respect to passenger routings. The first model allows arbitrary routings, the second only unsplittable routings, and the third only shortest path rou tings with respect to the network. We compare these models theoretically and computationally on data for the city of Potsdam.
Morse matchings capture the essential structural information of discrete Morse functions. We show that computing optimal Morse matchings is NP-hard and give an integer programming formulation for the problem. Then we present polyhedral results for the corresponding polytope and report on computational results.
The \emph{line planning problem} is one of the fundamental problems in strategic planning of public and rail transport. It consists of finding lines and corresponding frequencies in a public transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize its operating cost; the passengers request short travel times. We propose two new multi-commodity flow models for line planning. Their main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically.