IPCO 2008 Summer School
University Residential Center, Bertinoro (Forlì-Cesena), Italy
May 29-30, 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' program
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 mixed-integer 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 NP-hard 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 interior-point 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 Max-Cut, Stable Set, Coloring and the Quadratic Assignment Problem will be given.
Martin Skutella
Dynamic Network Flows
A crucial characteristic of network flows occuring in real-world 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.
University Residential Center, Bertinoro (Forlì-Cesena), Italy
May 29-30, 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' program
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 mixed-integer 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 NP-hard 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 interior-point 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 Max-Cut, Stable Set, Coloring and the Quadratic Assignment Problem will be given.
Martin Skutella
Dynamic Network Flows
A crucial characteristic of network flows occuring in real-world 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.
Commenti