Dokument-ID Dokumenttyp Verfasser/Autoren Herausgeber Haupttitel Abstract Auflage Verlagsort Verlag Erscheinungsjahr Seitenzahl Schriftenreihe Titel Schriftenreihe Bandzahl ISBN Quelle der Hochschulschrift Konferenzname Quelle:Titel Quelle:Jahrgang Quelle:Heftnummer Quelle:Erste Seite Quelle:Letzte Seite URN DOI Abteilungen OPUS4-879 misc Pfetsch, Marc A Branch-And-Cut for the Maximum Feasible Subsystem Problem 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. 2005 urn:nbn:de:0297-zib-8797 ZIB Allgemein OPUS4-812 misc Joswig, Michael; Pfetsch, Marc Computing Optimal Morse Matchings 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. 2004 urn:nbn:de:0297-zib-8120 ZIB Allgemein OPUS4-852 misc Borndörfer, Ralf; Grötschel, Martin; Pfetsch, Marc A Column-Generation Approach to Line Planning in Public Transport 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. 2005 urn:nbn:de:0297-zib-8522 /10.1287/trsc.1060.0161 ZIB Allgemein OPUS4-854 misc Borndörfer, Ralf; Neumann, Marika; Pfetsch, Marc Fare Planning for Public Transport 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. 2005 urn:nbn:de:0297-zib-8541 Mathematical Optimization OPUS4-856 misc Borndörfer, Ralf; Grötschel, Martin; Pfetsch, Marc Public Transport to the fORe! 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?. 2005 urn:nbn:de:0297-zib-8562 ZIB Allgemein OPUS4-785 misc Borndörfer, Ralf; Grötschel, Martin; Pfetsch, Marc Models for Line Planning in Public Transport 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. 2004 urn:nbn:de:0297-zib-7854 10.1007/978-3-540-73312-6_18 Mathematics of Transportation and Logistics OPUS4-1117 misc Borndörfer, Ralf; Neumann, Marika; Pfetsch, Marc The Steiner Connectivity Problem The Steiner connectivity problem is a generalization of the Steiner tree problem. It consists in finding a minimum cost set of simple paths to connect a subset of nodes in an undirected graph. We show that polyhedral and algorithmic results on the Steiner tree problem carry over to the Steiner connectivity problem, namely, the Steiner cut and the Steiner partition inequalities, as well as the associated polynomial time separation algorithms, can be generalized. Similar to the Steiner tree case, a directed formulation, which is stronger than the natural undirected one, plays a central role. 2009 urn:nbn:de:0297-zib-11171 10.1007/s10107-012-0564-5 Mathematical Optimization OPUS4-1055 misc Borndörfer, Ralf; Neumann, Marika; Pfetsch, Marc Angebotsplanung im öffentlichen Nahverkehr Die Angebotsplanung im öffentlichen Nahverkehr umfasst die Aufgaben der Netz-, Linien-,Fahr- und Preisplanung. Wir stellen zwei mathematische Optimierungsmodelle zur Linien- und Preisplanung vor. Wir zeigen anhand von Berechnungen für die Verkehrsbetriebe in Potsdam(ViP), dass sich damit komplexe Zusammenhänge quantitativ analysieren lassen. Auf diese Weise untersuchen wir die Auswirkungen von Freiheitsgraden auf die Konstruktion von Linien und die Wahl von Reisewegen der Passagiere, Abhängigkeiten zwischen Kosten und Reisezeiten sowie den Einfluss verschiedener Preissysteme auf Nachfrage und Kostendeckung. 2008 urn:nbn:de:0297-zib-10555 Mathematical Optimization OPUS4-1123 misc Berthold, Timo; Heinz, Stefan; Pfetsch, Marc Nonlinear pseudo-Boolean optimization: relaxation or propagation? Pseudo-Boolean problems lie on the border between satisfiability problems, constraint programming, and integer programming. In particular, nonlinear constraints in pseudo-Boolean optimization can be handled by methods arising in these different fields: One can either linearize them and work on a linear programming relaxation or one can treat them directly by propagation. In this paper, we investigate the individual strengths of these approaches and compare their computational performance. Furthermore, we integrate these techniques into a branch-and-cut-and-propagate framework, resulting in an efficient nonlinear pseudo-Boolean solver. 2009 urn:nbn:de:0297-zib-11232 Mathematical Optimization OPUS4-1082 misc Borndörfer, Ralf; Neumann, Marika; Pfetsch, Marc The Line Connectivity Problem This paper introduces the "line connectivity problem", a generalization of the Steiner tree problem and a special case of the line planning problem. We study its complexity and give an IP formulation in terms of an exponential number of constraints associated with "line cut constraints". These inequalities can be separated in polynomial time. We also generalize the Steiner partition inequalities. 2008 urn:nbn:de:0297-zib-10820 Mathematical Optimization