| 9h30-9h45 |
Accueil des participants |
| 10h00-12h00 |
Extended Formulations in Combinatorial Optimization
Volker KAIBEL
(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
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.
|
| 14h15-15h00 |
Linear vs. Semidefinite Extended Formulations : Exponential Separation and Strong Lower Bounds
Samuel FIORINI
(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
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 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
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
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 |
