SPOC 11 "Casser les symétries en programmation mathématique"
Date:
Friday, 26 September, 2014
11ème Séminaire POC
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
Sur le thème
"Casser les symétries en programmation mathématique"
| 9h30-10h00 | Accueil des participants |
| 10h00-12h00 | Symmetry and Optimization
François Margot Présentation en pdfOptimization 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
To tackle symmetries in the representation of solutions to |
| 15h00-15h15 | QUESTIONS |
| 15h15-15h30 | PAUSE |
| 15h30-16h00 | Reformulation compacte sans symétrie du problème de coloration
Denis Cornaz Présentation en pdf
Le problème de coloration consiste à partitionner l’ensemble des sommets |
| 16h00-16h30 | Breaking symmetries in the bin packing problem and applications in network design
Amal Benhamiche Présentation en pdfWe 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 |