Christophe Finot
email: christophe.finot@u-bourgogne.fr

Julien Fatome

Alexej A Sysoliatin

Fedorovich Alexey

Stefan Kosolapov

Wabnitz

A Kosolapov

Stefan Wabnitz

Competing Four-Wave Mixing Processes in Dispersion Oscillating Telecom Fiber

Keywords: optics, fibers, (190.4380) Nonlinear optics, four-wave mixing, (190.4410) Nonlinear optics, parametric process

published or not. The documents may come

The generation of a set of new optical frequencies from a pump laser has a variety of applications, ranging from optical metrology to spectroscopy and wavelength division multiplexing. Nonlinear methods to generate a regular comb of new frequency components are based on the multiple four-wave mixing (FWM) process occurring in highly nonlinear waveguides [1]. The mechanism for the generation of frequency sidebands from a CW pump is Kerr-induced phase-matching of the FWM interaction or modulation instability (MI), which requires operating in the anomalous dispersion regime. Such restriction can be circumvented with a cavity geometry, where MI [2] and frequency comb generation [3] may also be observed in the normal dispersion regime. Alternatively, one may obtain MI and unequally spaced Kerr frequency comb of sidebands with average normal, periodically varying dispersion, so that the FWM process is quasi-phasematched (QPM) [4][5][6][7]. QPM-FWM was recently observed in a dispersion oscillating photonic crystal fiber by using intense 2 ns pulses from a master optical power oscillator emitting at 1072 nm [8]. The interplay of QPM-FWM with supercontinuum (SC) generation was also studied in a dispersion oscillating, highly nonlinear fiber with average anomalous dispersion at telecom wavelengths [9]. In this Letter we present the first experimental demonstration of the generation of unequal spacing frequency comb of sidebands based on the QPM-FWM process in average normal, dispersion oscillating fiber (DOF) at telecom wavelengths. Moreover, our experiments reveal that higher-order QPM-FWM sideband generation competes with the cascade or multiple four-wave mixing (MWFM) process which is activated by the mixing of the pump with the first-order QPM-FWM sideband pair.

Pulse propagation in a DOF can be described by the Nonlinear Schrödinger Equation (NLSE)

2 2 2 2 () | | 0 2 zt z i           (1)
Here z and t denote the distance and retarded time (in the frame travelling at the group-velocity) coordinates,  is the complex field envelope,

2



and  are the longitudinally-varying second order group velocity dispersion (GVD) and the constant Kerr nonlinear coefficients, respectively. We have numerically checked that for the fiber parameters and the typical range of powers that will be described in the experimental section, fiber loss and higher order linear and nonlinear effects such as third order dispersion, Raman scattering or selfsteepening have a very limited impact, and therefore can be neglected in a first approximation and for the clarity of the discussion.

In our DOF, the variation of GVD with distance may be approximated with the expression

  22 2 ( ) sin 2 / A zz          (2)
where

2  , 2 A 
and  are the average normal dispersion of the fiber, the amplitude and the spatial period of the dispersion fluctuations, respectively. We have numerically found that , which is a phase shift of the sinusoidal dispersion modulation, does not significantly influence the spectrum at the output of the DOF: therefore we have also neglected this term in our analysis.

As well known, in the normal dispersion regime a CW pump of power P in a DOF leads to a QPM-FWM sidebands at relative frequencies [4] :

2 2 / 2 p pP        (3)
where 1, 2, 3 p     . More recently [5] it has been shown that the gain undergone by the p th sidebands after a propagation length L can be predicted by the formula

               (4)
where J p is the Bessel function of order p. In order to achieve and study the generation of unequal spacing frequency sidebands according to the relation of Eq. ( 3), we have designed and fabricated a highly nonlinear DOF with a zero dispersion wavelength (ZDW) in the telecom C band. The fiber preform was prepared by the MCVD process using mixtures of SiF in order to obtain the necessary refractive index profile (see inset of Fig. 1), and it was drawn into a 400 m long highly nonlinear DOF. Fig. 1(a) shows the measured values of the average dispersion of the fiber as a function of wavelength. As it can be seen, the average fiber GVD remains normal for wavelengths below the ZDW which located at about 1556 nm. On the other hand, Fig. 1(b) shows the estimated periodic variation with distance of the GVD 2  at the pump wavelength of 1534.7 nm: the imposed dispersion oscillation period  was equal to 20 m, and the resulting GVD oscillation amplitude is estimated as 2 A  = 2 ps 2 /km, with an average value 2  of 0.74 ps 2 /km. The nonlinear and loss coefficients are 10 W -1 .km -1 and 0.7 dB/km, respectively.

In the experiments, we pumped the DOF with a microchip laser emitting 3.7 ns pulses, with a repetition rate of 2.68 kHz. Given the ns duration of the pulses, we can assimilate the pump to a quasi-CW source having a power close to the peak power of the pulses. As the power was raised above P=5 W, a primary set of spectral sidebands was generated involving multiple sidebands with unequal frequency spacing on either side of the pump (see Fig. 2(a)). Moreover, a second set of sidebands having a regular frequency spacing 1 is superimposed on the first one. We may associate this secondary set to cascade or MFWM initiated by the mixing between the pump and the first QPM sidebands. We may also note additional sidebands located between the 1 st QPM sideband and the pump, that we attribute to FWM between the 1 st and the 2 nd QPM sidebands. Whenever the pump power increased above P=8 W, the frequency peaks merge into a nearly flat SC, and the nonlinear Raman contribution becomes a significant factor. Details of the evolution of the first and third sidebands are provided in panels (b1) and (b2) of Fig. 2, respectively. These panels qualitatively describe the influence of pump power on both the position and shape of the generated sidebands. Contrary to the well-known MI process occurring in the anomalous dispersion regime of uniform dispersion fibers, increasing here the input pump power leads to sidebands which are closer to the pump. The 1 st QPM Stokes sideband in Fig. 2(b1) is located in the close vicinity of the fiber ZDW (see the dashed vertical line), which enhances the efficiency of additional competing FWM processes. We may also clearly notice in Fig. 2(b1) that the tail of the 1 st QPM Stokes sideband undergoes a strong and asymmetric spectral broadening when crossing the ZDW. On the other hand, the third QPM sideband in Fig. 2(b2) exhibits a double peak structure, where each peak has a different growth rate as the pump power increases. As we shall see, the two sideband peaks in Fig. 2(b2) originate from two distinct and competing FWM processes, namely QPM and MFWM.

A more quantitative analysis of the sideband dependence upon pump power is provided in Fig. 3, where the analytical results of Eqs. ( 3) and ( 4) are compared with the experimental measurements and the numerical integration of the NLSE (1). From Fig. 3(a) we may point out a good agreement between theory and experiments for the frequency location of both the 1 st and 2 nd QPM sidebands: the experimental results are well within the frequency range which is predicted by the numerics. The evolution of the third sideband, which exhibits a much larger bandwidth, follows the predictions of Eq. ( 3) at relatively low pump powers (i.e., for P<6W). Whereas at higher pump powers the peak gain frequency shifts towards lower frequencies, in qualitative agreement with the detuning corresponding to the MFWM process resulting from the FWM of the pump and the 1 st QPM sideband, namely 2 1. The dependence of the sidebands gain upon input pump power P is plotted in Fig. 3(b). Results from numerical simulations (solid lines) are in reasonable agreement with the results predicted by Eq. ( 4) (dotted lines) for the first and second sidebands. However, we notice that the agreement is limited to low powers only for the third sidebands. Indeed for input pump peak powers above P=4W, instead of experiencing the gain drop which is predicted by Eq. ( 4), a second process, i.e., the MFWM between the pump and the first sideband, effectively boosts the 3 rd sideband gain. The experimental evolution of the spectral component peak power of the first three sidebands qualitatively confirms these numerical trends. Indeed, as shown in Fig. 3(c), the sideband intensity grows rapidly larger with increasing pump power: nearly 20 dB of sideband gain is obtained for a 1 dB increase of pump power. Fig. 3(c) also confirms that the 3 rd sideband experiences a larger gain than the 2 nd sideband, which is not consistent with the prediction of Eq. ( 4) that does not take into account the presence of MFWM.

In Fig. 4(a) we summarize the experimental measurements carried out with increasing input pump power. The development of the various sidebands originating from either the QPM or the MFWM processes is well reproduced by numerically solving the NLSE (1) (see Fig. 4(b)). This validates the various assumptions that we made for the clarity of the discussion. Among those assumptions, it is worth noting that, in spite of the frequency dependence of the GVD shown in Fig. 1(a), and of the fact that a non-negligible part of the spectrum falls within the region of anomalous dispersion, it appears that neglecting higher order dispersive terms is a fully reasonable approximation. In other words, the consequences on the nonlinear wave dynamics of the longitudinal variation of We have complemented our measurement studies by experimentally investigating the FWM dynamics with partially coherent pumping. Therefore we replaced the nanosecond microchip laser by a home-made source based on the amplification of spectrally filtered continuous amplified spontaneous emission [10]. The spectral full width at half maximum of the optical band pass Gaussian filter centered at 1534.37 nm was tuned between 10 and 200 GHz. The influence of the average power of the partially incoherent field with a 20-GHz spectral bandwidth on the generated FWM spectrum is summarized in Fig. 5(a). When compared with the previously discussed coherent case, one may point out several different features. For average powers as low as 1W, several QPM and MFWM sidebands can already be distinguished. This contrasts with Fig. 4, where peak powers exceeding 5 W were required in the coherent case in order to observe the cascading of the FWM process. The 2 nd QPM-FWM sideband is already clearly apparent as soon as 0.5 W of average power is reached, whereas Eq. ( 4) predicts a gain below the dB level in the case of fully coherent pumping. As far as the frequency of the sidebands is concerned, we may note that for 1 W of pump power the 1 st QPM sideband is detuned by 2.7 THz from the pump frequency, which is lower than the analytical prediction of Eq. ( 3), i.e. 3 THz.

Moreover, in the partially coherent case the different sidebands are significantly broader than those recorded in the coherent case. Subplot 5(b) reveals the influence of the input source spectral bandwidth on the sideband spectrum. As it can be seen, increasing the source incoherence while maintaining its average power fixed leads to a drop of the spectral gain, as well as to a modification of the spectral sidebands. All of those different features are in qualitative agreement with numerical simulations (not reported here) of the NLSE (1) with incoherent pumping. These results confirm that the source incoherence has a dramatic influence on parametric processes in optical fibers. The strong fluctuations of the instantaneous temporal intensity of the partially coherent pump associated with the high powerdependence of the sideband gain explain in part such a behavior and may also lead the emergence of extreme events. [10]. A more detailed description of the impact of the incoherence is beyond the scope of the present study, and will be the subject of further investigations.

In conclusion, we proposed and demonstrated the use of a ns-pulse pumped DOF for the generation of a comb of multiple spectral sidebands in the telecom C-band. We observed multiple QPM-FWM peaks mixed with standard cascade FWM sidebands. The observation of such competition is made possible by the unequal spacing of QPM-FWM sidebands, in contrast with the equally spaced MFWM sidebands. This example confirms all the potentialities brought by the interplay of the QPM-FWM process with better known parametric interactions [11,12]. We also experimentally investigated the generation of modulational instability and FMW sidebands under partially coherent pumping. We found that in this case a nearly 6-fold reduction in the average power needed to reach a detectable level for the QPM sidebands is obtained. In this context, using a partially coherent source such as a fiber Raman laser may become an attractive solution.

Fig. 1 .

 1 Fig. 1. (a) Measured values of average GVD (crosses) vs. wavelength, with linear approximation as a guide to the eye (solid curve). The refractive index profile of the fiber preform is plotted as an inset. (b) Estimated periodic variation of the GVD at the pump wavelength of 1534.7 nm.

4

 4

Fig. 2 .

 2 Fig. 2. Sideband intensities vs frequency detuning from the pump, showing: (a) the variation of the output spectrum vs input pump power in the range of 4W-10W. Magnification of the evolution with pump energy of the first and third sidebands is provided in panels (b1) and (b2), respectively.

Fig. 3 .

 3 Fig. 3. Comparison of the experimental, numerical and analytical dependence of first three QPM sidebands upon pump power P. Results are plotted in blue, green and red for the 1 st , 2 nd and 3 rd sideband, respectively. Experimental results are plotted with filled markers, whereas analytical results from Eqs. (3) or (4) are plotted with dotted lines. For the 3 rd sideband, the measured data correspond to either the maximum of the 3 rd QPM sideband or of the FWM sideband once they merge. (a) Evolution of the sideband frequencies. Grey areas correspond to the 10dB bandwidth of the numerically obtained sidebands. The dashed dotted line represents the frequency resulting from FWM of the pump and the 1 st QPM sideband. (b) Comparison of the gain obtained from numerical simulation (solid lines) with the predictions of Eq (4). (c) Experimental pump power dependence of spectral component peak power for the various sidebands.

2 

 2 are here much more significant than the frequency dependence of 2  .

Fig. 4 .

 4 Fig. 4. Contour plot of (a) experimental and (b) numerical spectral intensity vs. input pump power. Spectra obtained from simulations are averaged over 20 shots.

Fig. 5 .

 5 Fig. 5. (a) Experimental variation of the output spectrum vs pump power for an initial incoherence width of 20 GHz. (b) Evolution of the output spectrum vs the incoherence width of the pump (as defined by the filter width) for a fixed input average power of 1.5 W. We acknowledge the financial support of the Conseil Regional de Bourgogne (Pari Photcom) and the funding of the Labex ACTION program (ANR-11-LABX-01-01). The experimental work has benefited from the PICASSO Platform of the University of Burgundy. This research was funded by the European Research Council under Grant Agreement 306633 and by Fondazione Cariplo, grant n.2011-0395. A.S. acknowledges support from a Landau Network-Cariplo Foundation fellowship and from the Ministry of Education and Science of the Russian Federation.

Additional page :


Hannah Bast

Jonas Sternisko

Sabine Storandt

Delay-Robustness of Transfer Patterns in Public Transportation Route Planning *

Keywords: 1998 ACM Subject Classification F.2.2 Nonnumerical Algorithms and Problems Route planning, public transportation, transfer patterns, delay, robustness Digital Object Identifier 10.4230/OASIcs.ATMOS.2013.42

Transfer pattern routing is a state-of-the-art speed-up technique for finding optimal paths which minimize multiple cost criteria in public transportation networks. It precomputes sequences of transfer stations along optimal paths. At query time, the optimal paths are searched among the stored transfer patterns, which allows for very fast response times even on very large networks. On the other hand, even a minor change to the timetables may affect many optimal paths, so that, in principle, a new computation of all optimal transfer patterns becomes necessary. In this paper, we examine the robustness of transfer pattern routing towards delay, which is the most common source of such updates. The intuition is that the deviating paths caused by typical updates are already covered by original transfer patterns. We perform experiments which show that the transfer patterns are remarkably robust even to large and many delays, which underlines the applicability and reliability of transfer pattern routing in realistic routing applications.

Introduction

When traveling with public transportation, not only the absolute time of travel matters: Also the number of transfers and the total fare are important or, for instance, the reliability of connections along the journey. The goal of public transportation route planning is to find paths that minimize a multi-criteria cost function. Public transportation data is typically available as a set of timetables and can be modeled as a directed graph. Classical route planning algorithms perform a multi-criteria variant of Dijkstra's algorithm on the graph. To our knowledge, transfer pattern routing [START_REF] Bast | Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns[END_REF] is the fastest speed-up technique for this problem.

After precomputing sequences of transfers along all optimal paths which uses quadratic time in the number of stations, it allows to find the Pareto-optimal paths in huge networks within a few milliseconds. Because of its excellent scalability, the idea of transfer pattern routing is employed by Google Maps. If the underlying network (read: the information of the timetables) changes, the precomputed transfer patterns become outdated and optimal results cannot be guaranteed anymore. Incorporating an update into the transfer patterns is hard, because the dependency between a changed connection and the affected transfer patterns is unclear. In principle, the whole expensive precomputation has to be done again. But this is impossible as in realistic settings there are often updates. Our idea is, that provided there are only minor changes to the network, the original transfer patterns are sufficient to find optimal routes in most cases.

Criticism of transfer pattern routing often refers to its theoretical suboptimality and lacking support for dynamic scenarios. At the time of writing, there are no publications about if and how real-time updates can be handled by transfer pattern routing. But this is an important aspect for the practicability of the algorithm, because route planning service providers wish to recompute the transfer patterns only occasionally, when long-term changes to the timetables are made. The main contribution of this work resides in empirically proving the reliability of transfer pattern routing for location-to-location queries in the context of real-time updates. We evaluate the quality of transfer patterns in different global delay scenarios and study the immediate effect of delaying connections involved in optimal paths. Moreover, we investigate on which parameters the robustness depends and how it can be increased.

Related Work

Transfer pattern routing has been introduced by Bast et al. [START_REF] Bast | Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns[END_REF]. The authors outline the key components of the algorithm and present a set of techniques and heuristics to render the computation of transfer patterns feasible. Most notably is the concept of computing only parts of transfer patterns up to important stations and combining these parts at query time.

Geisberger [START_REF] Geisberger | Advanced Route Planning in Transportation Networks[END_REF] elaborates how to compute transfer patterns in fully realistic settings with walking between stations and for answering location-to-location queries.

The requirements for a route planning algorithm in a dynamic network are analyzed in [START_REF] Müller-Hannemann | Efficient Timetable Information in the Presence of Delays[END_REF]. There have not been any publications on transfer patterns in such a setting yet. Speed-up techniques without a time-consuming precomputation and thus suitable for dynamic scenarios are for example SUBITO [START_REF] Berger | Fully Dynamic Speed-Up Techniques for Multi-criteria Shortest Path Searches in Time-Dependent Networks[END_REF] and RAPTOR [START_REF] Delling | Round-Based Public Transit Routing[END_REF]. These approaches allow to find Pareto-optimal paths between stations in short time (SUBITO about 100 ms on German railway network, RAPTOR about 100 ms for London transit). However, the query times of these approaches cannot compete with transfer pattern routing on large networks (43 ms for North America).

A related field of research focuses on robustness to delay in the sense that the probability of missing a connection along a route is minimized. Most recently, a framework of algorithms based on a technique called Connection Scan has been introduced [START_REF] Dibbelt | Intriguingly Simple and Fast Transit Routing[END_REF]. The authors report convincing average query times for finding the route with earliest arrival time (1.8 ms) and for multi-criteria profile queries (255 ms) on the London data set. However, it remains unclear how fast the algorithm answers one-to-one queries when more than one cost-criterion is minimized. Besides the solution of classical route planning problems, the authors apply Connection Scan to find alternative routes by minimizing the expected arrival time. Goerigk et al. [START_REF] Goerigk | The Price of Robustness in Timetable Information[END_REF] compute routes which are robust to delays in the sense that all transfers along a route are guaranteed, given a specific delay scenario. They observe that strictly robust routes last longer than the fastest routes, whereas light robust routes have a relatively small overhead. Keyhani et al. [START_REF] Keyhani | Reliability and Delay Distributions of Train Connections[END_REF] introduce a stochastic model which rates the reliability of transfers along routes. Other than in those articles, robustness does not refer to routes with reliable transfers in this paper, but to sustaining optimality. Section 4.1 refers to the delay models of the aforementioned works in more detail.

AT M O S ' 1 3 3 Preliminaries

This section defines preliminary concepts and models. It explains the idea and components of transfer pattern routing. ). Let stop(T, s) denote the index of s in the station sequence of T . We say a trip connects two stations s a and s b , if s a , s b ∈ stops(T ) and stop(T, s a ) < stop(T, s b ), and call s a and s b the start-and endpoint of the connection, respectively. Multiple trips which share the same sequence of stations and do not overtake each other form a line.

Modeling timetables

A route between two stations is a sequence of alternating rides on board of a vehicle and transfers between connections. The start-and endpoints of the n connections along a route form a sequence of 2n stations, which is called transfer pattern of the route. For queries between two locations (not stations) X and Y , there is an additional walking part at the beginning and the end. A routing algorithm answers a query with a set of routes that minimize multiple cost criteria. The costs of a route are the sum of the costs of all its connections and transfers. When comparing cost tuples, we say that a dominates b (a < b), if it is as good as b in every component and better in at least one. a and b are incomparable, if neither a < b nor b < a. The costs of optimal paths to a query are pairwise incomparable, they form a Pareto-set.

Time-expanded Graph

We use publicly available timetable data following the General Transit Feed Specification (GTFS) format and model it as time-expanded graph according to Pyrga et al. [START_REF] Pyrga | Efficient Models for Timetable Information in Public Transportation Systems[END_REF]. Each departure and arrival event along a trip is explicitly modeled as a node with a timestamp. The successive nodes are connected with arcs of costs corresponding to the time difference between the two events. Beside arrival and departure nodes, there are nodes modeling transfers and waiting at a station. For each departure node, there is a transfer node with the same timestamp and an arc connecting it to the departure node. At each station, every transfer node is connected to the next transfer node in time. To model transfers between vehicles, an arc connects each arrival node to a subsequent transfer node. Usually, a traveler cannot instantly change from one vehicle to another. We model this with the difference between the arrival and the connected transfer node not being less than a fixed transfer buffer of 120 seconds. We want to find routes which minimize the time of travel and the number of transfers. Therefore, the arcs have a tuple weight consisting of the time difference between the connected nodes and the penalty, which is 1 for arcs from arrival to transfer nodes and 0 for all other arcs. In order to decrease the size of the graph, we remove departure nodes by redirecting incoming arcs to the respective successors.

Walking Between Stations

In a model for realistic route planning, transfers involving walking between two stations must be possible. Therefore, we maintain an additional walking graph with arcs between neighboring stations and the duration of walking as costs. For the sake of simplicity, we take the straight-line distance between the connected stations and assume a fixed speed of 5 km/h to compute the costs. During search, when expanding a label at an arrival node at station S and time t arr , the walking graph is used to determine the first transfer node after t arr + walk(S, T ) + transfer buffer for every neighbor station T . The time difference between the two nodes and a penalty of 1 are used as weight for the relaxed virtual arc. By restricting walking to happen between arrival and transfer nodes, this model implicitly forbids via-walking over multiple stations in a row.

Routing with Transfer Patterns

The transfer pattern of a route is the sequence of stations where a change of the transportation vehicle occurs, including the departure and arrival station. When considering all possible departure times at a station A, the optimal paths for journeys A → B form a set of transfer patterns. In public transportation, this set has typically only a few elements. For example, when traveling from Paris to Nice there is a direct TGV which leaves every other hour. In between its departure times, the journey with the earliest arrival time at Nice is one of two connections with transfers at Lyon or Marseilles. We say that Paris -Nice, Paris -Lyon -Nice and Paris -Marseilles -Nice are the optimal transfer patterns for this station pair.

The key idea of the algorithm is that the set of optimal transfer patterns between two stations A and B at all times form a search space, which is orders of magnitude smaller than the original graph. Given they are known, the Pareto-optimal paths at a specific time can be found among them. In short, the algorithm determines the optimal transfer patterns for all pairs of stations and searches on the graph described by the patterns.

Computation of Optimal Transfer Patterns

Conceptually, the optimal transfer patterns for a station pair A, B can be determined by running a multi-criteria variant of Dijkstra's algorithm from A. On the time-expanded graph1 , we compute the transfer patterns as described in [START_REF] Bast | Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns[END_REF]: From every station, a profile query determines the optimal paths to all reachable destinations. For every destination and its arrival nodes at times t 1 < t 2 < . . . the arrival-chain algorithm selects a dominating subset among the set of labels consisting of (i) labels settled at t i , and (2) labels settled at t i-1 with duration increased by t i -t i-1 . Every selected label corresponds to an optimal path, which is backtracked to its origin while recording stations where transfers happened. The resulting optimal transfer patterns are stored as a directed acyclic graph (DAG). In extension to [START_REF] Bast | Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns[END_REF], we exploit the fact that the departure and destination station of a transfer pattern is always known from context [START_REF] Sternisko | On Compact Representation and Robustness of Transfer Patterns in Public Transportation Routing[END_REF]. This allows to store all patterns in one joint DAG, which automatically resolves redundancies and reduces the size of the data.

The precomputation has quadratic time effort in the number of stations. When computing transfer patterns for location-to-location queries (which we do), the arrival-chain algorithm has to consider all arrival events in the walking neighborhood N (s) of each destination s. With an unbound neighborhood radius the running time would become cubic. Therefore we limit walking to stations within 1 000 meters. Nevertheless, the precomputation is very expensive. This is the price for the very fast query times. In order to reduce its duration, we employ the concept of important stations (hubs) and compute only parts of transfer patterns [START_REF] Bast | Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns[END_REF]. Global (unlimited) transfer patterns are computed only from important stations. From all other stations, we compute the transfer patterns up to the first transfer at a hub and a maximum of three trips. Although this heuristic leads to a loss of optimality (the search cannot find optimal paths with more than two transfers, none of which is at a hub), in practice, only very few optimal paths are affected [START_REF] Bast | Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns[END_REF]. In Section 5 we will see its marginal effect on the optimality of the algorithm's results.

Routing with Transfer Patterns

Once computed, the patterns between stations A and B describe a compact graph. A location-to-location query X@t → Y is answered by constructing a query graph and performing a search on it. The query graph is created from the transfer patterns between departure stations s ∈ N (X), the important stations and the destination stations s ∈ N (Y ) as demonstrated in [START_REF] Bast | Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns[END_REF][START_REF] Geisberger | Advanced Route Planning in Transportation Networks[END_REF]. We follow the refinements of Geisberger [START_REF] Geisberger | Advanced Route Planning in Transportation Networks[END_REF] and distinguish between two nodes representing alternating arrival and departure events for each station. The arcs in this graph correspond to (walking-) transfers or direct connections between stations. During the search, the travel time along these arcs can be determined using an efficient data structure. We proceed in analogy to [START_REF] Bast | Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns[END_REF]

Delay and Robustness

This section presents our delay model, points out the problem of frequent updates for a preprocessing-based algorithm and introduces our approach to handle delay with transfer pattern routing.

Delay Scenarios

Among different sources of real-time updates to timetables (trip cancellation, redirection, auxiliary connections, ...) we focus on the most common one, which is delay of trips. The literature distinguishes between primary delay (e.g. a train is late due to engine issues) and secondary delay (other trains waiting for the former) [START_REF] Müller-Hannemann | Efficient Timetable Information in the Presence of Delays[END_REF]. Delay models in related projects range from simplistic independence assumptions [START_REF] Dibbelt | Intriguingly Simple and Fast Transit Routing[END_REF] over models which allow for delay to accrue [START_REF] Goerigk | The Price of Robustness in Timetable Information[END_REF] to sophisticated models respecting primary delay of trains, knock-on delay to other trips and delay due to waiting for late connections [START_REF] Higgins | Modeling Train Delays in Urban Networks[END_REF]. In a survey of stochastic models for delay, Yuan [START_REF] Yuan | Stochastic Modelling of Train Delays and Delay Propagation in Stations[END_REF] successfully anneals distributions of non-negative primary delay with exponential functions. Once a trip is delayed, the propagation over successive connections follows complex rules. Refer to Berger et al. [START_REF] Berger | Stochastic Delay Prediction in Large Train Networks[END_REF] for an overview and a stochastic model for delay propagation in timetables.

For the sake of simplicity and because data about real-time updates is hardly available, we focus on primary delay, ignore knock-on effects as well as scheduled security headways between trains and model delay independently between trips. In six different scenarios (Table 1), the set of trips is partitioned into groups of common average delay Eδ. For each group, a random subset of all trips is selected. Every selected trip is delayed with time δ drawn from an exponential distribution with probability density function pdf 1). The delay is inserted starting at a uniformly random stop i, i.e. the trip's times (t arr j , t dep j ) are replaced with (t arr j + δ, t dep j + δ) for j ≥ i. We choose three different scenarios where one quarter of the connections are delayed with 5 (Low), 15 (Medium) an 50 minutes (High) in average. In addition, we generate three combined scenarios with an increasing mixture of average delay (Mix Low, Mix Normal and Mix Chaos). In the last scenario, every trip is delayed.

(δ) = 1/Eδ • exp(-1/Eδ • δ) (Figure
One might argue that this model is too far from reality. However, by modeling delay independently between trips, the scenarios become harder to deal with than in reality. If delay occurs frequently along a specific line or in a street prone to congestion, alternative routes are more obvious and could be retrieved during the precomputation. Furthermore, in typical metropolitan networks with high service frequencies, connections typically do not wait for delayed trips. Waiting policies in hierarchical train networks are designed such that the important transfers between trips are maintained and the resulting delay for waiting trips can be compensated during the remainder of their trip and knock-on delay to further connections is minimized. Therefore, we believe that in a refined model with realistic waiting rules transfer patterns will perform more robust than in our simplified model. We are working on another set of experiments with such a model, but by the time of writing there are no results yet.

Delay and Transfer Patterns

The routing algorithm finds optimal routes only if the precomputed transfer patterns are optimal. If a trip is delayed, it is possible that an optimal route previously taking this trip will resort to another connection, thereby changing its transfer pattern. Unfortunately, not only routes along the delayed trip are affected and it is hard to decide which transfer patterns have to be updated. To make this clear, think of a train which is delayed and stops at some station at 10:15 instead of 9:45. Another train arrives at the same station at 10:00. Passengers of this train may benefit from the delayed train and arrive at their destination earlier than with a regular connection.

Thus, the optimal transfer patterns have to be computed from scratch. But this is timeconsuming: for example, the transfer pattern computation for New York requires around 800 core hours ( [START_REF] Bast | Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns[END_REF], Table 3). Given a steady flow of updates to the timetables, it is impossible to keep the transfer patterns up to date. On the other hand, the data structure for direct connection lookup can be computed within a few minutes ([1], Table 2). Updating a single trip is fast, as we will prove. It is thus adaptable to frequent changes of the timetables. Our

AT M O S ' 1 3

approach to deal with real-time updates is to update only the direct connection data, and search on query graphs generated from the original transfer patterns.

Updating the Direct Connection Data

Now we explain how a single trip in the direct connection data structure can be updated in real-time. When constructing the data from a collection of trips, we create a mapping from sequences of station ids to all lines that serve these stations in the given order. When updating a specific trip, the trip's stop times are changed within its line. If the line still has the FIFO-property (the trip does not overtake another trip and is not overtaken), we are done. Otherwise, the trip is removed from the line. If it does not fit into another line serving the same sequence of stations, a new line is created. The line id and the respective stop position along the line is added to the incidence list of every served station (see Section 3.2). For example in New York City, there are 16 454 lines and C has a maximum size of 66. For the most frequent lines, |trips(l)| is 299 and for the longest trips |stops(T )| is 117. Updating a trip takes 40-80 µs. Typical update rates are about 70 updates per second (German railway; primary delay, secondary delay and forecast) [START_REF] Müller-Hannemann | Efficient Timetable Information in the Presence of Delays[END_REF], so our approach clearly allows for real-time updates.

Experiments

In the previous section, we proposed to deal with delays by searching routes using the original transfer patterns (computed for the graph without delays) and updated direct connection data. This potentially leads to non-optimal responses. In this section, we present several experiments which show that this is rarely the case, even for many and large delays.

Global Delay Scenarios

Method We present experiments conducted on the data sets of Toronto (10 883 stations, 1.5 M departures) and New York City (16 765 stations, 2.3 M departures). The data can be accessed at http://ad.informatik.uni-freiburg.de/publications. The time-expanded graph is generated for a random weekday (from 1:00 am until 6:30 am the next day) and the transfer patterns are computed on this graph according to Section 3.2. This forms the baseline Null. We apply different delay scenarios from Section 4.1 to the data sets and compute the direct connection data and the updated time-expanded graph from it. At search time, the query graphs are constructed from the transfer patterns computed on the original graph. We generate random queries X@t → Y in the following manner: The departure and destination locations X and Y are drawn from the set of locations of the stations S, taking into account the number of departing connections n s at each station s ∈ S: The probability of selecting s is p s = √ n s / s ∈S √ n s . To avoid trivial connections, the two locations must be more than 2 000 meters away from each other. The departure time t is drawn from an interval of 24 hours starting at 4:00 am. To account for varying traffic density during the day, departure times during the rush hours are selected twice as often.

The random queries are answered by transfer pattern routing. The resulting paths are compared to reference routes. In order to compute the latter, the delayed time-expanded graph is extended with two nodes x, y representing the source and target location X and Y . For each station s ∈ N (X), x is connected to the first transfer node of s after time t + walk(X, s) and every arrival node at s ∈ N (Y ) is connected to y by an arc of costs walk(s , Y ). On this extended graph, a multi-criteria Dijkstra is used to determine the optimal paths.

In this setting, we evaluate the robustness in each scenario. For each response to a query, the paths found by transfer pattern routing are classified independently as follows: If a path of equal costs is among the reference paths, the response is optimal. For every Dijkstra-generated path which has no correspondent of equal costs, the most similar path in terms of penalty is selected. If there is a path with the same penalty, the duration difference is inspected. If the path found by transfer pattern routing is less than 5% of the total travel time and less than five minutes slower than the reference path, it is almost optimal a. If it is not classified as almost optimal a but less than 10% and less than ten minutes late, it is almost optimal b. Otherwise, the path is classified as bad.

Results Tables 2a and2b show the results of our experiments with 50 000 random queries with at least one feasible route found by the reference algorithm. For each delay scenario, the found paths were classified (about 82 000 paths in Toronto, 67 000 in New York City). The classification results show the influence of the scenarios: With increasing average delay, the share of optimal paths decreases. Although we are using the important station heuristic, almost all paths found by transfer pattern routing are optimal for the baseline Null. The few suboptimal paths are dominated by paths with more than two transfers without an important station, which cannot be found because of the restriction of local profile queries to three trips (see Section 3.2).

Among the results for the different scenarios there are just very few suboptimal paths. Even for the worst scenario the share of suboptimal paths is below 2.6% for Toronto, and below 1% for New York City. Beside this, most of the suboptimal paths are quite close to the optimum: The major part is classified as almost optimal a and the share of bad paths is never larger than 0.8%. For suboptimal paths, Tables 3a, 3b and Figures 2a,2b show the distribution of the relative differences to the corresponding optimal path. The influence of the scenarios' average delay reflects similarly in the distributions as for the classification results above. We observe that the median of the distributions is below 0.05 for both data sets in all scenarios. There are a few outliers, some of which are much worse than the optimal path (at most factor 4.95 for Toronto, factor 0.37 for New York City). Manual inspection of these critical outliers showed that they typically stem from queries between remote locations with bad connectivity. For example, the worst route in Toronto misses the last connection before midnight and has to wait for six hours. Note that only paths which are dominated by a reference path of equal number of transfers are reported here. Therefore, the number of paths in the Tables 3a, 3b is slightly smaller than the number of suboptimal paths in the classification tables.

AT M O S ' 1 3

In summary, the results indicate that transfer patterns are very robust to delay. Even in the worst scenario the share of suboptimal responses is very small, and most of these paths are almost optimal. Furthermore, the results show that the limit of three trips for local transfer patterns leads only to very few suboptimal results. Number of queries which are still answered optimally after iteratively adding systematic delay of 30 minutes to the optimal paths and repeating the query. Results for 5 000 queries with a limit of nine iterations on New York City.

Controlled Delay

In our opinion, the global scenarios discussed beforehand model real transportation networks quite sufficiently. On the other hand, delaying random trips in a memoryless fashion does not clearly show why transfer patterns are robust. It is still possible that the optimal paths remain rather unchanged, for example when the delay is so small that a trip reaches the same connections as without delay. To examine the robustness of transfer patterns in more detail, we conduct another series of experiments and directly delay the optimal routes.

In a first setup, random queries are issued on the New York City data set. For every resulting optimal route one of its conducting trips is delayed with 30 minutes, such that the delay definitely affects the optimal routes. Then the query is repeated on the delayed data and the response is classified as in Section 5.1. Repeating this experiment for more than 32 000 queries showed that only 1.34% of the queries become suboptimal if we influence the connections of the optimal routes in this way.

In order to get a better understanding of the robustness, we extend this experiment to multiple rounds: A random query is drawn as before. In each round, the response of transfer pattern routing is compared to the reference response. Then, one trip of each optimal route is delayed by 30 minutes. This is repeated until the response becomes suboptimal, at most for nine times. Figure 3 summarizes the number of executed iterations until the response became suboptimal. The majority of queries was still optimal after nine successive delays. Also in this setting the transfer patterns computed on the original network proved to be very robust.

Dependencies of the Robustness

Consider an arbitrary query X@t → Y . Let r 0 = {p 0 1 , p 0 2 , . . .} denote the set of paths found by transfer pattern routing in the baseline null. In the delayed scenario, the response is r = {p 1 , p 2 , . . .} and r * = {p * 1 , p * 2 , . . .} is the (guaranteed optimal) response of the reference algorithm. The transfer patterns are robust if r = r * in terms of path costs. An alternative AT M O S ' 1 3 path is a path p i ∈ r with costs equal to the costs of a reference path p * i ∈ r * and p i = p 0 i in terms of the transfer stations. How come such alternative paths are contained in the query graph? This is because in the precomputation, during the course of time paths of different transfer pattern are optimal for a station pair A, B. Besides, the query graph is a digraph with one node (-pair) for each station and can therefore contain further alternatives. For illustration, consider the digraph build from the patterns A → B → C → D and A → C → B → D. In addition to the patterns it is created from, it also contains the paths ABD and ACD. This effect increases with growing number of patterns between a station pair, and thus also by building the query graph from patterns to and from important stations.

The number of alternatives depends also on the number of neighboring stations of X and Y , as the query graph is built from all patterns between these stations. The observations for both data sets in Section 5.1 differ. For Toronto, there are more suboptimal responses and they deviate more from the optimum. Here, the average number of neighbor stations |S| -1 • s∈S |N (s)| is 50, whereas for New York City it is 92. To investigate this further, we select the ten percent of stations with the most and with the fewest neighbor stations of New York City and answer queries as in Section 5.1, but with locations X, Y drawn from one of the groups. The results clearly express a difference. Queries in the group with 152 to 306 neighbor stations are less often answered suboptimally than in the group with 1 to 36 neighbors (for Mix Chaos: 0,61% vs. 3.11%). As the maximum walking distance influences the size of the neighborhood, increasing this parameter will probably further improve the robustness.

In summary, transfer patterns allow for alternative routes. When the optimal path is iteratively delayed, at some point the optimum switches to a path with another pattern. Figure 4 shows some examples how the transfer pattern of the optimal path evolves, if the trips along the optimal path are subsequently delayed.

Improving the Robustness

The routing algorithm yields suboptimal responses whenever the optimal path is not contained in the query graph or the overlaid transfer patterns respectively. We studied reasons why the optimal paths in case of delay cannot be found in the overlaid patterns. When there is no delay, these paths are typically just slightly dominated by other paths.

The arrival-chain algorithm described in Section 3.2 selects a dominant subset among the paths between two stations. In a first approach to improve the robustness of the transfer patterns, we relaxed the domination relation for travel times in the arrival-chain algorithm: A cost-tuple a dominates another tuple b, if its travel time increased by 5%/10%/20% or at least 2/2/5 minutes is less than that of b. Other than expected, the resulting patterns are only slightly more robust, whereas even in the first setting the number of patterns has doubled. This would slow down the search time. Provided that the suboptimal responses are only a few, this minor improvement does not seem worth the additional effort.

To motivate our next approach, consider an optimal path with the transfer pattern U → V → W → X and imagine the trip serving V → W is delayed. We observed that some of the not-found optimal paths take redirections over some station R, but otherwise use parts of the original pattern, for example UVRX or URWX. As described in Section 5.3, overlaying transfer patterns generates a graph which contains additional paths. We tried to exploit this by enhancing the query graph with additional patterns. In the example, we would add transfer patterns for the station pairs U,W and V,X hoping that this adds subpaths VRX or URW to the query graph. While this works in theory, in practice the trigger of this extension remains unclear. Extending the query graph for every delayed arc is impractical, as this Figure 4 Evolution of the pattern of an optimal path. From the response to a fixed query, the path with the highest number of transfers is selected and one of its connections is iteratively delayed with two minutes. The plots show how the travel time increases and the pattern is occasionally changed for four exemplary queries.

would blow up its size and the construction time. Triggering the extension only for arcs with delay above a fixed threshold does not reflect the fact that occurrence and severity of suboptimal paths are only weakly related to the amount of delay. Another idea is to repeat the search on the query graph whenever the first search yields a path over a delayed connection. Alternative routes for this connection would be added to the graph. However, the suboptimal paths often do not go via delayed connections, so this is unreliable, too.

Conclusion & Future Work

We described how delays can be handled by transfer pattern routing without repeating its expensive precomputation. We showed how the data structure for efficient direct connection queries can be updated fast, allowing to adapt to updates in real-time. It transpired that our approach sustains the high quality of results even under extreme delay scenarios. Just a few paths are suboptimal, most of which do not deviate too much from the optimum. For example, when delaying every trip on the New York City data set with 5-50 minutes in average and answering 50 000 queries, only 450 of the resulting paths are not optimal. More than 75% of these are less than 10% and less than ten minutes off the optimum. Furthermore, we provided insight why the transfer patterns contain alternative routes and we analyzed on which factors the robustness depends. The inherent disadvantage of the scenarios is that they model delay independently. On the one hand, in realistic public transportation delay is often systemic. For example, a traffic jam will delay a series of trips. On the other hand, there are mechanisms to compensate AT M O S ' 1 3 delay: a bus can drive faster to catch up with its schedule. Another example are traffic agencies in the EU, which are bound by law to reimburse passengers for excessive delay. Because of this, the agencies employ decision algorithms which can make connections wait for delayed trains. As delay occurs not independently as assumed in this paper, the acquisition of realistic delay data and repetition of the experiments on top of that is a topic for future research.

Although the quality of responses are almost always optimal, there are some critically suboptimal paths. Future work should focus on eliminating these or making them less severe, for example by adding alternative transfer patterns for frequently delayed trips. We proposed three improvement approaches and discussed why they fail. If a detection mechanism for such bad responses can be found, a fall-back algorithm [START_REF] Berger | Fully Dynamic Speed-Up Techniques for Multi-criteria Shortest Path Searches in Time-Dependent Networks[END_REF][START_REF] Delling | Round-Based Public Transit Routing[END_REF][START_REF] Dibbelt | Intriguingly Simple and Fast Transit Routing[END_REF] could be used to find optimal responses on the updated transportation network. In order to be practicable, such a detection must not increase the running-time for the majority of queries, which are already answered optimally. This seems to be a hard problem.

Figure 1

 1 Figure 1 Probability density functions for exponential distributions with mean Eδ.

Lemma 1 .

 1 Let L denote the set of lines and let trips(l) denote the trips of l ∈ L. Further, C ⊆ L is the set of lines which share the same station sequence as l. Then updating a trip T ∈ trips(l) in the direct connection data structure has running time O (log |L| • |stops(T )| + |C| • (|stops(T )| + log |trips(l)|)) Proof. (1) Finding the trip in the line can be done in O(log |trips(l)|), because the trips of l are sorted by time (Section 3.2). (2) Updating the trip's stop times is in O(|stops(T )|). (3) Checking the FIFO-property takes O(|stops(T )|). In case it is violated, candidate lines C with the same same sequence of stations have to be found in L. This takes time O(log |L|•|stops(T )|) using the mapping described above. Steps (1) and (3) have to be repeated for every c ∈ C in the worst case.

Figure 2

 2 Figure 2Suboptimal paths: Boxplot for relative time of travel compared to the optimal path with equal number of transfers. The red line marks the median, the box contains the interval between the upper and lower quartile of the data. The whiskers have a length of 1.5 times the distance between the quartiles. The crosses mark outliers. Outliers above 0.6 are not shown.

Figure 3

 3 Figure 3Number of queries which are still answered optimally after iteratively adding systematic delay of 30 minutes to the optimal paths and repeating the query. Results for 5 000 queries with a limit of nine iterations on New York City.

  A transit network is described by a set of timetables. It comprises information about stations S (e.g. train stations or bus stops) and trips of transport vehicles. A trip T serves a sequence of stations stops(T ) = (s 1 , s 2 , . . . , s n ), s i ∈ S at arrival and departure

	times (t arr 1 , t dep 1 ), (t arr 2 , t dep 2 ), . . . (t arr n , t dep n

  and store trips grouped by lines like this:

	line17	s14	s9	s56	...
	trip 1	8:05 9:00 9:15 10:00 10:05 ...
	trip 2	8:35 9:30 9:45 10:30 10:35 ...
	...	...	...	...	...

For each station, we compute a list of incident lines with the respective position of the station along the line. For instance: s 14 : {(line 17 , 0), (line 26 , 8), . . .}, s 56 : {(line 12 , 6), (line 17 , 2), . . .} and so on. To determine the next direct connection between two stations, their incidence-lists are intersected and the next trip of a line connecting both stations is determined. With the query graph consisting of only several hundred arcs and the direct connection queries taking 2-10µs each, the total search time is only a few milliseconds.

Table 1

 1 How many trips are delayed by how much in our six delay scenarios.

	Scenario	Average delay Eδ 5 min 15 min 50 min
	Low	25%	-	-
	Medium	-	25%	-
	High	-	-	25%
	Mix Low	10%	3%	1%
	Mix Normal	20%	10%	5%
	Mix Chaos	40%	40%	20%

Table 2

 2 Classification of paths under different scenarios. Abbreviates almost optimal σ as σ.

		(a) Toronto				(b) New York City
		optimal	a	b	bad		optimal	a	b	bad
	Null	99.97% 0.02% 0.01% 0.00%	Null	99.99% 0.01% 0.00% 0.00%
	Low	99.71% 0.15% 0.04% 0.10%	Low	99.87% 0.01% 0.00% 0.04%
	Medium	99.55% 0.22% 0.06% 0.17%	Medium	99.68% 0.19% 0.03% 0.10%
	High	99.42% 0.29% 0.08% 0.21%	High	99.72% 0.17% 0.02% 0.09%
	Mix Low	99.81% 0.10% 0.03% 0.06%	Mix Low	99.93% 0.05% 0.00% 0.02%
	Mix Normal 99.52% 0.26% 0.06% 0.16%	Mix Normal 99.89% 0.07% 0.01% 0.03%
	Mix Chaos 97.46% 1.40% 0.34% 0.80%	Mix Chaos 99.19% 0.57% 0.07% 0.17%

Table 3

 3 Suboptimal paths: Relative offset to optimal travel time. Summary statistics of distributions for different delay scenarios. For example, in Toronto under the scenario Low, 25% of the suboptimal paths are at most 0.02 times slower than the optimal path.

			(a) Toronto					(b) New York City
		N Q0.25 Q0.5 Q0.75 max		N Q0.25 Q0.5 Q0.75 max
	Low	276	0.02 0.04		0.08 4.95	Low	46	0.00 0.03		0.05 0.20
	Medium	441	0.01 0.04		0.08 3.96	Medium	149	0.01 0.03		0.06 0.19
	High	552	0.01 0.04		0.08 3.17	High	144	0.01 0.04		0.06 0.23
	Mix Low	184	0.01 0.04		0.08 0.74	Mix Low	24	0.00 0.01		0.02 0.29
	Mix Normal 451	0.02 0.04		0.10 0.69	Mix Normal 41	0.02 0.03		0.06 0.21
	Mix Chaos 2300	0.02 0.05		0.09 4.42	Mix Chaos 332	0.02 0.05		0.09 0.40
								Low
	Low							Medium
	Medium							High
	High
	Mix Low							Mix Low
	Mix Normal							Mix Normal
	Mix Chaos							Mix Chaos
	0.0	0.1	0.2	0.3	0.4	0.5	0.6	0.0	0.1	0.2	0.3	0.4	0.5	0.6
		Relative offset to optimal travel time			Relative offset to optimal travel time
		(a) Toronto					(b) New York City

Note that our results are independent of the used graph model.AT M O S ' 1 3

* Partially supported by a Google Focused Research Award.


Ralf Borndörfer
email: borndoerfer@zib.de

Heide Hoppmann
email: hoppmann@zib.de

Marika Karbstein
email: karbstein@zib.de

A Configuration Model for the Line Planning Problem *

Keywords: 1998 ACM Subject Classification G.2.3 Applications in Discrete Mathematics Keywords and phrases combinatorial optimization, polyhedral combinatorics, line planning Digital Object Identifier 10.4230/OASIcs.ATMOS.2013.68

We propose a novel extended formulation for the line planning problem in public transport. It is based on a new concept of frequency configurations that account for all possible options to provide a required transportation capacity on an infrastructure edge. We show that this model yields a strong LP relaxation. It implies, in particular, general classes of facet defining inequalities for the standard model.

Introduction

Line planning is an important strategic planning problem in public transport. The task is to find a set of lines and frequencies such that a given demand can be transported. There are usually two main objectives: minimizing the travel times of the passengers and minimizing the line operating costs.

Since the late nineteen-nineties, the line planning literature has developed a variety of integer programming approaches that capture different aspects, see Schöbel [START_REF] Schöbel | Line planning in public transportation: models and methods[END_REF] for an overview. Bussieck, Kreuzer, and Zimmermann [START_REF] Michael | Optimal lines for railway systems[END_REF] (see also the thesis of Bussieck [START_REF] Bussieck | Optimal Lines in Public Rail Transport[END_REF]) propose an integer programming model to maximize the number of direct travelers. Operating costs are discussed in the articles of Claessens, van Dijk, and Zwaneveld [START_REF] Claessens | Cost optimal allocation of rail passanger lines[END_REF] and Goossens, van Hoesel, and Kroon [START_REF] Goossens | On solving multi-type line planning problems[END_REF][START_REF] Goossens | A branch-and-cut approach for solving railway line-planning problems[END_REF]. Schöbel and Scholl [START_REF] Schöbel | Line planning with minimal traveling time[END_REF] and Borndörfer and Karbstein [START_REF] Borndörfer | A direct connection approach to integrated line planning and passenger routing[END_REF] focus on the number of transfers and the number of direct travelers, respectively, and further integrate line planning and passenger routing in their models. Borndörfer, Grötschel, and Pfetsch [START_REF] Borndörfer | A column-generation approach to line planning in public transport[END_REF] also propose an integrated line planning and passenger routing model that allows to generate lines dynamically.

All these models employ some type of capacity or frequency demand constraints in order to cover a given demand. In this paper we propose a concept to strengthen such constraints by means of a novel extended formulation. The idea is to enumerate the set of possible configurations of line frequencies for each capacity constraint. We show that such an extended formulation implies general facet defining inequalities for the standard model. We remark that configuration models have also been used successfully in railway vehicle rotation planning [START_REF] Borndörfer | A Hypergraph Model for Railway Vehicle Rotation Planning[END_REF] and railway track allocation applications [START_REF] Borndörfer | Models for railway track allocation[END_REF].

Problem Description

We consider the following basic line planning problem. We have an undirected graph G = (V, E) representing the transportation network, and a set L = {l 1 , . . . , l n }, n ∈ N, of lines, where every line l i is a path in G. Denote by L(e) := {l ∈ L : e ∈ l} the set of lines on edge e ∈ E. Furthermore, we are given an ordered set of frequencies (

F = {f 1 , . . . , f k } ⊆ N, such that 0 < f 1 < . . . < f k , k ∈ N,
) 1
We define the cost of a line plan ( L, f ) as c( L, f ) = l∈ L c l, f (l) . The line planning problem is to find a feasible line plan of minimal cost.

Standard Model

The common way to formulate the line planning problem uses binary variables x l,f indicating whether line l ∈ L is operated at frequency f ∈ F, cf. the references listed in the introduction.

In our case, this results in the following standard model:

(SLP) min l∈L f ∈F c l,f x l,f s.t. l∈L(e) f ∈F f • x l,f ≥ F (e) ∀e ∈ E (2) f ∈F x l,f ≤ 1 ∀l ∈ L (3) x l,f ∈ {0, 1} ∀l ∈ L, ∀f ∈ F. (4)
Model (SLP) minimizes the cost of a line plan. The frequency demand constraints (2) ensure that the frequency demand is covered. The assignment constraints (3) ensure that every line operates at only one frequency. Hence, the solutions of (SLP) correspond to the feasible line plans.

Extended or Configuration Model

In the following, we give an extended formulation for (SLP) in order to tighten the LPrelaxation. The formulation is based on the observation that the frequency demand for an edge e ∈ E can also be expressed by specifying the numbers q f of lines that are operated at frequency f , f ∈ F, on edge e. We explain the idea using the example in Figure 1. The transportation network consists of two edges and three lines. Each line can be operated at frequency 2 or 8. The frequency demand on edge {u, v} is 9. To cover this demand using at most three lines we need at least two lines with frequency 8 or one line with frequency 2 and one line with frequency 8. We call these feasible frequency combinations configurations. In this case the set of all possible configurations is Q({u, v}) = {(0, 2), (0, 3), (1, 1), (1, 2), (2, 1)}, where the first coordinate gives the number of lines with frequency 2 and the second

AT M O S ' 1 3

coordinate gives the number of lines with frequency 8. The set of minimal configurations is Q({u, v}) = {(0, 2), (1, 1)}, i.e., any line plan that matches one configuration covers the frequency demand of the edge {u, v}. Similarly, the minimal configurations for edge {v, w} are Q({v, w}) = {(0, 1), (1, 0)}. Any line plan that matches one configuration for each edge is a feasible line plan. A formal description is as follows.

Definition 1. For e ∈ E denote by Q(e) := q = (q f1 , . . . , q f k ) ∈ N k 0 :

f ∈F q f ≤ |L(e)|, f ∈F f • q f ≥ F (e)
the set of (feasible) (frequency) configurations of e and by Q(e) := q ∈ Q(e) : (q f1 , . . . , q fi -1, . . . , q f k ) / ∈ Q(e) ∀i = 1, . . . , k the set of minimal configurations of e.

Let q = q(e) e∈E be some vector of minimal configurations, i.e., q(e) ∈ Q(e) for all e ∈ E, and ( L, f ) a line plan. If ( L, f ) satisfies the inequality |{l ∈ L(e) : f (l) = f }| ≥ q(e) f for all e ∈ E, f ∈ F, then ( L, f ) is feasible. Conversely, if ( L, f ) is a feasible line plan, then

q f = |l ∈ L(e) : f (l) = f |, f ∈ F
, is a feasible frequency configuration for each edge e. In other words, satisfying the frequency demand is equivalent to choosing a feasible configuration for each edge. We extend (SLP) using binary variables y e,q that indicate for each edge e ∈ E which configuration q ∈ Q is chosen. This results in the following extended formulation:

(QLP) min l∈L f ∈F c l,f x l,f s.t. l∈L(e) x l,f ≥ q∈Q(e) q f • y e,q ∀e ∈ E, ∀f ∈ F (5)
q∈Q(e)

y e,q = 1 ∀e ∈ E (6) f ∈F x l,f ≤ 1 ∀l ∈ L (7) x l,f ∈ {0, 1} ∀l ∈ L, ∀f ∈ F (8) y e,q ∈ {0, 1} ∀e ∈ E, ∀q ∈ Q(e). (9)
The (extended) configuration model (QLP) also minimizes the cost of a line plan. The configuration assignment constraints [START_REF] Bussieck | Line optimization[END_REF] ensure that exactly one configuration for each edge is chosen while the coupling constraints (5) guarantee that sufficient numbers of lines are operated at the frequencies of the chosen configurations.

Example 2. Consider the line planning problem in Figure 1. We define the costs as c l1,f = c l2,f = 2 • f and c l3,f = f . The standard model for this example reads as follows: The configuration model for this example is:

(SLP) min 4x l1,2 +16x l1,8 +4x l2,2 +16x l2,8 +2x l3,2 +8x l3,8 s.t. 2x l1,2 +8x l1,8 +2x l2,2 +8x l2,8 +2x l3,2 +8x l3,8 ≥ 9 2x l1,2 +8x l1,8 +2x l2,2 +8x l2,8 ≥ 1 x l1,2 +x l1,8 ≤ 1 +x l2,2 +x l2,8 ≤ 1 +x l3,2 +x l3,8 ≤ 1 x li,f ∈ {0, 1}. v u w l 3 l 2 l 1 F = {2, 8} e e1 = {u, v} e2 = {v, w} F (e) 9 1 L(e) {l1, l2, l3} {l1, l2} Q(e) {(0, 2), (1, 1)} {(0, 1), (1, 0)}
(QLP) min 4x l1,2 +16x l1,8 +4x l2,2 +16x l2,8 +2x l3,2 +8x l3,8 s.t. x l1,2 +x l2,2 +x l3,2 -ye 1 ,q2 ≥ 0 +x l1,8 +x l2,8 +x l3,8 -2ye 1 ,q1 -ye 1 ,q2 ≥ 0 x l1,2 +x l2,2 -ye 2 ,q2 ≥ 0 +x l1,8 +x l2,8 -ye 2 ,q1 ≥ 0 x l1,2 +x l1,8 ≤ 1 +x l2,2 +x l2,8 ≤ 1 +x l3,2 +x l3,8 ≤ 1 +ye 1 ,q1 +ye 1 ,q2 = 1 +ye 2 ,q1 +ye 2 ,q2 = 1 x li,f ∈ {0, 1} ye,q ∈ {0, 1}.

Comparison of the Models

In this section we compare the standard and the extended configuration model for the line planning problem. We need some further notation. For an integer program (IP) = min{c T x : Proof. Let (x, ȳ) ∈ P LP (QLP). Obviously, x satisfies (3) and (4). We further get

Ax ≥ b, x ∈ Z n }
l∈L(e) f ∈F f • xl,f (5) ≥ f ∈F f • q∈Q(e) q f • ȳe,q = q∈Q(e)
ȳe,q

(6) = 1 • f ∈F f • q f ≥F (e)∀q∈Q(e) ≥ F (e).
Hence, x satisfies (2) as well and is contained in P LP (SLP).

AT M O S ' 1 3

The converse, i.e., P LP (SLP) ⊆ P LP (QLP) | x , does not hold in general, indeed, the ratio of the optimal objectives of the two LP relaxations can be arbitrarily large.

QLP LP : min M • x l,M SLP LP : min M • x l,M s.t. x l,M -y q ≥ 0 s.t. M • x l,M ≥ 6 y q = 1 y q , x l,M ≥ 0 x l,M ≥ 0
Obviously, x l,M = 1 is the only and hence optimal solution to QLP LP with objective value M and x l,M = 6 M is an optimal solution to SLP LP with objective value 6. In the following subsections we show that the LP relaxation of the configuration model implies general classes of facet defining inequalities for the line planning polytope P IP (SLP) that are discussed in the literature.

Band Inequalities

In this section we analyze band inequalities, which were introduced by Stoer and Dahl [START_REF] Stoer | A polyhedral approach to multicommodity survivable network design[END_REF] and are closely related to the knapsack cover inequalities, see Wolsey [START_REF] Wolsey | Valid inequalities for 0-1 knapsacks and MIPs with generalized upper bound constraints[END_REF]. We call the band f B maximal if f B is valid and there is no valid band f B with f B (l) ≤ f B (l) for every line l ∈ L(e) and f B (l) < f B (l) for at least one line l ∈ L(e). We call the band f B symmetric if f B (l) = f for all l ∈ L(e) and for some f ∈ F.

Applying the results of Stoer and Dahl [START_REF] Stoer | A polyhedral approach to multicommodity survivable network design[END_REF] yields

Proposition 7. Let f B be a valid band of e ∈ E, then l∈L(e) f ∈F f >f B (l) x l,f ≥ 1 ( 10
)
is a valid inequality for P IP (SLP).

The simplest example is the case f B (l) ≡ 0, which states that one must operate at least one line on every edge, i.e., one has to cover the demand.

Proposition 8. The set cover inequality

l∈L(e) f ∈F x l,f ≥ 1 ( 11
)
is valid for P IP (SLP) for all e ∈ E.

The set cover inequalities [START_REF] Goossens | On solving multi-type line planning problems[END_REF] do not hold in general for the LP relaxation of the standard model, compare with Example 5. Note that they are symmetric band inequalities.

Maximal band inequalities often define facets of the single edge relaxation of the line planning polytope [START_REF] Karbstein | Line Planning and Connectivity[END_REF]. The symmetric ones are implied by the configuration model. Theorem 9. The LP relaxation of the configuration model implies all band inequalities [START_REF] Dash | MIR closures of polyhedral sets[END_REF] that are induced by a valid symmetric band.

Proof. Assume f B is a valid symmetric band of some edge e with f B (l) = f for all l ∈ L(e) and for some f ∈ F, f < f k . Thus l∈L(e) f B (l) = |L(e)|• f < F (e). Hence, in every minimal configuration q ∈ Q(e) there is a frequency f > f such that q f ≥ 1. Starting from (5), we get:

l∈L(e) x l,f ≥ q∈Q(e) q f • y q ∀f ∈ F ⇒ f ∈F f > f l∈L(e) x l,f ≥ f ∈F f > f q∈Q(e) q f • y q ⇔ l∈L(e) f ∈F f > f x l,f ≥ q∈Q(e) y q • f ∈F f > f q f ≥1 ≥ q∈Q(e)
y q = 1.

The same does not hold for the standard model as the following example shows.

Example 10 (Example 2 continued).

A valid symmetric band for edge e 1 in Figure 1 is given by f B (l) = 2 for all l ∈ L(e 1 ). The corresponding band inequality

x l1,8 + x l2,8 + x l3,8 ≥ 1 ( 12
)
is violated by x ∈ P LP (SLP), where xl2,8 = 7 8 , xl3,2 = 1, and xl,f = 0 otherwise. One can show that ( 12) is facet-defining for P IP (SLP) in this example.

MIR Inequalities

We study in this section the mixed integer rounding (MIR) inequalities and their connection to the configuration model. MIR inequalities can be derived from the basic MIR inequality as defined by Wolsey [START_REF] Wolsey | Integer Programming[END_REF], see also Raack [START_REF] Raack | Capacitated Network Design -Multi-Commodity Flow Formulations, Cutting Planes, and Demand Uncertainty[END_REF].

Lemma 11 (Wolsey [22]).

Let Q I := {(x, y) ∈ Z × R : x + y ≥ β, y ≥ 0}. The basic MIR inequality rx + y ≥ r β with r := r(β) = β -β is valid for Q I and defines a facet of conv(Q I ) if r > 0.
We use mixed integer rounding to strengthen the demand inequalities [START_REF] Borndörfer | A column-generation approach to line planning in public transport[END_REF].

AT M O S ' 1 3

Proposition 12. Let λ ∈ R + , e ∈ E, and define r = λF (e) -λF (e) and r f = λf -λf . The MIR inequality l∈L(e) f ∈F (r λf + min(r f , r))x l,f ≥ r λF (e) [START_REF] Karbstein | Line Planning and Connectivity[END_REF] induced by the demand inequality (2) scaled by λ is valid for (SLP).

Proof. Scaling inequality (2) by λ > 0 yields

λ • F (e) ≤ λ • l∈L(e) f ∈F f • x l,f = l∈L(e) f ∈F r f <r λ • f • x l,f + l∈L(e) f ∈F r f ≥r λ • f • x l,f ≤ l∈L(e) f ∈F r f <r ( λ • f + r f ) • x l,f + l∈L(e) f ∈F r f ≥r ( λ • f + 1) • x l,f = l∈L(e) f ∈F r f <r r f • x l,f ≥0 + l∈L(e) f ∈F λ • f • x l,f + l∈L(e) f ∈F r f ≥r x l,f . ∈Z Applying Lemma 11 yields r • λ • F (e) ≤ l∈L(e) f ∈F r f <r r f • x l,f + r • l∈L(e) f ∈F λ • f • x l,f + l∈L(e) f ∈F r f ≥r x l,f = l∈L(e) f ∈F (r • λf + min(r f , r)) • x l,f .
Notice that λ ∈ R + only produces a non-trivial MIR inequality (13) if r = λF (e) -λF (e) = 0. Dash, Günlük and Lodi [START_REF] Dash | MIR closures of polyhedral sets[END_REF] analyze for which λ the MIR inequality ( 13) is non-redundant.

Proposition 13 (Dash,Günlük and Lodi [10]). Each non-redundant MIR inequality [START_REF] Karbstein | Line Planning and Connectivity[END_REF] is defined by λ ∈ (0, 1), where λ is a rational number with denominator equal to some f ∈ F.

Again, we can show that these inequalities are implied by the LP relaxation of the configuration model. The proof is based on the following lemma, a configuration version of Proposition 12. Lemma 14. For e ∈ E, q ∈ Q(e), and λ ∈ (0, 1), it holds

f ∈F (r • λf + min(r f , r))q f ≥ r • λ • F (e) ,
where r = λF (e) -λF (e) and r f = λf -λf .

Proof. q ∈ Q(e) implies f ∈F f • q f ≥ F (e) and hence we get for λ ∈ (0, 1)

λ • F (e) ≤ λ • f ∈F f • q f = f ∈F r f <r λ • f • q f + f ∈F r f ≥r λ • f • q f ≤ f ∈F r f <r ( λ • f + r f ) • q f + f ∈F r f ≥r ( λ • f + 1) • q f = f ∈F r f <r r f • q f ≥0 + f ∈F λ • f • q f + f ∈F r f ≥r q f . ∈Z Applying Lemma 11 yields r • λ • F (e) ≤ f ∈F r f <r r f • q f + r • f ∈F λ • f • q f + f ∈F r f ≥r q f = f ∈F (r • λf + min(r f , r)) • q f . Theorem 15. Let λ ∈ (0, 1), e ∈ E, r = λF (e) -λF (e) and r f = λf -λf . Then the MIR inequality l∈L(e) f ∈F (r λf + min(r f , r))x l,f ≥ r λF (e)
is implied by the LP relaxation of the configuration model, i.e., the MIR inequalities (13) are valid for P LP (QLP) | x .

Proof. Let (x, y) ∈ P LP (QLP). Then by [START_REF] Borndörfer | Models for railway track allocation[END_REF] l∈L(e)

x l,f ≥ q∈Q(e) q f • y q ∀f ∈ F.

Scaling this inequality by λ r

f := r • λf + min(r f , r) yields l∈L(e) λ r f • x l,f ≥ q∈Q(e) λ r f • q f • y q ∀f ∈ F ⇒ f ∈F l∈L(e) λ r f • x l,f ≥ f ∈F q∈Q(e) λ r f • q f • y q ⇔ l∈L(e) f ∈F λ r f • x l,f ≥ q∈Q(e) f ∈F λ r f • q f • y q ( * ) ≥ q∈Q(e) r • λ • F (e) • y q = r • λ • F (e) • q∈Q(e) y q (6) = r • λ • F (e) .
( * ) apply Lemma 14 here.

AT M O S ' 1 3

Table 1 Statistics on the line planning instances. The columns list the instance name, the number of edges of the preprocessed transportation network, the number of lines, the number of variables for lines and frequencies, and the number of configuration variables in the configuration model and in the mixed model. 14) is even facet-defining for P IP (SLP) in this example.

(SLP)/(SLP + ) (SLP Q ) (QLP

Computational Results

We have implemented the configuration approach to provide a computational evaluation of the strength of the extended formulation (QLP). We compare it with the standard model (SLP) and with two additional models (SLP + ) and (SLP Q ). Model (SLP + ) is obtained by adding the set cover, symmetric band, and MIR inequalities for all edges to the standard model (SLP). Model (SLP Q ) has been developed to cut down on the number of configuration variables, which can explode for large instances. This model is situated between (SLP + ) and (QLP) and constructed as follows. We order the edges with respect to an increasing number of minimal configurations and generate the configuration variables and the associated constraints iteratively as long as the number of generated configuration variables does not exceed 25% of the number of variables for lines and frequencies. For the remaining edges we use the set cover, symmetric band, and MIR inequalities.

Our test set consists of five transportation networks that we denote as China, Dutch, SiouxFalls, Chicago, and Potsdam. The instances SiouxFalls and Chicago use the graph and the demand of the street network with the same name from the Transportation Network Test Problems Library of Bar-Gera [START_REF]Transportation network test problems[END_REF]. Instances China, Dutch, and Potsdam correspond to public transportation networks. The Dutch network was introduced by Bussieck in the context of line planning [START_REF] Bussieck | Line optimization[END_REF]. The China instance is artificial; we constructed it as a showcase example, connecting the twenty biggest cities in China by the 2009 high speed train network. The Potsdam instances are real multi-modal public transportation networks for 1998 and 2009.

We constructed a line pool by generating for each pair of terminals all lines that satisfy a certain length restriction. To be more precise, the number of edges of a line between two terminals s and t must be less than or equal to k times the number of edges of the shortest path between s and t. For each network, we increased k in three steps to produce three instances with different line pool sizes. For Dutch and China instance number 3 contains all lines, i.e., all paths that are possible in the network. The Potsdam2010 instance arose within a project with the Verkehr in Potsdam GmbH (ViP) [18] to optimize the 2010 line plan [START_REF] Borndörfer | Optimierung des Linienplans 2010 in Potsdam[END_REF]. The line pool contains all possible lines that fulfill the ViP requirements.

For all instances the lines can be operated at frequencies 3, 6, 9, 18, 36, and 72. This corresponds to a cycle time of 60, 30, 20, 10, 5, and 2.5 minutes in a time horizon of 3 hours. We set the line cost to be proportional to the line length and the frequency plus a fixed cost term that is used to reduce the number of lines. The costs and the capacities of the lines depend on the mode of transportation (e.g., bus, tram). In the instances each edge is associated with exactly one mode, i.e., all lines on an edge have the same capacity, see Karbstein [START_REF] Karbstein | Line Planning and Connectivity[END_REF] for more details. Hence, we can express capacities in terms of frequency demands. Table 1 lists some statistics about the test instances. The second and third columns give the number of edges and lines in the transportation network. The remaining columns list the number of variables and constraints for the four models after preprocessing. The preprocessing eliminates for instance dominated constraints and dominated and infeasible frequency assignments. For example a frequency f is dominated for line l if f > max e∈l {F (e)}.

The instances were solved using the constraint integer programming framework SCIP version 3.0.1 [START_REF]SCIP -Solving Constraint Integer Programs[END_REF] with Cplex 12.5 as LP-solver. We set a time limit of 1 hour for all instances and used the default settings of SCIP, apart from the primal heuristic "shiftandpropagate" which we turned off. All computations were done on an Intel(R) Xeon(R) CPU E3-1290, 3.7 GHz computer (in 64 bit mode) with 13 MB cache, running Linux and 16 GB of memory. The results are shown in Table 2.

The computations show that the set cover, symmetric band, and MIR cuts indeed improve the standard model. The superiority of model (QLP) does not always show up, because its root LP cannot be solved within one hour for those instances where the number of configuration variables is more than 10 times higher than the number of line and frequency variables. For all other instances, the dual bounds after solving the root node for (SLP Q ) and (QLP) are better than those for (SLP + ). Model (SLP Q ) is performing best on nearly all instances. Except for Chicago it has a better dual bound after terminating the computations than models (SLP) and (SLP + ). Hence, model (SLP Q ) is a good compromise between improving the formulation with configuration variables and keeping the size of the formulation small.

  and costs c l,f for operating line l ∈ L at frequency f ∈ F. Finally, each edge e ∈ E in the network bears a positive frequency demand F (e) giving the number of line operations that are necessary to cover the demand on this edge.A line plan ( L, f ) consists of a subset L ⊆ L of lines and an assignment f : L → F of frequencies to these lines. A line plan is feasible if the frequencies of the lines satisfy the given frequency demand F (e) for each edge e ∈ E, i.e., if l∈ L(e) f (l) ≥ F (e) for all e ∈ E.

Figure 1

 1 Figure 1 An instance of the line planning problem. Left: Transportation network consisting of two edges and three lines. Right: The given set of frequencies, frequency demands, and the minimal frequency configurations.

Example 5 .

 5 Consider an instance of the line planning problem involving only one edge E = {e}, one line L(e) = {l}, a frequency demand F (e) = 6, and one frequency F = {M } such that M > 6 with cost function c l,M = M . The only minimal configuration for e is q = (1).

Definition 6 .

 6 Let e ∈ E. A band f B : L(e) → F ∪ {0} assigns to each line containing e a frequency or 0. We call f B a valid band of e if l∈L(e) f B (l) < F (e).

  The LP relaxation of P IP (QLP) | x is tighter than the LP relaxation of P IP (SLP), i.e., P LP (QLP) | x ⊆ P LP (SLP) .

we denote by P IP (IP) the polyhedron defined by the convex hull of all feasible solutions of (IP) and by P LP (IP) the set of feasible solutions of the LP relaxation of (IP), i.e., P IP (IP) = conv{x ∈ Z n : Ax ≥ b} and P LP (IP) = {x ∈ R n : Ax ≥ b}. For a polyhedron P = {(x, y) ∈ R n+m : Ax + By ≥ b} denote by P | x := {x ∈ R n : ∃y ∈ R m s.t. (x, y) ∈ P } the projection of P onto the space of x-variables.

Using this notation, we can state that solving (QLP) is equivalent to solving (SLP):

Lemma 3. (QLP) provides an extended formulation for (SLP), i.e., P IP (QLP) | x = P IP (SLP) .

For the LP relaxations, however, the following holds:

Theorem 4.

  Again, we can give an example where a MIR inequality is not valid for the LP relaxation of the standard model.

								)
	name	|E|	|L|	#vars	#cons	#vars	#cons	#vars	#cons
	China1	27	474	2 793	499 / 620	3 732	654	41 196	661
	China2	27	4 871	29 170	4 896 / 5 016	36 757	5 058	67 575	5 058
	China3	27	19 355	116 074	19 380 /19 500	145 736	19 542	154 479	19 542
	Dutch1	30	402	1 544	424 / 502	1 760	580	1 760	580
	Dutch2	30	2 679	11 779	2 701 / 2 779	11 997	2 859	11 997	2 859
	Dutch3	30	7 302	33 988	7 324 / 7 402	34 206	7 482	34 206	7 482
	SiouxFalls1	37	866	5 188	902 / 1 113	6 680	1 117	753 840	1 124
	SiouxFalls2	37	9 397	56 374	9 433 / 9 644	73 531	9 648	902 703	9 655
	SiouxFalls3	37	15 365	92 182	15 401 /15 612	117 711	15 616	938 511	15 623
	Potsdam1998b 351	1 907	10 765	1 998 / 2 679	13 795	3 969	38 637	4 114
	Potsdam1998c 351	4342	25 306	4 431 / 5 112	32 037	6 484	53 184	6 549
	Potsdam2010 517	3433	9 535	3 109 / 3 584	11 524	4 986	11 524	4 986
	Chicago	1 028	23 109	131 915	24 066 /28 297	165 083	30 229	2 503 163	30 285
	Example 16 (Example 2 continued). Let λ = 1 8 , then the MIR inequality for edge e 1
	x l1,2 + x l1,8 + x l2,2 + x l2,8 + x l3,2 + x l3,8 ≥ 2				(14)
	is violated by x ∈ P LP (SLP), where xl2,8 = 7 8 , xl3,2 = 1, and xl,f = 0 otherwise. It can be
	verified that (

Acknowledgment

We thank three referees for helpful comments and suggestions.

DFG Research Center Matheon "Mathematics for key technologies".

Table 2 Statistics on the computations for the models (SLP), (SLP + ), (SLP Q ), and (QLP). The columns list the instance name, model, computation time, number of branching nodes, the integrality gap, the primal bound, the dual bound, and the dual bound after solving the root node.