9h309h45 
Accueil des participants 
10h0012h00 
Extended Formulations in Combinatorial Optimization
Volker KAIBEL
(OttovonGuericke Universität Magdeburg)
The polytopes that seem to be associated naturally with combinatorial
optimization problems tend to have rather complicated linear
descriptions. However, in some cases there are very simple, nice, and
easy to handle extended formulations for such polytopes, i.e., linear
descriptions of higher dimensional polyhedra that can be projected
linearly to the polytopes of interest. In this lecture, we discuss some
aspects of this approach that has attracted quite some attention
recently. Besides introducing the concept, we present some selected
examples of extended formulations in particular meant to overview some
techniques for their construction, and we discuss fundamental
limitations of the approach, where we mainly concentrate
on combinatorial obstructions that sometimes prevent the existance of
small extended formulations.

12h0013h30 
REPAS 
13h3014h15 
Using extended formulations to solve MIPs in practice
Mathieu VanVYVE
(CORE, LouvainLaNeuve)
We consider the following practical setting. The MIP that you want to
solve is hard in the sense that the LP relaxation is weak, and the
builtin cutting planes of your favourite solver are not very effective.
Moreover, you know how to reformulate part of the problem using an
extended formulation, yielding much sharper bounds. Unfortunately the
resulting LP relaxation is too large to be used in a branchandbound
framework.
We describe several practical approaches to leverage the knowledge of
the extended formulation. The first one is to use an approximate
extended formulation, that is ideally nearly as strong but more compact
than the original one. The second one is to solve the LP relaxation of
the extended formulation, and then heuristically fix some variables and
solve this restricted MIP, generating a heuristic solution, but with a
guarantee of quality. The third one is to use the extended formulation
to quickly generate strong valid inequalities in the original variable
space. We illustrate these three approaches on practical examples.

14h1515h00 
Linear vs. Semidefinite Extended Formulations : Exponential Separation and Strong Lower Bounds
Samuel FIORINI
(Université de Bruxelles)
We solve a 20year old problem posed by M. Yannakakis and prove that there exists no polynomialsize linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the maximum cut problem and the stable set problem.
These results follow from a new connection that we make between oneway quantum communication protocols and semidefinite programming
reformulations of LPs.
This is a joint work with Serge Massar (ULB), Sebastian Pokutta
(Erlangen), Hans Raj Tiwary (ULB), Ronald de Wolf (CWI).

15h0015h15 
Questions ouvertes 
15h1515h30 
PAUSE 
15h3016h15 
Extended formulations for the design of approximation algorithms : an example in inventory control
Gautier STAUFFER
(Université de Bordeaux)
Linear programming plays a central role in the design of efficient
approximation algorithms. In particular, many approximation algorithms
builds on the ’natural’ linear programming formulation of the problem
and apply some rounding techniques and/or primaldual schemes. In this
talk, we show how extended formulations can help in the design of
approximation algorithms. We illustrate those findings on the one
warehouse multiretailer problem, a standard in inventory control.

16h1517h00 
Extended Formulations for the Survivable Network Design Problem with Hop Constraint
Ibrahima DIARRASSOUBA
(Université du Havre)
Survivability problems are one of the key issues when designing telecommunication networks. In these problems, one look for a network which is still functionning in case of failure of a given number of equipments of that network. One may also combine survivability issues with some routing constraints such as length bound on the routing paths (hop constraint).
In this talk, we consider the survivable network design problem with
hopconstraint in undirected networks. We present extended formulations for the problem in the case where the length of the routing paths is bounded by 3.
We compare these formulations in terms of linear relaxation and
compare them with the socalled natural formulation (formulation based
on the design variables). We also discuss some computational results on the problem.

17h00 
Clôture de la journée 