Accueil > Séminaires POC > SPOC 11 : 26/09/14

SPOC 11 : 26/09/14

Casser les symétries en programmation mathématique

jeudi 11 septembre 2014, par fouilhoux



http-equiv="content-type" />
journee.html

<p
style="text-align: center; font-weight: bold; color: rgb(0, 0, 153);"
class="spip">

11ème Séminaire POC

class="spip">

Le VENDREDI 26 SEPTEMBRE 2014



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

<a
href="http://www.lip6.fr/informations/comment.php"> Accès

Sur le thème

"Casser les symétries en programmation mathématique"



Pour s’incrire : Merci de remplir le formulaire d’inscription


<a
href="spip.php?article47">INSCRITS à la journée SPOC11

9h30-10h00 Accueil des participants
10h00-12h00 Symmetry and Optimization

François Margot
(Tepper School of Business, Carnegie Mellon University)

Présentation en pdf


Optimization problems have sometimes natural symmetries : dispatching jobs on identical machines, partitioning tasks into subsets with specific properties, for example. The presence of symmetry usually makes the problem much harder to solve, in particular for enumeration techniques such as Branch-and-Bound or Backtracking. Techniques for handling symmetries have been devised and they can be divided into five types : Perturbations, Reformulations, Symmetry-breaking inequalities, .Symmetry Breaking during Search, and Isomorphism Pruning. This talk discusses these five basic approaches, as well as symmetry detection, primarily for Integer Linear Programs, but most of the ideas can be used for Mixed Integer Nonlinear Programs.

The last part of the code present some of the features of the open-source software ISOP implementing Isomorphism Pruning.

12h00-14h00 REPAS
14h00-15h00 Dealing with Symmetries through/in Reformulation and Decomposition Approaches

Francois Vanderbeck
(Institut de Math., Université de Bordeaux & INRIA, équipe RealOpt)


To tackle symmetries in the representation of solutions to
In formulating combinatorial optimization problems, one can introduce
alternative representations of a given solution.
Such symmetry drawback, can often be avoided by an appropriate selection of decision variables, sometimes in a higher dimensional space, leading
to an extended formulation (Dantzig-Wolfe reformulation being a
special case). We shall review some examples of such reformulation,
showing that one might also be introducing new symmetries in doing so ;
or one might just be hiding symmetries that re-arise in the branching
procedure. The second part of the talk will focus of symmetries that
arises in solving linear programs (degeneracy and multiple optima), in
particular in column generation approaches. We
shall review some methods to handle them that can be understood as
stabilization techniques.

15h00-15h15 QUESTIONS
15h15-15h30 PAUSE
15h30-16h00 Reformulation compacte sans symétrie du problème de coloration


Denis Cornaz
(LAMSADE, Université Paris-Dauphine)

Présentation en pdf


Le problème de coloration consiste à partitionner l’ensemble des sommets
d’un graphe en sous-ensembles stables.
Sa formulation la plus naturelle utilise un nombre exponentiel de variables.
Une autre formulation, compacte elle, s’appuie sur la réduction
classique du problème de coloration au problème du stable maximum
mais, avec cette formulation, chaque partition admet un nombre
exponentiel de représentations symétriques.
Nous proposons une seconde réduction du problème de coloration à celui
du stable maximum.
Il s’agit de construire un graphe auxiliaire S(G) d’ordre O(n²) où les
stables de S(G) sont en bijection avec les colorations de G.
Nous discuterons des propriétés du graphe S(G). Notamment il permet
d’améliorer substantiellement la qualité de la borne inférieure
pour la coloration obtenue par la programmation semi-définie (ie avec la
fonction théta Lovasz).

16h00-16h30 Breaking symmetries in the bin packing problem and applications in network design

Amal Benhamiche
(Lamsade, Université de Paris-Dauphine)

Présentation en pdf


We are interested in the Unsplittable Non-Additive Capacitated Network Design (UNACND) problem. This is a network design problem which consists, given a graph G = (V, A), a set of commodities K and a set of non-additive capacities, in determining the number of capacities to install on the arcs of G so that a routing path may be associated with every commodity. This problem when restricted to a single arc reduces to the bin packing problem. We focus on this restriction and propose a new "aggregated" formulation in order to overcome the symmetries of the bin packing problem and study the polyhedron of its solutions. We then introduce two classes of facet-defining valid inequalities and embed them whithin a Branch-and-Cut algorithm the solve efficiently the UNACND problem. Finally, we show some numerical experiments for SNDlib based instances.

16h30-16h45 QUESTIONS
16h45 Clôture de la journée



Messages