1.8.3 Méthode commune aux deux types de
problèmes
On constate que les heuristiques proposées, en ce qui
concerne les choix des valeurs sur lesquelles brancher, sont fortement
dépendantes du type de problème. Dans la section suivante, nous
proposons une heuristique de choix de valeur qui ne dépend pas du type
de problème étudié.
Choix des valeurs
Rappelons le principe général de fonctionnement
d'un Branch & Bound dans le cas d'un problème d'optimisation
combinatoire. On choisit une variable parmi les variables non
instanciées. On crée autant de noeuds fils que le nombre de
valeurs de la variable. Pour chaque valeur, on calcule une borne
inférieure (par résolution d'une relaxation spécifique, de
programmation linéaire, etc.). Si cette borne inférieure est
supérieure à la plus petite borne supérieure connue, on
arrête l'exploration du sous-arbre engendré par cette valeur et on
passe à une autre valeur. Dans le cas contraire, il existe deux
possibilités : soit on est à une feuille et dans ce cas, on met
à jour la borne supérieure, soit on continue l'exploration de
l'arbre de recherche. On peut remarquer que cette méthode est fortement
dépendante de l'efficacité du calcul de la borne
inférieure.
On peut remarquer une analogie entre la coupe effectuée
dans l'arbre lorsque la borne inférieure est supérieure à
la borne supérieure avec les retraits des valeurs d'un domaine d'une
variable suite à une propagation de contraintes dans un problème
de satisfaction de contraintes. En effet, lorsqu'une valeur est
supprimée d'un domaine, cela revient à dire que l'instanciation
de cette valeur est impossible, puisqu'elle violerait un certain nombre de
contraintes. Lorsqu'un sous-arbre est fermé pour une valeur dans
un Branch & Bound, cela revient à dire que cette
valeur viole la contrainte qui assure que les bornes inférieures doivent
être inférieures à la plus petite borne
supérieure.
Une heuristique de critère de choix pour les valeurs
est donc la suivante. Pour chaque valeur, on garde en mémoire le nombre
de fois où l'arbre est coupé (ou que la valeur est
supprimée du domaine de la variable dans le cas du problème de
satisfaction de contraintes). On triera les pondérations sur les valeurs
par ordre croissant afin de diriger la recherche dans l'arbre vers les
meilleures solutions (ou vers les espaces de recherche étant
supposés contenir une solution). Néanmoins, on se rend compte que
ce critère n'est pas assez précis. En effet, ce critère ne
tient pas compte du nombre de fois où la valeur en question a
été choisie. Le critère retenu est donc le suivant. On
cherche la valeur qui minimise:
nombre de fois où la valeur a mené à un
échec (1.5)
nombre de fois où la valeur a été
choisie
Ce critère est adapté aux deux types de
problèmes et permet dans un cas comme dans l'autre de diriger la
recherche vers un espace de solutions de qualité.
Choix des variables
L'ensemble des heuristiques proposées pour le choix
concernant les variables dans le cas de problèmes d'optimisation
combinatoire ou de problèmes de satisfaction de contraintes sont
adaptées à l'heuristique de critère de choix pour les
valeurs que nous avons proposée ci-dessus.
| 
