Search

Your search keyword '"El Mouelhi, Achref"' showing total 19 results
Start Over Author "El Mouelhi, Achref"

Refine your results

more »

more »

more »
19 results on '"El Mouelhi, Achref"'

1. Extending Broken Triangles and Enhanced Value-Merging

Author

Cooper, Martin C., El Mouelhi, Achref, Terrioux, Cyril, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Rueher, Michel, editor

Published
2016
Full Text
View/download PDF

4. On Broken Triangles

Author

Cooper, Martin C., El Mouelhi, Achref, Terrioux, Cyril, Zanuttini, Bruno, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and O’Sullivan, Barry, editor

Published
2014
Full Text
View/download PDF

5. Different Classes of Graphs to Represent Microstructures for CSPs

Author

El Mouelhi, Achref, Jégou, Philippe, Terrioux, Cyril, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Goebel, Randy, editor, Siekmann, Jörg, editor, Wahlster, Wolfgang, editor, Croitoru, Madalina, editor, Rudolph, Sebastian, editor, Woltran, Stefan, editor, and Gonzales, Christophe, editor

Published
2014
Full Text
View/download PDF

6. Some New Tractable Classes of CSPs and Their Relations with Backtracking Algorithms

Author

El Mouelhi, Achref, Jégou, Philippe, Terrioux, Cyril, Zanuttini, Bruno, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Gomes, Carla, editor, and Sellmann, Meinolf, editor

Published
2013
Full Text
View/download PDF

12. On Broken Triangles (IJCAI 2016)

Author

Cooper, Martin, El Mouelhi, Achref, Terrioux, Cyril, Zanuttini, Bruno, Argumentation, Décision, Raisonnement, Incertitude et Apprentissage (IRIT-ADRIA), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse III - Paul Sabatier (UT3), Laboratoire des Sciences de l'Information et des Systèmes (LSIS), Centre National de la Recherche Scientifique (CNRS)-Arts et Métiers Paristech ENSAM Aix-en-Provence-Université de Toulon (UTLN)-Aix Marseille Université (AMU), COntraintes, ALgorithmes et Applications (COALA), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Equipe MAD - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), University of Oxford - Constraint Network Tractability: Beyond Structure and Language - EPSRC grant EP/L021226/1, International Joint Conferences on Artificial Intelligence (IJCAI), Association for the Advancement of Artificial Intelligence, ANR-10-BLAN-0210,TUPLES,Polynomialité pour la Compréhension et l'Extension des Limites des Solveurs Performants(2010), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Arts et Métiers Paristech ENSAM Aix-en-Provence-Centre National de la Recherche Scientifique (CNRS), Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Normandie Université (NU)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), and Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], [INFO]Computer Science [cs], Computer Science::Computational Complexity, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

International audience; A binary CSP instance satisfying the broken-triangle property (BTP) can be solved in polynomial time. Unfortunately, in practice, few instances satisfy the BTP. We show that a local version of the BTP allows the merging of domain values in binary CSPs, thus providing a novel polynomial-time reduction operation. Experimental trials on benchmark instances demonstrate a significant decrease in instance size for certain classes of problems. We show that BTP-merging can be generalised to instances with constraints of arbitrary arity. A directional version of the general-arity BTP then allows us to extend the BTP tractable class previously defined only for binary CSP.

Published
2016

13. Les triangles cassés, encore et encore

Author

Cooper, Martin, El Mouelhi, Achref, Terrioux, Cyril, Argumentation, Décision, Raisonnement, Incertitude et Apprentissage (IRIT-ADRIA), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse III - Paul Sabatier (UT3), Laboratoire des Sciences de l'Information et des Systèmes (LSIS), Centre National de la Recherche Scientifique (CNRS)-Arts et Métiers Paristech ENSAM Aix-en-Provence-Université de Toulon (UTLN)-Aix Marseille Université (AMU), Arts et Métiers ParisTech, HESAM Université (HESAM), COntraintes, ALgorithmes et Applications (COALA), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Aix-Marseille Université - AMU (FRANCE), Arts et Métiers ParisTech (FRANCE), Centre National de la Recherche Scientifique - CNRS (FRANCE), Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE), Université Toulouse III - Paul Sabatier - UT3 (FRANCE), Université Toulouse - Jean Jaurès - UT2J (FRANCE), Université Toulouse 1 Capitole - UT1 (FRANCE), Université de Toulon - UTLN (FRANCE), Institut National Polytechnique de Toulouse - INPT (FRANCE), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Arts et Métiers Paristech ENSAM Aix-en-Provence-Centre National de la Recherche Scientifique (CNRS), and HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)

Subjects
Logique en informatique, Triangles cassés, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Informatique et langage, Intelligence artificielle, Apprentissage, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

International audience; Les triangles cassés représentent un concept important, non seulement pour la résolution en temps polynomial des problèmes de satisfaction de contraintes, mais aussi pour l'élimination de variables ou encore la réduction de la taille des domaines par la fusion des valeurs. Plus précisément, pour une variable donnée d'un CSP binaire arc-cohérent, si aucun triangle cassé ne se produit sur aucun couple de valeurs, alors cette variable peut être éliminée tout en préservant la satisfiabilité. Plus récemment, il a été démontré qu'en cas de non applicabilité de cette règle à cause de l'existence d'au moins un triangle cassé, il se peut qu'il existe deux valeurs de cette même variable sur lesquelles aucun triangle cassé ne s'est produit. Dans ce cas, ces deux valeurs peuvent être fusionnées en une seule tout en préservant la satisfiabilité. Dans ce papier, nous montrons que sous certaines conditions, et même en cas d'existence de quelques triangles cassés sur un couple de valeurs d'une variable donnée, les deux valeurs peuvent être fusionnées sans changer la satisfiabilité de l'instance.

Published
2016

15. Autour des Triangles Cassés

Author

Cooper, Martin, El Mouelhi, Achref, Terrioux, Cyril, Zanuttini, Bruno, Argumentation, Décision, Raisonnement, Incertitude et Apprentissage (IRIT-ADRIA), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université Toulouse III - Paul Sabatier (UT3), Laboratoire des Sciences de l'Information et des Systèmes (LSIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Arts et Métiers Paristech ENSAM Aix-en-Provence-Centre National de la Recherche Scientifique (CNRS), Equipe MAD - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Normandie Université (NU)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS), ANR-10-BLAN-0210,TUPLES,Polynomialité pour la Compréhension et l'Extension des Limites des Solveurs Performants(2010), Aix-Marseille Université - AMU (FRANCE), Arts et Métiers ParisTech (FRANCE), Centre National de la Recherche Scientifique - CNRS (FRANCE), Ecole Nationale Supérieure d'Ingénieurs de Caen - ENSICAEN (FRANCE), Institut National Polytechnique de Toulouse - INPT (FRANCE), Université Toulouse III - Paul Sabatier - UT3 (FRANCE), Université Toulouse - Jean Jaurès - UT2J (FRANCE), Université Toulouse 1 Capitole - UT1 (FRANCE), Université de Caen Basse-Normandie (FRANCE), Université de Toulon - UTLN (FRANCE), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Centre National de la Recherche Scientifique (CNRS)-Arts et Métiers Paristech ENSAM Aix-en-Provence-Université de Toulon (UTLN)-Aix Marseille Université (AMU), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), and Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)

Subjects
Logique en informatique, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Propriété des triangles cassés, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Informatique et langage, Intelligence artificielle, Apprentissage, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

Une instance CSP binaire qui satisfait la propriété des triangles cassés (BTP) peut être résolue en temps polynomial. Malheureusement, en pratique, peu d'instances satisfont cette propriété. Nous montrons qu'une version locale de BTP permet de fusionner des valeurs dans les domaines d'instances binaires quelconques. Des expérimentations sur des instances benchmarks démontrent la diminution significative de la taille de l'instance pour certaines classes de problèmes. Nous montrons que cette fusion peut être gén éralisée aux instances ayant des contraintes d'arité quelconque et nous étudions les liens avec la résolution dans SAT. Une version orientée nous permet ensuite d'étendre la classe polynomiale BTP précédemment définie pour les CSP binaires. Ce papier est un résume de l'article M. C. Cooper, A. El Mouelhi, C. Terrioux et B. Zanuttini. On Broken Triangle In Proceedings of CP, LNCS 8656, 9-24, 2014.

Published
2015

16. On Broken Triangles (CP 2014)

Author

Cooper, Martin, El Mouelhi, Achref, Terrioux, Cyril, Zanuttini, Bruno, Argumentation, Décision, Raisonnement, Incertitude et Apprentissage (IRIT-ADRIA), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse III - Paul Sabatier (UT3), Laboratoire des Sciences de l'Information et des Systèmes (LSIS), Centre National de la Recherche Scientifique (CNRS)-Arts et Métiers Paristech ENSAM Aix-en-Provence-Université de Toulon (UTLN)-Aix Marseille Université (AMU), Equipe MAD - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), Association for Constraint Programming, ANR-10-BLAN-0210,TUPLES,Polynomialité pour la Compréhension et l'Extension des Limites des Solveurs Performants(2010), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Arts et Métiers Paristech ENSAM Aix-en-Provence-Centre National de la Recherche Scientifique (CNRS), Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Normandie Université (NU)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), and Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Computer Science::Computational Complexity, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

International audience; A binary CSP instance satisfying the broken-triangle property (BTP) can be solved in polynomial time. Unfortunately, in practice, few instances satisfy the BTP. We show that a local version of the BTP allows the merging of domain values in binary CSPs, thus providing a novel polynomial-time reduction operation. Experimental trials on benchmark instances demonstrate a significant decrease in instance size for certain classes of problems. We show that BTP-merging can be generalised to instances with constraints of arbitrary arity. A directional version of the general-arity BTP then allows us to extend the BTP tractable class previously defined only for binary CSP.

Published
2014
Full Text
View/download PDF

19. Sur la complexité des algorithmes de backtracking et quelques nouvelles classes polynomiales pour CSP

Author

El Mouelhi, Achref, Jégou, Philippe, Terrioux, Cyril, Zanuttini, Bruno, Laboratoire des Sciences de l'Information et des Systèmes (LSIS), Centre National de la Recherche Scientifique (CNRS)-Arts et Métiers Paristech ENSAM Aix-en-Provence-Université de Toulon (UTLN)-Aix Marseille Université (AMU), Equipe MAD - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), Simon de Givry, Inria Saclay, Ist, Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Arts et Métiers Paristech ENSAM Aix-en-Provence-Centre National de la Recherche Scientifique (CNRS), Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Normandie Université (NU)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), and Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

The question of tractable classes of constraint satisfaction problems (CSPs) has been studied for a long time, and is now a very active research domain. However, studies of tractable classes are typically very theoretical. They usually introduce classes of instances together with polynomial time algorithms for recognizing and solving them, and the algorithms can be used only for the new class. In this paper, we address the issue of tractable classes of CSPs from a di erent perspective. We investigate the complexity of classical, generic algorithms for solving CSPs (such as Forward Checking). We introduce a new parameter for measuring their complexity and derive new complexity bounds. By relating the com- plexity of CSP algorithms to graph-theoretic parameters, our analysis allows us to point at new tractable classes, which can be solved directly by the usual CSP algorithms in polynomial time, and without the need to recognize the classes in advance., L'étude des classes polynomiales, pour les problèmes de satisfaction de contraintes (CSP), constitue depuis longtemps un domaine de recherche important qui s'avère aujourd'hui très actif. Cependant, les travaux réalisés jusqu'à présent se sont révélés pour l'essentiel théoriques. En effet, ils se cantonnent en général à la définition de classes d'instances pour lesquelles des algorithmes polynomiaux ad hoc, à la fois pour la reconnaissance et pour la résolution, sont proposes. Ces algorithmes ne peuvent être, en fait, utilisés que pour le traitement d'une classe d'instances donnée. Ils s'avèrent ainsi difficilement exploitables en pratique, et ne sont donc pas exploités au sein de solveurs généraux. L'intérêt pratique des classes polynomiales est ainsi très limitée. Dans cet article, nous abordons la question des classes polynomiales CSP d'un point de vue différent de l'approche classique, en nous intéressant aux algorithmes que l'on peut retrouver dans les systèmes de résolution opérationnels. Pour cela, nous _étudions d'abord la complexité d'algorithmes génériques de résolution de CSP tels que le Forward-Checking par exemple. Cette étude s'appuie sur l'exploitation d'un paramètre issu de la théorie des graphes, et qui permet de proposer de nouvelles bornes de complexité. La mise en relation de ces nouvelles bornes avec certains résultats issus de la théorie des graphes nous permet d'exhiber de nouvelles classes polynomiales. De cette façon, nous montrons comment des algorithmes classiques de résolution de CSP peuvent traiter efficacement en pratique ainsi qu'en théorie, des instances de CSP, sans devoir reconnaître au préalable leur appartenance à d'éventuelles classes polynomiales.

Published
2012

Catalog

Books, media, physical & digital resources
See catalog results