IPCO 2008 Summer School
University Residential Center, Bertinoro (ForlìCesena), Italy
May 2930, 2008
The IPCO Summer School will take place immediately after the IPCO conference. The lecturers will be Michele Conforti, Franz Rendl and Martin Skutella.
Lectures
 M. Skutella, An Introduction to Network Flows Over Time
 M. Skutella, Dynamic Network Flows
 F. Rendl, Solution methods for SDP arising from combinatorial optimization problems (part 1)
 F. Rendl, Solution methods for SDP arising from combinatorial optimization problems (part 2)
Lectures' abstracts
Michele Conforti
Extended Formulations in Integer Programming and Combinatorial
Optimization

An extended formulation of a polyhedron P is a system of inequalties S that defines a
polyhedron Q in a higher dimensional space such that P is the
projection of Q in the original space. If one can efficiently
optimize a linear function over Q then one can optimize it over
P, and if S is a "small" system, optimizing over Q can be
efficiently done via Linear Programming. We first discuss a result of Yannakakis on the existence of such small
systems and then survey some extended formulations in
Combinatorial Optimization, related to matchings, cuts, stable
sets, hamiltonian tours, etc. Extended
formulations can be derived from effcient enumeration
algorithms, such as Dynamic Programming and this has some
interesting applications. For some selected
mixedinteger programs, an optimal solution can be easily
determined, once a set of optimal fractional parts of the
continuos variables is found. This is the case e.g. for some
problems arising in production planning. We show how this
property can be used to construct small extended formulations
for the convex hull of the feasible solutions. We
finally discuss how to explicitly obtain from a system S that
defines Q a system of inequalities that defines P and survey
some of the results known in this area.
Franz Rendl
Solution methods for SDP arising from combinatorial
optimization problems

Semidefinite programs have turned out to be a useful
tool in approximating some NPhard optimization problems. In
this lecture several of these SDP models will be investigated. The
main focus will be on how these SDP can be solved in
practice. While interiorpoint based methods are known to have
nice convergence properties, they are too slow once the
problem size gets large. Several very recent algorithmic
approaches will be explained, which are capable of dealing with
large scale SDP. The main features of these algorithms will
be described, and some practical experience with these methods
applied to MaxCut, Stable Set, Coloring and the Quadratic Assignment
Problem will be given.
Martin Skutella
Dynamic Network Flows

A crucial characteristic of network flows occuring in
realworld applications is flow variation over time. This characteristic
is not captured by classical "static" network flow models known from
the literature. Moreover, apart from the effect that flow values on
arcs may change over time, there is a second temporal dimension in
many applications: Usually, flow does not travel instantaneously through
a network but requires a certain amount of time to travel through
arcs. Already back in the 1950s Ford and Fulkerson introduced the
notion of dynamic flows which comprises both temporal features mentioned
above. They consider networks with capacities and transit times on the
arcs and give an efficient algorithm for the problem of sending the
maximum possible amount of flow from a source to a sink within a given
time horizon. In order to get an intuitive understanding of dynamic
flows, one can associate arcs of the network with pipes in a pipeline
system for transporting some kind of fluid. The length of each
pipeline determines the transit time of the corresponding arc while the
width determines its capacity. The intention of the
lectures is to give an introduction into the area of flows over time and
discuss both classical and more recent results.