Chapter 2 Résolution du Set Covering Problem

Après avoir étudié plusieurs problèmes caractéristiques de l'optimisation combinatoire ainsi que les méthodes permettant de les résoudre, nous allons nous intéresser plus en détail à différentes méthodes de résolution d'un de ces problèmes ayant fait l'objet d'une littérature importante : le Set Covering Problem. Ainsi, nous nous focaliserons sur deux méthodes, l'une exacte et l'autre approchée, proposées par [Garfinkel et al.72] et par [Feo et al.94a].

2.1 Résolution exacte : algorithme de Branch & Bound

La méthode exacte que nous avons choisie pour résoudre le Set Covering Problem est un algorithme de Branch & Bound proposé par [Garfinkel et al.72]. Celui-ci reprend l'architecture générale d'un Branch & Bound mais en utilisant des règles d'évaluation et de parcours de l'arbre adaptées au Set Covering Problem. De plus, des règles de réductions permettent de diminuer la taille du problème initial. L'architecture de cet algorithme ainsi qu'un exemple didactique de son fonctionnement sont présentés en annexe I et II. Dans la suite, nous utiliserons les notations suivantes :

t_i correspond à la ligne i Î I de la matrice T
t_j correspond à la colonne j Î J de la matrice T.

2.1.1 Architecture du Branch & Bound

Le principe général de l'algorithme (voir Figure 2.1) est celui d'un Branch & Bound classique auquel ont été ajoutés des tests de réductions.

Figure 2.1: Architecture du Branch & Bound pour le SCP

2.1.2 Règles de réductions

Les règles utilisées pour réduire la dimension du problème sont au nombre de trois. Elles permettent de fixer certaines variables dont la valeur optimale est évidente et d'éliminer les contraintes redondantes.

La première règle (2.1) sert à fixer à 1 les variables nécessaires à l'admissibilité de la solution. Celles-ci sont détectées en recherchant des contraintes (lignes de la matrice) égales à un vecteur unité. Dans ce cas le coût de la variable est ajouté au coût fixe et elle est sortie du problème. De plus, l'ensemble des contraintes satisfaites par cette variable sont aussi supprimées.

Si t_i est le

vecteur unite e_k

ì
í
î

Þ X_k = 1 et t_k est enleve ; t_i est enleve

Þ si T_lk = 1, t_l est enleve

(2.1)

La deuxième règle (2.2) permet d'éliminer les contraintes redondantes. Pour cela, il faut les comparer une à une afin de détecter si l'une d'elle est couverte par au moins toutes les variables couvrant l'autre. Dans ce cas elle peut être retirée du problème, la satisfaction de l'autre contrainte garantissant la satisfaction de la contrainte supprimée.

Si t_l ³ t_p	(Û T_lj³ T_pj, " j Î J)
	Þ t_l est enleve

(2.2)

Enfin, la troisième règle (2.3) sert à fixer à zéro les variables dites moins intéressantes. Pour les détecter, les variables sont comparées une à une afin de détecter si l'une d'elle couvre au moins les même contraintes que l'autre pour un coût moindre ou égal (seulement moindre si l'on désirait obtenir toutes les solutions optimales). Notons que ces comparaisons pourraient également être effectuées non pas seulement une à une mais entre des combinaisons de toutes tailles. Cependant, le temps nécessaire pour effectuer ces tests augmenterait de manière importante. Pour un problème à n variables, une comparaison une à une est de complexité n2, une comparaison deux à deux de complexité n4 et une comparaison de toutes les combinaisons de complexité nn+1. On voit bien que tester toutes les combinaisons est une solution aussi coûteuse que l'énumération de toutes les solutions (et donc aussi peu envisageable pour des problèmes réels).

Si $ j Î J,	t_j ³ t_k et C_j £ C_k
	Þ t_k est enleve (X_k = 0)

(2.3)

Toutes ces règles sont ainsi testées jusqu'à ce qu'aucune d'entre elles ne puisse plus être activée. Bien évidemment, une fois le problème réduit résolu, la solution complète doit être reconstruite en y intégrant les variables fixées lors des tests de réduction (phase de Reconstruction).

2.1.3 Principes de parcours de l'arbre

Le principe utilisé pour ce Branch & Bound est celui de la profondeur d'abord. Les règles de sélection des noeuds à explorer sont fixées a priori et ne dépendent pas des évaluations obtenues pour les différents noeuds. De même, il n'y a pas de liste des noeuds à explorer car ceux-ci le sont selon l'ordre dans lequel ils sont obtenus, soit par une séparation, soit par un backtracking.

Un noeud est en fait défini par les variables qui y sont fixées en utilisant la notation usuelle de Balas-Geoffrion où l'ensemble des indices des variables fixées sont indiqués (les indices des variables fixées à zéro étant signalé par un signe négatif). Par exemple, le noeud de la Figure 2.2 correspond à l'ensemble S={-3,5,8,-9}.

Figure 2.2: Exemple d'un noeud d'un Branch & Bound

Pour être complet, cette notation comprend aussi un pointeur permettant de connaître les noeuds déjà explorés. Cependant celui-ci n'est pas utile dans notre cas car comme nous le verrons, les règles de séparation et de backtracking employées évitent de revenir sur un noeud déjà rencontré.

Séparation d'un noeud intéressant

Lorsqu'un noeud a obtenu une évaluation permettant de supposer qu'il peut contenir une solution strictement meilleure que celles trouvées jusqu'à présent, et si la solution correspondant au problème relaxé n'est pas aussi une solution du sous-problème (dans ce cas la solution est entière et la règle de coïncidence peut s'appliquer), alors l'algorithme explore ce noeud. Pour cela, il cherche à fixer certaines variables encore libres en utilisant une heuristique de type glouton. Cette heuristique fonctionne en classant les variables dans l'ordre des å_i=1^m T_ij/C_j décroissants. De plus elle fixe uniquement des variables à un, de sorte que le noeud obtenu est à une extrémité de l'arbre généré à partir du sous-problème évalué. Notons que cette heuristique est utilisée dès la première itération pour descendre vers une solution admissible.

Backtracking lorsqu'un noeud est sondé

Lorsque l'évaluation d'un noeud montre qu'il ne peut pas contenir de solution meilleure que celles trouvées ou que la solution optimale de ce noeud est connue, alors l'algorithme doit rechercher un nouveau noeud à explorer.

Pour cela il se déplace dans l'arbre en fixant à zéro des variables fixées à un. Il libère donc les dernières variables de S si celles-ci étaient fixées à zéro, et fixe à zéro la dernière variable fixée à un. Par exemple, si l'algorithme doit effectuer un backtracking à partir d'un noeud défini par l'ensemble Sⁱ={-3,5,8,-9}, il obtient le noeud défini par Sⁱ⁺¹={-3,5,-8}.

Notons que l'algorithme a fini de parcourir l'arbre lorsqu'il revient au noeud vide.

2.1.4 Évaluation d'un noeud

La relaxation continue est utilisée pour évaluer le sous-problème formé par les variables libres du noeud. Ce type de relaxation autorisant des évaluations peu coûteuses en temps, elle permet d'explorer un plus grand nombre de noeuds.

Malgré tout, lorsque le sous-problème à évaluer est très petit (peu de variables et/ou peu de contraintes), il est trivial et donc une solution entière optimale évidente peut facilement être trouvée sans qu'il soit nécessaire d'utiliser une relaxation.

2.2 Résolution approchée : la métaheuristique GRASP

La méthode approchée que nous avons choisi pour résoudre le Set Covering Problem est la métaheuristique GRASP¹ [Feo et al.94a]. Pour cela, nous avons repris et amélioré un algorithme développé par [Vancoppenolle98] et [Gandibleux et al.98] pour le Set Covering Problem. En particulier, nous avons travaillé sur des améliorations permettant de le rendre plus efficace sur les problèmes à coûts unitaires. L'architecture de l'algorithme de GRASP ainsi qu'un exemple didactique de son fonctionnement sont présentés en annexe III et IV.

GRASP peut en outre être facilement parallélisé pour une architecture multiprocesseur [Feo et al.94b]. Cependant, nous n'utiliserons pas cette propriété dans le cadre de notre travail.

2.2.1 Architecture de GRASP pour le SCP

Le principe général de GRASP (voir Figure 2.3) consiste à utiliser plusieurs fois un algorithme glouton choisissant les variables fixées de manière partiellement aléatoire puis à améliorer les différentes solutions ainsi trouvées grâce à une recherche locale. GRASP est donc un compromis entre un algorithme glouton² et un algorithme entièrement aléatoire, un paramètre à régler permettant de s'approcher plus ou moins de l'un ou de l'autre.

Figure 2.3: Architecture de GRASP pour le SCP

2.2.2 Obtention d'une solution initiale

La première phase de l'algorithme consiste à construire une solution initiale réalisable itérativement grâce à un algorithme glouton basé sur une fonction de sélection utilisant les principes suivants.

A chaque itération, les variables sont classées en fonction de leur intérêt à être sélectionnées dans une couverture minimum dans une liste de candidats CL (Candidate List). Cet intérêt est mesuré en faisant le rapport entre le nombre de contraintes satisfaites et le coût. Ce calcul est mis à jour à chaque itération en ne prenant en compte que les contraintes n'étant pas encore satisfaites par les variables déjà sélectionnées.

Une liste des meilleures candidates RCL (Restricted Candidate List) est ensuite obtenue en ne gardant que les variables ayant un intérêt supérieur ou égal à a

Notons aussi qu'un paramètre b peut être utilisé pour limiter le nombre de variables de la RCL. Cependant, ce paramètre n'a pas été utilisé.
Cette phase est répétée autant de fois que l'on désire de solutions initiales.

2.2.3 Recherche locale

La deuxième phase de l'algorithme consiste à améliorer les solutions obtenues avec l'algorithme glouton grâce à une recherche locale. En effet, rien ne garantit que ces solutions soient des optima locaux (au sens du voisinage considéré). La méthode de recherche locale utilisée est un algorithme de descente (k-p échanges³).

Évidemment, le choix d'un voisinage approprié sera très important pour obtenir un algorithme efficace. En effet, si celui-ci est trop restreint la recherche locale ne fournira pas de meilleures solutions, alors que s'il est trop vaste elle sera trop coûteuse en temps. Le voisinage proposé pour le SCP par [Vancoppenolle98] et [Gandibleux et al.98] est celui des 1-0 échanges (suppression des redondances).

2.2.4 Intensification de la recherche locale

Enfin, afin de compenser le fait que le voisinage choisi pour la recherche soit assez restreint, une nouvelle recherche locale est effectuée sur les meilleures solutions obtenues avec un voisinage plus vaste. Le fait que le nombre de recherches à effectuer soit moindre permet de conserver des temps de résolution corrects malgré le coût de ces recherches.

Cette partie de l'algorithme ne fait en réalité pas partie de l'algorithme original, mais est une modification proposée par [Vancoppenolle98]. Le voisinage qu'il utilisait était celui des 1-2 (suppression d'une variable de la solution et ajout de deux autres de coût total moindre tout en conservant une couverture), 1-1 et 1-0 échanges. Cependant, le choix de ce voisinage n'était pas toujours très approprié, en particulier pour les problèmes à coûts unitaires pour lesquels les 1-2 et 1-1 échanges ne peuvent être effectués étant donné qu'il n'existe pas de variables de coût moindre (toutes les variables étant de coût égal). Ces recherches ne sont donc pas effectuées dans ce cas. De plus, une recherche dans le voisinage des 2-1 échanges a été ajoutée pour l'ensemble des problèmes.

1: Greedy Randomized Adaptative Search Procedure
2: Algorithme fixant successivement les variables par ordre d'intérêt uniquement jusqu'à obtenir une solution admissible
3: Un k-p échange correspond au remplacement dans la solution de k variables par p variables n'appartenant pas à la solution