DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
(titres de publication, de périodique et noms de colloque inclus)
2014-06-23 - Colloque/Présentation - poster - Anglais - 1 page(s)

Vandaele Arnaud , "A refined rectangle covering number as lower bound for extended formulations" in The 17th Conference on Integer Programming and Combinatorial Optimization, Bonn, Allemagne, 2014

  • Codes CREF : Mathématiques (DI1100), Recherche opérationnelle (DI1150)
  • Unités de recherche UMONS : Mathématique et Recherche opérationnelle (F151)
  • Instituts UMONS : Institut de Recherche sur les Systèmes Complexes (Complexys)
Texte intégral :

Abstract(s) :

(Anglais) An extended formulation of a polytope P is a polytope Q of higher dimension which can be projected onto P. When P is associated with combinatorial optimization problems, it is especially of interest to find an extension Q with fewer facets as less inequalities must be used to describe the polytope. Hence the problem is to determine the extension complexity which is the smallest number of facets that an extended formulation can have. Most methods used to compute lower bounds on the extension complexity are based on the rectangle covering number of the slack matrix of the polytope. Such bounds only rely on the combinatorial structure of the problem. In this work, we proposed a refined bound based on the rectangle number which uses the true numbers of the slack matrix. This bound is greater or equal to the rectangle covering number. This is why we present also several examples of application of this bound where new results can be presented when the bound is tight with the extension complexity.