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.

Abstract

This research evaluates the application of message passing to Constraint Optimization Problems (COPs). While message passing has proven effective for Constraint Satisfaction Problems (CSPs) using the Sum-Product algorithm, its usefulness for optimization remained undemonstrated. The primary objective introduces and evaluates the Max-Product algorithm as an alternative to Sum-Product for optimization. The central hypothesis proposes that Max-Product can provide marginals identifying values participating in optimal solutions. The methodology introduces an Oracle constraint applied to the objective variable, sending messages proportional to values to bias toward better solutions. This constraint proves essential for Max-Product, which otherwise produces uniform marginals equivalent to generalized arc consistency. Max-Product message computation algorithms are developed for four global constraints. For AllDifferent, computation reduces to the assignment problem in bipartite graphs, optimized to reuse intermediate matchings. For Table, Sum, and Regular constraints, existing Sum- Product algorithms are adapted by replacing sum accumulation with maximum operations. An empirical evaluation on 321 XCSP corpus instances uses normalized mean score as the primary metric. The DomWDeg + Max Marginal heuristic outperforms all alternatives. Limited discrepancy search, marginal reuse between propagation phases, and entropy-based early termination improve efficiency. Results demonstrate message passing effectiveness for optimization with 15% improvement over non-message-passing methods, showing that increased inference costs are offset by improved search guidance. Sum-Product with few iterations excels for short resolutions, while high iteration counts become advantageous for extended resolutions. Max-Product provides a compromise when resolution time is uncertain. We conclude that message passing constitutes an effective advanced inference method for constraint optimization. While Sum-Product generally demonstrates superiority over Max- Product, this study extends MiniCPBP’s applicability to COPs and opens perspectives for solving combinatorial optimization problems.