Mohamed Réda SAÏDI

Membre de l'équipe INCA   Fonction : Attaché temporaire d'enseignement et de recherche, Post-doctorant (ATER post-doc.) UFR : Université de la Méditerranée (U2)   Tél. : 04 91 11 35 41 E-mail : mohamedsaidilsisorg   Adresse :  Laboratoire des Sciences de l'Information et des Systèmes (LSIS - UMR 6168) Université de Provence (U1) - Centre de Mathématiques et d'Informatique Technopôle Château-Gombert 39, rue F. Joliot Curie 13453 Marseille Cedex 13 Bureau : R117

	Thèse soutenue jeudi 13 décembre 2007, à 14h30 - CMI - Technopôle de Château Gombert en salle C101 Etude de la symétrie et de la dominance dans les réseaux de contraintes au sens CSPs à domaines finis discrets

THÈSE

Sujet de thèse : Symétrie et Décomposition dans les Problèmes de Satisfaction de Contraintes (CSPs) Directeur(s) de thèse : Belaïd Benhamou Résumé : La symétrie et la décomposition de contraintes sont deux approches connues dans la résolution de contraintes. Leurs apports ont été considérables dans la résolution de problèmes réputés difficils. Nous voulons étudier les avantages et les inconvénients qui peuvent émerger de leur association. Pour se faire, nous nous sommes intéressé dans un premier temps aux contraintes de différence. Les CSPs à contraintes de différence sont des CSPs particuliers où toutes les contraintes sont des contraintes de différence. Une contrainte de différence entre deux variables Xi et Xj du CSP, exprime l’inégalité entre elles. Dans les CSPs à domaines finis discrets cette contrainte force les deux variables Xi et Xj à prendre deux valeurs différentes. Ce cadre restreint de CSP est suffisamment expressif pour représenter des problèmes du domaine de l’intelligence artificielle. Plusieurs travaux de recherche ont été consacrés pour résoudre ces réseaux de contraintes. Un premier travail a porté sur l’association des propriétés de symétries et des techniques de décomposition pour la résolution des CSP à contraintes de différence. Nous avons appliqué les résultats pour résoudre des instances du problème de coloriage de graphes (instances de DIMACS, et instances aléatoires). Cette étude sera étendu dans le futur aux CSP à contraintes quelconques pour couvrir un champs d’application plus large.

PUBLICATIONS

[ présentation : catégorie > année / année > catégorie / compacte / BibTeX ]

[1] B. Benhamou, Mohamed Réda Saidi, “Une nouvelle méthode basée sur la dominance et la coloration pour le test d'inconsistance de CSPs”, in: JFPC'08, 2008.[bib]

[2] B. Benhamou, M. R. Saïdi, “A new incomplete method for CSP inconsistency checking”, in: Twenty-Third AAAI Conference on Artificial Intelligence (AAAI-08), AAAI Press, Chicago, Illinois, USA, juillet 2008. à paraître.[bib]

[3] B. Benhamou, M. R. Saïdi, “Detecting and Eliminating Local Symmetry During Search in CSPs”, in: 3rd Indian International Conference on Artificial Intelligence (IICAI-07), Bhanu Prasad, n° ISBN 978-0-9727412-2-4, pp. 151-166, Pune, India, décembre 2007.[bib]

[4] B. Benhamou, M. R. Saïdi, “Local Symmetry Breaking During Search in CSPs”, in: The 13th International Conference on Principles and Practice of Constraint Programming (CP 2007), Springer, LNCS, vol. 4741, pp. 195-209, Providence, USA, septembre 2007.[bib]

[5] B. Benhamou, M. R. Saïdi, “Dynamic Detection and Elimination of Local Symmetry in CSPs”, in: The CP 2007 Workshop on Symmetry and Constraint Satisfaction Problems (SymCon'07), B. Benhamou, B.Y. Choueiry, and B. Hnich (Eds.), pp. 22-29, Providence, USA, septembre 2007.[bib]

[6] Stéphane Zampelli, Yves Deville, M. R. Saïdi, B. Benhamou, “Symmetry Breaking in Subgraph Isomorphism”, in: The CP 2007 Workshop on Symmetry and Constraint Satisfaction Problems (SymCon'07), Providence, USA, septembre 2007. à paraître.[bib]

[7] B. Benhamou, M. R. Saïdi, “Elimination des symétries locales durant la résolution des CSPs”, in: Actes des troisièmes Journées Francophones de Programmation par Contraintes (JFPC’2007), pp. 245-254, Rocquencourt, France, juin 2007.[bib]

[8] B. Benhamou, M. R. Saïdi, “Eliminating Local Symmetry in CSPs”, in: The International Symmetry Conference (ISC 2007), Edinburgh, SCOTLAND, janvier 2007.[bib]

[9] Stéphane Zampelli, Yves Deville, M. R. Saïdi, B. Benhamou, Pierre Dupont, “Breaking Local Symmetries in Subgraph Pattern Matching”, in: The International Symmetry Conference (ISC 2007), Edinburgh, SCOTLAND, janvier 2007.[bib]

[10] B. Benhamou, M. R. Saïdi, “Reasoning by dominance in Not-Equals binary constraint networks”, in: Proceedings of the Twelfth International Conference on Principles and Practice of Constraint Programming (CP 2006 ), Springer, LNCS, vol. 4204, pp. 670-674, Cité des Congrès - Nantes, France, septembre 2006.[bib]

[11] B. Benhamou, M. R. Saïdi, “Reasoning by dominance in Not-Equals binary constraint networks”, in: The CP 2006 Workshop on Symmetry and Constraint Satisfaction Problems (SymCon'06), pp. 9-16, Cité des Congrès - Nantes, France, septembre 2006.[bib]

[12] B. Benhamou, M. R. Saïdi, “Etude de la dominance dans les CSPs à contraintes de différence”, in: Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC'2006), pp. 63-70, juin 2006.[bib]

[13] M. R. Saïdi, B. Benhamou, “Dealing with symmetry in Not-Equals binary constraint networks: application to graph coloring”, in: Colloque sur l'Optimisation et les Systèmes d'Information (COSI'06), Alger, Algérie, juin 2006.[bib]

[14] B. Benhamou, M. R. Saïdi, “Some improvements in symmetry elimination in not-equals binary constraint networks”, in: Proceedings of the satelite workshop of CP 2005, Symmetry and Constraint Satisfaction Problems (SymCon'05), pp. 1-7, Sitges, Spain, October 2005.[bib]

[15] M. R. Saïdi, B. Benhamou, “Symétries dans les réseaux de contraintes de différence”, in: 7ème Rencontres Jeunes Chercheurs en Intelligence Artificielle, RJCIA'05, Emmanuel Guéré, Plate-Forme AFIA, pp. 239-252, Nice, France, juin 1-3 2005.[bib]

webmaster