1.8.2 Problèmes d'Optimisation Combinatoire
Dans le cadre de problèmes d'optimisation combinatoire,
plusieurs possibilités se sont présentées à nous
pour les choix des valeurs, ainsi que pour le choix des variables.
Choix des Valeurs
Dans un problème d'optimisation combinatoire, on
cherche à minimiser (ou maxi-miser) un objectif. Par la suite, nous
considérerons uniquement le cas où l'on cherche à
minimiser un objectif.
La qualité des solutions trouvées peut donc
être un critère pertinent pour le calcul des pondérations
liées aux valeurs ou aux variables. Pour chaque valeur de chaque
variable, on garde en mémoire le coût de la meilleur solution
trouvée par cette affectation variable - valeur.
De manière équivalente aux problèmes de
satisfaction de contraintes, la moyenne des coûts des solutions ne nous a
pas semblé être un bon critère de sélection. En
effet, une valeur qui amènerait à un sous-arbre très
déséquilibré (de très bonne qualité d'un
côté et de très mauvaise qualité d'un autre
côté) aurait une moyenne de coût des solutions de sous-arbre
assez élevée, alors que cette valeur peut s'avérer
très intéressante.
Comme on cherche à se diriger vers les sous-arbres
contenant les feuilles de coûts les plus faibles, on va donc choisir pour
chaque variable, la valeur ayant la pondération la moins importante.
Choix des variables
On a vu que le choix des variables était primordial
pour la taille de l'arbre de recherche. Comme pour les problèmes de
satisfaction de contraintes, un certain nombre de choix sur les variables sont
possibles :
- Plus petit domaine,
- Plus petit regret minimum (le regret est calculé
généralement par rapport à la valeur de la fonction
objectif),
- Plus petit regret maximum,
- Plus fort degré,
Pour les choix des variables qui utilisent les
pondérations sur les variables, nous avons proposé les
possibilités suivantes (pour plus de détails, voir la section
1.8.1) :
- Moyenne maximale,
- Moyenne minimale,
- Plus petit écart aux extrêmes.
On remarque que les heuristiques de critères de choix sur
les valeurs doivent être adaptées en fonction du type de
problème sur lequel on veut appliquer notre méthode.
Néanmoins, on retrouve, pour l'heuristique de choix sur
les valeurs à brancher, de grandes ressemblances entre les
problèmes de satisfaction de contraintes et les problèmes
d'optimisation combinatoire.
La question que nous nous sommes posé est de savoir si une
heuristique de choix sur les valeurs peut être identique pour les deux
types de problèmes.
| 
