Equipe Optimisation Combinatoire 
Séminaires 2005 - 2006
- 22 juin 2006 : Oleg Karpenkov
(Paris Dauphine) : Symmetries of lattice polytopes. Regular lattice
polytopes.
Euclidean regular polytopes were explicitly described by L.Schlafli. Further, P.McMullen proved that the combinatorial structure of any regular abstract combinatorical polytope coincides with the structure of some Euclidean regular polytopes. In this talk for any dimension n we give a complete descriptgon of lattice convex polytopes in R^n that are regular with respect to the group of affine transformations preserving the lattice. In conclusion we discuss some possible applications of the description to lattice geometry and theory of multidimensional continued fractions, and introduce some unsolved problems.
- 13 juin 2006 : Attila Sali
(Budapest) : Parameterized Matching with Mismatches.
The problem of approximate parameterized string searching consists of finding, for a given text $x = x_1x_2...x_n$ and pattern $y=y_1y_2...y_m$ over respective alphabets $\Sigma_t$ and $\Sigma_p$, the injection $\pi_i$ from $\Sigma_p$ to $\Sigma_t$ maximizing the number of matches between $\pi_i(y)$ and $x_ix_{i+1}...x_{i+m-1}$ $(i = 1,2, ... n-m+1)$. We examine the special case where both strings are run-length encoded, and further restrict to the case where one of the alphabets is binary. For this case, we give a construction working in time $O( n + (r_p \times r_t) ~ \alpha( r_t) ~ \log ( r_t)) $, where $r_p$ and $r_t$ denote the number of runs in the corresponding encodings for $y$ and $x$, respectively, and $\alpha$ is the inverse of the Ackermann's function. We also give effective solution for the case of general alphabets.
- 15 mai 2006 : Endre Boros
(Rutgers) : Vertex generation is hard.
A classical problem in polyhedral combinatorics is to find the vertices of a given polyhedron. A decision variant of this, proposed by Lovasz (1992), considers a polyhedron P, represented by a set of linear inequalities, and a set V of its vertices, and asks to decide whether V contains all vertices of P, or not. The vertex generation problem has many applications, and was considered for numerous special cases. In all known special cases it is possible to generate all vertices efficiently (e.g., for simple polytopes, 0-1 polytopes, polytopes in fixed dimension, etc.). We show that in general however vertex generation is a hard problem, e.g., the above mentioned decision problem is NP-hard. We also show that this problem is equivalent to many other problems, related to convex geometry and/or to systems of linear inequalities and equalities. For instance, our results imply that generating minimal infeasible subsystems of a given infeasible linear system is also hard. (Joint results with K. Borys, K. Elbassioni, V. Gurvich and L. Khachiyan.)
- 28 avril 2006 : Zoltán
Szigeti
(Paris Dauphine) : L'amélioration de la fiabilité des réseaux.
Comment améliorer la fiabilité d'un réseau ? Comment rendre une structure statique plus sûre ? Ces questions se traduisent en théorie des graphes comme le problème d'augmenter l'arête-connexité d'un graphe ou d'un graphe biparti en ajoutant un nombre minimum de nouvelles arêtes. De tels problèmes seront l'objet de cet exposé.
- 20 avril 2006 : Nicolas Trotignon
(Paris 1) : Décomposition des graphes de Berge et détection des skew
partitions paires.
La "skew partition paire" est un raffinement de la skew partition de Chvatal. C'est l'une des décompositions qui a permis à Chudnovsky, Robertson, Seymour et Thomas de prouver la conjecture forte des graphes parfaits. On montre que le problème consistant à décider si un graphe donné possède une skew partition paire est NP- difficile. On donne un algorithme en O(n9) pour ce même problème restreint aux graphes de Berge. Cet algorithme repose sur un nouveau théorème de décomposition des graphes de Berge, qui généralise ceux connus jusqu'à présent.
- 13 avril 2006 : A. Ridha Mahjoub
(Clermont-Ferrand) : Optimisation Combinatoire et Conception de Réseaux.
Les techniques d'optimisation combinatoires se sont avérées très efficaces pour formuler, analyser et résoudre à l'optimum des problèmes concrets difficiles. En particulier, plusieurs problèmes de conception de réseaux ont été formulés comme des modèles d'optimisation combinatoire. Avec l'introduction de nouvelles technologies de pointe telle que la technologie des fibres optiques, le domaine des télécommunications a connu un développement considérable ces dernières années. Aujourd'hui, il ne s'agit plus d'assurer seulement la transmission de sons, mais plus généralement celle de données. En plus celle-ci ne cesse d'augmenter en volume (comme dans les réseaux Internet). En conséquence, les opérateurs de télécommunications sont souvent confrontés à des problèmes de synthèse de réseaux composites. Ces problèmes concernent plutôt la planification à moyen ou à long terme, et consistent à trouver la topologie optimale du réseau (en terme de liens) et le dimensionnement pour écouler la demande. Très souvent, des études de fiabilité (sécurisation de réseaux) viennent se greffer à ces problèmes de synthèse de réseaux. En effet il est crucial au moment de la conception du réseau de tenir compte des possibilités de panne de liaisons ou de nœuds dans le réseau. Les fibres optiques ont une capacité presque illimitée, et une rupture dans le réseau peut être de lourdes conséquences. Pour cela la fiabilité d'un réseau de télécommunications est toujours un objectif principal dans sa conception.
Nous discutons d'un modèle général de conception de réseaux fiables. Nous étudions le problème de séparation pour certaines familles de contraintes valides. Nous étudions aussi la relaxation linéaire du problème et caractérisons, dans certains cas, les graphes pour lesquels cette relaxation est entière. Nous discutons enfin de certaines applications algorithmiques dans le cadre d'une méthode de coupes pour le problème.
- 06 avril 2006 : Frédéric Gardi
(Experian-Prologia) : Optimisation de plans de financement immobiliers.
Bien que le champ d'application traditionnel de la recherche opérationnelle demeure autour des métiers de l'industrie, de nombreux problèmes émergent dans les secteurs de la finance, de la banque et de l'assurance, faisant apparaitre un besoin d'aide à la décision. Dans le domaine financier, plusieurs problèmes ont été étudiés dont l'optimisation de portefeuille, devenu un classique du genre, ou encore l'ordonnancement des mouvements de trésorerie. Les applications de la recherche opérationnelle dans les domaines de la banque ou de l'assurance sont plus rares: les livres consacrées à leurs fondements mathématiques ne mentionnent rien à ce sujet et il est difficile de trouver des articles traitant de ces sujets dans la littérature scientifique ou spécialisée. Pourtant, les métiers de la banque et de l'assurance, en particulier l'actuariat, sont des métiers complexes, souvent très techniques, dans lesquels la recherche opérationnelle encore absente est amenée à jouer un rôle important. En effet, la complexité croissante des produits ainsi que des réglementations qui les régissent, obligent les différents acteurs du domaine à s'équiper d'outils informatiques avancés d'aide à la décision, voire d'optimisation, pour faire face à la concurrence. Dans cet exposé, nous abordons une problématique d'actualité dans le secteur bancaire français : l'optimisation de plans de financement immobiliers.
Le financement d'une opération immobilière requiert d'importantes sommes d'argent, généralement prêtées par une banque ou un organisme de crédit. Si certaines banques peuvent proposer des financements adossés à des assemblages de prêts, ceux-ci demeurent limités tant par la technicité de ces prêts que par les outils de calculs classiques qui aident à les composer. Dans leur grande majorité, les plans de financement se contentent d'un seul prêt dont l'échéance est constante sur la durée de celui-ci. Une grande banque française, qui avait préalablement fait évoluer sa gamme de produits immobiliers vers des technicités permettant plus de souplesse dans le remboursement, souhaitait pratiquer des assemblages de prêts afin de proposer des plans de financement les plus compétitifs possibles. Pour aider les chargés de clientèle dans ce travail et être certain de proposer les meilleures solutions à ses clients, cette banque française a décidé d'intégrer à son nouvel outil informatique d'instruction de prêts immobiliers - entièrement développé par la société EXPERIAN-PROLOGIA - un module d'optimisation de plans de financement immobiliers. Ce module, qui a demandé près de deux ans de recherche et développement, est entré en production dans le réseau des 2000 agences de cette grande banque en ce début d'année.
- 31 mars 2006 : Claude Lemaréchal
(INRIA Grenoble) : Le problème des coupes, vu sous l'angle de
l'analyse convexe.
Couper, c'est renforcer une relaxation pour améliorer la borne inferieure dans un algorithme de type séparation-évaluation ; c'est ce que font par exemple les coupes disjonctives. Le problème se pose alors de trouver de "bonnes" coupes. Ce problème est généralement étudié dans le cadre restreint de la programmation linéaire. Dans ce séminaire, on étudie ce problème de façon intrinsèque. Les concepts utiles sont maintenant ceux de l'analyse convexe fondamentale (fonctions d'appui, cônes normaux, enveloppes convexes,...), qui remplacent les notations matricielles habituelles.
- 31 mars 2006 : Gérard Cornuéjols
(Marseille) : Les matrices de Lehman.
On appelle matrices de Lehman des matrices carrées A et B a éléments 0,1 telles que AB=E+kI ou E est une matrice n x n de 1 et k est un entier positif. Ces matrices figurent de façon proéminentes dans le théorème de Lehman sur les matrices minimalement non idéales. Il y a deux choix de k pour lesquels on connait une infinité de solutions a cette équation matricielle. Les plans projectifs finis sont obtenus lorsque n=k2+k+1 et B est la transposée de A, et ils ont fait l'objet d'une étude poussée depuis de nombreuses années. L'autre classe est obtenue lorsque k=1 et n est quelconque, et l'on sait très peu de choses dans ce cas-la. Cornuejols, Guenin et Tuncel ont étudié ces matrices récemment et ils les classifient d'après leur similarité aux matrices circulantes. Cet expose présentera ces résultats.
- 30 mars 2006 : Pierre Charbit
(Paris 7) : Les digraphes de majorité.
Etant donné une famille d'ordres linéaires sur un ensemble fini {1,..n}, on peut construire un digraphe en prenant comme ensemble d'arcs les couples (i,j) pour lesquels i apparait avant j dans plus d'une certaine proportion r des ordres de la famille. Je montrerai comment cette classe de digraphes, appelée digraphes de majorité, peut être mise en relation avec une conjecture célèbre de théorie des graphes, la conjecture de Caccetta-Häggkvist (1978). Cette question peut s'énoncer en disant que si un digraphe a un gros degré sortant en chaque sommet, alors il doit contenir des petits circuits orientés. Il est facile de voir que ces digraphes de majorité ont la particularité d'avoir des petits feedback arc set, un feedback arc set étant un ensemble d'arcs dont la suppression rend le digraphe acyclique. La détermination de la taille minimale d'un tel ensemble est un problème dont on sait depuis longtemps (Karp 1972) qu'il est NP-dur pour la classe des digraphes. Il avait été conjecturé par Bang-Jensen et Thomassen (1992) que ce problème restait NP-dur pour la classe des tournois. Je donnerai une idée de la preuve de ce résultat obtenu en 2005 en collaboration avec Stephan Thomassé et Anders Yeo.
- 29 mars 2006 :
Anass Nagih
(Paris 13) : Optimisation et ré-optimisation dans les systèmes de production
complexes-application à la planification en transport.
Les graphes colores ont été introduits pour répondre a un besoin de modélisation des réseaux multiniveaux dans une optique de planification de la tolérance aux pannes. Ils découlent du concept de Shared Risk Resource Group (SRRG) ou groupe de ressources partageant un risque d'indisponibilité. Par exemple dans un réseau de télécom, deux connections routées via un même câble tombent en panne simultanément lorsque ce câble est coupe, ces deux connections partagent donc un risque et ainsi forment un SRRG. Un graphe colore est un graphe dont les arêtes sont partitionnées en couleurs. Dans les graphes classiques de nombreux problèmes consistent a trouver des ensembles d'arêtes vérifiant certaines propriétés (chemin, coupe...). Or dans un graphe coloré les arêtes sont liées entre elles par leur couleur et non plus indépendantes et la donnée des arêtes ne suffit plus à déterminer la structure du graphe. C'est pourquoi dans les graphes colores, les problèmes étudies consistent a trouver des ensembles de couleurs. En particulier, on définit un chemin coloré entre deux sommets comme un ensemble de couleur tel que le sous graphe induit par ses arêtes contient un chemin au sens classique entre ces sommets. De la même façon on définit une st-coupe colorée, une coupe colorée et un arbre couvrant coloré. Nous verrons que la complexité et l'approximabilité des problèmes d'optimisation associes (coupe colore minimum ...) sont très différentes de celles de leurs équivalents classiques.
- 23 mars 2006 : Marie-Emilie Voge
(Lille 1) : Graphes colorés, définitions et complexité des
problèmes d'optimisation.
Les travaux de recherche présentés dans cette exposé s'inscrivent dans le cadre de la résolution globale et efficace de problèmes d'optimisation combinatoire de grande taille, issus notamment de la planification en transport, avec des volets théoriques, algorithmiques et applicatifs.
Le travail de recherche présenté ici concerne les problèmes de construction de rotations d'équipages en transport aérien et leur résolution par des méthodes basées sur la génération de colonnes. Il s'agit d'améliorer la qualité des solutions produites par le problème auxiliaire tout en réduisant le temps de résolution de chacune de ses instances ainsi que le nombre global d'itérations du schéma itératif. Les approches proposées sont basées - d'une part sur des réductions de l'espace des états par agrégation des ressources - d'autre part sur l'utilisation de la ré-optimisation en exploitant l'historique des résolutions des différentes instances du processus. Les principaux résultats théoriques et algorithmiques ont été validés expérimentalement sur des instances de la compagnie Air Canada issus de problèmes de planification opérationnelle.
- 09 mars 2006 : Yann Vaxès
(Université de la Méditerrannée) : Augmentation de graphe sous contrainte de
diamètre.
Dans cet exposé, nous nous intéressons au problème de conception de réseau suivant : Etant donné un graphe G=(V,E), trouver un nombre minimum d'arêtes à ajouter à G pour obtenir un graphe G'=(V,E U E') dans lequel chaque paire de sommets est à distance au plus D. Nous présentons quelques résultats de complexité et d'approximation concernant ce problème. En particulier, dans le cas où le graphe de départ est un arbre, nous présentons des algorithmes polynomiaux qui permettent d'obtenir des solutions dont le côté est inférieur à 2 fois l'optimum dans le cas d'un diamètre pair et à $2+1/\delta$ fois l'optimum dans le cas d'un diamètre impair. Nous présentons également quelques questions qui se posent lorsque l'on veut généraliser notre approche au cas des graphes planaires.
Travail en collaboration avec Victor Chepoi, Bertrand Estellon et Karim Nouioua.
- 09 mars 2006 : Attila Bernath (Budapest) : Source location.
- 20 février 2006 : Frédéric Meunier
(ENPC) : Les sigma-jeux.
Frédéric Meunier nous parlera des "\sigma-jeux" un jeu sur lequel on lit beaucoup dans la litérature de vulgarisation des mathématiques et qui participe beaucoup dans les énigmes mathématiques aussi ... Frédéric nous présentera quelques résultats et questions et conjectures concernant ce problème.
- 14 février 2006 : Fritz Eisenbrand
(Dortmund) : Cutting stock problem.
Nous allons écouter les détails de l'algorithme de Karmakar and Karp sur l'écart d'intégralité O(log d)^2 dans le problème de "cutting stock" (où d est la dimension), dans un exposé détaillé de Fritz Eisenbrand. All colleagues interested in the geometry of numbers or the cutting stock problem are welcome !
- 09 février 2006 : Irith Hartman
(Haifa) : The Berge's strong path partition conjecture.
Berge's strong path partition conjecture from 1982 extends the Greene-Kleitman Theorem and Dilworth's Theorem for all digraphs. The conjecture is known to be true for all digraphs for k=1 by the Gallai - Milgram Theorem, for k= lambda (length of longest path) by the Gallia-Roy Theorem, and for k>1 only for acyclic digraphs. In this talk we shall prove the conjecture for k=2.
This is joint work with Eli Berger.
- 24 novembre 2005 :
Gennady Shmonin (Budapest) : Carathéodory Bounds and the Cutting Stock Problem.
We consider some issues related to the cutting stock problem. The cutting stock problem is the following: Given a demand on d item types, each type i in {1, 2, ..., d} characterised by the size a_i common for all items of this type and the number b_i of items of this type, find the minimum number of stocks of length beta needed to cut all these items.
The integer program due to Gilmore and Gomory includes exponentially many variables. However, it is possible to show that one can provide a solution of polynomial size, thus the decision version of the problem (``Is there a cutting using m stocks'') is NP-complete. For the cutting stock problem with a fixed number d of different item sizes only fixed number of nonzero variables are required.
The Gilmore-Gomory integer program has the very strong linear programming relaxation. In fact, no instance is known with the gap between the integer optimum value and the optimum value of the linear programming relaxation achieving 2, and it was conjectured that the cutting stock problem has the modified integer rounding-up (MIRU) property, that is, the integer optimum value is at most ceil(LIN) + 1 where LIN is the optimum value of the corresponding linear programming relaxation. We prove the property for some particular classes of the cutting stock problem.
- 24 novembre 2005 : Kahina Meslem
(Alger) : On the extension of distance-hereditary graphs.
Given a simple and finite connected graph G, the distance d(u,v) is the length of the shortest induced {u,v}-path linking the vertices u and v in G. Bandelt and Mulder [1] have introduced and characterized the class of distance hereditary graphs where the distance is preserved in each connected subgraph. In this paper, we are interested with the class of k-distance hereditary graphs (k in N*) which consists in a parametric extension of distance-hereditary notion. We allow the distance in each induced subgraph to increase by at most k-1 unities to the original graph. We provide a characterization of k-distance hereditary graphs in terms of forbidden configurations for each k in N*.
Références : [1] H. J. Bandelt and H. M. Mulder, Distance Hereditary Graphs, J.Combin, Series (1986) B41, 182--208.
- 10 novembre 2005 : André Bouchet
: Groupes de marche et files périodiques dans le jeu de wari.
Nous présentons le résultat d'une recherche inspirée par un article récent de Ron Eglash [1]. On désigne sous le nom de wari un jeu de semis répandu en Afrique et une partie de l'Asie sous de très nombreuses variantes. L'espace du jeu est fait de trous disposés selon un ordre circulaire dans lequel se trouvent des pions (cailloux, graines, ...). Une action typique du jeu consiste ˆ vider un trou de ses graines pour les semer une par une dans les trous suivants. Un groupe de marche est fait de n trous successifs dont les nombres de pions sont donnés par la suite [n, n-1, ..., 2, 1]. Un tel groupe de marche se retrouve, décalé d'un trou, lorsque l'on ramasse les n pions du premier trou pour les semer dans les trous suivants. Ron Eglash [2] pose implicitement la question de caractériser de faon générale les configurations périodiques, les groupes de marche étant les configurations de période 1. C'est le problème que nous résolvons ici.
Références :
[1] Ron Eglash, L'algorithmique ethnique, Pour la Science, Dossier N¡ 47, avril/juin 2005.
[2] Ron Eglash, African Fractals: modern computing and indigenous design. New Brunswick: Rutgers University Press 1999.
- 06 octobre 2005 : Henning Bruhn
(Hambourg) : Infinite circuits in infinite graphs.
There are a number of well-known theorems concerning the cycle space of a finite graph, such as Tutte's generating theorem, and MacLane's, Tutte's and Whitney's planarity criterions. In a locally finite graph, all of these either have to be weakened considerably or even become false if the na•ve definition of the cycle space is used.
In the talk, I shall present how these problems can be overcome by introducing infinite circuits. These circuits will be (the edge sets of) homeomorphic images of the unit circle in the graph compactified by its ends. In the resulting cycle space all of the theorems above as well as the basic properties of a cycle space will have almost verbatim extensions.
The talk is based on work by Diestel and KŸhn, and on joint work with Diestel and Stein.
- 04 octobre 2005 : Vincent Jost
(Grenoble) : Coloration bornée.
Colorier un graphe c'est partitionner ses sommets de telle sorte qu'aucune classe de la partition contienne une arête. En général, étant donné un graphe on cherche à le colorier en utilisant le moins de couleurs possibles.
Ce problème est utile pour de nombreuses applications, toutefois il est rarement utilisable tel quel. Il faut souvent enrichir la formulation pour prendre en compte des contraintes spécifiques au problème appliqué. Les enrichissements nécessaires sont souvent déjà connus dans la théorie de l'ordonnancement.
Je présenterai succinctement quelques exemples de tels enrichissements, qui ont été étudiés par des "chromatologues" ou par des "ordonnanceurs" en essayant de donner une intuition de la similarité des questionnements et de l'interfécondation possible entre la théorie de la coloration et la théorie de l'ordonnancement.
Je traiterai en détail du problème de la coloration bornée, qui consiste à demander que chaque couleur soit utilisée au plus b fois (ou b est un entier).
Je présenterai une étude polyédrale détaillée basée sur l'étude d'une borne inférieure qui généralise Berge-Tutte pour le couplage max dans un graphe et l'inégalité de clique pour la coloration. Selon l'intérêt de l'auditoire je donnerai avec plus ou moins de détail,
-Des algorithmes pour résoudre optimalement le problème sur des classes de graphes comme line-graphe de bipartis (avec application à des problèmes d'emploi du temps), compléments d'intervalles (avec application à des problèmes de production et de transport)...
-Des algorithmes d'approximation, avec les intervalles ou se situent les seuils d'approximabilité.
J'essaierai de donner un éventail de conjectures qui synthétisent la frontière de ce qui est compris sur le sujet (ou plutôt de ce que j'en ai compris). (Les conjectures étant toutes de moi, les questions ne sont pas forcement profondes, mais le potentiel à publication est certain. Avis à ceux qui veulent être les prochains à couper des gâteaux... ).
J'essaierai d'argumenter ma conviction que les approches "polyédrales", "compléxité", "approximation" et "classes de graphes" sont complémentaires, en montrant comment les résultats que l'on obtient avec l'angle de vue d'une de ces approches renforce d'autant la pertinence des autres approches. (J'argumenterai avec des théorèmes qui ont P!=NP comme hypothèse). Autrement dit, pour bien avancer dans la compréhension d'un problème d'optimisation combinatoire, j'en arrive à la conclusion qu'il est plus important d'utiliser une palette d'outils de manière harmonieuse que d'en utiliser un seul à fond.
- 08 septembre 2005 : Edwin O'Shea
(Seattle) : Polyhedral aspects of Perfect Graphs.
Given a fixed integer matrix A and cost vector c the system yA <= c is said to be totally dual integral (TDI) if the linear program mininize{c.x : Ax = b, x >= 0} has an integral optimal solution whenever b is a non- negative integer combination of the columns of A. By work of Chvataland Fulkerson, the weak perfect graph theorem (WPGT) of Lovasz is equivalent to a certain system being TDI.
We introduce a new sufficient condition for detecting if a system is TDI and using this we conjecture that WPGT can be strengthened slightly by placing an order on the maximal cliques of the perfect graph. We provide examples to support our conjecture and prove it for chordal graphs.