SPOC 8 "Formulations étendues"

Friday, 2 March, 2012

8ème Séminaire POC


Au laboratoire LIP6 de l’Université Pierre et Marie Curie - Paris 6
4 place Jussieu Paris 6 CEDEX 05

Tour 26 - Premier étage - Couloir 25-26 - Salle 105


Sur le thème

"Formulations étendues"

Pour s’incrire : envoyer un mail à gdt.poc at gmail.com

INSCRITS à la journée JSPOC8


9h30-9h45 Accueil des participants
10h00-12h00 Extended Formulations in Combinatorial Optimization

(Otto-von-Guericke 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.

12h00-13h30 REPAS
13h30-14h15 Using extended formulations to solve MIPs in practice

Mathieu VanVYVE
(CORE, Louvain-La-Neuve)

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
built-in 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 branch-and-bound
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.

14h15-15h00 Linear vs. Semidefinite Extended Formulations : Exponential Separation and Strong Lower Bounds

(Université de Bruxelles)

We solve a 20-year old problem posed by M. Yannakakis and prove that there exists no polynomial-size 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 one-way 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).

15h00-15h15 Questions ouvertes
15h15-15h30 PAUSE
15h30-16h15 Extended formulations for the design of approximation algorithms : an example in inventory control

(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 primal-dual 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 multi-retailer problem, a standard in inventory control.

16h15-17h00 Extended Formulations for the Survivable Network Design Problem with Hop Constraint

(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
hop-constraint 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 so-called natural formulation (formulation based
on the design variables). We also discuss some computational results on the problem.

17h00 Clôture de la journée