|
Techniques hybrides de recherche exacte et approchée: application à des problèmes de transport( Télécharger le fichier original )par Boris BONTOUX Université d'Avignon et des pays de Vaucluse - Doctorat spécialité informatique 2008 |
1.9.3 Application à des problèmes de Satisfaction de Contraintes académiquesPour mesurer l'efficacité de notre méthode, nous l'évaluons sur trois jeux de problèmes académiques. Le premier est un ensemble d'instances du problème de sac-àdos multidimensionnel (Multiknapsack Problem, voir (Kellerer et al., 2004) pour plus de détails). Généralement, l'objectif du Multiknapsack Problem est de maximiser la valeur des objets emportés. Dans les instances choisies, le problème est transformé en un problème de satisfaction de contraintes, pour lequel une seule solution doit être trouvée. Pour cela, une contrainte est ajoutée : la valeur de l'objectif doit être supérieure à une valeur donnée. Le problème est modélisé par un ensemble de contraintes linéaires portant sur des variables binaires. Ces problèmes sont généralement complexes pour des solvers basés sur de la propagation de contraintes. 6 problèmes sont issus d'une bibliothèque d'instances de Recherche Opérationnelle1 pour lesquels la fonction objectif est contrainte à prendre la valeur optimale. Ces problèmes ont entre 6 et 11 contraintes et le nombre de variables est compris entre 15 et 50. Le second jeu de problèmes est le problème du Carré Magique (voir le livre de Descombes (2000) pour une vision historique de ce problème). Le problème consiste à remplir une matrice de taille n par n de telle sorte que toutes les cases contiennent une valeur différente et que les sommes sur chaque ligne, sur chaque colonne et sur les deux diagonales soient les mêmes. Enfin, le troisième jeu de problèmes est le problème de Coloration de Graphes (voir le livre de Jensen et Toft (1995) pour plus de détails sur ce problème). Les instances 1. Les instances sont disponibles sur le site http :// mscmga.ms.ic.ac.uk/jeb/orlib/mdmkpinfo.html sont issues d'une bibliothèque d'instances2. Afin de mesurer plus efficacement notre méthode dans le temps imparti, nous limitons la taille des instances à k. Pour cela, nous ne prenons en considération que les k premiers noeuds du graphe. Ainsi, nous réduisons le temps de calcul, ce qui nous permet de comparer notre méthode avec les méthodes du solver ILOG Solver. On peut noter que les instances ainsi construites sont de petites tailles. De plus, les méthodes que nous proposons ne sont pas comparables en terme de qualité et de temps d'exécution aux méthodes dédiées à ce problème. Toutes les expérimentations ont été faites sur un AMD 64 X2 3800, 1 Go de RAM, en utilisant ILOG Solver 6.0. Les tableaux 1.3, 1.4 et 1.5 présentent les temps d'exécution en secondes et le temps a été limité à 1500 secondes. Le nombre de points de choix est présenté afin de montrer une mesure de la taille de l'arbre de recherche. Pour tous les problèmes qui suivent, le critère d'évaluation du sous-arbre qui a été retenu est la profondeur maximale du sous-arbre. La mise à jour des pondérations suit le principe du maximum. Ainsi, une pondération associée à un couple variable-valeur est mise à jour dès qu'une profondeur de taille plus importante est trouvée dans un sous-arbre issu du même couple variable-valeur. La mise à jour consiste en un remplacement de l'ancienne pondération par la nouvelle pondération. Pour chaque variable, la valeur choisie en premier est celle ayant la pondération la plus important. Enfin, la phase de sondage consiste la construction de K chemins aléatoires, où K est égal à la somme de la cardinalité des domaines des variables. Ce choix permet de ne pas passer un temps trop important dans la phase de sondage. Le tableau 1.3 présente les résultats sur les instances du problème de sac-à-dos multidimensionnel. Nous comparons plusieurs méthodes : la méthode « Aléatoire » choisit aléatoirement la variable à instancier parmi les variables non instanciées ainsi que la valeur à instancier, la méthode « MinDomainSize » choisit en premier la variable de plus petit domaine et la plus petite valeur du domaine, la méthode DLS est la méthode telle que présentée précédemment et la méthode DLS avec sondage est la méthode présentée précédemment, initialisée par la phase de sondage. Pour les deux dernières méthodes, le choix de la valeur pour chaque variable est la valeur ayant la plus grande pondération. Les en-têtes des colonnes sont les suivants : - Problemes : numéro de l'instance, - Random : temps d'exécution en secondes (CPU) et nombre de points de choix (Pts Ch.) pour la méthode « Aléatoire », - MinDomainSize : temps d'exécution en secondes (CPU) et nombre de points de choix (Pts Ch.) pour la méthode de choix de la variable
ayant le plus domaine, Ch.) pour la méthode DLS, - DLS et sondage : temps d'exécution en secondes (CPU) et nombre de points de choix (Pts Ch.) pour la méthode DLS, combiné avec la phase de sondage. Les résultats présentés dans le tableau 1.3 montrent l'intérêt de notre méthode cou- 2. Les instances sont disponibles sur le site http :// mat.gsia.cmu.edu/COLOR/instances.html
TABLE 1.3 - Résultats expérimentaux, instances de Sac-à-dos Multidimensionnel plée avec une phase d'initialisation par sondage. La méthode « Aléatoire » ne permet pas de résoudre l'instance mknap1-6 dans le temps imparti. La stratégie du plus petit domaine est ici peu efficace, puisque toutes les variables ont le même domaine. On re-marque que la méthode DLS sans phase de sondage est légèrement plus rapide que la méthode du plus petit domaine. Par contre, couplée avec la phase de sondage, la méthode DLS est plus rapide que les autres méthodes, montrant ainsi clairement l'intérêt d'une phase de sondage. Le tableau 1.4 présente les résultats sur les instances du problème de sac-à-dos multidimensionnel. Les méthodes comparées sont les mêmes que pour le problème du sacà-dos multidimensionnel. Les en-têtes des colonnes sont les suivants : - Taille : taille du carré, - Random : temps d'exécution en secondes (CPU) et nombre de points de choix (Pts Ch.) pour la méthode « Aléatoire », - MinDomainSize : temps d'exécution en secondes (CPU) et nombre de points de choix (Pts Ch.) pour la méthode de choix de la variable
ayant le plus domaine, Ch.) pour la méthode DLS, - DLS et sondage : temps d'exécution en secondes (CPU) et nombre de points de choix (Pts Ch.) pour la méthode DLS, combiné avec la phase de sondage.
TABLE 1.4 - Résultats expérimentaux, instances de Carré Magique Les conclusions que l'on peut tirer à la lecture des résultats présentés dans le tableau 1.3 sont similaires à celles pour le problème de sac-à-dos multidimensionnel. Pour les instances de taille supérieure à 7, la méthode « Aléatoire » et la méthode de choix du plus petit domaine ne trouvent aucune solution dans le temps imparti. La méthode DLS sans phase de sondage est un peu plus rapide et efficace que la méthode de choix du plus petit domaine, mais ne permet pas de résoudre l'ensemble des instances. En ce qui concerne la méthode DLS avec phase de sondage, on peut remarquer que les temps d'exécution sont légèrement plus longs pour les instances de petite taille. Cela est dû au temps requis par la phase de sondage. Néanmoins, la phase de sondage semble important dans la méthode DLS car elle permet à la méthode de résoudre l'ensemble des instances dans le temps imparti. Le tableau 1.5 présente les résultats sur le problème de Coloration de Graphes. Ce problème est un problème particulier. L'objectif étant de minimiser le nombre chromatique (c'est-à-dire le nombre de couleurs différentes utilisées), on peut voir ce problème comme un problème d'optimisation combinatoire. Cependant, on peut le voir comme un problème de satisfaction de contraintes : existe-t-il une solution à ce problème telle que le nombre chromatique soit inférieur à C ? Ainsi, les pondérations qui déterminent les priorités de branchement ne sont pas calculées pour la variable à minimiser, représentant le nombre chromatique. Nous comparons dans ce tableau plusieurs méthodes : la méthode « Aléatoire », la méthode « MinDomainSize », la méthode DLS avec plusieurs critères de choix pour les variables (moyenne des pondérations mini-male, moyenne des pondérations maximales et écarts aux extrêmes, présentées dans la section 1.8.1). Pour ce problème, la méthode DLS est toujours couplée avec la phase de sondage. Les en-têtes des colonnes sont les suivants : - Problèmes : nom de l'instance, - k : limite fixée à la taille de l'instance, - Random : temps d'exécution en secondes (CPU) pour la méthode « Aléatoire », - MinDomainSize : temps d'exécution en secondes (CPU) pour la méthode de choix de la variable ayant le plus domaine, - Moy Min. : temps d'exécution en secondes (CPU) pour la
méthode DLS avec le - Moy Max. : temps d'exécution en secondes (CPU) pour la méthode DLS avec le critère de plus grande moyenne des pondérations pour sélectionner les variables, - Ecart Min : temps d'exécution en secondes (CPU) pour la méthode DLS avec le critère de plus petit écart des pondérations aux extrêmes pour sélectionner les variables, Les résultats présentés dans le tableau 1.5 montrent l'efficacité de la plus petite moyenne des pondérations comme critère de choix pour les variables. Ce critère, qui suit la politique de « First Fail », est le plus efficace pour les instances choisies. La méthode « Aléatoire » et la méthode de choix de la variable ayant le plus domaine ne permettent pas de résoudre l'ensemble des instances. La méthode DLS avec le critère de plus petit écart des pondérations aux extrêmes propose des solutions de bonnes qualités, comparables à la méthode par défaut d'ILOG Solver, sans toutefois la surpasser. 1.10. Conclusion et perspectives
TABLE 1.5 - Résultats expérimentaux, instances de Coloration de Graphes |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
