Le problème de couverture par sommets en Integer Linear Programming avec LP-solve

Le problème de couverture par sommets (ou Vertex Cover en anglais) consiste, étant donné un graphe, à trouver un ensemble minimum de sommets de sorte que toutes les arêtes soient couvertes.

Formellement: soit \(G(V, E)\) un graphe, une couverture est un ensemble \(S\) tel que: \[ S \subseteq V \text{ tel que } \forall e = (u, v) \in E, u \in S, \text{ ou } v \in S \]

L’objectif est de miniser la taille de \(S\).

Le problème de la couverture par sommets est NP-complet.

Dans ce post, nous allons tenter d’utiliser l’integer programming pour résoudre ce problème.

Encodage du problème en Integer Programming

En Integer Programming, on peut utiliser des variables entières, et des contraintes, telles que \(a + b \geq c\).

Pour encoder notre problème en Integer Programming, on va se donner une variable Booléenne \(x_v\) pour chaque sommet \(v\), sur \(\{0, 1\}\), évaluée à 1 si \(v\) est sélectionné dans \(S\).

Puis, pour chaque arête \((u, v)\), on crée une contrainte pour s’assurer qu’elle soit couverte:

\[ x_u + x_v \geq 1 \]

Dans cette condition, la contrainte est satisfaite si au moins une des variables \(x_u\) et \(x_v\) est vraie (c’est-à-dire égale à 1).

La fonction à miniser, correspondant au cardinal de \(S\) est simplement: \[ \sum_{v \in V} x_v \]

Les valeurs de \(x_v\) en sortie du solveur d’Integer Programming indiquent quel est l’ensemble \(S\) de la solution.

Implementation avec LP-solve

LP-solve est un solveur pour le problème Mixed Integer Linear Programming.

Pour l’exemple présenté au début de ce post, le graphe est composé des arrêtes suivantes: \((a, c), (c, b), (d, e), (a, e), (a, d)\)

min: a + b + c + d + e;

r_1: a + c >= 1;
r_2: d + e >= 1;
r_3: c + b >= 1;
r_4: a + e >= 1;
r_5: a + d >= 1;

bin a;
bin b;
bin c;
bin d;
bin e;

Value of objective function: 3.00000000

Actual values of the variables:
a                               1
b                               0
c                               1
d                               0
e                               1

Ce qui correspond à la couverture suivante (sommets jaunes), sur le graphe initial.