Document [original]

Strong formulations for the Multi-module PESP and a

quadratic algorithm for Graphical Diophantine

Equation Systems

Laura Galli⋆and Sebastian Stiller⋆⋆

Abstract. ThePeriodicEventSchedulingProblem(PESP)isthe method of choice

for real-world periodic timetabling in public transport. Its MIP formulation has

been studied intensely for the case of uniform modules, i.e., when all events have

the same period. In practice, multiple modules are equally important. The strength

of current methods for uniform modules rests on three ingredients: Every feasible

instance allows for an optimal solution with a certain structure. Therefore, it can

be reformulated with the use of an integral cycle basis. Finally, a certain type of

rounding cuts arising from cycles has proven very powerful. All of this fails in

the multi-module case. Therefore, applications with multiple periods were hardly

solvable so far.

We analyze a certain type of Diophantine equation systems closely related to the

multi-module PESP. Thereby, we identify a structure, so-called sharp trees, that

allows to solve the system in O(n2)time. We show, a sharp tree is guaranteed to

exist and found by a similar algorithm, if the modules form a linear lattice. Based

on this we develop the machinery to solve multi-module PESPs on real-world

scale. In particular, we recover all three ingredients for the multi-module case.

In our computational results the new MIP-formulations drastically improve the

solvability of multi-module PESPs. We also demonstrate that without sharp trees

no similar approach can be hoped for.

1 Introduction

The Periodic Event Scheduling Problem (PESP) is a combinatorial optimization

problem of great practical importance. It is the model of choice for periodic

timetabling in public transport, has been used for periodic job shop and traffic

signal scheduling, and has successfully and repeatedly been applied in practice.

The task is to schedule periodic recurring events, e.g., the arrivals and departures

of trains, such that between pairs of periodic events periodic constraints are ful-

filled. A periodic constraint between periodic events iand jmeans that for every

realization of ithere is at least one realization of j, with time difference greater or

equal some lower respectively less or equal some upper bound. Such constraints

can model for periodic timetables the headway constraints, the stopping times, or

that passengers can quickly transfer between trains of different lines. In fact, the

high modeling power of the PESP (cf. [7]) even allows to include rolling stock

⋆DEIS, University of Bologna, Italy. E-mail: [email protected]

⋆⋆ MATHEON, Technische Universit¨

at Berlin, Germany. E-mail:

[email protected]

minimization and crew scheduling into the timetabling. This facilitated the con-

struction of the first mathematically optimized railway timetable, namely for the

Berlin underground in 2005.

The PESP is most powerfully solved as a (mixed) integer linear program ((M)IP).

Apart from their practical importance, the IPs arising from the PESP are of in-

dependent theoretical interest. Any such IP is naturally associated to a digraph.

There are variables

ifor each node iand kafor each arc a. Two constraints cor-

respond to each arc a= (i,j):ℓa≤

j−

i+kaP≤ua. Thus, for each arc the

difference of the node variables must be in the interval [ℓa,ua]modulo a constant

P. This constant is the period of the application, e.g., the time that elapses until

the next train of the same line arrives. This special class of IPs has attracted a

lot of research attention from combinatorics and integer programming perspec-

tives. It has been shown to be NP-complete, even MAXSNP-hard, and to have an

unbounded Chvatal rank [22]. Nevertheless, research efforts exploiting the graph

structure have led to a rich understanding of these IPs. These insights facilitate

methods that are eventually capable to solve instances of considerable and prac-

tically relevant size—e.g., the timetable optimization of a complete national rail-

way system. Some of these instances are challenging enough to be found in the

MIPLIB. (These are the instances on which we base the computational validation

of our method.)

The strong methods for uniform-module PESP have three ingredients (cf. [10]):

first, if the instance is feasible, then for any tree exist optimal solutions, that

have offsets equal to zero on that tree, second, a strong formulation of the MIP

constructed by an integral cycle basis, and finally, a class of rounding cuts (the

Odijk inequalities) also based on a well chosen set of cycles.

All of this fails, if the modules are not uniform. In general, solutions need non-

zero offsets on all arcs. In general, an integral cycle basis does not give an equiva-

lent formulation, and the Odijk inequalities become arbitrarily loose for multiple

modules.

The powerful previous results apply to PESPs with a single module Pfor all

constraints. Yet multi-module PESPs are justified and even desired from the ap-

plications perspective: A public transport system is often comprised of lines with

different periods, e.g., subways running every ten minutes, some busses running

every 30 minutes, other every five minutes, and regional trains every hour. Also

traffic lights in the same urban area may well have different periods. Despite this

ample practical need, until now we lack the theory for a strong approach to multi-

module PESPs.

For solving PESPs a special class of linear Diophantine equation systems (DES)

naturally related to the PESP is important. Again, given a digraph one associates

variables

to the nodes and kto the arcs, and each arc represents an equation

of the form:

j−

i+kaPa=xa. Note, the coefficients of the node variables are

equal to 1. Setting the arc coefficients Pa=1 would allow for a trivial solution k≡

≡0. In this sense the proposed class is the simplest non-trivial class of DES

one can associate to a digraph. Therefore, we call them Graphical Diophantine

Equation Systems (GDES). GDESs are not only similar to PESPs, they also play

a role in the state-of-the-art solving methods for PESPs. In the special case, when

all modules Paare equal, the GDES can be solved in linear time by a straight

forward algorithm. For the general case so far one has to resort to constructing

the Hermite Normal Form (HNF) of the GDES matrix, which can be done in

(high) polynomial time.

In this work, starting from an analysis of and a new algorithm for GDES we

develop a method capable of solving real-world multi-module PESPs. We test this

on multi-period instances which we get by changing the periods in the uniform

PESP instances that can be found in the MIPLIB, namely, timtab1 and timtab2.

These MIPLIB instances are real-time railway timetabling instances.

Related work: The PESP has been introduced by [23] and applied to timetabling

problems by [21,22], periodic job shop [23], and traffic signaling [5,4]. In [20]

a set of particularly useful rounding cuts have been proposed for the first time. A

concise exposition of the PESP and the state-of-the-art theory and solving meth-

ods can be found in [7]. We summarize some of these results at the end of this

section. The NP-hardness has first been shown in [18,20] and the MAXSNP-

hardness is proven in [7]. Recently, it has been shown [22] that the PESP has

unbounded Chvatal rank. In [13] optimization over the first Chvatal rank of the

PESP has been studied.

Diophantine equations systems can be solved as any other linear equation system,

once they are presented by their Hermite Normal Form (HNF). There is a standard

polytime algorithm for constructing the HNF [24]. While further research on the

HNF focuses on algorithms that use less space, we are not aware of a specific

algorithm for GDES.

The GDES are a special, and particularly simple class of DES. Similar flavor the

Mixing Set Problem defines a particularly simple class of Diophantine inequal-

ities that has been studied intensively [1,2] and also has practical applications.

Another very important class of DES that are closely related to GDES are the

so-called unique games [6].

For practical instances which feature two different modules P|P′(e.g., a system

of trains of which some run every hour and others every two hours) the state-

of-the-art [7] approach is to use a PESP with uniform module P′and double the

events that have higher frequency. The duplications of such an event have to be

mutually fixed by additional constraints. This increases the size of the PESP.

Our contribution and outline: We show in Section 2 that in case a so-called

sharp tree exists, the offsets can be chosen zero on it. These trees exist and can

be found in O(n2)time, if the modules are nested, i.e., form a linear lattice with

respect to division. In Section 3 we show that the existence of a sharp tree allows

for a cycle basis formulation, which is equivalent to the original arc formulation

and gives a stronger IP. Moreover, we show that we can prune a multi-module

PESP, such that the fundamental cycles of a sharp tree give particularly good

inequalities.

The same algorithm that finds a sharp tree in case of nested modules, also solves

a GDES in time quadratic in the number of nodes (cf. Section 2). We also show

that without the existence of a sharp tree similar approaches to strengthen the IP

formulation or to quickly solve a GDES do not extend in general.

In the final section we report on twelve instances derived from the afore men-

tioned MIPLIB timetabling problems. The computations impressively testify the

strength of our method.

Definitions and basics: Firstly, we define the two main mathematical objects

under consideration.

Definition 1. A digraph G(V,A)together with a natural valued function on the

arc set, P :A→N, and an integer valued function on the arc set x:A→Zis called

a graphical representation of the following system of Diophantine equations on

variable vectors (

,k)∈Z|V|,|A|:

j−

i+kaPa=xa∀a(= (i,j)) ∈A.(1)

A system for which a graphical representation exists is called a graphical Dio-

phantine equation system (GDES).

The results we derive also hold if xmaps to the rationals and Pcan be negative,

but we can restrict w.l.o.g. (cf. [7]) to natural numbers for simplicity and also

for its significance in a practical context. From a GDES one can straight forward

construct its representation and this representation is unique up to isomorphism.

So we speak of the representation of a GDES.

Definition 2. Given a digraph G(V,A)together with two rational functions on

the arc set, ℓ:A→Qand u :A→Q, a third natural valued function on the arcs,

P:A→N, and a vector c ∈Q|A|. The following mixed integer program is called

aclassical formulation for the periodic event scheduling problem (PESP):

min ∑

(i,j)=a∈A

c(a)(

j−

i+kaPa)

ua≤

j−

i+kaPa≤ℓa∀a(= (i,j)) ∈A(2)

∈Q|V|,k∈Z|A|

The reader is referred to [7] for a comprehensive work on the PESP. One may

distinguish between the Periodic Event Scheduling Problem as such and its for-

mulation as a MIP. Originally, the constraints are: ua≤

j−

i≤ℓamod Pa. We

ignore this notational difference. It is more important that in most applications the

events, i.e., the nodes—not primarily the arcs—are periodic. So the constraints

should rather read: ua≤(

j+kjPj)−(

i+kiPi)≤ℓa. It is easily checked that

this is equivalent to the formulation above, when we choose Pa=gcd{Pi,Pj}.

We will use subscripts for the arguments of the functions x,u,ℓ and Pin the re-

mainder. We abbreviate n:=|V|and m:=|A|. We will use V(G)and A(G)to

denote node and arc sets of a graph. Generally the values of Pare called periods

or modules, those of xtensions, those of

potentials, an those of koffsets. In the

remainder we will assume w.l.o.g. the graphs to be connected. It is easy to see,

that if the image of uand lare in the integers there is always an optimal solu-

tion with all

integral. So basically, the PESP is an IP, although it is constantly

referred to in the literature as a MIP.

We summarize some basics on the PESP: Notice, the objective function only

refers to pairwise differences of potentials. This is partly due to the pertinent ap-

plications, partly to the mathematical structure. The kvariables model the modulo

operator. It would be strange to count them in a practical objective. Moreover, for

any feasible solution (

,k)and any q∈Qalso (q+

,k)is also feasible.

Assume all Paare equal, and let xbe the vector of arc differences of a solution

(

,k), i.e., x(i,j)=

j−

i+k(i,j)P. A vector xarising from a solution in this way

is called its tension. It is easily checked—and we will re-prove it as a by-product

of a more general theorem—that for any tree Tthere is a vector (

,k)′with the

same tension xbut k′

a=0 for all a∈T. Note, that (

,k)′is also a feasible solution

and has the same objective value as (

,k), because it has the same tension. This

gives rise to two important features of the PESP with uniform modules.

First, if we know the tension x, we can construct a feasible solution in a simple

way: Set

i=0 for an arbitrary node i. Choose an arbitrary spanning tree T, and

propagate

starting from i along T with respect to x. Propagation means, that

we solve the equality system

j−

i=xafor all a∈A(T)iteratively fixing the

node values as we traverse the tree.

It is helpful to notice, that any arc awith ua−ℓa≥Pastates a redundant condition.

Also, we can replace a directed arc by its antiparallel arc, simply by multiplying

both constraint by (−1).

The second important concept are cycle bases. A cycle basis is a basis for the

linear subspace spanned by the incidence vectors of cycles in the vector space

Qmspanned by the arc incidence vectors. Note that a cycle may have forward

and backward arcs. For the latter the incidence vector of the cycle has a (−1)

entry. A cycle basis is called integral, if all cycles are integer linear combination

of the elements of the basis. Given a spanning tree Tin the graph, the fundamental

cycles C(a,T)of all non-tree arcs a/∈A(T)form a cycle basis. A fundamental

cycle C(a,T)of a non-tree arc awith respect to a spanning tree Tis composed

of the arc itself and the unique path in Tconnecting its endnodes. Such a basis

is called a fundamental cycle basis (sometimes also: strictly fundamental). Every

fundamental cycle basis is integral.

Finally, in the case of uniform modules, we can sum the constraints along a cy-

cle C, yielding a new, valid constraint. Replacing

j−

iby x(i,j)this constraint

reads: ∑a∈Cxa=kCP, where kC=∑a∈Cka, and we assume w.l.o.g. all arcs to be

directed in the orientation of the cycle. If a tension vector xfulfills this cycle con-

straint for all cycles of an integral cycle basis, then it is the tension of a solution

(

,k). If in addition xa∈[ℓa,ua]it is the tension of a feasible solution (

,k). In

other words, for uniform modules an integral cycle basis gives rise to an equiva-

lent MIP formulation. This cycle basis formulation has proven [10] significantly

stronger than the original arc formulation.

For a cycle Cwe abbreviate gcd(C):=gcd{Pa:a∈C}.

2 Graphical Diophantine Equations Systems

Both, the Diophantine and the MIP results in this paper are based on Lemma 1

that guarantees the existence of well structured solutions under certain conditions.

To state these conditions we define the following.

Definition 3. Let Gbe a GDES and G the graph of its representation. A spanning

tree T in G is called a sharp tree, if each of its fundamental cycles C(a,T)has

greatest common divisor equal to Pa, the module of the cycle’s non-tree arc a ∈

A(G)\A(T).

Lemma 1. Let Gbe a GDES and T a sharp tree in the graph of its representa-

tion. If Ghas a solution, then there is a solution of Gwith ka=0for all a ∈T.

Proof. Reorder the matrix of the GDES such that the following holds: The new

matrix Mstarts with the n−1 rows corresponding to the arcs in T. Restricted to

the columns affecting the

variables, these rows form a lower triangular matrix

(the first column omitted). The columns affecting kform a diagonal matrix.

Index the nodes according to their column and arcs according to their rows in M.

For two nodes vand wdenote by P(v,w,T)the unique path from vto win T.

Let (

,k)0be some solution. We construct a solution (

,k)n−1over n−1 stages

denoted (

,k)i,i∈ {1...n−1}. For each i∈ {1...n−1}successively with in-

creasing row index we take four steps:

1. Set ki

i=0.

2. Re-establish the correctness of the i-th equation by changing the node value

jcorresponding to Mi,i, the right most non-zero entry in the first n−1

columns, i.e.,

i:=

i−1

i+sgn(Mi,i)k0

iPi. Let ℓ(i)be minimal with Mi,ℓ(i)6=

0, i.e., the other node of arc i.

3. Propagate the new node value downwards along the tree. Formally: For all

remaining tree rows t∈ {i+1...n−1}successively with increasing row

index set

t:=

i−1

t+sgn(Mi,i)k0

iPiin case ℓ(i)/∈P(i,t,T).

4. Re-establish correctness (in arbitrary order) for the equations of non-tree

arcs by adjusting their arc variables. Formally: For all j∈ {n,...,m}let

1≤r<s≤n−1 be the nodes of arc j, i.e., Mj,rand Mj,s6=0. Set kij:=

ki−1

j−sgn(Mj,r)(

r−

i−1

r)+sgn(Mj,s)(

s−

i−1

Pj.

(We were a bit sloppy dropping exceptional handling of first row and column, and

omitting when

j:=

i−1

jand likewise for k.)

Obviously, each (

,k)ifulfills all equalities. Observe, we touch the arc variable

ktof any tree row only in stage t. Therefore, (

,k)ithe solution of any stage

i∈ {1...n−1}has ki

t=0 for all t∈ {1...i}. It remains to show for the non-tree

arcs j∈ {n...m}that every kijis an integer, in particular, that

Pj|hsgn(Mj,r)(

r−

i−1

r)+sgn(Mj,s)(

s−

i−1

s)i.

For all nodes swe have

s−

i−1

s=|k0

iPi|. Now, distinguish whether ℓ(i)∈

P(r,s,T)or not. If ℓ(i)is in, so is iand the i-th arc is on the fundamental cycle

of jin T. Thus, Pj|Piby condition of the lemma and we are done. In case, ℓ(i)/∈

P(r,s,T)both nodes are changed by the same value. Therefore, sgn(Mj,r)(

r−

i−1

r)+sgn(Mj,s)(

s−

i−1

s) = 0, which completes the proof. ⊓⊔

To guarantee the existence of sharp trees we need the following property:

Definition 4. We say a GDES (or a PESP) has nested modules, if for each pair

of its modules Pa≤Pbwe have Pa|Pb.

We will show that GDES with nested modules have sharp trees, whereas sharp

trees do not exist in general. Therefore, we can solve GDES with nested modules

in a fast way.

Nested modules: The following DENDI–algorithm (Diophantine Equations with

Nested DIvisors) solves GDES with nested modules. In addition it constructs a

sharp tree.

The algorithm considers the arcs in subsequent levels according to their module.

On the first level, it constructs spanning trees in the connected components of

arcs with maximal modules. Then it shrinks these components to super-nodes and

carries on with the next smaller level of modules. This way DENDI constructs a

tree, along which one can propagate the potentials

according to the tensions.

Finally, it verifies whether the equations of the non-tree arcs can also be fulfilled

for the chosen

. A formal description can be found in the appendix. For the

correctness of the algorithm we show two lemmata.

Lemma 2. The subgraph T returned by the DENDI–algorithm is a sharp tree.

Proof. Obviously, Tis a spanning tree. Consider a non-tree arc aand its module

Pa=Pℓ. Every other arc bin the fundamental cycle C(a,T)either belongs to the

same component as aon level ℓor to a tree of a component shrunk into a super-

node on an earlier level. In both cases Pℓ≤Pb. The modules being nested, this

implies Pa|Pb, and thus Tis sharp. ⊓⊔

Thus, we have:

Theorem 1. A GDES with nested modules has a sharp tree.

Lemma 3. The DENDI–algorithm returns failure, iff the GDES is infeasible.

Moreover, the offset ka=0for all tree arcs a ∈A(T).

Proof. The offsets vanish on the tree arcs by construction, and because of the test

in the final loop (

,k)is a solution to the GDES, if they are returned. By Lemma 2

subgraph Tis sharp and we can apply lemma 1 to know that the GDES has a

solution iff it has a solution with ka=0 for all a∈A(T). If such a solution exists,

it is fully determined by the potential of one node i, because one can propagate

along the spanning tree T. But, if

∗is such a solution, then

∗+zis also one for

all z∈Z. In particular, the

constructed in DENDI is one. Thus, if this

fails

one of the equations, there can be no solution to the GDES. ⊓⊔

Observe that one can force any minimum spanning tree algorithm to return the

sametreeasthe(weighted)DENDI-algorithmbyintroducingthe followingweights:

The weight of an arc is (the sum of its original weight wand) a multiple of a large

constant M(>∑w), where arcs with larger period get smaller multiples of M.

Therefore, we can substitute DENDI by any MST algorithm and conclude in par-

ticular:

Theorem 2. The DENDI-algorithm is correct, and has a running time in O(n2),

where n is the dimension of the solution vector.

General modules: Requiring nested modules may be suitable for the application

but constitutes a strong mathematical restriction. Still, the example on the left of

Figure 1(a) shows that we cannot hope for similar results in the general case.

Example 1. In Figure 1(a) the numbers next to the arcs and nodes give the mod-

ules of the arcs respectively the nodes. On the right, the arc modules result as gcd

of the node modules. Assume the tensions along the cycle sum up to 1. This is

feasible, because the gcd of all arcs is 1. Yet, a feasible solution must have k6=0

on all arcs for the left graph, and either on the two vertical or the two horizontal

arcs for the right graph.

In general, a solution for any cycle Cmust have non-zero offsets kon a subset

Sof C’s arcs, such that gcd(S) = gcd(C). As in the example this may require all

offsets to be non-zero.

Looking at GDESs from the perspective of the PESP and its applications, the fol-

lowing objection is valid: In the application we are given periods for the events,

i.e., the nodes. The period (module) of an arc a= (i,j)arises in an equivalent for-

mulation as Pa=gcd{Pi,Pj}. Thus, the situation on the left of Figure 1(a) cannot

occur. This is true. But, in general (cf. the example on the right in Figure 1(a))

node modules can be such, that a solution must have non-zero offsets on a subset

of the arcs, that forms a maximal matching on any cycle.

105

30 42

105

(a) General modules

may prevent vanishing

offsets on any spanning

tree.

[1,5]

[2,5]

[1,5]

[2,4]

[1,2]

(b) A sharp and a non-sharp

fundamental cycle basis. Non-

tree arcs are dashed.

a8a9

a10

sharp cycle basis.

3 Solving PESP with multiple modules

The methods for the PESP with uniform modules rest on a strong formulation

based on an integral cycle basis and on certain rounding cuts, that also stem from

cycles. We will show that in general an integral cycle basis for a multi-module

PESP does not give an equivalent formulation. Whereas, if a sharp tree exists,

we will show that, its fundamental cycle basis provides for the desired strong

formulation. In general, a multi-module PESP need not have a sharp tree. But we

have seen in the previous section that a sharp tree can be found in case of nested

modules.

The proper generalization of integral cycle bases for multi-module PESPs is the

following type of basis:

Definition 5. A fundamental cycle basis stemming from a sharp tree is called a

sharp cycle basis.

In particular, this means for each cycle Cin a sharp basis, that the gcd(C)is

attained by the non-arc ofC. Recall, that any fundamental cycle basis, and thereby

any sharp cycle basis is integral.

Lemma 4. Let Bbe a sharp cycle basis in a PESP model. For an arc vector x

the following three statements are equivalent:

1. The vector x is the arc tension of a node potential

2. The vector x fulfills the cycle equality for every cycle C, i.e., there is kC∈Z

such that ∑a∈Cxa=kC·gcd(C).

3. The vector x fulfills the cycle equality for every cycle C ∈B.

Proof. The inclusion 2 ⇒3 being trivial, we show 1 ⇒2 and 3 ⇒1.

1⇒2: According to (1) we have x(i,j)=

j−

i+k(i,j)P(i,j)for all arcs (i,j)∈A.

Summing along a cycle C(multiplying the equation of awith (−1)for arcs

athat lie in Ccontrary to its orientation) we get ∑(i,j)∈Cx(i,j)=k(i,j)P(i,j).

3⇒1: Define a node potential

by setting

s=0 for some node sand propagate

the xvalue along the sharp tree T. It remains to show that for every non-tree

arc (i,j)∈A\Tthere is k(i,j)∈Zsuch that

j−

i+x(i,j)=k(i,j)P(i,j).(3)

The fundamental cycle C:= (P(i,j,T),(i,j)) is in Band P(i,j)=gcd(C),

and Equation (3) follows.

⊓⊔

Together with Theorem 2 we get:

Theorem 3. Let Gbe a PESP in the arc formulation. If a sharp cycle basis for-

mulation for Gexists, it is equivalent. If Ghas nested modules, then a sharp cycle

basis formulation exists and can be found in time in O(n2).

For multiple modules the cycle basis formulation is not equivalent to the arc for-

mulation even if the modules are nested. In the following example we show that

non-sharp trees do not guarantee an equivalent cycle basis formulation.

Example 2. Consider the graph on the left of Figure 1(b). Set the module Pa=6

for all arcs except the diagonal one. For this set the module to 3. The interval next

to an arc shows its upper and lower bounds. As cost vector choose the unit vector.

On the right of Figure 1(b) we show two fundamental cycle bases corresponding

to two different trees. The non-tree arcs of a fundamental cycle are drawn dashed.

On top, the cycle basis consists of two triangles. The corresponding tree is not a

sharp tree, because for both cycles the non-tree arc has module 6 and the cycle’s

gcd is 3. Again, the example cannot occur if the periods stem from the nodes.

Still, if one replaces the diagonal arc by two arcs of period 3 one can choose the

node periods accordingly.

Index the arcs clockwise starting left and put the diagonal arc last. Then the opti-

mal solution for this cycle basis formulation is x= (2,2,1,2,2), for which Algo-

rithm 1 returns failure, i.e., it is not a tension of a feasible solution and thus the

cycle basis formulation is not equivalent to the original arc formulation.

Yet, if we consider the sharp tree consisting of the left, upper, and lower arc,

the corresponding cycle basis, shown at the bottom right of Figure 1(b), gives a

formulation which is equivalent to the arc formulation, as stated in Theorem 3. In

particular, the optimal solution we get is x= (3,2,3,2,1), for which Algorithm 1

is able to find a feasible set of potentials.

Algebraic pruning: Assume again nested modules. Consider an arc athat is in

no cycle or only in cycles Cwith gcd(C)strictly smaller than Pa. Assume we

have a solution (x,k)∗to a DENDI-cycle basis formulation of the PESP. The arc

amust lie in the DENDI-tree Tof any such formulation. Therefore, recovering

node potentials from x∗will result in a solution (

,k)′with k′

aPa=kC(a,T)gcd(C).

Thus, the inequality of arc ais also fulfilled modulo gcd(C)—which is strictly

smaller than Pa. This observation allows to simplify a PESP with nested divisors:

Theorem 4. Given a PESP Gwith nested modules containing an arc a with

gcd(C)<Pafor all cycles C ∋a. The PESP G′, resulting from Gby replacing Pa

by its largest divisor P′

a6=Pa, is equivalent to G.

One may repeatedly apply Theorem 4 to simplify the PESP in a pre-processing.

In case the considered arc is in no cycle, its module is ultimately set to 1, which

is equivalent to removing the arc. Indeed any solution for the (after the removal)

disconnected graph can easily be amalgamated to a solution of the original PESP

in a linear time post-processing. Recall, that we can also remove arcs, for which

the difference between upper and lower bound is greater or equal to the module.

Therefore, even reducing to a non-trivial module can result in the arc being ob-

solete. This way we can reduce the dimension of the MIP. A side effect of this

pruning is, that we can assume the following property for the sharp basis found

by the DENDI algorithm:

Observation 1 W.l.o.g. for every arc a a sharp cycle basis contains a cycle C,

such that gcd(C) = Pa.

The basis of the DENDI algorithm is sharp and thus has a tight cycle for each

arc. This will be exploited in the last section, where we seek to give a small set of

strong cuts derived from cycle inequalities.

Cuts and the sharp tree: We now turn to the last ingredient that makes state-of-

the-art solvers for uniform-module PESPs powerful. Solving a uniform-module

PESP cycles are also used to produce a special class of rounding cuts, the so-

called Odijk inequalities:

∑a+∈Cℓa−∑a−∈Cua

P≤kCand ∑a+∈Cua−∑a−∈Cℓa

P≥kC

The key question is, for which cycles one should add the corresponding Odijk

inequalities to the MIP formulation. For the case of uniform modules there is a

well established heuristic reasoning: The right-hand side is rounded down (or up)

by a value between 0 and P−1. If the total value of the right-hand side is large

in comparison to Pthe effect of rounding cannot be large.

Therefore, one is interested in shortest integral cycle bases. There is no polyno-

mial time algorithm know for this problem. Yet, there are many heuristics to find

short integral cycle bases. A standard approach is to construct a fundamental cy-

cle bases from a minimum spanning tree (MST). Here the heuristic idea is, that

the non-tree arcs feature in exactly one cycle, whereas the minimized tree arcs

can occur in several cycles of the basis. Thus, the sum of all cycles will be rather

small, and the Odijk inequalities on average rather tight.

For multiple modules one has to consider a second argument. In this case the

rounding on a cycle Cis between 0 and gcd(C). Assume the cycle Ccontains an

arc awith a significantly smaller module Pathan that of all other arcs inC. Recall,

that we can assume the difference between upper and lower bound on an arc to be

less than its module. Nevertheless, the contribution to the right-hand side of each

other arc bcan be much larger than Pa, because they have larger modules. Still,

the rounding cannot be larger than Pa. If an arc bis in no cycle Cwith gcd(C)

close to its own module Pb, the set of cuts will not have a relevant effect on the

number of choices for xb.

Now, Theorem 4 allows to assume that every arc b∈Ais in at least one cycle

Cwith gcd(C) = Pb. And a sharp cycle basis will for every arc bcontain such

a cycle Cwith tight rounding. So, for multiple-modules PESPs we propose to

choose the following type of cycle basis Bto derive strong Odijk inequalities:

1. Bis a sharp cycle basis.

2. Barises from a sharp tree with minimal sum of arc weights (with respect to

(u−ℓ)) among all sharp trees.

Note, that the weighted version of Algorithm 1 finds a sharp tree as desired here.

4 Computational results

We study twelve instances derived from timtab1 and timtab2, the MIPLIB

PESPinstances1.ThesetwoMIPLIB instances are anonymizedreal-world timetabling

1We like to thank Elmar Swarat for providing us with the raw data of timtab 1 and 2.

problems of a major European railway provider. The second one has only recently

been solved. We changed the original periods of 60 on the nodes randomly to the

nested periods 120,60,30,15 and 5, giving lower probability to the small periods

as they dominate in the transition from node to arc periods. After this transition,

the bounds on the arcs were adjusted relative to the change in period.

On these instances we compare the standard formulation to a sharp cycle base

formulation with the basis’ Odijk inequalities. For each we use CPLEX 10.0

with a timelimit (TL) of 2 hours on a 2.4Ghz processor. The results in Table 1

clearly show the advantage of the formulation that is possible because of the the-

ory developed here. Especially the increase in speed for detecting infeasibility is

striking. Further, all except one of the feasible instances are solved with a bet-

ter gap by the sharp cycle base formulation. (The interested reader is referred to

the appendix for a small example in which one can study the influence of the

formulation explicitly.)

Classical Sharp Tree +Odijks

instance status GAP% time (sec.) status GAP% time (sec.)

mpesp1 feasible 5.99 TL feasible 4.19 TL

mpesp2 feasible 6.13 TL feasible 5.73 TL

mpesp3 feasible 5.58 TL feasible 3.83 TL

mpesp4 feasible 2.94 TL feasible 2.50 TL

mpesp5 feasible 5.33 TL feasible 5.29 TL

mpesp6* feasible 9.81 TL feasible 10.26 TL

mpesp7 feasible 12.09 TL feasible 9.72 TL

mpesp8 feasible 12.87 TL feasible 9.71 TL

mpesp9 - - TL infeasible - 0

mpesp10 - - TL infeasible - 3431

mpesp11 infeasible - 6934 infeasible - 0

mpesp12 infeasible - 657 infeasible - 0

Table 1. multi-period miplib PESP statistics

5 Conclusion

We develop the theory and method to solve the MIPs of real-world multi-module

PESPs with nested modules. Our computations on adjusted MIPLIB instance tes-

tify the superiority of our method.

To this end we introduce the concept of sharp trees which we show to be a pre-

requisite for both a propagation approach to solve GDES and for the strong cycle

basis formulations of the PESP. We show that and how sharp can be found in case

of nested divisors.

The advantage of nested periods for timetable optimization suggests to use nested

periods in practice. But nested periods are also recommendable from the perspec-

tive of quality of service: They yield that more passenger actually experience the

optimized transfer time, because for co-prime periods every transfer time will be

experienced by some passengers.

References

1. CONFORTI M., ZAMBELLI G.: The mixing set with divisible capacities: A

simple approach, LNCS, Volume 5035/2008.

2. CONFORTI M., DISUMMA M., WOLSEY L.: The mixing set with divisible

capacities, in: Proc. of IPCO 2008, Springer.

3. FISCHETTI M., LODI A.: Optimizing over the first Chvatal closure, in: Proc.

of IPCO 2005, Springer.

4. HASSIN R.: A flow algorithm for network synchronization, Operations Re-

search 44, 1996, pp. 570–579.

5. K¨

OHLER E., M¨

OHRING R., N¨

OKEL K., W¨

UNSCH G.: Optimization of

Signalized Traffic Networks, Mathematics Key Technology for the Future,

Springer 2008, pp. 179–180.

6. KHOT, S.: On the power of unique 2-prover 1-round games, Proc. of STOC

2002, ACM, pp. 767–775.

7. LIEBCHEN C.: Periodic Timetable Optimization in Public Transport, Ph.D.

thesis, Technische Universit¨

at Berlin.

8. LIEBCHEN C., PEETERS L.: On cyclic timetabling and cycles in graphs,

Technical Report 761 (2002), Mathematical Institute TU Berlin.

9. LIEBCHEN C., PEETERS L.: Some practical aspects of periodic timetabling,

Operations Research 2001, Springer.

10. LIEBCHEN C., PROKSCH M., WAGNER F. H.: Performance of Algorithms

for Periodic Timetable Optimization, CASPT 2008, Springer, pp. 151–180.

11. LIEBCHEN C., RIZZI R.: Cycles bases of graphs, Technical Report 018

(2005), Mathematical Institute TU Berlin.

12. LIEBCHEN C., RIZZI R.: A greedy approach to compute a minimum cycle

basis of a directed graph, Inf. Process. Lett. 94(3), pp. 107–112.

13. LIEBCHEN C., SWARAT E.: The Second Chvatal Closure Can Yield Better

Railway Timetables, in: Proc. of ATMOS 2008.

14. LINDNER T.: Train Schedule Optimization in Public Rail Transport, Ph.D.

thesis, Technische Universit¨

at Braunschweig.

15. MILLER A., WOLSEY L.: Tight formulations for some simple MIPs and con-

vex objective IPs, Mathematical Programming B 98 (2003), pp. 73–88.

16. NACHTIGALL K.: Exact solution methods for periodic programs,

Hildesheimer Informatik-Berichte 14/93 (1993), Universit¨

at Hildesheim.

17. NACHTIGALL K.: Periodic Network Optimization with different arc frequen-

cies, Discrete Applied Mathematics 69(1-2) (1996), pp. 1–17.

18. NACHTIGALL K.: Cutting planes for a polyhedron associated with a peri-

odic network, Institutsbericht IB 112-96/17, DLR.

19. NACHTIGALL K.: Periodic Network Optimization and Fixed Interval

Timetables, Habilitation, Universit¨

at Hildesheim.

20. ODIJK M.: Construction of periodic timetables, Part1: a cutting plane algo-

rithm, Technical Report 94-61 (1994), TU Delft.

21. ODIJK M.: A constraint generation algorithm for the construction of peri-

odic railway timetables, Transportation Research B 30(6) (1996), pp. 455–

464.

22. PEETERS L.: Cyclic Railway Timetable Optimization , Ph.D. thesis, Erasmus

Universiteit Rotterdam.

23. SERAFINI P., UKOVICH W.: A mathematical model for periodic scheduling

problems, SIAM Journal on Discrete Mathematics 2(4) (1989), pp. 550–581.

24. SCHRIJVER A.: Theory of Linear and Integer Programming, Wiley & Sons,

1986.

A A small example on the power of sharp cycle basis

formulations

We now demonstrate the power of such minimum-sharp trees on a small example.

The following example rises three important observations about the tightness of

IP formulations for PESPs with nested modules.

Example 3. Consider a PESP instance derived from the 5–wheel graph on the

left of Figure 1(c). There are 10 arcs. Let xbe the vector of arcs variables, and

consider the input data of Table 2.

x1x2x3x4x5x6x7x8x9x10

l 1 1 1 1 1 1 1 1 1 1

u 29 29 29 29 29 29 1 2 2 2

c 10 15 45 13 12 18 16 61 34 41

w 28 28 28 28 28 28 0 1 1 1

P 30 30 30 30 30 60 30 30 30 30

Table 2. Input data for the 5–wheel PESP

formulation LP # tight Odijk ineq.s

classical 0 -

sharp-basis 18 1

short sharp-basis 79 2

Table 3. Statistics for the 5–wheel PESP

Note, all periods are equal to 30, except for P6=60. By ℓ,u, and cwe denote

the lower and upper bound and the cost vector. We also define a weight vector

w=u−ℓ, since the tightness of an Odijk inequality can be heuristically mea-

sured as xa−xa. The optimal value of this PESP instance is 1327, and in Table

3 we report some statistics for three different formulations. In particular, we con-

sider the classical PESP formulation and two different cycle basis formulations,

corresponding to the two trees in Figure 1(c). Both trees are sharp, so they give

cycle basis formulations equivalent to the original arc formulation. The tree in the

middle is not minimal among the sharp trees, it contains arcs with large weights.

The tree on the right is a minimum-sharp tree. For each formulation we show the

LP bound and for the cycle basis formulations we also indicate the number of

fully tight Odijk inequalities.

The data in Table 3 show that:

1. thesharpbasisleadstoonefullytight Odijkinequality(x4=x4=0),whereas

the minimum-sharp basis leads to two such inequalities (x1=x1=0, x5=

x5=0),

2. the LP bound of the sharp basis and additionally that of the minimum-sharp

basis improves drastically,

B Pseudocode for the DENDI-algorithm

We give a formal description of the weighted and unweighted DENDI-algorithm

sketched before.

Algorithm 1: The DENDI–algorithm for GDES with nested modules (and arc

weights).

Input: A GDES with nested modules given by a digraph G(V,A), arc tensions x:A→Z,

modules P:A→ {Pr|Pr−1...|P1}(and arc weights w:A→Z).

Output: FAILURE or a feasible solution given by node potentials

, and offsets k, and a

sharp tree Twith ka=0 for all a∈A(T).

Initialize: Super-nodes of level 0: V0={{1}...{n}}. Node potentials:

≡0. Tree:1

T←(V,/0).

for Level 1≤ℓ≤rdo2

Gℓ←G(Vℓ−1,{(s,t,a):s6=t∈Vℓ−1,a= (v,w)∈A,Pa=Pℓ,v∈s,w∈t}).3

Cℓ←The set of connected components in Gℓ.4for C∈Cℓdo5

T(C)←a (minimum for w) spanning tree in C.6

A(T)←A(T)∪A(T(C)).7

end8

Vℓ← {t=∪s∈V(C)s:C∈Cℓ}.

end10

Set

v←0 for an arbitrary node vand propagate

along Taccording to x.11 for a= (v,w)∈A\A(T)do ka←(

w−

v−xa)/Pa.12 if ka/∈Zthen Return FAILURE.13

Return

and T.14

Line 3: The graph Gℓmay contain parallel arcs. They can be distinguished by

their corresponding arc a∈G.Line 7: We slightly misuse notation here: It makes

no sense to add arcs between super-nodes to A(T). Instead, we add a∈A(G):

the arc corresponding to (s,t,a)∈A(T(C)).Line 9: Notice, each element tof Vℓ

contains nodes but no super-nodes.