coopération entre résolution search et  l’énumération implicite pour le sac à dos multidimensionnel en 0-1

Principe général 

D’un point de vue global, les branchements étant réalisés suivant l’ordre décroissant des coûts réduits, l’arbre de re her he est exploré suivant trois niveaux : Resolution search explore les branches hautes (variables à fort coût réduit), l’énumération impli ite explore les branches médianes (variables à coût réduit moyen) et l’algorithme de backtracking explore les bandes basses (variables de plus faible coût réduit et variables de base). Les deux méthodes opèrent de la manière suivante : Resolution search fournit des sous problèmes à l’énumération impli ite qui, en les résolvant, permet d’obtenir des obstacles de petite taille utilisés par Resolution search pour guider l’exploration vers des zones prometteuses de l’espace de re her he. Fig. 4.1  Exploration de l’arbre de re her he en trois niveaux resolution search énumération implicite des 4.2 Contributions apportées à Resolution search Dans cette section, nous présentons deux modifications apportées à Resolution search. La première est une version à itérations limitées de l’algorithme qui permet d’explorer itérativement chaque sous problème lié à la dé omposition par hyperplans et la deuxième est une modi cation de la phase de remontée fondée sur des relations d’implication entre n÷uds de l’arbre de re her he. 

Exploration itérative de l’espace de recherche 

Comme nous l’avons mentionné dans le chapitre 2, l’ordre dans lequel les hyperplans sont explorés inuen et fortement l’e a cité de la mise à jour de la borne inférieure. Nous allons voir que la structure de Resolution search présente un avantage intéressant qui permet de pallier ce problème.

Contributions apportées à Resolution search

Dans le chapitre 3, nous avons montré que la famille pathlike F constitue un résumé des explorations passées : après chaque exé ution de la bou le prin ipale, F nous donne l’état de la re her he et le n÷ud suivant de l’exploration u(F). Cette particularité permet de pouvoir interrompre le processus de recherche à un moment donné et de le récupérer ultérieurement sans perte d’information. De cette façon, il est possible de résoudre le problème P en ee tuant de manière répétée un nombre d’itérations limité pour chaque sousproblème P(k) jusqu’à e que tous les sousproblèmes soient résolus. L’ordre d’exploration n’a alors plus d’importance car il n’est pas nécessaire qu’un sousproblème soit résolu pour commencer la résolution du sousproblème suivant. Les algorithmes 4.1 et 4.2 illustrent ette façon itérative de résoudre le problème. Algorithme 4.1  Algortithme Resolution search itératif IRS(P ,Nb_Iter, BI,F ) { iter = 0 ; while(iter < Nb_Iter) { try = obsta le(P , u(F ),BI,S) ; if(try > BI) BI = try ; ajouter S à F et mettre à jour F ; if((∗, ∗, …, ∗) ∈ F ) Break ; iter++ ; } } Algorithme 4.2  Exploration des hyperplans resoudre_MKP() { BI = glouton() ; Cal uler les bornes kmin et kmax ; Définir K = {kmin, …, kmax} ; for(k = kmin, …, kmax) CFamily[k℄ = ∅ While (K 6= ∅) { Choisir k ∈ K ; Choisir Nb_Iter_k ≥ 1 ; IRS(P(k),Nb_iter_k,BI,CFamily[k℄) ; if((∗, ∗, …, ∗) ∈ CFamily[k℄) K = K − {k} ; } } La fon tion IRS de l’algorithme 4.1 prend en arguments : un problème P , un nombre d’itérations limité Nb_Iter, un minorant BI et une famille pathlike F . Cet algorithme onsiste à ee tuer un nombre Nb_Iter d’itérations de Resolution sear h. 63 Chapitre 4. Coopération entre Resolution sear h et l’énumération impli ite pour le sa à dos multidimensionnel en 01 La fon tion resoudre_MKP() de l’algorithme 4.2 onsiste à résoudre le problème MKP en utilisant ette version iterative de Resolution sear h. L’algorithme a utilisé une borne inférieure gloutonne an de déduire les bornes kmin et km , puis elle tue un certain nombre d’itérations de IRS sur chaque sous problème P(k). La variable Family[k℄ correspond à la famille pathlike de IRS pour le problème P(k). Lorsque l’un des problèmes P(k) est résolu, ‘està dire que (∗, ∗,…, ∗) ∈ C Family[k℄, il est éliminé de la re her he. Le problème P est alors résolu lorsque tous les sous problèmes P(k) sont éliminés. Ce type d’exploration peut être étendu à une quelconque décomposition P1,P2,…,Pm du problème P original. Il peut par exemple être utilisé pour la résolution itérative de sous problèmes pour lesquels certaines variables sont axées. La guerre 4.2 illustre cette approche de résolution. Fig. 4.2  Exploration itérative des sous problèmes P P1 P2 Pm−1 Pm 

Phase de remontée implicite 

Dans le papier original de Resolution search, Chvátal propose de libérer une à une les variables pré évidemment instant idées dans la phase de descente (sauf la dernière) et de varier à chaque fois la faisabilité de la solution partielle correspondante en exécutant la fonction orale ( chapitre 3). Cette phase de remontée correspond à la portion de code suivante de l’algorithme 3.4 : while(la pile n’est pas vide){ dépiler j ; Sj = ∗ ; if(ora le(S) > BI) Sj = u + j ; } Nous avons montré par des expérimentations que cette portion de l’algorithme ralentit considérablement le processus de recherche ( f. chapitre 3 section 3.9.1). Nous proposons un autre moyen d’identifier la clause S que nous appelons phase de remontée impli ite. Contrairement à la phase de remontée originale, cette méthode ne cherche pas à libérer des variables une fois l’é he rencontré, mais identique, lors de la phase de descente, un ensemble d’instan iations qui ne seront pas contenues dans le futur obsta le. Cette méthode est basée sur des relations d’implication existantes entre certains n÷uds de l’arbre de re her he. Supposons que l’instan iation des variables dans le n÷ud u implique la xation de variables supplémentaires onstituant le n÷ud v. En d’autres termes, supposons que u ⇒ v. Si, pendant la phase de des ente, u est étendu en u + = u ∪ v ∪ w et que u + viole une ou plusieurs ontraintes du problème, la lause S des ae tations responsables de l’é he est réduite à u ∪ w. Proposition 4.1 Soit u,v et w des ve teurs de {0, 1, ∗}n . Si u ⇒ v et si u ∪ v ∪ w est un obsta le, alors u ∪ w est un obsta le. Preuve Nous allons prouver la proposition par indu tion sur la longueur de v et par l’absurde. Supposons que v soit de longueur 1 tel que v = {xj}, don u ′ = u ∪ {x¯j} est un obsta le puisque u ⇒ v et u ′′ = u ∪ {xj} ∪ w est un obsta le par hypothèse. Alors, la résolvante de u ′ et u ′′ qui est u ′∇u ′′ = u ∪ w est un obsta le. Supposons à présent que la proposition soit vraie pour un ve teur v de longueur k, nous allons prouver que la proposition est toujours vraie si v est de longueur k + 1. Soit v = v ′ ∪ {xj}, alors u ′ = u ∪ v ′ ∪ {x¯j} est un obsta le et u ′′ = u ∪ v ′ ∪ {x¯j} ∪ w est également un obsta le. Don la résolvante de u ′ et u ′′ qui est u ′∇u ′′ = u ∪ v ′ ∪ w est un obsta le et par hypothèse d’indu tion, u ∪ w est un obsta le.  Bien que la phase de remontée impli ite puisse rempla er la phase de remontée originale de Resolution sear h, son e a ité dépend du problème résolu et des relations d’impli ation qui peuvent être déduites entre les n÷uds de l’arbre de re her he. Dans le as de la résolution du MKP, nous proposons une implémentation fondée sur les relations d’impli ation qui peuvent être déduites de la ontrainte des oûts réduits. Dans le as où le n÷ud de départ u(F) donné à la fon tion obsta le ontient des instan iations des variables à l’opposé de leur valeur optimale, gap est diminuée de la valeur des oûts réduits orrespondants et ette diminution implique la xation des variables non instan iées dans u(F) ayant un oût réduit supérieur à gap. D’après la proposition 4.1, les variables ainsi fixées à cause de la diminution de gap engendrée par u(F) ne sont alors pas prises en compte dans la lause S .