Les inégalités valides

Les inégalités valides

Les inégalités (3.6) peuvent se séparer par l’algorithme de [109]. Un autre algorithme [87], plus efficace peut aussi être utilisé. Un exemple est donné dans la figure (3.2) où une instance Euclidienne avec 150 noeuds est prise. Dans le premier cas (la partie gauche de la figure (3.2)), S contient 70 noeuds représentés par des carrés noirs. Le problème est alors résolu en utilisant la formulation étendue. On obtient une solution où le coût est approximativement égal à 852. Lorsque on relaxe les contraintes de Steiner, on obtient une solution tracée dans la partie droite de la figure (3.2), et le coût est de 759 approximativement. Le fait que le problème d’optimisation soit facile à résoudre laisse espérer l’existence d’une bonne description de l’enveloppe convexe des vecteurs d’incidence de ces réseaux. Par équi- valence entre séparation et optimisation [60], on sait qu’il est possible de séparer en temps polynomial tout point rationnel et non réalisable de cette enveloppe convexe.en utilisant la dualité. Cependant, ceci reste une caractérisation compliquée. Alors, on essayera de trouver directement quelques classes d’inégalités valides. Leur séparation sera étudiée dans la Section 3.5. ≤ 1. En d’autres termes, lorsque nous considérons les inégalités (3.8), on peut supposer que |A| > 0 et |F| est impaire (Ceci implique que |B| > 0). Si S = V , les contraintes (3.7) sont les contraintes classiques de blossom introduites dans le contexte du 2-couplage (voir, e.g., [117, 80]). Padberg et Rao [109] ont montré que les inégalités dites de blossom peuvent se séparer en temps polynomial en résolvant un problème de T -coupe de poids minimum dans un graphe non orienté. orientées). Soient u et v deux sommets adjacents de V (G) (donc ils sont aussi sommets de H), et supposons que (u, v) est orienté de u à v ([u, v] ∈ V (H)). On considère trois cas possibles :

On considère une variante dans laquelle il existe un sous-ensemble de sommets T ⊂ V (G)tel que chaque sommet u ∈ T doit être soit une feuille (sommet de degré 1) ou sur un cycle etOn peut aussi imposer la contrainte suivante : soit l’arête (u, v) appartient au cycle, ou elle ne figure pas dans la solution. En d’autres mots, (u, v) ne doit pas figurer dans les sous arbres attachés aux cycles. Pour mieux cerner cette contrainte, on peut penser à la situation où toutes les arêtes qui ont un poids plus grand qu’un certain seuil, seront dans la solution si et seulement si elles contribuent à la construction des cycles. Cette contrainte peut être aussi satisfaite en supprimant les arêtes (u, vu) et (v, uv).En utilisant les mêmes techniques, il est facile de montrer que le problème de 2-couplage avec contrainte de type Steiner est facile à résoudre. Dans cette variante, un sommet est soit isolé ou appartient à un cycle. La solution est alors un ensemble de cycles disjoints couvrant un certain ensemble de sommets. Cependant, la résolution polynomiale de cette variante est un résultat bien connu [21].Nous présentons dans cette section quelques résultats numériques. D’une part, nous avons implémenté un Branch&Cut utilisant la formulation (3.1) avec les inégalités (3.3) et (3.7). D’autre part, nous avons implémenté le programme linéaire étendu. Dans la première phase de l’algorithme du Branch&Cut (à la racine), les deux familles d’in- égalités citées ci-dessus ont été intégrées. Uniquement les inégalités de base (3.3) sont rajoutées au niveau des autres noeuds de l’arbre de recherche. En effet, la séparation des inégalités (3.3) est exacte et rapide. Signalons qu’on a choisit la stratégie de recherche en profondeur d’abord dans l’algorithme de Branch&Cut, et une borne supérieure est calculée par la recherche d’un 2-couplage dans le graphe de départ.

Le gap final, qui est la différence entre la borne supérieure et la meilleure solution trouvée,le tout divisé par la borne supérieure, est donné et noté par « gap ». Si ce gap est égal à 0, alors le problème est résolu jusqu’à l’optimum. On donne aussi la valeur de « gap 2 », qui représente la différence entre la meilleure borne supérieure et le coût obtenu avec |S| = 0, le tout sera divisé (temps sep) dans la phase de l’algorithme à plans coupants (avant le Branch&Cut). Par (temps relax), on note le temps mis pour la résolution de la relaxation (avant le Branch&Cut), et (temps tot) est le temps total mis pour résoudre le problème jusqu’à la fin. On donne aussi le nombre de contraintes générées dans la phase de l’algorithme à plans coupants parmi les deux familles citées ci-dessus. Par « Nb coupes » et « Nb noeuds » on donne le nombre de coupes du type (3.3) générées dans la phase du Branch&Cut, ainsi que le nombre de noeuds de l’arborescence du Branch&Cut.