Cassures de symétries à base de stabilisateurs. Applications aux CSP matriciels.
L'addition de contraintes pour casser les symétries est une des méthodes les plus efficaces pour résoudre les problèmes de satisfaction de contraintes (CSPs.) Nous présentons une variante de cette méthode dans laquelle les contraintes cassant les symétries compatibles avec l'affectation partielle courante sont ajoutées pendant la recherche de solution. Le calcul de ces contraintes repose sur un calcul de tous les automorphismes d'un graphe. Le calcul des automorphismes d'un graphe n'est pas connu pour être NP-complet, et peut être résolu très efficacement en utilisant un CSP auxiliaire. Notre méthode est appliquée aux CSP matriciels où toutes les colonnes et toutes les lignes sont interchangeables. Des résultats expérimentaux sur une classe de problèmes combinatoires très symétriques montrent que l'efficacité de notre méthode est d'un ordre de grandeur supérieure à celle des méthodes publiées jusqu'alors.
The addition of symmetry breaking constraints is one of the most successful symmetry breaking technique for constraint satisfaction problems (CSP). In this paper we present a refinement of this method where we only add during search constraints that are not yet broken by the current partial assignment. The computation of those additional constraints require the computation of graph automorphism at each node. Graph automorphism computation is not know to be NP complete, and in practice can be solved quite efficiently using an auxiliary CSP. The method is refined to be applied to matrix problems where rows and columns can be permuted. An experimental comparison on a class of highly symmetrical combinatorial problems, namely BIBD show that our technique is at least an order of magnitude more efficient than best published techniques so far.
CSP, Cassures de symétries, Algorithmes de recherche, Isomorphisme de graphe, Stabilisateurs, BIBD.
CSP, Symmetry breaking, Search, Graph isomorphism, Stabilizers, BIBD.
Français
|
