Plusieurs problèmes issus de domaines divers se ramènent à maximiser (ou minimiser) une fonction linéaire sous des contraintes linéaires avec des variables bivalentes. Ces problèmes, dits d'optimisation combinatoire, sont généralement NP-difficiles. Des méthodes efficaces ont été ainsi développées pour formuler et résoudre ce type de problèmes. En particulier, les approches dites polyédrales se sont avérées puissantes pour les résoudre à l'optimum. Celles-ci consistent à ramener le problème à la résolution d'un programme linéaire en décrivant l'enveloppe convexe de ses solutions par un système d'inégalités linéaires.
L'équivalence établie entre la séparation et l'optimisation sur un polyèdre d'une part, et l'évolution des outils de calcul d'autre part, ont donné un essor important à ces méthodes. Ainsi celles-ci permettent d'élaborer des algorithmes polynomiaux et d'obtenir des relations min-max entre des structures combinatoires. Aussi, la technique dite de « Branch and Cut », qui est une méthode arborescente, inspirée de cette équivalence, est maintenant largement appliquée pour obtenir des solutions optimales ou proches de l'optimum pour les problèmes d'optimisation combinatoire difficiles.
Nous discutons de ces méthodes et présentons certaines applications à des problèmes de topologie de réseaux.

Tout d'abord, nous présentons une nouvelle approche par la programmation linéaire en 0-1 pour plusieurs problèmes de sous-graphe maximum (avec poids sur les aretes):
 - le biparti complet (biclique) maximum
 - le multiparti complet maximum
 - le biparti induit maximum
 - la foret induite maximum
Cette approche, qui s'inspire de celle du problème du biparti maximum, consiste à définir les structures propres à une formulation qui n'utilise que les variables nécessaires (sur les aretes). Elle consiste aussi à élaborer un algorithme polynomial de séparation.
Ensuite, nous montrons comment cette approche peut s'appliquer au problème de la coloration de graphe, au recouvrement minimum par des bicliques et plus généralement à tout problème qui se modélise comme un problème de coloration d'hypergraphe pour lequel on dispose d'un algorithme polynomial pour déterminer une hyperarete de cout minimum.

Le problème de l'affectation quadratique est un problème d'optimisation combinatoire réputé pour sa difficulté. Il se modélise comme un problème quadratique sous des contraintes linéaires dites d'affectation.
Nous présentons une famille d'inégalités valides induisant des facettes du polytope associé à la linéarisation de ce problème. Nous proposons alors deux relaxations l'une linéaire (PL) et l'autre semi-définie (SDP) basées sur un algorithme de coupes mettant en oeuvre ces inégalités valides. Des résultats numériques montrent l'intéret, aussi bien en PL qu'en SDP, des coupes utilisées.

Le problème Anneau- Etoile (Ring Star Problem (RSP)) a été introduit dans [1]. Il s'agit de trouver un cycle simple traversant un sous-ensemble de sommets d'un graphe de manière à ce que la somme du cout lié à la longueur du cycle et le cout d'affectation du reste des sommets aux plus proches sommets dans le cycle, soit minimum.
Ce problème a des applications dans les réseaux de télécommunications, dont quelques-unes ont été décrites dans [1]. Le problème est défini sur un graphe mixte complet G=(V,E,A), où V={1,2,..,n} est l'ensemble des sommets, E ={(i,j) : i,j in V, i<j} est l'ensemble des aretes, et A = {(i,j) : i,j in V} est l'ensemble des arcs (boucles incluses). Le sommet 1 est considéré comme le dépot. A chaque arete (i,j) de E, on associe un cout d'anneau non-négatif c(i,j) et à chaque arc (i,j) de A on associe un cout d'affectation d(i,j) non-négatif. Une solution du RSP est un cycle simple dans G traversant un sous-ensemble de sommets V' de V devant contenir le sommet 1. Le problème revient à trouver une solution minimisant la somme du cout d'anneau et du cout d'affectation.
RSP est NP-difficile car le cas dans lequel le cout d'affectation est extremement grand par rapport aux couts d'anneau est le problème du Voyageur de Commerce. Dans [1], les auteurs ont présenté une description polyédrale partielle du RSP. Ils ont proposé également un algorithme de Branch-and-Cut basé sur la description donnée et ont pu résoudre des instances ayant jusqu'à 300 sommets. Cette description est très inspirée d'une caractérisation partielle du polyèdre des cycles de P.Bauer [3]. Le polyèdre des cycles n' étant qu'une relaxation de la projection du polyèdre RSP sur les aretes, sa structure est plutot complexe [2]. Nous ajoutons un clone du sommet 1 au graphe pour ramener ce problème de recherche de cycle à un problème de recherche de st-chemins. Cela nous permet de donner une nouvelle formulation mathématique plus précise basée sur une caractérisation des st-chemins. Nous introduisons de nouvelles facettes et nous présentons un algorithme de Branch-and-Cut pour RSP implémenté avec COIN/BCP, avec les résultats numériques.
Bibliographie
 [1] Labbé, M. and Laporte, G. and Martin, I.R. and Gonzalez, J.J.S : The Ring Star Problem: Polyhedral Analysis and Exact Algorithm, Vol 43(3), Networks, 177-189 (2004)
 [2] Maurras, J.F. and V.H. Nguyen : On the linear description of 3-cycle polytope, Vol 137, EJOR, 310-325 (2002)
 [3] Bauer, P. The circuit polytope : Facets, Vol 22, Math Oper Res, 110-145 (1997)

Le problème de dimensionnement multi-périodes avec conservation des routages, appelé PDMCR, est un cas particulier du problème de dimensionnement de réseau multi-périodes. Il s'agit d'une généralisation du problème de dimensionnement de réseau à coûts discontinus pour plusieurs périodes, appliquée à l'aménagement des réseaux de transmissions optiques.
Nous optimisons simultanément l'architecture de réseau et le dimensionnement des liens, permettant d'écouler l'ensemble des demandes de trafic ajoutées tout au long d'un horizon de temps donné. Les fonctions de coût associées aux capacités installées sur les liens sont discontinues. Compte tenu des impératifs d'ingénierie de trafic, les chemins empruntés pour router les demandes à une période restent les mêmes pour router ces mêmes demandes aux périodes suivantes. Ainsi la bande passante utilisée à une période ne peut plus être consommée pour écouler les demandes ajoutées aux périodes suivantes.
Nous proposons une formulation compacte de ce problème combinatoire NP-difficile de grandes dimensions, basée sur un modèle polyédrique. L'étude du polyèdre des solutions réalisables du problème a permis d'exhiber des classes d'inégalités valides pour PDMCR. Nous avons élaboré une méthode exacte efficace, s'appuyant sur une procédure de génération de contraintes combinée à la résolution de relaxations entières de PDMCR.