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)
Orbitopal Fixing
(2006)
The topic of this paper are integer programming models in which a subset of 0/1-variables encode a partitioning of a set of objects into disjoint subsets. Such models can be surprisingly hard to solve by branch-and-cut algorithms if the permutation of the subsets of the partition is irrelevant. This kind of symmetry unnecessarily blows up the branch-and-cut tree. We present a general tool, called orbitopal fixing, for enhancing the capabilities of branch-and-cut algorithms in solving this kind of symmetric integer programming models. We devise a linear time algorithm that, applied at each node of the branch-and-cut tree, removes redundant parts of the tree produced by the above mentioned permutations. The method relies on certain polyhedra, called orbitopes, which have been investigated in (Kaibel and Pfetsch (2006)). However, it does not add inequalities to the model, and thus, it does not increase the difficulty of solving the linear programming relaxations. We demonstrate the computational power of orbitopal fixing at the example of a graph partitioning problem motivated from frequency planning in mobile telecommunication networks.
We introduce orbitopes as the convex hulls of 0/1-matrices that are lexicographically maximal subject to a group acting on the columns. Special cases are packing and partitioning orbitopes, which arise from restrictions to matrices with at most or exactly one 1-entry in each row, respectively. The goal of investigating these polytopes is to gain insight into ways of breaking certain symmetries in integer programs by adding constraints, e.g., for a well-known formulation of the graph coloring problem. We provide a thorough polyhedral investigation of packing and partitioning orbitopes for the cases in which the group acting on the columns is the cyclic group or the symmetric group. Our main results are complete linear inequality descriptions of these polytopes by facet-defining inequalities. For the cyclic group case, the descriptions turn out to be totally unimodular, while for the symmetric group case, both the description and the proof are more involved. The associated separation problems can be solved in linear time.
Public transport to the fORe
(2006)
We present a branch-and-cut algorithm for the NP-hard maximum feasible subsystem problem: For a given infeasible linear inequality system, determine a feasible subsystem containing as many inequalities as possible. The complementary problem, where one has to remove as few inequalities as possible in order to render the system feasible, can be formulated as a set covering problem. The rows of this formulation correspond to irreducible infeasible subsystems, which can be exponentially many. The main issue of a branch-and-cut algorithm for MaxFS is to efficiently find such infeasible subsystems. We present three heuristics for the corresponding NP-hard separation problem and discuss further cutting planes. This paper contains an extensive computational study of our implementation on a variety of instances arising in a number of applications.
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 transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize operating costs, the passengers want to minimize travel times. We propose a n ew multi-commodity flow model for line planning. Its main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically. We discuss properties of this model and investigate its complexity. Results with data for the city of Potsdam, Germany, are reported.
In this paper we introduce the fare planning problem for public transport which consists in designing a system of fares maximizing revenue. We propose a new simple general model for this problem. It i s based on a demand function and constraints for the different fares. The constraints define the structure of the fare system, e.g., distance dependent fares or zone fares. We discuss a simple example with a quadratic demand function and distance dependent fares. Then we introduce a more realistic discrete choice model in which passengers choose between different alternatives depending on the numb er of trips per month. We demonstrate the examples by computational experiments.
Can OR methods help the public transport industry to break even? The article gives evidence that there exist significant potentials in this direction, which can be harnessed by a combination of modern mathematical methods and local planning knowledge. Many of the planning steps in public transport are classical combinatorial problems, which can be solved in unprecedented size and quality due the rapid progress in large-scale optimization. Three examples on vehicle scheduling, duty scheduling, and integrated vehicle and duty scheduling illustrate the level that has been reached and the improvements that can be achieved today. Extensions of such methods to further questions of strategic, online, and market-oriented planning are currently investigated. In this way, OR can make a significant contribution to answer the basic but extremely difficult question ``What is a good public transport network?.
The \emph{fare planning problem} for public transport is to design a system of fares that maximize the revenue. We introduce a nonlinear optimization model to approach this problem. It is based on a d iscrete choice logit model that expresses demand as a function of the fares. We illustrate our approach by computing and comparing two different fare systems for the intercity network of the Netherlands.
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.