FAKULT ¨
AT II
MATHEMATIK UND
NATURWISSENSCHAFTEN
Institut f ¨ur Mathematik
THE SECOND CHV ´
ATAL CLOSURE
CAN YIELD
BETTER RAILWAY TIMETABLES
by
CHRISTIAN LIEBCHEN ELMAR SWARAT
No. 027/2008
The Second Chv´
atal Closure Can Yield
Better Railway Timetables∗
Christian Liebchen Elmar Swarat
July 31, 2008
Abstract
We investigate the polyhedral structure of the Periodic Event Scheduling Problem (PESP),
which is commonly used in periodic railway timetable optimization. This is the first investigation
of Chv´
atal closures and of the Chv´
atal rank of PESP instances.
In most detail, we first provide a PESP instance on only two events, whose Chv´
atal rank is
very large. Second, we identify an instance for which we prove that it is feasible over the first
Chv´
atal closure, and also feasible for another known prominent class of known valid inequalities,
which we reveal to live in much larger Chv´
atal closures. In contrast, this instance turns out to be
infeasible already over the second Chv´
atal closure. We obtain the latter result by introducing new
valid inequalities for the PESP, the multi-circuit cuts.
In the past, for other classes of valid inequalities for the PESP, it had been observed that these
do not have any effect in practical computations. In contrast, the new multi-circuit cuts that we
are introducing here, indeed show some effect in the computations that we perform on several
real-world instances – a positive effect, in most of the cases.
1 Introduction
It has been only recently that combinatorial optimization entered the practice of service design in
public transport. The 2005 timetable of Berlin Underground is the first optimized timetable that was
put into service [9]. It had been computed with integer programming techniques, namely profiting
from several different classes of valid inequalities. Today, also the Dutch railways are operating a
timetable that was designed with the help of techniques from combinatorial optimization and con-
straint programming [7]. Both projects build upon the Periodic Event Scheduling Problem (PESP).
The PESP, in its pure formulation of a feasibility problem, had been introduced by Serafini and
Ukovich [18] and it generalizes the vertex coloring problem. In particular, for the two most natural
optimization problems that are investigated on top of the PESP, MAXSNP-hardness has been estab-
lished [8, 9]. In practice, this results in the following typical behavior of MIP solvers on medium to
large sized instances. Known valid inequalities are able to close 60–90% of the initial gap between
the integer optimum value and the optimum value of the LP relaxation. Still, solving this tightened
IP risks to take several hours, if it is solvable at all.
There are of course much larger transportation networks in practice, which are beyond the com-
putational limits of the methods that were used so far. As a consequence, at present there are several
other research groups trying to tackle the periodic railway timetabling problem, and they are sharing
the PESP as their model of choice [2, 17, 19]. For instance, Villumsen put the polyhedral approach
that was suggested by Lindner [14] into practical computations for the commuter train network of
Copenhagen. Unfortunately, he had to make the observation that
∗Supported by the DFG Research Center MATHEON in Berlin.
1
“the chain cuts [14] have no effect on the solution” [19].
This is one motivation for us to have a closer look at the polyhedral structure of the feasible region
of PESP instances. We do so by following the methodology that has been suggested recently by
Fischetti and Lodi [6] for optimizing over the first Chv´
atal closure. Notice that one of the first
instances to which they applied their method was the “hard MIPLIB instance timtab1”, which is
in fact a PESP model [10].
As a motivation, we first generalize an infeasible PESP instance – which is due to Lindner [14] –
to a family of instances that are defined on wheel graphs. In Section 6 we will prove that these
instances are feasible over the first Chv´
atal closure. Still worse, even the change-cycle inequalities
that have been introduced by Nachtigall [15], of which in Section 4 we prove that, in general, they lie
in much larger Chv´
atal closures, are not suited to certify infeasibility. Nevertheless, the techniques
of Fischetti and Lodi suggested that these particular instances might be infeasible already over the
second Chv´
atal closure. Indeed, by expoiting problem-specific insight, in the second Chv´
atal closure
we identify general new valid inequalities for the PESP (Section 5) by which we prove that these
particular instances are infeasible. We call these new inequalities the multi-circuit cuts.
In Section 7 we add multi-circuit cuts to the IP formulations of several timetabling instances that
we took from practice. Although we have to admit that the results are not fully striking, on many
instances we observe a perceptible speed-up in the solution time. In turn, on more complex instances,
for which up to now no optimal solution has been found, our new cuts from the second Chv´
atal
closure might indeed yield better railway timetables.
2 An IP for PESP
Initially, the Periodic Event Scheduling Problem (PESP, [18]) has been stated as a pure feasibility
problem. We are given a directed graph D= (V, A), which may feature (anti-) parallel arcs. For each
arc a, there are defined some lower bound ℓaand some upper bound ua. The PESP then asks whether
for the given fixed period time T, the instance admits a (periodically) feasible node potential π∈
[0, T)V, i.e.,
(πj−πi−ℓa) mod T≤ua−ℓa,∀a= (i, j)∈A. (1)
In a railway timetabling context, the value Tis the period time ofthe railway system, e.g., 60 minutes.
A node irepresents an arrival or departure of some specific directed line in the network, and we must
assign a time value πito this event. For instance, in the current timetable, the direct ICE trains from
Berlin to Karlsruhe leave Berlin main station 33 minutes past the hour. Finally, in the constraint
parameters ℓand uone may encode lower and upper bounds on time durations to ensure safety
requirements, transfer quality requirements, as well as many other things [11].
In a mixed-integer linear programming formulation, the modulo-operator in (1) is resolved by
introducing integer variables pafor the arcs, which we denote periodical offsets. Furthermore, we
penalize any slack on the lower bounds ℓain a linear objective function,
min Pa=(i,j)∈Awa(πj−πi+Tpa)
s.t. πj−πi+T pa≥ℓa,∀a= (i, j)∈A
πj−πi+Tpa≤ua,∀a= (i, j)∈A
πi∈[0, T),∀i∈V
pa∈Z,∀a∈A.
(2)
Other formulations for this problem had been stated in terms of so-called tension variables ya=
πj−πi, or even periodic tension variables xa=πj−πi+T pa, see e.g. [4, 11]. Observe that we
always have ℓa≤xa. In particular, the resulting MIPs, in which we can make the node potential
variables πredundant, already perform considerably better [13]. Yet, their performance can even be
enhanced—and it has to!—by adding valid inequalities. In this spirit, in the remainder of the paper
2
we illustrate the limits of known valid inequalities, and introduce new classes of valid inequalities,
which let us go beyond.
In Section 4, when we provide a relatively large lower bound on the Chv´
atal rank of PESP polyhe-
dra, we will also find it most convenient to make use of the periodic tension variables xa. Throughout
the other parts of this article, however, we stay with (2). This is because we consider this formulation
being more accessible, in particular for the newcomer, and it is a straightforward computation to adapt
the classes of valid inequalities that we identify there to other equivalent mixed-integer programming
formulations of the PESP.
The following lemma reveals that we are in fact dealing with pure integer programs.
Lemma 1 ([16]).If ℓ,u, and Tare integers, then in (2) w.l.o.g. we may replace πi∈[0, T )with
πi∈ {0,...,T −1}.
Proof. Consider an optimum solution (π∗, p∗)of (2). Now, fix the vector p∗. The resulting problem
is a linear optimization problem with twice the node-arc incidence matrix of the constraint graph D
as constraint matrix, which is thus totally unimodular. Since the right-hand side is integer, the LP has
some integer optimum solution π◦, and (π◦, p∗)is feasible for (2) and not worse than the optimum
solution (π∗, p∗).
Note that the periodical offset variables paare either binary, or may in addition take the value
two, provided that ua>ℓa+ε
TT. Nevertheless, w.l.o.g. we forget about any explicit bound on any
of the variables in (2), and just keep their integrality requirements.
3 Chv´
atal Closures
Let Mbe an m×nmatrix and consider the general rational polyhedron
P={x|Mx ≤b}.
The (first) Chv´
atal closure P′of Pis characterized by
P′={x|λTMx ≤ ⌊λTb⌋,for all λ≥0with λTMinteger}.
Also, set P(0) := Pand recursively define P(i+1) = (P(i))′. In integer programming, we are
interested in the integer hull PIof P,
PI:= conv({x∈Zn|Mx ≤b}).
The following is a key theorem in integer programming.
Theorem 2 ([3]).For each rational polytope Pthere exists some integer tsuch that P(t)=PI.
Note that in the sequel, we will switch back to n=|V|and m=|A|.
Now, denote by Bthe node-arc incidence matrix of a PESP constraint graph D. Then, consider
the matrix
M:= −BT−T·Im
BTT·Im,(3)
where Imrefers to the m-dimensional unit matrix. Together with the right-hand side vector
b:= −ℓ
u,(4)
the convex hull of the feasible solutions of (2) is nothing but PI.
Also for the PESP, several studies of its polyhedral structure have been conducted [14, 15, 16].
In the sequel, we summarize some of their results and relate them to the general concept of Chv´
atal
3
closures. To this end, define an oriented circuit C=C+˙
∪C−as a subset of the arcs of Dsuch
that reorienting the elements of C−would result in a directed circuit. The arcs in C+are called the
forward arcs, and the arcs in C−are the backward arcs. In particular, we distinguish the two oriented
circuits that map onto the same circuit in the underlying undirected graph.
The following valid inequalities for PESP have been identified by Odijk [16].
Theorem 3 ([16]).Let Dbe the constraint graph of a PESP instance and consider some oriented
circuit Cin D. Then the cycle inequality
X
a∈C+
pa−X
a∈C−
pa≤$X
a∈C+
ua
T−X
a∈C−
ℓa
T%(5)
is valid for (2). More precisely, the cycle inequalities already show up in the first Chv´
atal closure P(1)
of the LP-relaxation Pof a PESP-polytope PI.
Proof. We combine these inequalities from the ones in (2). To this end, for each forward arc in C,
multiply the less-than inequality of its upper bound uawith 1
T. Similarly, for each backward arc in C,
multiply the greater-than inequality of its lower bound ℓawith −1
T, which translates into a positive
coefficient in the vector λ. It is a simple observation that the node variables πall cancel out in a
telescope sum. Finally, we round down the right-hand side and obtain (5).
Both, the potential strength of the cycle inequalities and the key role of the periodical offset
variables pare reflected by the following theorem.
Theorem 4 ([16]).An instance of PESP is feasible, if and only if there exists an integer vector psuch
that psatisfies all the cycle inequalities.
This is why we are seeking stronger valid inequalities in terms of the periodical offset variables p.
In the next theorem we show that doing so we need to investigate the second Chv´
atal closure. This
will be the main topic from Section 5 on. There, we start by highlighting that there exist some
oriented circuits Cin which the upper bound in (5) can even be decreased, still being valid for PI,
of course. In fact, Lindner [14] proved that the coefficients of any valid inequality for the PESP that
only features periodical offset variables p, have to constitute a circulation in the constraint graph. Let
us already mention that in Section 4 we provide an explicit proof that the Chv´
atal rank of a PESP
instance may be at least T
2.
Denote by Qthe polyhedron that is defined by taking all the inequalities from P(1) that do not
feature any of the node variables π.
Theorem 5. Then, the cycle inequalities (5) constitute the complete description of Q, where
Q={p|psatisfies all cycle inequalities (5)}.
idea. Basically, the proof makes use of the decomposition of an integer circulation into oriented
circuits. However, due to space limitations we have to omit further details here.
Notice that we are aware of instances on which Qdoes not equal the projection of P(1) onto the
periodical offset variables p. In particular, there the p-part of some reversed-arc cut, which is defined
in the next section, is necessary to certify the emptiness of P(1), while Q6=∅.
4 A Lower Bound on the Chv´
atal Rank of PESP
In this section we present the change-cycle inequalities, which were introduced by Nachtigall [15].
We provide a PESP-instance on two vertices, on which the change-cycle inequalities appear first in
the T
2-th Chv´
atal closure, where Tdenotes the period time. To the best of our knowledge, this is the
4
[3,8]6
[0,5]6
Figure 1: A feasible PESP instance on the 2-circuit C2with T= 6
strongest explicit lower bound on the Chv´
atal rank of PESP. Unfortunately, due to space limitations
we have to omit details of the proof here.
Before formulating the change-cycle inequalities, we introduce a few notation. Let Cbe some
oriented circuit in the constraint graph of a PESP-instance. We sum the periodic tension values of the
forward arcs in x+and the periodic tension values of the backward arcs in x−, i.e.,
x+:= X
a∈C+
xaand x−:= X
a∈C−
xa.
Analogously, we define
ℓ+:= X
a∈C+
ℓa,and ℓ−:= X
a∈C−
ℓa.
Last, we define the slope µand the ordinate intercept νof the line that induces the change-cycle
inequality as
µ:= 1 −T
ℓ−−ℓ++T˜zand ν:= (1 −µ)ℓ+−T(˜z−1),(6)
where ˜z:= 1
T(ℓ+−ℓ−).
Theorem 6 ([15]).The following change-cycle inequalities
x−≥µx++ν(7)
are valid for (2).
Notice that a similar inequality, which involves the upper bounds uaof the arcs, is valid, too.
Moreover, it had been observed in [12, Fig. 5.1] that change-cycle inequalities (7) are in a sense
complementary to cycle inequalities (5).
In the remainder of this section we provide a two vertices instance of PESP, of which we prove
that its Chv´
atal rank is T
2. In particular, the change-cycle inequality (7) of this instance does only
appear in the T
2-th Chv´
atal closure. To this end, let Tbe a fixed period time and consider the following
PESP-instance on two vertices: Let a1and a2be two parallel arcs, where ℓa1=T
2,ua1=3
2T−1,
ℓa2= 0, and ua2=T−1. See Figure 1 for the example that corresponds to the period time T= 6.
In particular, in terms of periodic tension variables xawe are dealing with the following polytope
P={(xa1, xa2, z)T|T
2≤xa1≤3
2T−1,0≤xa2≤T−1, xa1−xa2=Tz},(8)
where the variable zis in fact a shorthand for pa1−pa2. Observe that PIcorresponds to the convex
hull of this PESP instance’s solutions.
Proposition 7. Consider the point Qi= (T
2+i·1
2, i ·1
2,1
2). Then Qi∈P(i)\P(i−1), for all
i∈ {1,...,T
2}. Moreover, for i < T
2the points Qiviolate the change-cycle inequality (7). In
particular, the change-cycle inequality (7) cannot be generated prior to the T
2-th Chv´
atal closure.
5
z
1
3 6 xa1
change-cycle inequality
initial PESP constraints
CG1-cut CG2-cut
Projection of the polyhedron P:
3≤xa1
z≤1
Txa1
Figure 2: A visualization of a change-cycle inequality for PESP, and its relation to Chv´
atal closures,
here T= 6
sketch. In this context, the situation can be inspected best by exploiting the redundancy of the equa-
tion xa1−xa2=Tz to only consider the projection into the xa1z-plane. In this space, the relevant
inequalities of Pare the initial inequality xa1≥T
2as well as z≤1
Txa1, which is obtained by
plugging 0≤xa2into xa1−xa2=Tz. Observe that the point (xa1, z)T= (T
2,0)Tmakes the
former inequality tight, while (xa1, z)T= (T, 1)Tmakes the latter inequality tight. In Figure 2, the
corresponding half-spaces are drawn in red, while our ultimate goal, the change-cycle inequality (7),
is drawn in green.
Then, here we can only summarize that by going from one Chv´
atal closure P(i−1) to the subse-
quent one P(i), both these inequalities are “rotated” around the points (T
2,0)Tand (T, 1)T, respec-
tively, such that the point Qibecome tight.
Corollary 8. The Chv´
atal rank of PESP is at least T
2.
5 New Valid Inequalities for the PESP
The next section will reveal the need for new valid inequalities for the PESP: There, we present an
instance for which all cycle inequalities (5) and change-cycle inequalities (7) are valid, although the
instance is infeasible. Also, in practical computations adding these two types of valid inequalities we
typically close no more than 60-90% of the initial gap between the IP optimum and its LP relaxation,
and the resulting refined IPs still risk to be hard to solve. This is why here, we identify two new types
of valid inequalities for the PESP polyhedron.
The first one is defined exclusively on the periodical offset variables p. By Theorem 5 we know
that these cannot stem from the first Chv´
atal closure of the feasible region Pof the LP relaxation
of (2). In more detail, we specify situations in which we may decrease the right-hand side of the
cycle inequalities (5). And with these new inequalities, we can easily prove the infeasibility of the
instance that we discuss in depth in the next Section 6. In Section 7, we complement this analysis
with promising empirical computations.
The second type of valid inequalities lives in the first Chv´
atal closure, and hence may now contain
both types of variables, πand p. Unfortunately, due to space limitations we cannot illustrate in-depth
their respective contribution here.
5.1 Multi-circuit Cuts
We start by presenting new PESP cuts from the second Chv´
atal closure P(2) of P.
6
Theorem 9. Let C0, . . . , Ckbe oriented circuits with incidence vectors γi. Let λi∈(0,1) such
that γ0=λ1γ1+···+λkγk. Finally, let βibe the right-hand sides in the cycle inequalities (5) of
C1,...,Ck. Then
γT
0p≤ ⌊λ1β1+... +λkβk⌋(9)
is a valid inequality for P(2).
The proof follows immediately from Theorem 3 together with the definition of the second Chv´
atal
closure. For some oriented circuits we may not be lucky at all, and (9) is the same as (5). However,
for other cycles, the right-hand side in (9) may be much smaller than the one in (5), see Remark 16 for
one such example. Since these cuts are obtained by representing an oriented circuit as the fractional
sum of multiple other circuits, we refer to (9) as multi-circuit cuts.
Despite the fact that these inequalities are somehow straightforward, they are indeed useful. We
will illustrate this in a detailed example in the next section, where in particular we find that
P(1) 6=∅but P(2) =∅.
5.2 Reversed-Arc Cuts
Here, we introduce one further new class of valid inequalities for the PESP, which stems from the
first Chv´
atal closure. These inequalities were inspired by the results that we obtained by applying the
methods of Fischetti and Lodi [6].
Theorem 10. Let Cbe an oriented circuit, and take some backward arc a0= (i, j)∈C−. The
following inequality is valid for P(1)
πj−πi+ (T−1)pa0+X
a∈C+
pa−X
a∈C−\a0
pa
≤
1
T
(T−1)ua0+X
a∈C+
ua−X
a∈C−\a0
ℓa
.(10)
Proof. We provide the vector λthat combines (10) for some circuit Cout of the initial matrix M. To
this end, for k∈ {0, . . . , m}consider the arc ak= (v, w)∈C. Then, the rows kand m+kof the
matrix Mcorrespond to the following two PESP inequalities
−πw+πv−Tpak≤ −ℓak,
πw−πv+Tpak≤uak.
Finally, choosing the components of the coefficient vector λas
λk=
T−1
T, k =m+c, where ac=a0,
1
T, k =c, where ac∈C−\ {a0},
1
T, k =m+c, where ac∈C+,and
0,otherwise
yields (10).
In fact, these inequalities emerge from cycle inequalities by reversing one of their backward arcs.
Hence, we refer to (10) as reversed-arccuts. Observe that in some special cases, these inequalities can
coincide with what Lindner [14] called chain cutting planes. However, for the latter Villumsen [19]
had to observe in practical computations that these have “no effect” on the solution of his PESP
instances. In addition to Theorem 4, this is another motivation for us to focus in our exposition on
the multi-circuit cuts.
7
[1,5]6
[1,5]6
[1,5]6
[1,5]6
[1,5]6
[0,1]6
[0,1]6
[0,1]6
[0,1]6
[0,1]6
Figure 3: An infeasible PESP instance on the wheel graph W6with T= 6
6 PESP Instances on Wheel Graphs
We introduce a family of infeasible PESP instances, for which the first Chv´
atal closure is still
nonempty. Since the pioneering work of Edmonds [5], we are not aware of too many explicit such
results. Here, even adding the change-cycle inequalities (7) does not change this status. Only adding
two appropriate multi-circuit cuts (9) provides a certificate for the infeasibility of these instances. Let
us annotate that these instances were inspired by an infeasible PESP instance which was studied by
Lindner [14] and whose constraint graph is the wheel graph W4on four vertices.
We consider one fixed period time T≥6for any of the instances that we are right about to define.
Let n≥4be some even number and consider the wheel graph Wn, see Figure 3 for an example
with n= 6. We set the feasible intervals of the spoke arcs to [0,1]T, while we require [1, T −1]Tfor
the remaining outer arcs.
We start investigating this class of instances by first giving a simple proof for the infeasibility of
these instances. Hereafter, we establish that P(1) 6=∅, but P(2) =∅.
Lemma 11. Let T≥2and n≥4be an even number. The PESP instance that is defined on the wheel
graph Wnwith feasible intervals [0,1]Ton the spokes and [1, T −1]Ton the arcs of the outer circuit
is infeasible.
Proof. We may assume w.l.o.g. that πh= 0, where his the hub vertex in Wn. The constraints on
the spokes restrict the πvalues of the other vertices to {0,1}. The constraints on the remaining arcs
require these two values to be used alternatingly around the outer circuit of Wn. Since we chose nto
be even, the outer circuit has an odd number of vertices. But this is not compatible with the πvalues
of all the vertices on the outer circuit taking the values zero and one alternatingly.
The next lemma slightly simplifies the argumentation in the proof of the main theorem of this
section, namely that P(1) is not empty.
Lemma 12. Consider some coefficient vector λ≥0. Let λaand λa−1correspond to two components
whose PESP inequalities refer to the very same arc aand define c:= min{λa, λa−1}. Derive λ′
from λby subtracting cfrom the components of both, aand a−1. Now, if λ′TM≤jλ′Tbkthen
λTM≤λTb.
Proof. First, observe that (λ−λ′)TM= 0. Second, (λ−λ′)Tb=c·(−ℓa+ua)≥0. Thus,
rounding down cannot provide any negative value. Finally, because of ⌊a⌋+⌊b⌋ ≤ ⌊a+b⌋we may
add (λ−λ′)to λ′while keeping any valid inequality valid.
8
As a consequence, for investigating P(1) we may assume w.l.o.g. that in any (relevant) valid
inequality for P(1) none of the arcs shows up with both its inequalities for its respective lower and
upper bounds.
Theorem 13. P(1) 6=∅. In particular, all the cycle inequalities (5) and reversed-arc cuts (10) are valid
for the same particular vector, in the case of T≥6.
Proof. Before starting, in the vector pwe distinguish the components that correspond to the n−
1spoke arcs from the components that correspond to the n−1arcs of the outer circuit, pT= (pT
s, pT
c).
Moreover, with 1we denote the all-one vector of appropriate dimension. Our goal is to establish that
y1:= (πT, pT
s, pT
c) = (0T,1
2T·1T,1
2·1T)∈P(1).(11)
To this end, let λTMx ≤λTbbe an arbitrary valid inequality of P(1), where Mand bare as
defined in (3) and (4), respectively. We have to check y1against this general inequality.
For ease of notation we rewrite the coefficient vector λas λT= (λT
1, λT
2, λT
3, λT
4), where λ1and
λ3refer to the rows that correspond to the spokes, while λ2and λ4refer to the rows that correspond
to the outer circuit of the wheel graph Wn. Moreover, λ3and λ4refer to the initial PESP-inequalities
that define the upper bounds ua, but λ1and λ2refer to the initial PESP-inequalities that define the
lower bounds ℓa, after having multiplied these with minus one.
Using these definitions, we find that
uTMy1= (λT
1, λT
2, λT
3, λT
4)·(−1
2·1T,−T
2·1T,1
2·1T,T
2·1T)T
=−1
2||λ1||1−T
2||λ2||1+1
2||λ3||1+T
2||λ4||1
and
jλTbk=j(λT
1, λT
2, λT
3, λT
4)·(0T,−1·1T,1·1T,(T−1) ·1T)Tk
=⌊−||λ2||1+||λ3||1+ (T−1)||λ4||1⌋.
In particular, for the point y1the initial inequality λTMy1≤λTbis equivalent to
−||λ2||1+||λ3||1+ (T−1)||λ4||1− ⌊−||λ2||1+||λ3||1+ (T−1)||λ4||1⌋(12)
≤1
2||λ1||1+T
2−1||λ2||1+1
2||λ3||1+T
2−1||λ4||1(13)
=1
2(||λ1||1+||λ3||1) + T
2−1(||λ2||1+||λ4||1).(14)
In order to prove that (12-13) is valid, observe first that the left-hand side (12) has values in the
interval [0,1). So, we first identify some coefficient vectors λfor which (14) is at least one. Hereafter,
we investigate the remaining vectors λ.
From Lemma 12, λ≥0,λTMbeing integer, and the coefficients of the periodical offsets p
having value |T|, we conclude that for each component iof λwe have λi=k
T, with k= 0,1,2,....
Case “||λ2||1+||λ4||1≥3
T”. We find immediately that (14) is at least as large as 3
2−3
T. Now,
recall that we chose the period time T≥6, and in particular (14) is at least one, establishing the
theorem in this case.
9
[1,5]6
[0,1]6
[0,1]6
a
i
j
h
Figure 4: A triangle in Wnwith T= 6
Case “||λ2||1+||λ4||1=1
T”. In other words, the Chv´
atal-Gomory coefficient vector λdoes only
involve exactly one inequality of one arc a= (i, j)of the outer circuit of Wn. In this case we are not
aiming at showing that (12-13) was indeed valid. Rather, we enumerate all the eight relevant valid
inequalities of P(1) that involve the arc aas the only arc of the outer circuit.
For that the requirement of λTMbeing integer is fulfilled, in particular for the node variables π,
some of the initial PESP constraints in which πior πjappear must have non-zero components in the
coefficient vector λ. Because of ||λ2||1+||λ4||1=1
T, these must correspond to the spokes (h, i)
and (h, j), where hdenotes the hub of the wheel graph Wn, see Figure 4 for an illustration.
Depending on whether we use the lower bound or the upper bound inequalities of the spokes,
w.l.o.g. the CG-multipliers are either 1
Tor T−1
T.
First, if we choose twice the 1
T, we end with the two standard cycle inequalities (5) for this
triangle,
0≤pa−p(h,j)+p(h,i)≤1.(15)
For the values ps≡1
2Tand pc≡1
2that we chose in our particular vector y1, these inequalities are
of course valid, because 0≤1
2≤1.
Second, if for the spokes we chose once the value 1
Tand once the value T−1
T, we obtain the
following four reversed-arc cuts,
1≤πj−πh+pa+ (T−1)p(h,j)+p(h,i)≤1(16)
0≤πi−πh−pa+p(h,j)+ (T−1)p(h,i)≤0,(17)
which are valid for our choice of y1, too.
Last, taking T−1
Tas the coefficient for both spokes yields
0≤πj−πi+pa+ (T−1)p(h,j)−(T−1)p(h,i)≤1.(18)
Also these two inequalities are valid for the vector y1as defined, 0≤1
2≤1.
To summarize, in the case of ||λ2||1+||λ4||1=1
Twe considered all the eight relevant valid
inequalities of P(1) and verified that the vector (πT, pT
s, pT
c) = (0T,1
2T·1T,1
2·1T)is valid for any of
them.
Case “||λ2||1+||λ4||1=2
T”. We distinguish between several subcases. First, we may have two
non-incident arcs a1and a2of the outer circuit being involved in the cut that is defined by the coeffi-
cient vector λ. But then we are done, because we are in fact twice in the case of ||λ2||1+||λ4||1=1
T.
Second, we may have just one arc of the outer circuit being involved. The two cycle inequali-
ties (5) that emerge from multiplying all its three initial constraints with 2
Tare in fact nothing but
just scaled versions of (15). Hence, here we need to consider valid inequalities in which some of
the initial constraints are multiplied with 2
T, while others are multiplied with T−2
T. The counterparts
of (16) and (17) read
1≤πj−πh+ 2pa+ (T−2)p(h,j)+ 2p(h,i)≤2
−1≤πi−πh−2pa+ 2p(h,j)+ (T−2)p(h,i)≤0.
10
For the particular point y1these terms evaluate to 3
2and −1
2, respectively, and all the four inequalities
are thus feasible. The same holds for the counterpart of (18), where y1yields one, which is feasible
in
0≤πj−πi+ 2pa+ (T−2)p(h,j)−(T−2)p(h,i)≤2.
Last, what we still have to investigate is the case in that two consecutive arcs a1and a2of the
outer circuit are activated by the coefficient vector λ. Due to their orientation in Wn, in the valid
inequality that is induced by λ, both arcs contribute either with their PESP inequalities that define
their lower bounds, or both contribute with their PESP inequalities that define their upper bounds. In
particular, the πvariable of their common vertex has coefficient zero in the cut.
Hence, we are in a situation that is quite similar to the one that we already discussed in the case
of ||λ2||1+||λ4||1=1
T. The only difference is that for the outer arcs we are now summing twice their
lower or upper bounds in the inequalities. We summarize the relevant computations by providing the
eight resulting valid inequalities – using the same notation as in the previous case – in which the
reader will have no difficulty to verify that y1is indeed feasible,
1≤pa1+pa2−p(h,j)+p(h,i)≤1,
1≤πj−πh+pa1+pa2+ (T−1)p(h,j)+p(h,i)≤2,
−1≤πi−πh−pa1−pa2+p(h,j)+ (T−1)p(h,i)≤0,and
0≤πj−πi+pa1+pa2+ (T−1)p(h,j)−(T−1)p(h,i)≤2.
This concludes the last case for the coefficient vector λand thus establishes (11).
Proposition 14. The change-cycle inequalities (7) are valid for the PESP instance that we consider
on the wheel graphs Wn.
sketch. We must omit the full proof due to space limitations. Nevertheless, let us compute the relevant
quantities of the particular fractional solution
y1= (πT, pT
s, pT
c) = (0T,1
2T·1T,1
2·1T) :
For a spoke arc a, here, the periodic tension variable is xa=1
2, and for any other arc a, its periodic
tension variable is xa=T
2. In the most interesting case, namely the case of a triangle, cf. Figure 4
for an illustration in the case of T= 6, the integer variable zof this triangle evaluates to 1
2. And with
these values, the reader might not have any difficulties to compute the slope µ=−1
T−1and ordinate
intersect ν=T
T−1, and thus verify that the corresponding change-cycle inequality (7) is tight. For
longer circuits, there is even some positive slack.
Theorem 15. P(2) =∅. In particular, two multi-circuit cuts (9) certify the emptiness of P(2).
Proof. We apply Theorem 9 to the outer circuit Cof the wheel graph Wn. We combine it linearly by
summing over all the |C|oriented 4-circuits that contain two consecutive edges of C.
Let Cibe one of these 4-circuits. Consider the cycle inequalities (5) of Ciand of its opposite
counterpart C−1
i,
p1+p2+p3−p4≤1
T(1 + (T−1) + (T−1) −0)=2T−1
T= 1,(19)
−p1−p2−p3+p4≤1
T(0 −1−1 + 1)=−1
T=−1,(20)
where p1and p4are the periodical offset variables that we introduced for the two spokes of Ci. In
other words, p1+p2+p3−p4= 1.
11
For that the oriented circuits Cilinearly combine C, we have to multiply each of them with 1
2.
Recall that we selected nto be even, thus |C|=n−1being odd. Doing so for their initial orientation,
using (19) we find that
X
a∈C
pa≤|C| · 1
2·1=n−1
2nodd
=n
2−1,(21)
because the periodical offset variables pof all the spokes cancel out. Similarly, summing (20) for all
their opposite counterparts C−1
iyields
X
a∈C
−pa≤|C| · 1
2·(−1)=−n+ 1
2nodd
=−n
2.(22)
Finally, multiplying (22) with minus one and comparing it to (21) yields n
2≤n
2−1and thus
reveals that indeed P(2) =∅.
Remark 16. It is highly interesting to compare the resulting pair of inequalities (9) to their initial
counterparts (5) in P(1):
P(1) :(n−1) 1
T≤P
a∈C
pa≤(n−1)T−1
Tvs.
P(2) :n
2≤P
a∈C
pa≤n
2−1.
Hence, in a sense on the wheel graph instances the multi-circuit cuts propagate to P(2) the rounding
benefit that particular cycle inequalities achieved already in P(1).
This is our main motivation for the separation heuristic that we apply in the next section.
7 Computational Results
For the PESP, we investigate the change in the solution behavior of CPLEX 11, when adding multi-
circuit cuts (9) to its IP models. To this end, we need to separate these cuts. In Remark (16) we
observed that if we combine valid inequalities (5) of the first Chv´
atal closure in which the rounding
was strong, i.e., b− ⌊b⌋ ≈ 1−ε, then, in the second Chv´
atal closure we can achieve much stronger
multi-circuit cuts (9) than their corresponding cycle inequalities (5) in the first Chv´
atal closure.
In most detail, we generate multi-circuit cuts (9) in the following way.
1. Build an initial IP model of an optimization instance of PESP.
Actually, instead of immediately using (2) we are using a purely tension-based formulation here, because
in [13] it was reported that these performed best.
2. Generate valid inequalities for this IP.
These are cycle inequalities (5) and change-cycle inequalities (7). For the separation heuristic we made
the same experience as Nachtigall, namely that considering the fundamental circuits subject to a minimum
spanning tree with the periodic tension values of the current LP relaxation as weights, empirically is the
most efficient deterministic solution heuristic. Denote the resulting LP by LP1.
3. Store “strong” cycle inequalities in a pool P.
While computing LP1, we record for each cycle inequality (5) that we generate its rounding benefit β:=
b− ⌊b⌋, no matter whether it is added to LP1or not. If βis larger than some threshold value – we used
β≥0.7– then this cycle inequality is added to a pool Pof “strong” cycle inequalities.
12
Bremen
Hamburg
Hannover
North Sea
Figure 5: The subregions of Lower Saxony and Westfalia (north-western part of Germany) of which
we distill our three test instances
4. Add multi-circuit cuts (9) to LP1.
After Steps 2 and 3 have been accomplished, denote by x∗the optimum fractional solution of the final
LP relaxation LP1. To cut this point x∗off with some multi-circuit cut (9), we formulate the Chv´
atal-
Gomory IP, that Fischetti and Lodi proposed in [6], for the cycle inequalities (5) in P. Since the cycle
inequalities already live in the first Chv´
atal closure, this way we are exploring parts of the second Chv´
atal
closure. We iterate this CG-procedure until for some subsequent linear program LP2(LP1plus some
multi-circuit cuts) its optimal solution can no more be separated by this procedure, or a time limit applies.
5. Solve the IP.
In LP2, switch on the integrality requirements on the periodical offset variables pand let CPLEX 11 solve
this (mixed) integer linear program.
Data. We investigate the performance of the multi-circuit cuts (9) on several real-world data sets.
Unfortunately, there is still not available any public library of real-world periodic railway timetabling
instances. Hence, we need to resort on instances that have been available at our institute, e.g., some
that had already been used in [8, 10]. In particular, all are subnetworks of the German passenger
railway network.
More precisely, we consider three regions within Lower Saxony and Westfalia: Harz (H), Ost-
friesland (O), and Ostwestfalen-Lippe (L), see Figure 5. All these networks are operated at a period
time of two hours. Together with the standard time precision that is used by Deutsche Bahn AG, and
which is 0.1minutes, in our models this yields T= 1200. It is a general observation that cycle in-
equalities (5) tend to be stronger, if the spans ua−ℓaof the PESP constraints are smaller. Obviously,
multi-circuit cuts (9) inherit this property. Hence, if these new valid inequalities bear any compu-
tational benefit, we hope to reveal it on instances where railway capacity is rather scarce. This is
done by modeling the complete passenger traffic in the respective regions (regional and long-distance
trains), and by considering single tracks. The sizes of the resulting PESP instances, after eliminating
redundancies such as contracting fixed arcs with zero span, are reported in Table 1. There, in the
column “tight arcs” we counted the number of arcs awith relatively small span, i.e., ua−ℓa≤T
10 .
In the column “width”, we provide a (rough) upper bound on the size of the Branch-and-Bound tree
that had already been considered in [13], which is the product of the possible number of values over
13
Table 1: Size of our test instances. Here, νis the cyclomatic number |A| − |V|+ 1, i.e., the number
of integer variables in the tension-based IP models that we apply [13].
Instance name service lines |V| |A|νtight arcs width
Harz 1 (H1) 17 54 309 256
Harz 2 (H2) 16 30 308 279
Harz 3 (H3) 12 43 226 184
Harz 4 (H4) 22 58 432 375
Harz 5 (H5) 15 55 332 278
Ostfriesland 1 (O1) 10 77 281 205 58 1099
Ostfriesland 2 (O2) 13 107 380 274 86 10128
Ostwestfalen-Lippe 1 (L1) 12 60 295 236 45 10108
Ostwestfalen-Lippe 2 (L2) 12 65 289 225 48 10112
Ostwestfalen-Lippe 3 (L3) 13 66 357 292 49 10145
Table 2: Computational Results of adding multi-circuit cuts (9) to PESP IP models. A boldface
entry indicates that the shortest solution time is achieved by adding multi-circuit cuts (9) (LP bounds
indexed to “intoptb=100”, time in seconds)
pure IP model IP + (5) + (7) IP + (5) + (7) + (9)
Instance LP bound opt time LP bound opt time # cuts (9) LP bound opt time
H1 4.4 325 86.0 75 2 86.0 42
H2 35.6 850 83.0 263 15 83.0 349
H3 4.3 64 77.8 13 64 81.0 12
H4 40.8 3059 86.8 2255 1 86.8 2727
H5 4.1 2921 56.7 1221 17 58.9 1663
O1 12.3 216 84.8 197 18 85.3 79
O2 16.7 338 84.4 365 25 85.0 187
L1 27.2 141 89.0 94 25 89.2 69
L2 11.2 203 94.7 71 22 94.7 56
L3 19.0 2652 90.3 1010 20 90.7 1226
all the integer variables z.
Results. We summarize our computational results in Table 2. There, we compare three different
policies for solving PESP instances. First, take the pure initial model as is, with no problem-specific
valid inequalities being added. Its LP relaxation admits a trivial optimal solution: simply take π≡0
and pa:= ℓa
T. When reporting on values of refined LP relaxations, we scale the values such that this
trivial solution has value zero, and the optimum value is 100.1Second, we add cycle inequalities (5)
plus some change-cycle inequalities (7), as described above. Last, we also add multi-circuit cuts (9).
We start by giving the optimum solutions of the respective (refined) LP relaxations in the columns
“LP bound”. Next to this, we put the solution time under standard settings of CPLEX 11 on an Intel
Core2 with 2.13 GHz and a 2GB RAM running Linux. In the last but third column we report how
many multi-circuit cuts (9) could be found by the separation heuristic that we sketched above, and
which was based on [6].
To summarize, in contrast to what Villumsen [19] had to observe for the chain-cutting planes,
which were due to Lindner [14], multi-circuit cuts (9) indeed have an effect on the solution behavior
of CPLEX 11 on PESP instances. First of all, on each instance, CPLEX is (still, see below) better off
when fed with the full machinery of additional valid inequalities, compared to not adding any cuts
at all. Unfortunately, there are some instances, on which adding multi-circuit cuts (9) cause longer
solution times, compared to the (5)+(7) setting. Nevertheless, in the majority of the cases, multi-
1In the tension-based IP (see [13]) we add cycle inequalities (5) as bounds on the integer variables, which typically yields
values slightly larger than zero, e.g, 5–25%.
14
circuit cuts (9) yield an improved solution behavior. In several cases, the solution time drops by more
than 40%.
Additional Comments. Let us close by commenting on two interesting effects. First, in Table 2,
we voluntarily decided to consider the pure LP bounds instead of the dual bound that CPLEX is able
to achieve in its root node preprocessing. This is mainly motivated by the fact that the LP bounds
are conceptually better accessible, compared to the result of a powerful “black box”. Yet, consider
the instance O2. For this, Table 2 contains entries of 16.7% and 85.0% for the LP bounds with and
without cuts, respectively. But after the root node preprocessing of CPLEX 11, the respective values
get together as close as 82.0% and 85.4%. Now, compare these values to the root node preprocessing
of CPLEX 8.1, which is the version that had been used in an extensive computational study on other
railway timetabling instances [13]: 28.6% and 85.3%. Similar observations can be made for the
respective solution times.
This illustrates the improvements that more recent versions of CPLEX are able to achieve in the
preprocessing of PESP IP models. Could this be a consequence of the fact that pure PESP IP models
have been included in the MIPLIB [1, 10], in combination with new general IP insight, e.g., the one
reported in [6]? Here, it might be interesting to recall that Fischetti and Lodi called the PESP IP
models in the MIPLIB “very hard”...
Nevertheless, although the preprocessed dual bounds get closer to each other, problem-specific
insight, e.g., in form of the new multi-circuit cuts (9) that we just introduced here, may still cut the
solution time by roughly one half.
Second, and last but not least, we point out the high sensitivity that the models show with respect
to certain specific multi-circuit cuts (9). As an example, on the instance H2 we had to make the
following observation. With just inequalities (5) and (7) being added, a solution time of 263s can be
observed, cf. Table 2. Then, adding just the first two multi-circuit cuts (9) that our separation heuristic
found, the solution time is cut by more than 73% to less than 70s. But adding the next two such cuts,
we end with a solution time of even 392s. In other words, if we just added the first two cuts, instead
of all the 25 that we were able to separate, in Table 2 we could have replaced the value 349s in the
H2 row with only 70s...
On the one hand, this underlines that multi-circuit cuts (9) indeed have some effect. On the other
hand, this asks for an understanding on which particular ones of these cuts are the “right” ones.
8 Conclusions
We introduced multi-circuit cuts as new valid inequalities for the Periodic Event Scheduling Prob-
lem (PESP). These live in its second Chv´
atal closure. For a particular family of infeasible PESP
instances, we managed to prove that its first Chv´
atal closure is nonempty. And even adding all
change-cycle inequalities, of which we further proved that in general they appear only in much larger
closures, does not turn the status to infeasible. Hence, it is a first theoretical merit of the multi-circuit
cuts to certify infeasibility of these particular instances. Complementary to this, in our computational
study, we observed that multi-circuit cuts are likely to reduce the solution time of CPLEX 11 on PESP
IP models.
We admit that up to now, our separation has not really been tuned. More theoretical insight is
needed to distinguish between helpful multi-circuit cuts, and unproductive ones. We are very much
confident that with such an additional insight, adding just the helpful multi-circuit cuts will always
improve on the two other settings that we considered in Table 2. In addition, practically efficient
separation heuristics for multi-circuit cuts are required, in particular if we want to use these cuts in
a branch-and-cut context, too. But also any further new classes of valid inequalities from whichever
Chv´
atal closure will be equally welcome – given that they have some (positive) effect on the solution
behavior of CPLEX 11.
15
To summarize, of course multi-circuit cuts are not the end of the story in the solution of PESP
instances. However, we feel that these are one step forward into a promising direction.
References
[1] T. Achterberg, T. Koch, and A. Martin. MIPLIB 2003. Oper. Res. Lett., 34(4):361–372, 2006.
[2] G. C. Caimi, M. Fuchsberger, M. Laumanns, and K. Sch¨
upbach. Periodic railway timetabling
with event flexibility. In C. Liebchen, R. K. Ahuja, and J. A. Mesa, editors, ATMOS 2007 - 7th
Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems,
Dagstuhl, Germany, 2007. Internationales Begegnungs- und Forschungszentrum f¨
ur Informatik
(IBFI), Schloss Dagstuhl, Germany.
[3] V. Chv´
atal. Edmond’s polytopes and a hierarchy of combinatorial problems. Discrete Mathe-
matics, 4:205–337, 1973.
[4] W. Dauscha, H. D. Modrow, and A. Neumann. On cyclic sequence types for constructing cyclic
schedules. Zeitschrift fur Operations Research, 29(1):1–30, 1985.
[5] J. Edmonds. Maximum matching and a polyhedron with 0,1-vertices. Journal of Research
National Bureau of Standards Section B, 69:125–130, 1965.
[6] M. Fischetti and A. Lodi. Optimizing over the first Chv´
atal closure. Mathematical Program-
ming, 110(1):3–20, 2007.
[7] L. G. Kroon. Mathematics for railway timetabling. ERCIM News, 68:22–23, January 2007.
[8] C. Liebchen. A cut-based heuristic to produce almost feasible periodic railway timetables. In
S. E. Nikoletseas, editor, WEA, volume 3503 of Lecture Notes in Computer Science, pages
354–366. Springer, 2005.
[9] C. Liebchen. The first optimized railway timetable in practice. Transportation Science, 2008.
accepted for publication.
[10] C. Liebchen and R. H. M¨
ohring. Information on MIPLIB’s timetab-instances. Preprint
049/2003, TU Berlin, Mathematical Institute, 2003.
[11] C. Liebchen and R. H. M¨
ohring. The modeling power of the periodic event scheduling problem:
Railway timetables - and beyond. In F. Geraets, L. G. Kroon, A. Sch¨
obel, D. Wagner, and C. D.
Zaroliagis, editors, ATMOS, volume 4359 of Lecture Notes in Computer Science, pages 3–40.
Springer, 2004.
[12] C. Liebchen and L. W. Peeters. On cyclic timetabling and cycles in graphs. Technical Report
761-2002, TU Berlin, Mathematical Institute, 2002.
[13] C. Liebchen, M. Proksch, and F. H. Wagner. Performance of algorithms for periodic timetable
optimization. In M. Hickman, P. Mirchandani, and S. Voß, editors, Computer-Aided Systems in
Public Transport (CASPT 2004), volume 600 of Lecture Notes in Economics and Mathematical
Systems. Springer, 2008.
[14] T. Lindner. Train Schedule Optimization in Public Rail Transport. Ph.D. thesis, Technische
Universit¨
at Braunschweig, 2000.
[15] K. Nachtigall. Periodic Network Optimization and Fixed Interval Timetables. Habilitation
thesis, Universit¨
at Hildesheim, 1998.
16
[16] M. A. Odijk. A constraint generation algorithm for the construction of periodic railway timeta-
bles. Transportation Research B, 30(6):455–464, 1996.
[17] J. Opitz and K. Nachtigall. A modulo network simplex method for solving periodic timetable,
2007. A german description of their software system TAKT can be found in Der Eisenbahnin-
genieur, 58(7/2007):50–55.
[18] P. Serafini and W. Ukovich. A mathematical model for periodic scheduling problems. SIAM
Journal on Discrete Mathematics, 2(4):550–581, 1989.
[19] J. C. Villumsen. Construction of Timetables Based on Periodic Event Scheduling. Master’s
thesis, Danish Technical University, Copenhagen, 2006.
17
Reports from the group
“Combinatorial Optimization and Graph Algorithms”
of the Department of Mathematics, TU Berlin
2008/27 Christian Liebchen and Elmar Swarat: The Second Chv´
atal Closure Can Yield Better Railway Timeta-
bles
2007/39 Ewgenij Gawrilow, Ekkehard K¨
ohler, Rolf H. M¨
ohring, and Bj¨
orn Stenzel: Dynamic Routing of Auto-
mated Guided Vehicles in Real-time
2007/22 Michael Elkin, Christian Liebchen, and Romeo Rizzi: New Length Bounds for Cycle Bases
2007/19 Nadine Baumann and Sebastian Stiller: The Price of Anarchy of a Network Creation Game with
Exponential Payoff
2007/17 Christian Liebchen, Michael Schachtebeck, Anita Sch¨
obel, Sebastian Stiller, and Andr´
e Prigge: Com-
puting Delay Resistant Railway Timetables
2007/04 Felix G. K¨
onig, Marco E. L¨
ubbecke, Rolf H. M¨
ohring, Guido Schfer, and Ines Spenke: Solutions to
Real-World Instances of PSPACE-Complete Stacking
2007/03 Christian Liebchen, Gregor W¨
unsch, Ekkehard K¨
ohler, Alexander Reich, and Romeo Rizzi: Bench-
marks for Strictly Fundamental Cycle Bases
2006/32 Romeo Rizzi and Christian Liebchen: A New Bound on the Length of Minimum Cycle Bases
2006/24 Christian Liebchen and Sebastian Stiller: Delay Resistant Timetabling
2006/08 Nicole MegowandTjark Vredeveld: ApproximationResultsfor PreemptiveStochasticOnlineSchedul-
ing
2006/07 Ekkehard K¨
ohler, Christian Liebchen, Romeo Rizzi, and Gregor W¨
unsch: Reducing the Optimality
Gap of Strictly Fundamental Cycle Bases in Planar Grids
2006/05 Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard K¨
ohler, and Heiko Schilling: Length-
Bounded Cuts and Flows
2005/30 Ronald Koch, Martin Skutella, and Ines Spenke : Maximum k-Splittable Flows
2005/29 Ronald Koch and Ines Spenke : Complexity and Approximability of k-Splittable Flows
2005/28 Stefan Heinz and Sven O. Krumke and Nicole Megow and J¨
org Rambau and Andreas Tuchscherer and
Tjark Vredeveld: The Online Target Date Assignment Problem
2005/18 Christian Liebchen and Romeo Rizzi: Classes of Cycle Bases
2005/11 Rolf H. M¨
ohring and Heiko Schilling and Birk Sch¨
utz and Dorothea Wagner and Thomas Willhalm:
Partitioning Graphs to Speed Up Dijkstra’s Algorithm.
2005/07 Gabriele Di Stefano and Stefan Krause and Marco E. L¨
ubbecke and Uwe T.Zimmermann: On Mini-
mum Monotone and Unimodal Partitions of Permutations
2005/06 Christian Liebchen: A Cut-based Heuristic to Produce Almost Feasible Periodic Railway Timetables
2005/03 Nicole Megow, Marc Uetz, and Tjark Vredeveld: Models and Algorithms for Stochastic Online
Scheduling
2004/37 Laura Heinrich-Litan and Marco E. L¨
ubbecke: Rectangle Covers Revisited Computationally
2004/35 Alex Hall and Heiko Schilling: Flows over Time: Towards a more Realistic and Computationally
Tractable Model
2004/31 Christian Liebchen and Romeo Rizzi: A Greedy Approach to Compute a Minimum Cycle Bases of a
Directed Graph
2004/27 Ekkehard K¨
ohler and Rolf H. M¨
ohring and Gregor W¨
unsch: Minimizing Total Delay in Fixed-Time
Controlled Traffic Networks
2004/26 Rolf H. M¨
ohring and Ekkehard K¨
ohler and Ewgenij Gawrilow and Bj¨
orn Stenzel: Conflict-free Real-
time AGV Routing
2004/21 Christian Liebchen and Mark Proksch and Frank H. Wagner: Performance of Algorithms for Periodic
Timetable Optimization
2004/20 Christian Liebchen and Rolf H. M¨
ohring: The Modeling Power of the Periodic Event Scheduling
Problem: Railway Timetables — and Beyond
2004/19 Ronald Koch and Ines Spenke: Complexity and Approximability of k-splittable flow problems
2004/18 Nicole Megow, Marc Uetz, and Tjark Vredeveld: Stochastic Online Scheduling on Parallel Machines
2004/09 Marco E. L¨
ubbecke and Uwe T. Zimmermann: Shunting Minimal Rail Car Allocation
2004/08 Marco E. L¨
ubbecke and Jacques Desrosiers: Selected Topics in Column Generation
2003/050 Berit Johannes: On the Complexity of Scheduling Unit-Time Jobs with OR-Precedence Constraints
2003/49 Christian Liebchen and Rolf H. M¨
ohring: Information on MIPLIB’s timetab-instances
2003/48 Jacques Desrosiers and Marco E. L¨
ubbecke: A Primer in Column Generation
2003/47 Thomas Erlebach, Vanessa K¨
a¨
ab, and Rolf H. M¨
ohring: Scheduling AND/OR-Networks on Identical
Parallel Machines
2003/43 Michael R. Bussieck, Thomas Lindner, and Marco E. L¨
ubbecke: A Fast Algorithm for Near Cost
Optimal Line Plans
2003/42 Marco E. L¨
ubbecke: Dual Variable Based Fathoming in Dynamic Programs for Column Generation
2003/37 S´
andor P. Fekete, Marco E. L¨
ubbecke, and Henk Meijer: Minimizing the Stabbing Number of Match-
ings, Trees, and Triangulations
2003/25 Daniel Villeneuve, Jacques Desrosiers, Marco E. L¨
ubbecke, and Franc¸ois Soumis: On Compact For-
mulations for Integer Programs Solved by Column Generation
2003/24 Alex Hall, Katharina Langkau, and Martin Skutella: An FPTAS for Quickest Multicommodity Flows
with Inflow-Dependent Transit Times
2003/23 Sven O. Krumke, Nicole Megow, and Tjark Vredeveld: How to Whack Moles
2003/22 Nicole Megow and Andreas S. Schulz: Scheduling to Minimize Average Completion Time Revisited:
Deterministic On-Line Algorithms
2003/16 Christian Liebchen: Symmetry for Periodic Railway Timetables
2003/12 Christian Liebchen: Finding Short Integral Cycle Bases for Cyclic Timetabling
Reports may be requested from: Sekretariat MA 6–1
Fakultt II – Institut fr Mathematik
TU Berlin
Straße des 17. Juni 136
D-10623 Berlin – Germany
e-mail: [email protected]n.DE
Reports are also available in various formats from
http://www.math.tu-berlin.de/coga/publications/techreports/
and via anonymous ftp as
ftp://ftp.math.tu-berlin.de/pub/Preprints/combi/Report-number-year.ps
