ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Autres revues >>

Ingénierie des Systèmes d'Information

Networking and Information Systems
1633-1311
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 8/RSTI1 - 2003  - pp.223-236
TITRE
Cassures de symétries à base de stabilisateurs. Applications aux CSP matriciels.

RÉSUMÉ
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.


ABSTRACT
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.


AUTEUR(S)
Jean-François PUGET

MOTS-CLÉS
CSP, Cassures de symétries, Algorithmes de recherche, Isomorphisme de graphe, Stabilisateurs, BIBD.

KEYWORDS
CSP, Symmetry breaking, Search, Graph isomorphism, Stabilizers, BIBD.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (213 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier