342
11 Optimisation et Combinatoire ´ enum´ erative
sous un nombre c 2 contraintes
∀1 ≤ i ≤ c 2
P i (u) :=
d
k=1
p
i
k u k ≤ p
i
Les param` etres p
i
∈
min 1≤k≤d p
i
k ,
d
k=1 p
i
k
d´ esignent des valeurs maximales des crit` eres autoris´ es. Optimiser les premiers c 1 crit` eres revient clairement ` a trouver (sous les c 2 contraintes P i ≤ p
i ) les extrema globaux de la
fonction
W(u) :=
c1
i=1
W i (u)
Les techniques d’exploration al´ eatoire de ces espaces de configurations sont
multiples et vari´ ees. Par exemple, par analogie avec (11.11) on peut choisir
d’explorer les intersections d’ensembles
A m := {u : W(u) ≥ m et ∀1 ≤ i ≤ c 2 P i (u) ≤ p
i } = ∩
c2
i=1 B m (i)
avec pour chaque 1 ≤ i ≤ c 2
B m (i) =
(u 1 , . . . , u d ) ∈ {0, 1}
d : W(u) ≥ m et
d
k=1
p
i
k u k ≤ p
i
V(u) =
c2
i=1
1 Pi≤p
i
(u)
D’autres strat´ egies fond´ ees sur la concentration de mesures de BoltzmannGibbs exponentielles se concentrant sur l’ensemble des solutions du probl` eme
d’optimisation peuvent ˆ etre d´ evelopp´ ees.
Par exemple, on peut consid´ erer les mesures de Boltzmann-Gibbs
Ψ G (μ)(dx) =
1
μ (e αV+βW )
e
αV(x)+βW(x) μ(dx)
avec des param` etres de temp´ erature inverse α, β ↑ ∞, la mesure uniforme μ
sur E, et la fonction de comptage des contraintes v´ erifi´ ees
V(u) =
c2
i=1
1 Pi≤p
i
(u)
11.8 Le probl` eme d’affectation quadratique
Ce probl` eme d’optimisation combinatoire consiste `
a rechercher la meilleure
strat´ egie de placement g´ eographique de d unit´ es (usines, services hospitaliers,