Guider la recherche grâce au passage de messages pour les problèmes d'optimisation sous contraintes

Cette recherche évalue l’application du passage de messages aux problèmes d’optimisation sous contraintes (COPs). Alors que le passage de messages a prouvé son efficacité pour les problèmes de satisfaction de contraintes (CSPs) avec l’algorithme Sum-Product, son utilité pour l’optimisation restait à démontrer. L’objectif principal consiste à introduire et évaluer l’algorithme Max-Product comme alternative à Sum-Product pour l’optimisation. L’hypothèse centrale propose que Max-Product peut fournir des marginales désignant les valeurs participant aux solutions optimales. La méthodologie introduit une contrainte Oracle appliquée à la variable objectif, envoyant des messages proportionnels aux valeurs pour biaiser favorablement les meilleures solutions. Cette contrainte s’avère indispensable pour Max-Product qui produit sinon des marginales uniformes équivalentes à la cohérence d’arc généralisée. Des algorithmes de calcul de messages Max-Product sont développés pour quatre contraintes globales. Pour AllDifferent, le calcul se réduit au problème d’assignation dans un graphe biparti, optimisé pour réutiliser des couplages intermédiaires. Pour les contraintes Table, Sum et Regular, les algorithmes Sum-Product existants sont adaptés en remplaçant l’accumulation par somme par un maximum. L’évaluation empirique sur 321 exemplaires du corpus XCSP utilise le score normalisé moyen comme métrique principale. L’heuristique DomWDeg + Max Marginal surpasse toutes les alternatives. La recherche à divergence limitée, la réutilisation des marginales entre phases de propagation et l’interruption anticipée basée sur l’entropie améliorent l’efficacité. Les résultats démontrent l’efficacité du passage de messages pour l’optimisation avec des améliorations de 15% comparées aux méthodes sans passage de messages, montrant que le coût accru de l’inférence est compensé par le guidage pertinent de la recherche. Sum-Product avec un faible nombre d’itérations excelle pour les résolutions courtes, tandis qu’un nombre élevé d’itérations devient avantageux sur les résolutions prolongées. Max-Product constitue une bonne alternative à Sum-Product si le temps de résolution est incertain. Nous concluons que le passage de messages constitue une méthode d’inférence avancée efficace pour l’optimisation sous contraintes. Si Sum-Product démontre généralement une supériorité sur Max-Product, l’étude étend l’applicabilité de MiniCPBP aux COPs et ouvre des perspectives pour la résolution de problèmes d’optimisation combinatoire.