Diagramme de séquence de la résolution d’un problème de PPC

Arbres de recherche

L’une des techniques principalement utilisé pour trouver des solutions en PPC est l’utilisation d’un arbre de recherche. Un arbre de recherche permet d’affecter des valeurs aux variables de manière structurée. Nous utilisons un algorithme de recherche par retours arrière dans le but d’explorer l’arbre. L’intérêt de ce type d’algorithme est qu’il est considéré comme étant complet. Un algorithme complet veut dire que nous avons la garantie que s’il existe une solution, alors nous la trouverons. Nous avons donc, réciproquement, la garantie que si une solution n’est pas trouvée malgré l’exploration complète de l’arbre, alors il n’existe pas de solution pour le modèle que l’utilisateur a fourni. Un autre intérêt pour ce type d’algorithme de recherche est que nous avons seulement besoin d’une quantité polynomiale d’espace mémoire pour trouver une solution. En effet, nous n’explorons qu’une seule branche de l’arbre à la fois. Puisque souvent un utilisateur ne souhaite pas trouver toutes les solutions, alors il est intéressant de constater que l’impact sur la mémoire vive est minimisé.

Dans un arbre de recherche, les noeuds représentent une solution partielle où un certain nombre de variables sont instanciées et les arêtes représentent une nouvelle assignation d’une valeur à une des variables du modèle. Le noeud racine de l’arbre représente un ensemble où aucune variable n’a été instanciée. Lorsque nous atteignons une feuille, alors nous avons une assignation complète de toutes les variables, ce qui correspond à une solution au problème. Nous illustrons, en premier lieu, une énumération simple de solutions d’un modèle qui ne possède aucune contrainte. Le problème génère l’arbre illustré par la figure 1.1. Nous voyons, dans les noeuds, l’état de la solution partielle. Chaque feuille représente une solution au problème. Essentiellement, considérant le fait qu’il n’y avait aucune contrainte, l’arbre généré est une énumération de toutes les combinaisons de valeurs que les variables peuvent prendre.

Heuristiques de branchement

Dans la section sur les arbres de recherche (section 1.1), nous instancions les variables dans l’ordre de déclaration et nous choisissons les valeurs en ordre croissant. Il est par contre possible d’influencer la topologie de l’arbre de recherche en utilisant un autre critère. En réalité, le but est de visiter les branches de l’arbre les plus prometteuses le plus tôt possible. Pour ce faire, nous utilisons une heuristique de choix de variables pour influencer l’ordre de sélection des variables et nous utilisons une heuristique de choix de valeurs pour influencer l’ordre de sélection des valeurs dans les variables. Ce qui est intéressant c’est que nous ne sommes pas limités qu’à un seul choix pour l’un ou l’autre type d’heuristique.

Un utilisateur peut même créer des heuristiques personnalisées si son problème le requiert. La bonne sélection des heuristiques appropriées dépend de l’expérience des utilisateurs. Par contre, comme Liberatore [36] le démontre, le simple fait de décider avec certitude si une variable est la première variable dans un ordonnancement optimal des variables est au moins aussi compliqué que de décider si le problème de PPC a une solution [65]. Trouver un ordonnancement optimal des valeurs est aussi très clairement au moins aussi complexe du fait que, si une solution existe, alors un ordonnancement optimal des valeurs pourrait être utilisé pour trouver rapidement une solution [65]. C’est pourquoi l’expertise de l’utilisateur est essentielle lorsque vient le temps de décider quelles heuristiques utiliser pour résoudre un problème.

Heuristiques de choix de variables

Nous pouvons distinguer deux types d’heuristiques de choix de variables. Nous avons les heuristiques à ordonnancement statique. Un ordonnancement statique indique que l’ordre dans lequel les différentes variables seront instanciées lors de la recherche est connu d’avance (avant de débuter la recherche dans l’arbre). Par exemple, dans l’exemple 2 de la section 1.1, nous utilisons l’ordre x1, x2, x3 pour instancier les variables. Par contre, nous aurions pu aussi utiliser l’ordre x3, x2, x1 ou x2, x3, x1 ou un autre pour instancier les variables. C’est au modélisateur de le déterminer selon ce qu’il juge être le plus performant. Il existe aussi des heuristiques à ordonnancement dynamique qui modifient l’ordre d’instanciation des variables selon les événements qui se produisent lors de la recherche dans l’arbre. Par exemple, Golomb et Baumert [20] propose une heuristique dynamique qui choisit la variable qui contient le plus petit nombre de valeurs restant dans son domaine. Une autre technique, proposée par Haralick et Elliott [23], est de sélectionner la variable qui a le plus de chance de mener rapidement à un échec et donc forcer un retour arrière.

Fouille en profondeur

Une stratégie très simple dans sa mise en oeuvre est la fouille en profondeur (Depth-First Search (DFS)). Lorsque nous explorons un arbre, la première variable à être sélectionnée par l’heuristique de choix de variables représente le niveau racine. La variable va être instanciée à la première valeur de l’heuristique de choix de valeurs. Par la suite, nous sélectionnons la deuxième variable de l’heuristique de choix de variables et nous y assignons aussi la première valeur choisie par l’heuristique de choix de valeurs. Nous continuons ainsi jusqu’à ce que toutes les variables soient instanciées (toujours en ordre de l’heuristique de choix de variables) auquel cas, nous avons une solution, ou jusqu’à ce que le domaine d’une variable soit vidé de ses valeurs du fait de la propagation des contraintes (donc un échec). Si nous cherchons également d’autres solutions ou que nous avons un échec, il faut revenir en arrière jusqu’à retrouver une variable pour laquelle nous avons une valeur que nous n’avons pas essayée encore (donc la deuxième valeur sélectionnée par l’heuristique de choix de valeurs).

Lorsque c’est le cas, alors nous assignons cette valeur à la variable et nous redescendons dans l’arbre à nouveau. Nous continuons ainsi tant et aussi longtemps que nous n’avons pas rempli la condition d’arrêt de l’exploration de l’arbre ou, encore, que l’arbre n’ait pas été exploré au complet. Essentiellement, DFS cherche à essayer toutes les valeurs possibles (dans l’ordre de l’heuristique de choix de valeurs) des variables les plus basses dans l’arbre avant de remettre en question les choix de valeurs des variables plus hautes. Nous pouvons aussi dire que nous sélectionnons toujours, en priorité, le noeud enfant non exploré le plus à gauche. La figure 1.3 montre l’exploration d’un arbre avec DFS.

Table des matières

Introduction
1 Notions préliminaires
1.1 Arbres de recherche
1.2 Filtrage et propagation
1.3 Heuristiques de branchement
1.4 Stratégies de recherche
1.5 Solveur
1.6 Bris de symétries
2 Création d’un nouveau solveur
2.1 Présentation du solveur
2.2 Diagramme de séquence de la résolution d’un problème de PPC
2.3 Conclusion
3 Utilisation du solveur pour la résolution d’un problème industriel: génération de patrons de chargement alternatifs pour les séchoirs à bois
3.1 Description du problème industriel
3.2 Description de l’approche de résolution proposée
3.3 Expérimentations
3.4 Discussion
3.5 Conclusion
4 Implémentation d’un nouvel événement : lorsque la procrastination paie
4.1 Balanced Incomplete Block Design
4.2 Filtrage tardif
4.3 Filtrage tardif pour le BIBD
4.4 Expérimentations
4.5 Discussion
4.6 Conclusion
Conclusion
A Modèle MIP pour le problème du séchoir
Bibliographie

Télécharger le rapport complet