11.8 Le probl` eme d’affectation quadratique
343
garages, etc.) sur exactement d sites donn´ es de sorte `
a minimiser les coˆ uts de
transit associ´ es ` a une fonction de flux de mati` ere transport´ ee. Pour simplifier,
on notera indistinctement i ∈ {1, . . . , d} l’indice de l’un des d sites et l’indice
de l’une des d unit´ es. On munit l’ensemble des sites {1, . . . , d} d’une fonction
de type distance
D : (i, j) ∈ {1, . . . , d}
2
→ D(i, j) ∈ [0, ∞[
et l’ensemble des unit´ es {1, . . . , d} d’une fonction de flux
F : (i, j) ∈ {1, . . . , d}
2
→ F (i, j) ∈ [0, ∞[
On repr´ esente une configuration des unit´ es sur les sites par la donn´ ee d’une
permutation σ ∈ G d des indices {1, . . . , d} ; σ(i) repr´ esente l’indice de l’unit´ e
plac´ e sur le site i, avec i ∈ {1, . . . , d}. Le coˆ ut d’un transit est ´ egal au produit de la distance D(i, j) entre les sites par le flux de mati` ere transport´ ee
F (σ(i), σ(j)) entre les unit´ es σ(i) et σ(j).
Le probl` eme est donc de r´ esoudre le probl` eme de minimisation suivant
min
σ∈G d
V (σ) avec V (σ) :=
1≤i,j≤d
D(i, j) F (σ(i), σ(j))
Ce probl` eme d’affectation quadratique admet des applications vari´ ees :
placement optimal de circuits ´ electroniques sur des plaquettes, planification
et analyse de r´ eactions chimiques.
L’interpr´ etation probabiliste des questions consiste ` a traduire ce probl` eme
d’optimisation combinatoire en un probl` eme de simulation d’une mesure de
probabilit´ e de plus en plus concentr´ ee sur l’ensemble des solutions optimales.
Nous avons d´ ej` a utilis´ es ces principes dans la section 6.2.1 et dans la section 7
d´ edi´ ee ` a l’´ etude de l’algorithme de recuit simul´ e. Dans le probl` eme d’affectation quadratique la mesure de Boltzmann-Gibbs naturelle est li´ ee ` a la mesure
de comptage μ sur l’espace des permutations :
η n (dσ) =
1
μ(G n )
G n (σ) μ(dσ) avec la mesure uniforme μ(dσ) =
1
d!
Le choix de la fonction potentiel est assez libre. On peut choisir des fonctions
exponentielles de Boltzmann-Gibbs li´ ees `
a des param` etres de temp´ erature
inverse β n ↑ ∞ lorsque n ↑ ∞
G n (σ) = e
−βnV (σ)
On peut aussi choisir des fonctions indicatrices d’ensembles de niveaux d’´ energie
d´ ecroissante et li´ ees ` a des param` etres n ↓ 0 lorsque n ↑ ∞
G n (σ) = 1 V (σ)≤n
343
garages, etc.) sur exactement d sites donn´ es de sorte `
a minimiser les coˆ uts de
transit associ´ es ` a une fonction de flux de mati` ere transport´ ee. Pour simplifier,
on notera indistinctement i ∈ {1, . . . , d} l’indice de l’un des d sites et l’indice
de l’une des d unit´ es. On munit l’ensemble des sites {1, . . . , d} d’une fonction
de type distance
D : (i, j) ∈ {1, . . . , d}
2
→ D(i, j) ∈ [0, ∞[
et l’ensemble des unit´ es {1, . . . , d} d’une fonction de flux
F : (i, j) ∈ {1, . . . , d}
2
→ F (i, j) ∈ [0, ∞[
On repr´ esente une configuration des unit´ es sur les sites par la donn´ ee d’une
permutation σ ∈ G d des indices {1, . . . , d} ; σ(i) repr´ esente l’indice de l’unit´ e
plac´ e sur le site i, avec i ∈ {1, . . . , d}. Le coˆ ut d’un transit est ´ egal au produit de la distance D(i, j) entre les sites par le flux de mati` ere transport´ ee
F (σ(i), σ(j)) entre les unit´ es σ(i) et σ(j).
Le probl` eme est donc de r´ esoudre le probl` eme de minimisation suivant
min
σ∈G d
V (σ) avec V (σ) :=
1≤i,j≤d
D(i, j) F (σ(i), σ(j))
Ce probl` eme d’affectation quadratique admet des applications vari´ ees :
placement optimal de circuits ´ electroniques sur des plaquettes, planification
et analyse de r´ eactions chimiques.
L’interpr´ etation probabiliste des questions consiste ` a traduire ce probl` eme
d’optimisation combinatoire en un probl` eme de simulation d’une mesure de
probabilit´ e de plus en plus concentr´ ee sur l’ensemble des solutions optimales.
Nous avons d´ ej` a utilis´ es ces principes dans la section 6.2.1 et dans la section 7
d´ edi´ ee ` a l’´ etude de l’algorithme de recuit simul´ e. Dans le probl` eme d’affectation quadratique la mesure de Boltzmann-Gibbs naturelle est li´ ee ` a la mesure
de comptage μ sur l’espace des permutations :
η n (dσ) =
1
μ(G n )
G n (σ) μ(dσ) avec la mesure uniforme μ(dσ) =
1
d!
Le choix de la fonction potentiel est assez libre. On peut choisir des fonctions
exponentielles de Boltzmann-Gibbs li´ ees `
a des param` etres de temp´ erature
inverse β n ↑ ∞ lorsque n ↑ ∞
G n (σ) = e
−βnV (σ)
On peut aussi choisir des fonctions indicatrices d’ensembles de niveaux d’´ energie
d´ ecroissante et li´ ees ` a des param` etres n ↓ 0 lorsque n ↑ ∞
G n (σ) = 1 V (σ)≤n