*   Domaine de compétence Optimisation Combinatoire   *
  *    Séminaire
  o    2014 - 2015
  o    2013 - 2014
  o    2012 - 2013
  o    2011 - 2012
  o    2010 - 2011
  o    2009 - 2010
  o    2008 - 2009
  o    2007 - 2008
  o    2006 - 2007
  o    2005 - 2006
  o    2004 - 2005
  o    2003 - 2004
  *    Evénements
  *    Liens

Séminaires 2014 - 2015

Ceci est la page web du séminaire de l'équipe Optimisation Combinatoire du laboratoire G-SCOP, à Grenoble.

Sauf mention contraire, le séminaire de Mathématiques Discrètes a lieu le jeudi à 14h30 en Salle C319. Les responsables sont Louis Esperet et András Sebő, n'hésitez pas à les contacter.

27 novembre 2014 Hyung-Chan An
(EPFL, Lausanne)
LP-Based Algorithms for Capacitated Facility Location
25 novembre 2014 Ola Svensson
(EPFL, Lausanne)
A Simple O(loglog(rank))-Competitive Algorithm for the Matroid Secretary Problem
6 novembre 2014 Marthe Bonamy
(LIRMM, Montpellier)
Algorithmes de pré-traitement de graphes
23 octobre 2014 Frédéric Maffray
(G-SCOP)
Coloration de certains graphes parfaits
2 octobre 2014 François Margot
(Tepper School of Business, Carnegie Mellon, USA)
Cut generation through binarization
  • Jeudi 27 novembre 2014 (à 14h30): Hyung-Chan An (EPFL, Lausanne) : LP-Based Algorithms for Capacitated Facility Location

    Linear programming has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic methodologies, such as LP-rounding and primal-dual method, have been applied to and evolved from algorithms for this problem. Unfortunately, this collection of powerful algorithmic techniques had not yet been applicable to the more general capacitated facility location problem. In fact, all of the known algorithms with good performance guarantees were based on a single technique, local search, and no linear programming relaxation was known to efficiently approximate the problem.

    In this paper, we present a linear programming relaxation with constant integrality gap for capacitated facility location. We demonstrate that the fundamental theories of multi-commodity flows and matchings provide key insights that lead to the strong relaxation. Our algorithmic proof of integrality gap is obtained by finally accessing the rich toolbox of LP-based methodologies: we present a constant factor approximation algorithm based on LP-rounding.

    Joint work with Mohit Singh and Ola Svensson.

  • Mardi 25 novembre 2014 (à 14h30): Ola Svensson (EPFL, Lausanne) : A Simple O(loglog(rank))-Competitive Algorithm for the Matroid Secretary Problem

    The last decade has seen an increased interest in generalizations of the secretary problem, a classical online selection problem. These generalizations have numerous applications in mechanism design for settings involving the selling of a good (e.g. ads) to agents (e.g. page views) arriving online. The matroid secretary problem is one of the most well-studied variants. It is general enough to deal with complex settings and, at the same time, it is sufficiently restricted to admit strong algorithms. A famous conjecture states that there is in fact a O(1)-competitive algorithm for the matroid secretary problem. This is an online algorithm that, in expectation and up to a constant factor, performs as well as any offline algorithm with perfect information.

    In this talk, we present a new method that improves on the previously best algorithm, in terms of simplicity and its competitive ratio. The main idea of our algorithm is to decompose the problem into a distribution over a simple type of matroid secretary problems which are easy to solve. We show that this leads to a O(loglog(rank))-competitive procedure.

    This is joint work with Moran Feldman (EPFL) and Rico Zenklusen (ETHZ).

  • Jeudi 6 novembre 2014 (à 14h30): Marthe Bonamy (LIRMM, Montpellier) : Algorithmes de pré-traitement de graphes

    Étant donné un problème paramétré de graphes (partition des sommets en k stables, ou en une forêt et au plus k sommets, détection d'un ensemble dominant de taille k, etc), on s'intéresse à des algorithmes efficaces (i.e. de complexité polynomiale) pour simplifier une instance de ce problème. "Simplifier" peut avoir plusieurs sens selon le résultat désiré. Intuitivement, si on cherche à k-colorier un graphe G, et que ce graphe G contient un sommet de degré au plus k-1, on sait que ce sommet n'aura pas d'influence sur le résultat et peut donc être enlevé du graphe, sans qu'il y ait perte d'information. De même, si ce graphe G contient un sommet qui est adjacent à tous les autres, on sait d'ores et déjà qu'il devra recevoir une couleur distincte de toutes les autres apparaissant sur le graphe, et on peut simplement le supprimer du graphe et chercher à colorier le reste avec seulement k-1 couleurs.

    Après avoir identifié un certain nombre de telles règles de simplification, on veut garantir l'efficacité de l'algorithme de pré-traitement correspondant, au moins sur une sous-classe de graphes (par exemple les graphes planaires). Selon le résultat voulu, on peut chercher à montrer que l'algorithme aboutit toujours au graphe vide, ce qui nous assure que la classe de graphes considérée admet toujours une solution (par exemple les graphes planaires pour le problème de 4-coloration). On peut plus généralement chercher à montrer que l'algorithme aboutit toujours à un graphe de taille bornée par une fonction de k, ce qui nous assure que, à k fixé, on peut en temps polynomial décider s'il y a une solution et en trouver une le cas échéant. Ce type de résultat est intéressant en particulier pour des problèmes que l'on sait NP-durs en général.

    Ici, on s'intéresse au problème Feedback Vertex Set (combien de sommets doit-on enlever à un graphe pour obtenir une forêt ?) paramétré par la taille de solution (suffit-il d'enlever k sommets ?), dans le cadre des graphes planaires. On présente un algorithme de pré-traitement qui aboutit en temps linéaire à un graphe planaire de taille au plus 13k. Il s'agit d'une collaboration avec Lukasz Kowalik (Université de Varsovie)

  • Jeudi 23 octobre 2014 (à 14h30): Frédéric Maffray (G-SCOP) : Coloration de certains graphes parfaits

    Dans un graphe G une paire d'amis est une paire de sommets x et y tels que tous les chemins de x à y sans corde sont pairs. L'utilisation des paires d'amis a permis de fabriquer des algorithmes de coloration efficaces pour diverses classes de graphes parfaits. Dans ce contexte, une conjecture de Reed et Everett est encore ouverte. On présentera des résultats nouveaux dans cette direction, concernant les graphes sans C4.

  • Jeudi 2 octobre 2014 (à 14h30): François Margot (Tepper School of Business, Carnegie Mellon) : Cut generation through binarization

    Cutting planes (or cuts) are an essential component of state-of-the-art solvers for Mixed-Integer Linear Program (MILP). Among the many classes of cuts, split cuts are one of the most useful and essential. It is known that split cuts are able to close a large part of the integrality gap for usual benchmark instances, but this requires a large cpu time. Empirical split cut generation aims at generating fast the most useful split cuts. Advances in this direction usually focus on finding strong disjunctions, involving several variables. In this talk, our aim is to use combinations of simple split cuts, i.e. cuts obtained using disjunctions of the form x_j = 0 or x_j = 1 for a binary variable x_j to generate cuts that have similar strength as general split cuts.

    Our cut generation scheme is based on two components. First, we use a binarization of general integer variables (i.e., replacing a general integer variable by a sum of binary variables), augmented by additional symmetry breaking constraints. This binarization was introduced by Roy for generating strong Lift-and-Project cuts. Second, we then use rank-2 simple-split cuts, i.e, cuts that can be obtained as a simple split cut for a polyhedron obtained by adding all simple split cuts for the binarization of the problem. We show that for a pure integer problem with two integer variables, these cuts are sufficient to obtain the integer hull of the problem, but that this does not generalize to problems in higher dimensions. We also give an algorithm to compute an approximation of the rank-2 simple split cut closure. We report empirical results on 22 benchmark instances showing that the bounds obtained compare favorably with those obtained with other approximate methods to compute the split closure or lattice-free cut closure. It gives a better bound than the split closure on 6 instances while it is weaker on 9 instances, for an average gap closed 3.8% smaller than the one for the split closure.

    Joint work with Pierre Bonami, IBM ILOG CPLEX.