Une comparaison de logiciels doptimisation sur une large collection de modèles graphiquesReportar como inadecuado




Une comparaison de logiciels doptimisation sur une large collection de modèles graphiques - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 UBIA - Unité de Biométrie et Intelligence Artificielle 2 Insight Centre for Data Analytics

Résumé : Le cadre des modèles graphiques à variables discrètes permet de modéliser des problèmes d-optimisation NP- difficiles pour lesquels la fonction objectif se factorise en un ensemble de fonctions locales. L-interprétation graphique de ces modèles est que chaque fonction est représentée par une clique sur les variables de sa portée. Les modèles graphiques dits déterministes ont pour objectif de minimiser la somme des fonctions locales, pouvant aussi être des contraintes si seuls les coûts zero ou infini sont utilisés. Les modèles graphiques dits probabilistes ont pour objectif de maximiser le produit des fonctions des contraintes si usage uniquement des probabilités zero ou un. Une transformation directe existe entre les deux classes de modèles graphiques, qui peuvent également être modélisés en programmation linéaire en nombres entiers ou en problème de satisfiabilité maximum en logique propositionnelle.Dans cet article, nous évaluons plusieurs logiciels implémentant l- état de l-art en méthodes complètes d-optimisation sur une large collection de modèles graphiques déterministes et probabilistes issus de diverses compétitions Max-CSP 2008, Probabilistic Inference Challenge 2011, Weighted Partial Max-SAT Evaluation 2013, MiniZinc Challenge 2012 & 2013, ainsi que des collections provenant des problème de satisfaction de contraintes pondérées et en traitement d-images. Au total, 3018 instances sont mises a disposition dans cinq formats et sept formulations avec les scripts de conversion. Les résultats montrent que différents logiciels généralistes obtiennent de bons résultats sur plusieurs catégories de modèles graphiques, suggérant des opportunités pour une approche portfolio d-algorithmes.

Keywords : graphical model constraint programming combinatorial optimization weighted constraint satisfaction problem





Autor: David Allouche - Simon De Givry - Barry Hurley - Georgios Katsirelos - Barry O-Sullivan - Thomas Schiex -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados