Multi Objective 3-SAT Problems addressed with Message Passing Techniques
Résumé
Message passing algorithms have been very successful in solving hard combinatorial problems, and have resulted in breakthrough results in the domain of random K-SAT problems. However, only single-objective SAT problems have been adressed by survey-propagation methods, whereas most real-world problems are indeed multi objective. A first approach to multi objective optimization using a message-passing algorithm is introduced, that aims at sampling the Pareto set, i.e. the set of Pareto-non-dominated solutions. Several heuristics are proposed and tested on a simple bi-objective 3-SAT problem. A first approach is based on a straightforward deformation of the survey-propagation equation to locally encode a Pareto trade-off. A simple heuristic is then tested, which combines an elimination procedure of clauses with the usual decimation of variables used in the survey propagation algorithm, and is able to sample different regions of the Pareto-front. In a second stage we study in more details the compliance of these deformed equations with basic belief-propagation (BP) properties. This lead us first to an explicit Markov random field of valid warning configuration, for which the survey-propagation equations are basic belief propagation equations. This observation is then generalized by defining a MRF for warnings configurations expected to approximate well the Pareto-front. The survey propagation equations associated to this new MRF are derived, allowing for consistent estimations of the Pareto-set on single problem instances. Numerical experiments on artificial problems up to 100000 variables are presented and discussed.
Les algorithmes de passage de messages ont permis de résoudre des problèmes combinatoires difficiles avec pour résultats des progrès notables dans le domaine K-SAT aléatoire. Cependant, les résultats obtenus par survey-propagation sont limités à des problèmes SAT mono-critères alors que la plupart des problèmes réel sont multi objectifs. Une première approche au contexte multi objectif est proposée, dont le but est d'échantillonner le front de Pareto, c.a.d. l'ensemble des solutions non-dominées au sens de Pareto. Plusieurs heuristiques sont proposées et testées, sur un problème 3-SAT bi-objectifs. Une première approche est basée sur une déformation directe des équations survey-propagation afin d'encoder localement un compromis de Pareto. Une heuristique simple est ensuite testée qui combine une procédure d'élimination des clauses avec la décimation habituelle des variables utilisée dans l'algorithm survey-propagation, permettant d'échantilloner différentes régions du front de Pareto. Dans un deuxième temps, nous étudions en détails la compatibilité de ces équations avec les propiétés basique de belief-propagation. Ceci nous conduit d'abord à trouver un Champ Markovien aléatoire explicite sur les configurations de warnings pour lesquelles les équations de survey-propagation coincident avec les equations de belief-propagation. Cette observation est ensuite généralisée en définissant un champ Markovien aléatoire pour les configurations situées dans le voisinage du de l'ensemble de Pareto. Les équations de survey-propagation correspondantes que nous obtenons donne alors la possibilité d'estimer de façon cohérente du front de Pareto sur des exemple de problèmes. Des expériences numériques sur des problèmes artificiels atteignants 100000 variables sont présentées et discutées.
Origine : Fichiers produits par l'(les) auteur(s)