TY - THES A1 - Kinder, Mathias T1 - Models for Periodic Timetabling N2 - We investigate the computation of periodic timetables for public transport by mixed integer programming. After introducing the problem, we describe two mathematical models for periodic timetabling, the PERIODIC EVENT SCHEDULING PROBLEM (PESP) and the QUADRATIC SEMI-ASSIGNMENT PROBLEM. Specifically, we give an overview of existing integer programming (IP) formulations for both models. An important contribution of our work are new IP formulations for the PESP based on time discretization. We provide an analytical comparison of these formulations and describe different techniques that allow a more efficient solution by mixed integer programming. In a preliminary computational study, on the basis of standard IP solvers, we compare different formulations for computing periodic timetables. Our results justify a further investigation of the time discretization approach. Typically the timetable is optimized for the current traffic situation. The main difficulty with this approach is that after introducing the new timetable the passengers’ travel behavior may differ from that assumed for the computation. Motivated by this problem, we examine an iterative timetabling procedure that is a combination of timetable computation and passenger routing. We discuss the algorithmic issues of the passenger routing and study properties of the computed timetables. Finally, we confirm our theoretical results on the basis of an own implementation. N2 - Wir untersuchen die Berechnung von Taktfahrplänen für den öffentlichen Verkehr mit gemischt-ganzzahliger Programmierung (MIP). Im Anschluss an die Problembeschreibung, stellen wir zwei mathematische Modellierungen vor, das PERIODIC EVENT SCHEDULING PROBLEM (PESP) und das QUADRATIC SEMI-ASSIGNMENT PROBLEM. Wichtiger Bestandteil ist ein Überblick über existierende ganzzahlige Formulierungen beider Modelle. Wir entwickeln neue ganzzahlige Formulierungen für das PESP auf der Basis von Zeitdiskretisierung. Diese werden analytisch miteinander verglichen und wir beschreiben verschiedene Techniken, die eine effizientere Lösung der Formulierungen mit gemischt-ganzzahliger Programmierung ermöglichen. In einer ersten Rechenstudie, unter Verwendung gängiger MIP-Löser, vergleichen wir verschiedene ganzzahlige Formulierungen zur Berechnung von Taktfahrplänen. Unsere Ergebnisse rechtfertigen eine weitere Untersuchung des Zeitdiskretisierungsansatzes. In der Regel werden Fahrpläne mit Bezug auf die gegenwärtige Verkehrssituation optimiert. Dies birgt jedoch folgendes Problem. Wenn der neue Fahrplan eingeführt wird, ist es möglich, dass die Passagiere ein anderes Fahrverhalten zu Tage legen, als für die Berechnung des Fahrplans angenommen wurde. Vor diesem Hintergrund behandeln wir ein iteratives Verfahren zur Berechnung von Taktfahrplänen. Dieses ist eine Kombination aus Fahrplanberechnung und Passagierrouting. Neben den algorithmischen Details des Passagierroutings untersuchen wir Eigenschaften der berechneten Fahrpläne. Abschließend bestätigen wir unsere theoretischen Ergebnisse auf Grundlage einer eigenen Implementierung des Verfahrens. KW - Taktfahrplanung KW - PESP KW - iterative Fahrplanung KW - gemischt-ganzzahlige Programmierung KW - periodic timetabling KW - PESP KW - iterative timetabling KW - mixed integer programming Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10887 ER - TY - GEN A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Wolter, Kati T1 - Constraint Integer Programming: Techniques and Applications N2 - This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques for solving satisfiability problems. SCIP is available in source code and free for noncommercial use. We demonstrate the usefulness of CIP on three tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we demonstrate how to use CIP techniques to compute the number of optimal solutions of integer programs. Third, we employ the CIP framework to solve chip design verification problems, which involve some highly nonlinear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the nonlinear constraints by employing constraint programming techniques. T3 - ZIB-Report - 08-43 KW - constraint programming KW - mixed integer programming KW - branch-and-cut KW - optimization software KW - chip verification Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10950 SN - 1438-0064 ER - TY - GEN A1 - Heinz, Stefan A1 - Beck, J. Christopher T1 - Reconsidering Mixed Integer Programming and MIP-based Hybrids for Scheduling N2 - Despite the success of constraint programming (CP) for scheduling, the much wider penetration of mixed integer programming (MIP) technology into business applications means that many practical scheduling problems are being addressed with MIP, at least as an initial approach. Furthermore, there has been impressive and well-documented improvements in the power of generic MIP solvers over the past decade. We empirically demonstrate that on an existing set of resource allocation and scheduling problems standard MIP and CP models are now competitive with the state-of-the-art manual decomposition approach. Motivated by this result, we formulate two tightly coupled hybrid models based on constraint integer programming (CIP) and demonstrate that these models, which embody advances in CP and MIP, are able to out-perform the CP, MIP, and decomposition models. We conclude that both MIP and CIP are technologies that should be considered along with CP for solving scheduling problems. T3 - ZIB-Report - 12-05 KW - constraint integer programming KW - constraint programming KW - cumulative constraint KW - mixed integer programming KW - optional activities Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14660 SN - 1438-0064 ER -