Chapitre 16. Méthodes arborescentes par séparation et évaluation

Irène Charon; Olivier Hudry

Introduction à l'optimisation continue et discrète 2019

Chapitre d’ouvrage

Chapitre 16. Méthodes arborescentes par séparation et évaluation

Par Irène Charon
et Olivier Hudry

Pages 375 à 402

CHARON, Irène
et HUDRY, Olivier,

2019. Chapitre 16. Méthodes arborescentes par séparation et évaluation. In : Introduction à l'optimisation continue et discrète Avec exercices et problèmes corrigés. Cachan : Lavoisier. IRIS, p.375-402. URL : https://stm.cairn.info/introduction-a-l-optimisation-continue-et-discrete--9782746248632-page-375?lang=fr.

Charon, Irène.
et al.

« Chapitre 16. Méthodes arborescentes par séparation et évaluation ». Introduction à l'optimisation continue et discrète Avec exercices et problèmes corrigés, Lavoisier, 2019. p.375-402. CAIRN.INFO, stm.cairn.info/introduction-a-l-optimisation-continue-et-discrete--9782746248632-page-375?lang=fr.

Charon, I.
et Hudry, O.

(2019). Chapitre 16. Méthodes arborescentes par séparation et évaluation. Introduction à l'optimisation continue et discrète : Avec exercices et problèmes corrigés (p. 375-402). Lavoisier. https://stm.cairn.info/introduction-a-l-optimisation-continue-et-discrete--9782746248632-page-375?lang=fr.

Notes

[1]
Un 1-arbre optimal relatif à so s’obtient en considérant les deux arêtes de moindre valua tion incidentes à "o et un arbre de valuation minimale couvrant
\mathcal { G }
\ {s₀}j ce que l’on sait déterminer en O(n²) à l’aide de l’algorithme de Prim (voir la partie 10.4, page 226), où n désigne l’ordre de
\mathcal { G }
. Ceci montre que l’on peut déterminer un 1-arbre optimal relatif à so aussi en O(n²). Plus loin, on cherchera des 1-arbres contenant certaines arêtes de
\mathcal { G }
imposées (ne créant pas de cycle dans
\mathcal { G }
\ {s₀}) et excluant d’autres arêtes de
\mathcal { G }
(ne déconnectant pas
\mathcal { G }
\ {s₀}). Il n’est pas difficile d’adapter l’algorithme de Kruskal (voir la partie 10.3, page 223) ou celui de Prim pour tenir compte de ces contraintes sans changer leurs complexités. Une autre façon de tenir compte de ces contraintes consiste à attribuer un très petit poids (typiquement, −∞) aux arêtes imposées et un très grand poids (typiquement, +∞) aux arêtes exclues.
[2]
Le principe de séparation décrit ici est dû à T. Volgenant et R. Jonker, A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation, European Journal of Operational Research 9 (1), 83-89, 1982. On trouvera d’autres principes de séparation dans le livre coordonné par E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan et D.B. Schmoys, The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimiza- tion, John Wiley and Sons, Chichester, 1985.
[3]
L’exercice 1, page 397, montre comment raffiner cette évaluation à l’aide de la relaxation lagrangienne.
[4]
Rappelons que la méthode d’Uzawa consiste à construire une suite (Λ_k) de la forme
\Lambda _ { k + 1 } = \widetilde { \Lambda } _ { k } + r _ { k } ( \widetilde { \delta } _ { s _ { 1 } } ( T _ { k } ) - 2, \delta _ { s _ { 2 } } ( T _ { k } ) - 2,..., \delta _ { s _ { n } } ( T _ { k } ) - 2 ) ^ { t }
, où r_k est un réel et où T_k désigne le 1-arbre associé à Λ_k. Comme la somme des degrés dans un 1-arbre est égale à 2n, on obtient que
\sum _ { i = 1 } ^ { n } ( \delta _ { s _ { i } } ( T _ { k } ) - 2 )
est nulle et la somme des multiplicateurs de Lagrange est constante. En particulier, si on part d’un vecteur des multiplicateurs de Lagrange nul (comme dans les questions suivantes), il n’y aura rien à retrancher…
[5]
En fait, on pourrait éviter de développer N₃ en constatant que les variables autres que x₂ et dont la valeur n’est pas fixée (c’est-à-dire finalement ici seulement x₃) ont des rapports utilité/poids strictement inférieurs à celui de x₂, du fait de l’ordre dans lequel on examine les variables ; toute autre solution contenue dans N₃ ne peut donc qu’être strictement moins bonne que celle associée à l’évaluation exacte de N₃. Cette remarque s’applique aussi au nœud N₈.

Citer ce chapitre

Charon, I.
et Hudry, O.

(2019). Chapitre 16. Méthodes arborescentes par séparation et évaluation. Introduction à l'optimisation continue et discrète : Avec exercices et problèmes corrigés (p. 375-402). Lavoisier. https://stm.cairn.info/introduction-a-l-optimisation-continue-et-discrete--9782746248632-page-375?lang=fr.

Charon, Irène.
et al.

« Chapitre 16. Méthodes arborescentes par séparation et évaluation ». Introduction à l'optimisation continue et discrète Avec exercices et problèmes corrigés, Lavoisier, 2019. p.375-402. CAIRN.INFO, stm.cairn.info/introduction-a-l-optimisation-continue-et-discrete--9782746248632-page-375?lang=fr.

CHARON, Irène
et HUDRY, Olivier,

2019. Chapitre 16. Méthodes arborescentes par séparation et évaluation. In : Introduction à l'optimisation continue et discrète Avec exercices et problèmes corrigés. Cachan : Lavoisier. IRIS, p.375-402. URL : https://stm.cairn.info/introduction-a-l-optimisation-continue-et-discrete--9782746248632-page-375?lang=fr.

Notes

[1]
Un 1-arbre optimal relatif à so s’obtient en considérant les deux arêtes de moindre valua tion incidentes à "o et un arbre de valuation minimale couvrant
\mathcal { G }
\ {s₀}j ce que l’on sait déterminer en O(n²) à l’aide de l’algorithme de Prim (voir la partie 10.4, page 226), où n désigne l’ordre de
\mathcal { G }
. Ceci montre que l’on peut déterminer un 1-arbre optimal relatif à so aussi en O(n²). Plus loin, on cherchera des 1-arbres contenant certaines arêtes de
\mathcal { G }
imposées (ne créant pas de cycle dans
\mathcal { G }
\ {s₀}) et excluant d’autres arêtes de
\mathcal { G }
(ne déconnectant pas
\mathcal { G }
\ {s₀}). Il n’est pas difficile d’adapter l’algorithme de Kruskal (voir la partie 10.3, page 223) ou celui de Prim pour tenir compte de ces contraintes sans changer leurs complexités. Une autre façon de tenir compte de ces contraintes consiste à attribuer un très petit poids (typiquement, −∞) aux arêtes imposées et un très grand poids (typiquement, +∞) aux arêtes exclues.
[2]
Le principe de séparation décrit ici est dû à T. Volgenant et R. Jonker, A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation, European Journal of Operational Research 9 (1), 83-89, 1982. On trouvera d’autres principes de séparation dans le livre coordonné par E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan et D.B. Schmoys, The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimiza- tion, John Wiley and Sons, Chichester, 1985.
[3]
L’exercice 1, page 397, montre comment raffiner cette évaluation à l’aide de la relaxation lagrangienne.
[4]
Rappelons que la méthode d’Uzawa consiste à construire une suite (Λ_k) de la forme
\Lambda _ { k + 1 } = \widetilde { \Lambda } _ { k } + r _ { k } ( \widetilde { \delta } _ { s _ { 1 } } ( T _ { k } ) - 2, \delta _ { s _ { 2 } } ( T _ { k } ) - 2,..., \delta _ { s _ { n } } ( T _ { k } ) - 2 ) ^ { t }
, où r_k est un réel et où T_k désigne le 1-arbre associé à Λ_k. Comme la somme des degrés dans un 1-arbre est égale à 2n, on obtient que
\sum _ { i = 1 } ^ { n } ( \delta _ { s _ { i } } ( T _ { k } ) - 2 )
est nulle et la somme des multiplicateurs de Lagrange est constante. En particulier, si on part d’un vecteur des multiplicateurs de Lagrange nul (comme dans les questions suivantes), il n’y aura rien à retrancher…
[5]
En fait, on pourrait éviter de développer N₃ en constatant que les variables autres que x₂ et dont la valeur n’est pas fixée (c’est-à-dire finalement ici seulement x₃) ont des rapports utilité/poids strictement inférieurs à celui de x₂, du fait de l’ordre dans lequel on examine les variables ; toute autre solution contenue dans N₃ ne peut donc qu’être strictement moins bonne que celle associée à l’évaluation exacte de N₃. Cette remarque s’applique aussi au nœud N₈.

Les méthodes arborescentes par séparation et évaluation (brandi and bound en anglais) sont des méthodes qui s’appliquent notamment à la résolution de problèmes d’optimisation combinatoire -difficiles. Au cours de la méthode, on développe une arborescence dont chaque nœud correspond à un sous-ensemble de l’ensemble des solutions réalisables. L’expansion de cette arborescence est régie par quatre principes : un principe de séparation, une fonction d’évaluation, l’utilisation d’une borne et une stratégie de développement. Ces principes sont développés dans ce chapitre.
D’une façon générale, on considérera ici un problème (P) de la forme suivante (des indications sont données plus loin pour l’adaptation à un problème de minimisation) :
où X est un ensemble fini non vide (ce qui assure l’existence d’au moins une solution optimale) et f est une application définie sur X à valeurs réelles (éventuellement entières). Souvent, on cherche non seulement la valeur maximale de f sur X, mais aussi un élément x* de X maximisant . Une variante consiste à chercher toutes les solutions optimales.
Nous appliquerons cette méthode à plusieurs problèmes -difficiles, en commençant par le problème de sac à dos en nombres entiers (voir la partie 13.4.3, page 314). Nous reprenons l’instance traitée à l’aide d’une heuristique gloutonne dans la partie 14.2.1, page 325 :Pour résoudre (P), on construit une arborescence , parfois appelée arborescence de recherche, dont les nœuds sont associés à des sous-ensembles d…

Date de mise en ligne : 01/06/2022

Ce chapitre est en accès conditionnel

Acheter cet ouvrage

65,00 €

504 pages, format électronique (HTML et feuilletage, par chapitre)

Acheter ce chapitre

5,00 €

28 pages format électronique (HTML, PDF et feuilletage)

Membre d'une institution cliente ?

Compte personnel

Chapitre 16. Méthodes arborescentes par séparation et évaluation

Notes

Citer ce chapitre

Notes

Ce chapitre est en accès conditionnel

Acheter cet ouvrage

Acheter ce chapitre

Accès institutions

Toutes les institutions