TY - GEN A1 - Prause, Felix A1 - Borndörfer, Ralf T1 - Construction of a Test Library for the Rolling Stock Rotation Problem with Predictive Maintenance N2 - We describe the development of a test library for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). Our approach involves the utilization of genuine timetables from a private German railroad company. The generated instances incorporate probability distribution functions for modeling the health states of the vehicles and the considered trips possess varying degradation functions. RSRP-PdM involves assigning trips to a fleet of vehicles and scheduling their maintenance based on their individual health states. The goal is to minimize the total costs consisting of operational costs and the expected costs associated with vehicle failures. The failure probability is dependent on the health states of the vehicles, which are assumed to be random variables distributed by a family of probability distributions. Each distribution is represented by the parameters characterizing it and during the operation of the trips, these parameters get altered. Our approach incorporates non-linear degradation functions to describe the inference of the parameters but also linear ones could be applied. The resulting instances consist of the timetables of the individual lines that use the same vehicle type. Overall, we employ these assumptions and utilize open-source data to create a library of instances with varying difficulty. Our approach is vital for evaluating and comparing algorithms designed to solve the RSRP-PdM. T3 - ZIB-Report - 23-20 KW - Rolling Stock Rotation Planning KW - Predictive Maintenance KW - Test Library Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-91734 SN - 1438-0064 ER - TY - GEN A1 - Löbel, Fabian A1 - Borndörfer, Ralf A1 - Weider, Steffen T1 - Non-Linear Battery Behavior in Electric Vehicle Scheduling Problems N2 - The currently most popular approach to handle non-linear battery behavior for electric vehicle scheduling is to use a linear spline interpolation of the charge curve. We show that this can lead to approximate models that underestimate the charge duration and overestimate the state of charge, which is not desirable. While the error is of second order with respect to the interpolation step size, the associated mixed-integer linear programs do not scale well with the number of spline segments. It is therefore recommendable to use coarse interpolation grids adapted to the curvature of the charge curve, and to include sufficient safety margins to ensure solutions of approximate models remain feasible subjected to the exact charge curve. T3 - ZIB-Report - 23-24 KW - Electric Vehicle Scheduling KW - Non-Linear Charging Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-92441 SN - 1438-0064 ER - TY - GEN A1 - Löbel, Andreas T1 - Solving Large-Scale Multiple-Depot Vehicle Scheduling Problems N2 - This paper presents an integer linear programming approach with delayed column generation for the {\em NP} Multiple-Depot Vehicle Scheduling Problem (MDVSP) in public mass transit. We describe in detail all basic ingredients of our approach that are indispensable to solve truly large-scale real-world instances to optimality, and we report on computational investigations that are based on real-world instances from the city of Berlin, the city of Hamburg, and the region around Hamburg. These real-world instances have up to 25 thousand timetabled trips and 70 million dead-head trips. Computational tests using the data of the Hamburger Hochbahn AG indicate savings of several vehicles and a cost reduction of about 10\% compared with the solution provided by HOT II, the vehicle scheduling tool of the HanseCom GmbH, Hamburg. Parts of our algorithms are already integrated in the BERTA system of the Berliner Verkehrsbetriebe (BVG) and will soon be integrated in the MICROBUS system of the Gesellschaft für Informatik, Verkehrs- und Umweltplanung mbH (IVU), Berlin. T3 - ZIB-Report - SC-97-17 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2866 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Ferreira, Carlos E. A1 - Martin, Alexander T1 - Decomposing Matrices into Blocks N2 - In this paper we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called {\em bordered block diagonal form}. More precisely, given some matrix $A$, we try to assign as many rows as possible to some number of blocks of limited size such that no two rows assigned to different blocks intersect in a common column. Bordered block diagonal form is desirable because it can guide and speed up the solution process for linear and integer programming problems. We show that various matrices from the LP- and MIP-libraries NETLIB and MITLIB can indeed be decomposed into this form by computing optimal decompositions or decompositions with proven quality. These computations are done with a branch-and-cut algorithm based on polyhedral investigations of the matrix decomposition problem. In practice, however, one would use heuristics to find a good decomposition. We present several heuristic ideas and test their performance. Finally, we investigate the usefulness of optimal matrix decompositions into bordered block diagonal form for integer programming by using such decompositions to guide the branching process in a branch-and-cut code for general mixed integer programs. T3 - ZIB-Report - SC-97-15 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2849 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Jünger, Michael A1 - Reinelt, Gerhard T1 - A Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints N2 - In this paper we consider a variant of the classical ATSP, namely the asymmetric Hamiltonian path problem (or equivalently ATSP) with precedence constraints. In this problem precedences among the nodes are present, stating that a certain node has to precede others in any feasible sequence. This problem occurs as a basic model in scheduling and routing and has a wide range of applications varying from helicopter routing[Timlin89], sequencing in flexible manufacturing [AscheuerEscuderoGroetschelStoer90,AscheuerEscuderoGroetschelStoer93], to stacker crane routing in an automatic storage system[Ascheuer95]. We give an integer programming model and summarize known classes of valid inequalities. We describe in detail the implementation of a branch&-cut algorithm and give computational results on real world instances and benchmark problems from TSPLIB. The results we achieve indicate that our implementation outperforms other implementations found in the literature. Real world instances up to 174 nodes could be solved to optimality within a few minutes of CPU-time. As a side product we obtained a branch&cut-algorithm for the ATSP. All instances in TSPLIB could be solved to optimality in a reasonable amount of computing time. T3 - ZIB-Report - SC-97-70 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3391 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Klostermeier, Fridolin A1 - Küttner, Christian T1 - Telebus Berlin: Vehicle Scheduling in a Dial-a-Ride System N2 - {\em Telebus\/} is Berlin's dial-a-ride system for handicapped people that cannot use the public transportation system. The service is provided by a fleet of about 100 mini-busses and includes aid to get in and out of the vehicle. Telebus has between 1,000 and 1,500 transportation requests per day. The problem arises to schedule these requests into the vehicles such that punctual service is provided while operation costs should be minimum. Additional constraints include pre-rented vehicles, fixed bus driver shift lengths, obligatory breaks, and different vehicle capacities. We use a {\em set partitioning\/} approach for the solution of the bus scheduling problem that consists of two steps. The first {\em clustering\/} step identifies segments of possible bus tours (``orders'') such that more than one person is transported at a time; the aim in this step is to reduce the size of the problem and to make use of larger vehicle capacities. The problem to select a set of orders such that the traveling distance of the vehicles within the orders is minimal is a set partitioning problem that we can solve to optimality. In the second step the selected orders are {\em chained\/} to yield possible bus tours respecting all side constraints. The problem to select a set of such bus tours such that each order is serviced once and the total traveling distance of the vehicles is minimum is again a set partitioning problem that we solve approximately. We have developed a computer system for the solution of the bus scheduling problem that includes a branch-and-cut algorithm for the solution of the set partitioning problems. A version of this system is in operation at Telebus since July 1995. Its use made it possible that Telebus can service today about 30\% more requests per day for the same amount of money than before. T3 - ZIB-Report - SC-97-23 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2925 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Weismantel, Robert T1 - Set Packing Relaxations of Some Integer Programs N2 - This paper is about {\em set packing relaxations\/} of combinatorial optimization problems associated with acyclic digraphs and linear orderings, cuts and multicuts, and vertex packings themselves. Families of inequalities that are valid for such a relaxation as well as the associated separation routines carry over to the problems under investigation. T3 - ZIB-Report - SC-97-30 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2998 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Weismantel, Robert T1 - Discrete Relaxations of Combinatorial Programs N2 - This paper investigates {\em relations\/} among combinatorial optimization problems. To establish such relations we introduce a transformation technique \mbox{---{\em aggregation}---} that allows to relax an integer program by means of another integer program. We prove that various families of prominent inequalities for the acyclic subdigraph problem, the multiple knapsack problem, the max cut, graph, and the clique partitioning problem, the set covering problem, and the set packing problem can be derived and separated in polynomial time in this way. Our technique is algorithmic. It has been implemented and used in a set partitioning code. T3 - ZIB-Report - SC-97-54 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3230 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Klostermeier, Fridolin A1 - Küttner, Christian T1 - Optimierung des Berliner Behindertenfahrdienstes N2 - In diesem Artikel geben wir einen Überblick über das Telebus-Projekt am Konrad-Zuse-Zentrum, Berlin, durch das der Behindertenfahrdienst in Berlin reorganisiert und optimiert wurde. Wir berichten kurz über die mathematischen Probleme und, etwas ausführlicher, über die nicht-mathematischen Schwierigkeiten, die bei der Durchführung dieses Projektes auftraten. T3 - ZIB-Report - SC-97-10 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2799 ER - TY - GEN A1 - Bestuzheva, Ksenia A1 - Chmiela, Antonia A1 - Müller, Benjamin A1 - Serrano, Felipe A1 - Vigerske, Stefan A1 - Wegscheider, Fabian T1 - Global Optimization of Mixed-Integer Nonlinear Programs with SCIP 8.0 N2 - For over ten years, the constraint integer programming framework SCIP has been extended by capabilities for the solution of convex and nonconvex mixed-integer nonlinear programs (MINLPs). With the recently published version~8.0, these capabilities have been largely reworked and extended. This paper discusses the motivations for recent changes and provides an overview of features that are particular to MINLP solving in SCIP. Further, difficulties in benchmarking global MINLP solvers are discussed and a comparison with several state-of-the-art global MINLP solvers is provided. T3 - ZIB-Report - 23-01 Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-89348 SN - 1438-0064 ER -