The node-edge weighted 2-edge connected subgraph problem : linear relaxation, facets and separation

Soit G=(V,E) un graphe non-orienté et 2-arêtes connexe. Chaque arête et sommet de G est muni d'un poids. Le problème du sous-graphe 2-arêtes connexe de poids minimum dans G (2ECSP), est de trouver un sous-graphe 2-arêtes connexe de G tel que la somme des poids sur ses sommets et ses arête soit minimum. Le 2ECSP généralise le problème, bien connu, du sous-graphe Steiner 2-arêtes connexe. Dans cet article, l'enveloppe convexe des vecteurs d'incidences des solutions de 2ECSP est étudiée. Une formulation naturelle du problème par un programme linéaire en nombres entiers est premièrement établie. Il est aussi montré que la relaxation ne suffit pas pour décrire l'enveloppe convexe associée au 2ECSP même dans une classe restreinte comme celle des graphes série-parallèles. Une nouvelle classe d'inégalités valides pour le 2ECSP est introduite. Il est monté qu'une sous-classe de ces inégalités peut être séparée en temps polynomial. Comme conséquence, ces nouvelles inégalités peuvent être séparées en temps polynomial dans la classe des graphes série-parallèles.