,
,
94 2.2.5.3 Comparaison en termes de bornes de complexité et de performances ,
,
,
,
210 6.3.1 Comptage aveugle vs comptage conscient ,
,
,
,
#EBTD la version présentée dans l'algorithme 6.2 est basée sur un simple algorithme de retourarrière chronologique (BT ). Toutefois, dans les expérimentations fournies dans la section suivante, nous considérons un algorithme plus puissant qui est RF L. Ainsi, #EBT D choisit en premier la prochaine variable xà assigner, vol.46 ,
heuristique de choix de valeur (lignes 51-52) et l'assigneà la variable x. Si la nouvelle affectation est cohérente vis-à-vis des contraintes initiales de C et des nogoods structurels de N d (ligne 53), la recherche continue en choisissant une nouvelle variable et en effectuant une nouvelle affectation. Sinon, #EBT D essaye d'assignerà x une autre valeur de D x ,
moment où il est certain que cette affectation admet une extension cohérente sur tout le problème, il vise ensuiteà compter le nombre de solutions de chaque sousproblème enraciné en chaque cluster fils du cluster courant comme ferait #BT D. Plus précisément, si E i est, par exemple, le cluster courant dans la figure 6.1 (E g et E h sont déjà instanciés), son but est de calculer le nombre de solutions de P j |A, Similairement, #BT D enregistrerait les #goods correspondantsà chaque sousproblème ,
#EBT D ne procède pas ainsi. Il vise au contraireàéviter les inconvénients de cette approche décrits dans la partie 6.2.2. #EBT D explore alors les clusters fils différemment. Plus précisément, il viseà garantir qu'il ne compte exactement le nombre de solutions du sous-problème enraciné en un cluster fils que s'il existe une solution globale du problème compatible avec l'affectation courante, c'est-à-dire une extension de l'affectation courante qui s'étend sur toutes les variables du problème. Ce faisant, le good exact ainsi enregistré est nécessairement utilisé au moins une fois. Pour illustrer ce principe, dans la figure 6.1, après l'affectation du cluster E i , #EBT D essaye d'instancier, par ordre, les clusters E j , E k , E l , E m et E n (#EBT D explore, dans ce cas, les clusters fils de E i dans l'ordre E j , E l et E n ) ,
ligne 56) suspend l'énumération des solutions relativesà E i lorsqu'un nogood de E p(?) par rapportà E ? est enregistré avec E ? est un cluster exploré après E i . Dans ce cas, E bt = E p(?) et la recherche fait retour-arrière vers le cluster E p(?) ,
-16). Si A[E i ? E j ] correspondà un exact good (ligne 10), le good est exploité et la recherche ,
Il ajouteà Z età Z inconnu chaque cluster fils E j de E i pour lequel A[E i ? E j ] ne correspond pas nià un good ,
Au contraire, si A n'a pas puêtreétendue au sous-problème enraciné en E j , A[E p(j) ? E j ] est enregistrée comme un nogood (lignes 31-35). Il està noter que E p(j) n'est pas forcément E i . Les lignes 27 et 33 permettent finalement de supprimer de la pile ,
, nous distinguons deux phases qui s'alternent
, ? La première phase viseà s'assurer que pour une solution partielle, il existe une solution globale, c'est-à-dire une affectation qui s'étend de fa¸con cohérente sur toutes les variables du problème
une fois la présence d'une solution globale garantie, l'ensemble des extensions cohérentes d'une affectation induisant un sous-problème pour ce dernier ,
, Ces deux phases garantissent que, chaque fois que le nombre de solutions d'un sousproblème est calculé, celui-ci est exploité pour le calcul du nombre de solutions du problème. Nous allons donc maintenant démontrer que #EBT D est capable de calculer le nombre exact de solutions d'un problème tout en garantissant d'éviter certains calculs inutiles au sensévoqué précédemment
,
j ) : l'ensemble des variables de Desc(E j ) sans compter les variables de E i ? E j tel que E j est un cluster fils de E i pour lequel A ,
,
est exploité selon la définition d'un good exact et le sous-problème correspondant n'est pas visité. Si A[E i ? E j ] est un good partiel, le sous-problème enraciné en E j n'est pas exploré lors de la recherche d'une solution globale (vu qu'au moins une extension cohérente existe pour ce sousproblème). Cependant, une fois une solution globale trouvée, il sera visité afin de calculer #sol E j . Sinon, A[E i ? E j ] est inconnu et le sous-problème correspondant doitêtre exploré pour déterminer si une solution globale existe ,
? E k ) : l'ensemble des variables de Desc(E k ) sans compter les variables de E p(k) ? E k tel que E k ? Z. Le cluster E k est ,
N d ) retourne une paire (#sol, E bt ) où #sol est le nombre exact de solutions de P i |A ,
ligne 32), les fils de E i sont supprimés de la pile Z vu que leur exploration est désormais inutile (ligne 33). Ainsi, #EBT D retourne (0, E i ) puisqu'il n'existe aucune extension possible de A sur les variables de Desc(E j ) et le cluster E i doitêtre modifié (ligne 34). Sinon, E i = E p(j) et la recherche doit faire un retour-arrière plus loin. Ainsi, #EBT D retourne (#sol, E p(j ) avec #sol une borne inférieure sur le nombre de solutions de P i |A ,
, Si #sol E j > 0 et E bt = E j alors le nombre de solutions retourné est nécessairement une borne inférieure sur le nombre de solutions P j |A
,
, est alors enregistrée comme un good partiel qui peutêtre exploité ultérieurement, si nécessaire. Le raisonnement des lignes 26-29 est similaireà celui pour les lignes 32-35
,
A[E p(j) ? E j ] est enregistrée comme un good exact.À ce niveau, Z est vide puisque sinon l'exploration des clusters de Z aurait continué jusqu'à atteindre le dernier cluster. En d'autres termes, l'enregistrement des goods exacts ne peut pas se faire avant que tous les clusters de Z ne soient explorés. En outre, sachant que la traversée de la décomposition se fait grâceà une pile, si A[E p(j) ? E j ] est enregistrée comme un good exact alors tous les clusters E k insérés dans Z avant E j sont déjà exhaustivement explorés et l'affectation A ,
est alors valide pour Z = ? pour les trois sous-cas possibles.À la ligne 36, Z = ?, une solution globale aété déjà trouvée et pour chaque cluster fils E j ? Z inconnu , #sol E j est calculé et #sol est mis a jour (ligne 37). Si Z good ? = ? ,
d )) est valide. Sinon, nous avons V AR, par hypothèse d'induction ,
est valide. Par définition d'un good partiel, P j |A[E i ?E j ] a au moins une seule solution. Comme Z est vide (une solution globale existe), l'appel récursifà #EBT D retourne nécessairement le nombre exact de solutions de P j |A ,
, Une fois, tous les clusters fils E j considérés, #sol est mis-à-jour et #EBT D retourne (#sol, E i )
,
En effet, dans le cas où V E i = ?, l'appel récursif fait par #EBT D considère l'ensemble V E i \{x} qui contient strictement moins de variables que V E i (une variable en moins). Ainsi, la taille de V AR est désormais plus petite, Si V E i = ?, comme nous l'avons déjà vu, les appels récursifs aux lignes 20 et 41 garantissent que V AR ,
Un extension générale de ces travaux est d'aller au-delà de BT D. En effet, bien que la méthode BT D soit ici la méthode référence employée pourévaluer l'intérêt des nouvelles méthodes de calcul ou d'exploitation de la décomposition arborescente, les objectifs de la thèse ne se limitent pasà l'amélioration de BT D. Ainsi, une extension générale de ce travail est de l'appliquer aux autres méthodes structurelles comme celles basées sur la décomposition hyperarborescente, En cas d'égalité, nous exploitons le fait que pour l'appel suivant par ce dernier, voire meilleures. Finalement, l'importance de la minimisation de la largeur w + aété soulignée pour le comptage contrairement aux problèmes de décision et d'optimisation, 1987. ,
En conclusion, dans cette thèse, notre ambition est d'intégrer la brique structurelle aux briques standards des solveurs actuels. Nous avons tenté d'améliorer les méthodes structurelles et de montrer qu'elles peuventêtre compétitives vis-à-vis des méthodes classiques. Notre ambition est d'autant plus réaliste que l'intégration des méthodes telles que BT D s'avèreêtre d'une simplicité remarquable, Cette approche est particulièrement justifiée par les similitudes existantes entre les différentes méthodes notamment en termes de la liberté restreinte accordéeà l'heuristique de choix de variables, 2006. ,
, Choco : an open source java constraint programming library
, Luebeck university implementation for pace competition, Csp competition, 2008.
, Utrecht university implementation for pace competition, 2017 XCSP3 Competition, 2017.
Hypertree width and related hypergraph invariants, European Journal of Combinatorics, pp.2167-2181, 2007. ,
URL : https://hal.archives-ouvertes.fr/hal-01184381
Anytime hybrid best-first search with tree decomposition for weighted CSP, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.12-29, 2015. ,
URL : https://hal.archives-ouvertes.fr/hal-01198361
Efficient approximation for triangulation of minimum treewidth, Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp.7-15, 2001. ,
Approximation algorithms for treewidth. Algorithmica, pp.448-479, 2010. ,
Improved algorithms for counting solutions in constraint satisfaction problems, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.81-95, 2003. ,
Lifted MEU by Weighted Model Counting, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.1861-1867, 2012. ,
Principles of constraint programming, 2003. ,
Complexity of finding embeddings in ak-tree, SIAM Journal on Algebraic Discrete Methods, pp.277-284, 1987. ,
Easy problems for tree-decomposable graphs, Journal of Algorithms, pp.308-340, 1991. ,
Structural decomposition methods and what they are good for, Symposium on Theoretical Aspects of Computer Science (STACS), pp.12-28, 2011. ,
URL : https://hal.archives-ouvertes.fr/hal-00573592
Inapproximability of treewidth, one-shot pebbling, and related layout problems, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp.13-24, 2012. ,
Value elimination : Bayesian inference via backtracking search, Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp.20-28, 2002. ,
On the forward checking algorithm, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.292-309, 1995. ,
New upper bound heuristics for treewidth, International Workshop on Experimental and Efficient Algorithms, pp.216-227, 2005. ,
A branch and bound algorithm for exact, upper, and lower bounds on treewidth, International Conference on Algorithmic Applications in Management (AAIM), pp.255-266, 2006. ,
Backtracking through biconnected components of a constraint graph, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.291-296, 2001. ,
Approximate resolution of hard numbering problems, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.169-174, 1996. ,
Complete search restart strategies for satisfiability, IJCAI Workshop on Stochastic Search Algorithms, 2001. ,
Counting models using connected components, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.157-162, 2000. ,
A complexity analysis of space-bounded learning algorithms for the constraint satisfaction problem, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.298-304, 1996. ,
Backtracking search algorithms, Foundations of Artificial Intelligence, pp.85-134, 2006. ,
On the desirability of acyclic database schemes, Journal of the ACM (JACM), pp.479-513, 1983. ,
Global constraint catalogue : Past, present and future, Constraints, pp.21-62, 2007. ,
, Global constraint catalog, 2005.
URL : https://hal.archives-ouvertes.fr/hal-00485396
SAT-Based Approaches to Treewidth Computation : An Evaluation, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp.328-335, 2014. ,
Graphes et hypergraphes, 1973. ,
Maximum cardinality search for computing minimal triangulations of graphs, Algorithmica, pp.287-298, 2004. ,
A wide-range algorithm for minimal triangulation from an arbitrary ordering, Journal of Algorithms, pp.33-66, 2006. ,
URL : https://hal.archives-ouvertes.fr/lirmm-00268438
The minimum degree heuristic and the minimal triangulation process, International Workshop on Graph-Theoretic Concepts in Computer Science, pp.58-70, 2003. ,
URL : https://hal.archives-ouvertes.fr/lirmm-00191916
A vertex incremental approach for dynamically maintaining chordal graphs, International Symposium on Algorithms and Computation (ISAAC), pp.47-57, 2003. ,
Nonserial dynamic programming, 1972. ,
Arc-consistency and arc-consistency again, Artificial intelligence, pp.179-190, 1994. ,
URL : https://hal.archives-ouvertes.fr/lirmm-02310614
Constraint propagation. Foundations of Artificial Intelligence, pp.29-83, 2006. ,
URL : https://hal.archives-ouvertes.fr/lirmm-00117128
Neighborhood-based variable ordering heuristics for the constraint satisfaction problem, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.565-569, 2001. ,
The complexity of reasoning with global constraints, Constraints, pp.239-259, 2007. ,
URL : https://hal.archives-ouvertes.fr/lirmm-00195881
On forward checking for non-binary constraint satisfaction, Artificial Intelligence, pp.205-224, 2002. ,
MAC and combined heuristics : Two reasons to forsake FC (and CBJ ?) on hard problems, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.61-75, 1996. ,
Arc consistency for general constraint networks : preliminary results, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1997. ,
Refining the Basic Constraint Propagation Algorithm, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.309-315, 2001. ,
An optimal coarse-grained arc consistency algorithm, Artificial Intelligence, pp.165-185, 2005. ,
Constraint satisfaction from a deductive viewpoint, Artificial Intelligence, pp.401-413, 1988. ,
Adaptive restart control for conflict driven SAT solvers, Proceedings of the International conference on theory and applications of satisfiability testing (SAT), 2008. ,
Handbook of satisfiability, 2009. ,
The good old Davis-Putnam procedure helps counting models, Journal of Artificial Intelligence Research, pp.457-477, 1999. ,
, Backtrack programming techniques. Communications of the ACM, pp.651-656, 1975.
A practical algorithm for making filled graphs minimal, Theoretical Computer Science, pp.125-141, 2001. ,
Configuration automatique d'un solveur generique integrant des techniques de decomposition arborescente pour la resolution de problemes de satisfaction de contraintes, 2015. ,
URL : https://hal.archives-ouvertes.fr/tel-01214086
A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM Journal on computing, pp.1305-1317, 1996. ,
A c k n 5-Approximation Algorithm for Treewidth, SIAM Journal on Computing, pp.317-378, 2016. ,
On exact algorithms for treewidth, Proceedings The Annual European Symposium on Algorithms (ESA), pp.672-683, 2006. ,
URL : https://hal.archives-ouvertes.fr/lirmm-00804792
On exact algorithms for treewidth, ACM Transactions on Algorithms, p.12, 2012. ,
URL : https://hal.archives-ouvertes.fr/lirmm-00804792
Approximating treewidth, pathwidth, frontsize, and shortest elimination tree, Journal of Algorithms, pp.238-255, 1995. ,
Treewidth computations I. Upper bounds. Information and Computation, pp.259-275, 2010. ,
, Treewidth computations II. Lower bounds. Information and Computation, pp.1103-1119, 2011.
Graph theory with applications, 1976. ,
An investigation of the laws of thought, 1854. ,
On treewidth approximations, Discrete Applied Mathematics, pp.183-196, 2004. ,
Treewidth and minimum fill-in : Grouping the minimal separators, SIAM Journal on Computing, pp.212-232, 2001. ,
Listing all potential maximal cliques of a graph, Theoretical Computer Science, pp.17-32, 2002. ,
Boosting Systematic Search by Weighting Constraints, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.146-150, 2004. ,
, XCSP3 : An integrated format for benchmarking combinatorial constrained problems. arXiv, 2016.
Graph classes : a survey, 1999. ,
New methods to color the vertices of a graph, Communications of the ACM, pp.251-256, 1979. ,
Graph-based algorithms for boolean function manipulation, pp.677-691, 1986. ,
Boolean-width of graphs, Theoretical Computer Science, pp.5187-5204, 2011. ,
URL : https://hal.archives-ouvertes.fr/hal-00640644
The complexity of the counting constraint satisfaction problem, The International Colloquium on Automata, Languages, and Programming (ICALP), pp.646-661, 2008. ,
Towards a dichotomy theorem for the counting constraint satisfaction problem, Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), pp.562-571, 2003. ,
A characterisation of rigid circuit graphs. Discrete mathematics, pp.205-212, 1974. ,
Non-uniqueness of measures of maximal entropy for subshifts of finite type. Ergodic Theory and Dynamical Systems, pp.213-235, 1994. ,
Radio link frequency assignment, Constraints, pp.79-89, 1999. ,
Knowledge Compilation for Itemset Mining, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.1109-1110, 2010. ,
On probabilistic inference by weighted model counting, Artificial Intelligence, pp.772-799, 2008. ,
A Theoretical Comparison of Selected Csp Solving and Modeling Techniques, 2000. ,
Efficient path-consistency propagation, International Journal on Artificial Intelligence Tools, pp.121-142, 1998. ,
Compiling probabilistic graphical models using sentential decision diagrams, Proceedings of European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty, pp.121-132, 2013. ,
Heuristic and metaheuristic methods for computing graph treewidth. RAIRO-Operations Research, pp.13-26, 2004. ,
A unified theory of structural tractability for constraint satisfaction problems, Journal of Computer and System Sciences, pp.721-743, 2008. ,
A Unified Theory of Structural Tractability for Constraint Satisfaction and Spread Cut Decomposition, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.72-77, 2005. ,
The complexity of theorem-proving procedures, Proceedings of the Annual ACM symposium on Theory of computing, pp.151-158, 1971. ,
Arc consistency for soft constraints. Artificial Intelligence, pp.199-227, 2004. ,
An optimal k-consistency algorithm, Artificial Intelligence, pp.89-95, 1989. ,
Reduction operations in fuzzy or valued constraint satisfaction. Fuzzy Sets and Systems, pp.311-342, 2003. ,
Virtual Arc Consistency for Weighted CSP, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.253-258, 2008. ,
Soft arc consistency revisited, Artificial Intelligence, pp.449-478, 2010. ,
Optimal Soft Arc Consistency, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.68-73, 2007. ,
The monadic second order theory of Graphs I : Recognisable 662 sets of finite graphs. Information and Computation, p.663, 1990. ,
Upper bounds to the clique width of graphs, Discrete Applied Mathematics, pp.77-114, 2000. ,
Minimal elimination ordering inside a given chordal graph, Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science, pp.132-143, 1997. ,
Decomposable negation normal form, Journal of the ACM (JACM), pp.608-647, 2001. ,
On the tractable counting of theory models and its application to truth maintenance and belief revision, Journal of Applied Non-Classical Logics, pp.11-34, 2001. ,
Recursive conditioning, Artificial Intelligence, pp.5-41, 2001. ,
New advances in compiling CNF into decomposable negation normal form, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.328-332, 2004. ,
Modeling and reasoning with Bayesian networks, 2009. ,
SDD : A new canonical representation of propositional knowledge bases, SDD : A new canonical representation of propositional knowledge bases, p.819, 2011. ,
A perspective on knowledge compilation, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.175-182, 2001. ,
A knowledge compilation map, Journal of Artificial Intelligence Research, pp.229-264, 2002. ,
Using more reasoning to improve #SAT solving, Proceedings of the National Conference on Artificial Intelligence (AAAI), p.185, 2007. ,
A machine program for theoremproving, Communications of the ACM, pp.394-397, 1962. ,
From restricted path consistency to max-restricted path consistency, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.312-326, 1997. ,
Some practicable filtering techniques for the constraint satisfaction problem, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1997. ,
Learning while searching in constraint-satisfaction problems, Proceedings of the National Conference on Artificial Intelligence (AAAI), 1986. ,
Enhancement schemes for constraint processing : Backjumping, learning, and cutset decomposition, Artificial Intelligence, pp.273-312, 1990. ,
Constraint networks, 1992. ,
Topological parameters for time-space tradeoff, Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp.220-227, 1996. ,
Bucket elimination : A unifying framework for reasoning, Artificial Intelligence, pp.41-85, 1999. ,
Constraint processing, 2003. ,
Tractable structures for constraint satisfaction problems, Foundations of Artificial Intelligence, pp.209-244, 2006. ,
Reasoning with probabilistic and deterministic graphical models : Exact algorithms, Synthesis Lectures on Artificial Intelligence and Machine Learning, pp.1-191, 2013. ,
Topological Parameters for Time-space Tradeoff, Artificial Intelligence, pp.93-118, 2001. ,
The impact of AND/OR search spaces on constraint satisfaction and counting, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.731-736, 2004. ,
AND/OR search spaces for graphical models. Artificial intelligence, pp.73-106, 2007. ,
Experimental evaluation of preprocessing techniques in constraint satisfaction problems, 1989. ,
Experimental evaluation of preprocessing algorithms for constraint satisfaction problems, Artificial Intelligence, pp.211-241, 1994. ,
The cycle-cutset method for improving search performance in AI applications, 1986. ,
Network-based heuristics for constraint-satisfaction problems, Artificial intelligence, pp.1-38, 1987. ,
Tree clustering for constraint networks, Artificial Intelligence, pp.353-366, 1989. ,
Compact-table : Efficiently filtering table constraints with reversible sparse bit-sets, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.207-223, 2016. ,
Minimal forward checking, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp.432-438, 1994. ,
Heuristic methods for hypertree decomposition, Proceedings of the Mexican International Conference on Artificial Intelligence (MICAI), pp.1-11, 2008. ,
Connected tree-width. Combinatorica, 2017. ,
Local conditioning in Bayesian networks, Artificial Intelligence, pp.1-20, 1996. ,
On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, vol.25, pp.71-76, 1961. ,
Fast Probabilistic Planning through Weighted Model Counting, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pp.243-252, 2006. ,
The calculus of fuzzy restrictions as a basis for flexible constraint satisfaction, Proceedings of the International Conference on Fuzzy Systems, pp.1131-1136, 1993. ,
An effective dichotomy for the counting constraint satisfaction problem, SIAM Journal on Computing, pp.1245-1274, 2013. ,
An extensible SAT-solver, Proceedings of the International conference on theory and applications of satisfiability testing (SAT), pp.502-518, 2003. ,
Graph algorithms, 1979. ,
Uncertainty in constraint satisfaction problems : a probabilistic approach, Proceedings of the European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty, pp.97-104, 1993. ,
A constraint satisfaction framework for decision under uncertainty, Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp.167-174, 1995. ,
Selecting preferred solutions in fuzzy constraint satisfaction problems, Proceedings of the European Congress on Fuzzy and Intelligent Technologies (EUFIT), 1993. ,
Knowledge Compilation Properties of Trees-of-BDDs, Revisited, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.772-777, 2009. ,
URL : https://hal.archives-ouvertes.fr/hal-00866834
Exploiting Problem Structure for Solution Counting, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.335-343, 2009. ,
Improved approximation algorithms for minimum weight vertex separators, SIAM Journal on Computing, pp.629-657, 2008. ,
, , 1999.
Parameterized complexity theory, 2006. ,
Exact (exponential) algorithms for treewidth and minimum fill-in, The International Colloquium on Automata, Languages, and Programming (ICALP), pp.568-580, 2004. ,
URL : https://hal.archives-ouvertes.fr/hal-00085561
Treewidth computation and extremal combinatorics, Combinatorica, pp.289-308, 2012. ,
Taking Advantage of Stable Sets of Variables in Constraint Satisfaction Problems, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.1076-1078, 1985. ,
Synthesizing constraint expressions, Communications of the ACM, pp.958-966, 1978. ,
A sufficient condition for backtrack-free search, Journal of the ACM (JACM), pp.24-32, 1982. ,
Complexity of K-Tree Structured Constraint Satisfaction Problems, Proceedings of the National Conference on Artificial Intelligence (AAAI), 1990. ,
,
Neighborhood inverse consistency preprocessing, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.202-208, 1996. ,
Grand challenges for constraint programming, Constraints, pp.150-162, 2014. ,
, Partial constraint satisfaction. Artificial Intelligence, pp.21-70, 1992.
Generalizing Inconsistency Learning for Constraint Satisfaction, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.563-571, 1995. ,
Dead-end driven learning, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.294-300, 1994. ,
Look-ahead value ordering for constraint satisfaction problems, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.572-578, 1995. ,
Complete restart strategies using a compact representation of the explored search space, IJCAI Workshop on Stochastic Search Algorithms, 2003. ,
Incidence matrices and interval graphs, Pacific journal of mathematics, pp.835-855, 1965. ,
Parameterized Algorithms for Modular-Width, International Symposium IPEC, pp.163-176, 2013. ,
Semiring-based constraint solving and optimization, American Mathematical Monthly, pp.261-268, 1985. ,
Performance measurement and analysis of certain search algorithms, 1979. ,
The intersection graphs of subtrees in trees are exactly the chordal graphs, Journal of Combinatorial Theory, Series B, pp.47-56, 1974. ,
Dual Viewpoint Heuristics for, Proceedings of the European Conference on Artificial Intelligence (ECAI), vol.92, pp.31-35, 1992. ,
Minion : A fast scalable constraint solver, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.98-102, 2006. ,
Data structures for generalised arc consistency for extensional constraints, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.191-197, 2007. ,
Efficient Boolean Manipulation with OBDD's Can be Extended to FBDD's. Transactions on Computers, pp.1197-1209, 1994. ,
Dynamic backtracking, Journal of Artificial Intelligence Research (JAIR), pp.25-46, 1993. ,
Existential arc consistency : Getting closer to full arc consistency in weighted CSPs, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), vol.5, pp.84-89, 2005. ,
Exploiting Tree Decomposition and Soft Local Consistency In Weighted CSP, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.22-27, 2006. ,
Combinaison de nogoods extraits au redémarrage, Actes des Journées Francophones de Programmation par Contraintes (JFPC), pp.55-64, 2017. ,
A complete anytime algorithm for treewidth, Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp.201-208, 2004. ,
Approximate counting by sampling the backtrackfree search space, Proceedings of the National Conference on Artificial Intelligence (AAAI), p.198, 2007. ,
Approximate solution sampling (and counting) on and/or spaces, Lecture Notes in Computer Science, p.534, 2008. ,
Backtrack programming, Journal of the ACM (JACM), pp.516-524, 1965. ,
Algorithmic graph theory and perfect graphs, 2004. ,
From Sampling to Model Counting, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.2293-2299, 2007. ,
Model counting : A new strategy for obtaining good bounds, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.54-61, 2006. ,
Heavy-tailed phenomena in satisfiability and constraint satisfaction problems, Journal of automated reasoning, pp.67-100, 2000. ,
Boosting combinatorial search through randomization, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.431-437, 1998. ,
Counting CSP solutions using generalized XOR constraints, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.204-209, 2007. ,
Combining hypertree, bicomp, and hinge decomposition, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.161-165, 2002. ,
Hypertree decompositions and tractable queries, Proceedings of the ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp.21-32, 1999. ,
A comparison of structural CSP decomposition methods, Artificial Intelligence, pp.243-282, 2000. ,
On the universal relation, 1980. ,
Constraint solving via fractional edge covers, Proceedings of the annual ACM-SIAM symposium on Discrete algorithm, pp.289-298, 2006. ,
Constraint solving via fractional edge covers, ACM Transactions on Algorithms, p.4, 2014. ,
Decomposing constraint satisfaction problems using database techniques, Artificial intelligence, pp.57-89, 1994. ,
A Decomposition Methodology for Cyclic Databases. Advances in data base theory, pp.85-122, 1982. ,
Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints. RAIRO-Operations Research, pp.241-267, 2016. ,
URL : https://hal.archives-ouvertes.fr/hal-01277953
Über die Auflösung von Graphen in vollständige Teilgraphen, Ann. Univ. Sci. Budapest, Eötvös Sect. Math, pp.113-121, 1958. ,
Bounding connected tree-width, SIAM Journal on Discrete Mathematics, pp.1391-1400, 2016. ,
Metaheuristic algorithms and tree decomposition, Handbook of Computational Intelligence, pp.1255-1270, 2015. ,
Comments on Mohr and Henderson's path consistency algorithm, Artificial Intelligence, pp.125-130, 1988. ,
Increasing tree search efficiency for constraint satisfaction problems, Artificial intelligence, pp.263-313, 1980. ,
Nonsystematic backtracking search, 1995. ,
Limited discrepancy search, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.607-615, 1995. ,
Minimal triangulations of graphs : A survey, Discrete Mathematics, pp.297-317, 2006. ,
Computing minimal triangulations in time O (n? log n)= O (n 2.376 ), Proceedings of the Annual ACM-SIAM symposium on Discrete algorithms, pp.907-916, 2005. ,
Efficient implementation of a minimal triangulation algorithm, Proceedings The Annual European Symposium on Algorithms (ESA), pp.175-176, 2002. ,
A dynamic programming approach to sequencing problems, Journal of the Society for Industrial and Applied Mathematics, pp.196-210, 1962. ,
A generic arc-consistency algorithm and its specializations, Artificial Intelligence, pp.291-321, 1992. ,
Stochastic local search : Foundations and applications, 2004. ,
Local search methods, Foundations of Artificial Intelligence, pp.135-167, 2006. ,
Using DPLL for efficient OBDD construction, Proceedings of the International conference on theory and applications of satisfiability testing (SAT), pp.157-172, 2004. ,
Multi-language evaluation of exact solvers in graphical model discrete optimization, Constraints, pp.413-434, 2016. ,
,
2-way vs. d-way branching for CSP, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.343-357, 2005. ,
A filtering process for general constraint-satisfaction problems : achieving pairwise-consistency using an associated binary representation, Proceedings of the IEEE Workshop on Tools for Artificial Intelligence, pp.420-427, 1989. ,
About a certain minimal problem, Práce Moravské Pr?rodovedecké Spolecnosti, pp.57-63, 1930. ,
Cyclic-clustering : a compromise between tree-clustering and cycle-cutset method for improving search efficiency, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.369-371, 1990. ,
On the consistency of general constraint-satisfaction problems, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.114-119, 1993. ,
An Algorithmic Framework for Decomposing Constraint Networks, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp.1-8, 2015. ,
De nouvelles approches pour la décomposition de réseaux de contraintes, Actes des Journées Francophones de Programmation par Contraintes (JFPC), pp.140-149, 2015. ,
Improving Exact Solution Counting for Decomposition Methods, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp.327-334, 2016. ,
Towards a Dynamic Decomposition of CSPs with Separators of Bounded Size, Proceedings of the International Conference on Principle and Practice of Constraint Programming (CP), pp.298-315, 2016. ,
Vers une décomposition dynamique des réseaux de contraintes, Actes des Journées Francophones de Programmation par Contraintes (JFPC), pp.123-132, 2016. ,
Adaptive and Opportunistic Exploitation of Tree-decompositions for Weighted CSPs, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), 2017. ,
Vers une exploitation dynamique de la décomposition pour les CSPs pondérés, Actes des Journées Francophones de Programmation par Contraintes (JFPC), 2017. ,
Combined strategies for decompositionbased methods for solving CSPs, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp.184-192, 2009. ,
Computing and exploiting treedecompositions for solving constraint networks, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.777-781, 2005. ,
An extension of complexity bounds and dynamic heuristics for tree-decompositions of CSP, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.741-745, 2006. ,
Strategies and heuristics for exploiting tree-decompositions of constraint networks, Inference methods based on graphical structures of knowledge (WIGSK'06), ECAI workshop, pp.13-18, 2006. ,
Dynamic Management of Heuristics for Solving Structured CSPs, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.364-378, 2007. ,
A new Evaluation of Forward Checking and its Consequences on Efficiency of Tools for Decomposition of CSPs, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp.486-490, 2008. ,
Hybrid backtracking bounded by tree-decomposition of constraint networks, Artificial Intelligence, pp.43-75, 2003. ,
A time-space trade-off for constraint networks decomposition, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp.234-239, 2004. ,
Decomposition and good recording for solving Max-CSPs, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.196-200, 2004. ,
Combining Restarts, Nogoods and Decompositions for Solving CSPs, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.465-470, 2014. ,
Tree-Decompositions with Connected Clusters for Solving Constraint Networks, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.407-423, 2014. ,
Combining restarts, nogoods and bag-connected decompositions for solving CSPs, Constraints, pp.191-229, 2017. ,
Bayesian updating in causal probabilistic networks by local computations, Computational statistics quarterly, pp.269-282, 1990. ,
, Maximum matching width : new characterizations and a fast algorithm for dominating set. arXiv, 2015.
On the enhancement of the informed backtracking algorithm, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.967-967, 2003. ,
A Study of Backtracking Based Informed Algorithms, Proceedings of the Starting AI Researchers'Symposium (STAIRS), p.147, 2004. ,
Approximation algorithms for combinatorial problems, Proceedings of the Annual ACM symposium on Theory of computing, pp.38-49, 1973. ,
, Graphical models. Statistical Science, pp.140-155, 2004.
Handbook of constraint programming, pp.837-868, 2006. ,
Maintaining arc-consistency within dynamic backtracking, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.249-261, 2000. ,
URL : https://hal.archives-ouvertes.fr/hal-00869126
Practical tractability of CSPs by higher level consistency and tree decomposition, 2013. ,
Reducibility among combinatorial problems, Complexity of computer computations, pp.85-103, 1972. ,
Monte-Carlo algorithms for the planar multiterminal network reliability problem, Journal of Complexity, pp.45-64, 1985. ,
Counting-based look-ahead schemes for constraint satisfaction, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.317-331, 2004. ,
Unrestricted nogood recording in CSP search, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.873-877, 2003. ,
Generalized nogoods in CSPs, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.390-396, 2005. ,
Exploiting decomposition in constraint optimization problems, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.478-492, 2008. ,
Triangulation of Graphs -Algorithms Giving Small Total State Space, Judex R.R, 1990. ,
Conjunctive-query containment and constraint satisfaction, Proceedings of the ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pp.205-213, 1998. ,
Probabilistic graphical models : principles and techniques, 2009. ,
Knowledge Compilation for Model Counting : Affine Decision Trees, SDD : A new canonical representation of propositional knowledge bases, pp.947-953, 2013. ,
URL : https://hal.archives-ouvertes.fr/hal-00866468
Compiling Constraint Networks into Multivalued Decomposable Decision Graphs, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.332-338, 2015. ,
, Treewidth : computational experiments. Electronic Notes in Discrete Mathematics, pp.54-57, 2001.
Frequency assignment : Models and algorithms, 1999. ,
A diffusion algorithm for decreasing energy of maxsum labeling problem, Glushkov Institute of Cybernetics, 1975. ,
Minimal fill in O(n 2.69 ) time. Discrete mathematics, pp.366-371, 2006. ,
Leveraging belief propagation, backtrack search, and statistics for model counting, Proceedings of the International Conference on Integration of Artificial Intelligence and Operations Research techniques in Constraint Programming (CPAIOR), pp.127-141, 2008. ,
A model counting characterization of diagnoses, 2002. ,
Minimal forward checking with backmarking and conflict-directed backjumping, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp.290-298, 1996. ,
Efficient parallel algorithms for graphs of bounded tree-width, Journal of Algorithms, pp.20-44, 1996. ,
An Improved Decision-DNNF Compiler, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2017. ,
On preprocessing techniques and their impact on propositional model counting, Journal of Automated Reasoning, pp.413-481, 2017. ,
Defining and Evaluating Heuristics for the Compilation of Constraint Networks, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.172-188, 2017. ,
An automatic method of solving discrete programming problems, Econometrica : Journal of the Econometric Society, pp.497-520, 1960. ,
Boosting search with variable elimination, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.291-305, 2000. ,
Node and arc consistency in weighted CSP, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.48-53, 2002. ,
Boosting search with variable elimination in constraint optimization and constraint satisfaction problems, Constraints, pp.303-326, 2003. ,
Pseudo-tree search with soft constraints, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.131-135, 2002. ,
In the quest of the best form of local consistency for weighted CSP, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.239-244, 2003. ,
Solving weighted CSP by maintaining arc consistency, Artificial Intelligence, pp.1-26, 2004. ,
Graphical models, 1996. ,
Branch-and-bound methods : A survey, Operations research, vol.14, issue.4, pp.699-719, 1966. ,
STR2 : optimized simple tabular reduction for table constraints, Constraints, pp.341-371, 2011. ,
URL : https://hal.archives-ouvertes.fr/hal-00868225
Constraint Networks : Targeting Simplicity for Techniques and Algorithms, 2013. ,
Exploiting multidirectionality in coarse-grained arc consistency algorithms, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.480-494, 2003. ,
Conservative dual consistency, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.237-242, 2007. ,
URL : https://hal.archives-ouvertes.fr/hal-00194544
Path consistency by dual consistency, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.438-452, 2007. ,
URL : https://hal.archives-ouvertes.fr/hal-00383830
Second-order consistencies, Journal of Artificial Intelligence Research, pp.175-219, 2011. ,
A Study of Residual Supports in Arc Consistency, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.125-130, 2007. ,
URL : https://hal.archives-ouvertes.fr/hal-00261267
STR3 : A path-optimal filtering algorithm for table constraints, Artificial Intelligence, pp.1-27, 2015. ,
Nogood Recording from Restarts, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.131-136, 2007. ,
URL : https://hal.archives-ouvertes.fr/hal-00261264
Recording and Minimizing Nogoods from Restarts, Boolean Modeling and Computation (JSAT), pp.147-167, 2007. ,
URL : https://hal.archives-ouvertes.fr/hal-00191092
Reasoning from last conflict(s) in constraint programming, Artificial Intelligence, pp.1592-1614, 2009. ,
URL : https://hal.archives-ouvertes.fr/hal-00868108
Generalized arc consistency for positive table constraints, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.284-298, 2006. ,
URL : https://hal.archives-ouvertes.fr/hal-00121127
Enforcing arc consistency using bitwise operations, Constraint Programming Letters (CPL), pp.21-35, 2008. ,
URL : https://hal.archives-ouvertes.fr/hal-00868075
Increasing Nogoods in Restart-Based Search, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.3426-3433, 2016. ,
An increasing-nogoods global constraint for symmetry breaking during search, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.465-480, 2014. ,
Representation of a finite graph by a set of intervals on the real line, Fundamenta Mathematicae, pp.45-64, 1962. ,
Segmentation de la sériation pour la résolution de# SAT, Mathematiques Informatique et Sciences Humaines, pp.113-134, 1999. ,
A fast arc consistency algorithm for n-ary constraints, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.405-410, 2005. ,
On the complexity of choosing the branching literal in DPLL, Artificial intelligence, pp.315-326, 2000. ,
Optimal speedup of Las Vegas algorithms, Information Processing Letters, pp.173-180, 1993. ,
Stochastic systematic search algorithms for satisfiability, Electronic Notes in Discrete Mathematics, pp.190-204, 2001. ,
Consistency in networks of relations, Artificial intelligence, pp.99-118, 1977. ,
Optimal and efficient filtering algorithms for table constraints, Constraints, pp.77-120, 2014. ,
Decomposition during search for propagationbased constraint solvers, 2007. ,
Advances in and/or branch-and-bound search for constraint optimization, Proceedings of the International Workshop on Preferences and Soft Constraints, 2005. ,
AND/OR branch-and-bound for graphical models, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.224-229, 2005. ,
Best-first AND/OR search for graphical models, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.1171-1176, 2007. ,
The elimination form of the inverse and its application to linear programming, Management Science, pp.255-269, 1957. ,
, Conflict-Driven Clause Learning SAT Solvers, pp.131-153, 2009.
Two new lightweight arc consistency algorithms, Proceedings of the International Workshop on Constraint Propagation and Implementation (CPAI), pp.109-123, 2004. ,
Tree-based Russian doll search : Preliminary results, Proceedings of the CP Workshop on Soft Constraints, 2000. ,
Specializing russian doll search, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.464-478, 2001. ,
Opportunistic specialization in russian doll search, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.264-279, 2002. ,
Activity-based search for black-box constraint programming solvers, Proceedings of the International Conference on Integration of Artificial Intelligence and Operations Research techniques in Constraint Programming (CPAIOR), pp.228-243, 2012. ,
Minimizing conflicts : a heuristic repair method for constraint satisfaction and scheduling problems, Artificial Intelligence, pp.161-205, 1992. ,
Resolution and constraint satisfaction, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.555-569, 2003. ,
Arc and path consistency revisited, Artificial intelligence, pp.225-233, 1986. ,
Networks of constraints : Fundamental properties and applications to picture processing, Information sciences, pp.95-132, 1974. ,
Chaff : Engineering an efficient SAT solver, Proceedings of the Annual Design Automation Conference, pp.530-535, 2001. ,
Dsharp : Fast d-DNNF Compilation with sharpSAT, Proceedings of the Canadian Conference on Artificial Intelligence, pp.356-361, 2012. ,
, Connected tree-width. arXiv, 2012.
Tree search and arc consistency in constraint satisfaction algorithms, Search in artificial intelligence, pp.287-342, 1988. ,
, Bounded Height Trees and Tree-Depth. Sparsity, pp.115-144, 2012.
Invitation to fixed-parameter algorithms, 2006. ,
Bayesian networks and decision graphs, 2009. ,
A fast algorithm for finding an optimal ordering for vertex elimination on a graph, SIAM Journal on Computing, pp.133-145, 1976. ,
Minimal triangulation of a graph and optimal pivoting order in a sparse matrix, Journal of Mathematical Analysis and Applications, pp.622-633, 1976. ,
Anytime AND/OR depth-first search for combinatorial optimization, AI Communications, pp.211-227, 2012. ,
Approximating clique-width and branch-width, Journal of Combinatorial Theory, Series B, pp.514-528, 2006. ,
On compiling CNF into decision-DNNF, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.42-57, 2014. ,
Pruning Conformant Plans by Counting Models on Compiled d-DNNF Representations, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pp.141-150, 2005. ,
The use of linear graphs in Gauss elimination, SIAM review, pp.119-130, 1961. ,
Heuristics : Intelligent Search Strategies for Computer Problem Solving, 1984. ,
Probabilistic reasoning in intelligent systems : Networks of plausible inference, 1988. ,
Probabilistic reasoning in intelligent systems : networks of plausible inference, 2014. ,
A survey of tractable constraint satisfaction problems, 1997. ,
Improving GAC-4 for table and MDD constraints, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.606-621, 2014. ,
URL : https://hal.archives-ouvertes.fr/hal-01344079
Counting solutions of CSPs : A structural approach, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.260-265, 2005. ,
Counting-based search : Branching heuristics for constraint satisfaction problems, Journal of Artificial Intelligence Research, 2012. ,
Minimal orderings revisited. SIAM journal on matrix analysis and applications, pp.271-294, 2001. ,
A generalized Cyclic-Clustering Approach for Solving Structured CSPs, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp.724-728, 2009. ,
URL : https://hal.archives-ouvertes.fr/hal-01488801
Width-Based Restart Policies for Clause-Learning Satisfiability Solvers, Proceedings of the International conference on theory and applications of satisfiability testing (SAT), pp.341-355, 2009. ,
Hybrid algorithms for the constraint satisfaction problem. Computational intelligence, pp.268-299, 1993. ,
The next challenge for CP : Ease of use, 2004. ,
Graph expansion and the unique games conjecture, Proceedings of the ACM symposium on Theory of computing, pp.755-764, 2010. ,
Finding approximate separators and computing tree width quickly, Proceedings of the Annual ACM symposium on Theory of computing, pp.221-228, 1992. ,
Impact-based search strategies for constraint programming, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.557-571, 2004. ,
Generalized arc consistency for global cardinality constraint, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.209-215, 1996. ,
Nogood learning for constraint satisfaction, Proceedings of the CP Workshop on Constraint Programming Applications, 1996. ,
Graph minors. I. Excluding a forest, Journal of Combinatorial Theory, Series B, pp.39-61, 1983. ,
Graph minors II : Algorithmic aspects of treewidth, Algorithms, pp.309-322, 1986. ,
Graph minors. XIII. The disjoint paths problem, Journal of combinatorial theory, Series B, pp.65-110, 1995. ,
A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. Graph theory and computing, p.217, 1972. ,
Algorithmic aspects of vertex elimination on graphs, SIAM Journal on computing, pp.266-283, 1976. ,
Scene labeling by relaxation operations, IEEE Transactions on Systems, Man, and Cybernetics, pp.420-433, 1976. ,
Handbook of constraint programming, 2006. ,
On the hardness of approximate reasoning, Artificial Intelligence, pp.273-302, 1996. ,
, Xml representation of constraint networks : Format xcsp 2.1. arXiv, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00872825
Probabilistic networks and expert systems, 2001. ,
Fuzzy constraint satisfaction, Proceedings of the International Conference on Fuzzy Systems, pp.1263-1268, 1994. ,
Local restarts in SAT, Constraint Programming Letters (CPL), pp.3-13, 2008. ,
Contradicting Conventional Wisdom in Constraint Satisfaction, Proceedings of European Conference on Artificial Intelligence (ECAI), pp.125-129, 1994. ,
Understanding and improving the MAC algorithm, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.167-181, 1997. ,
Tractable cases of the extended global cardinality constraint, Constraints, pp.1-24, 2011. ,
Encoding treewidth into SAT, Proceedings of the International conference on theory and applications of satisfiability testing (SAT), pp.45-50, 2009. ,
Russian Doll Search with Tree Decomposition, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.603-608, 2009. ,
Algorithm for optimal winner determination in combinatorial auctions, Artificial intelligence, pp.1-54, 2002. ,
Combining Component Caching and Clause Learning for Effective Model Counting, Proceedings of the International conference on theory and applications of satisfiability testing (SAT), 2004. ,
Performing Bayesian inference by weighted model counting, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.475-481, 2005. ,
Possibilistic constraint satisfaction problems or how to handle soft constraints ?, Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp.268-275, 1992. ,
Arc consistency for soft constraints, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.411-425, 2000. ,
Valued constraint satisfaction problems : Hard and easy problems, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.631-639, 1995. ,
Two approaches to the solution maintenance problem in dynamic constraint satisfaction problems, Proceedings of the IJCAI Workshop on Knowledge-based Production Planning, Scheduling and Control, 1993. ,
Nogood recording for static and dynamic constraint satisfaction problems, International Journal on Artificial Intelligence Tools, pp.187-207, 1994. ,
Stubborness : A Possible Enhancement for Backjumping and Nogood Recording, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.165-172, 1994. ,
Call routing and the ratcatcher, Combinatorica, pp.217-241, 1994. ,
Global conditioning for probabilistic inference in belief networks, Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp.514-522, 1994. ,
Probability propagation, Annals of Mathematics and Artificial Intelligence, pp.327-351, 1990. ,
A practical algorithm for finding optimal triangulations, Proceedings of the National Conference on Artificial Intelligence (AAAI) and of the Conference on Innovative Applications of Artificial Intelligence (IAAI), pp.185-190, 1997. ,
Model counting for formulas of bounded clique-width, International Symposium on Algorithms and Computation (ISAAC), pp.677-687, 2013. ,
The Brélaz heuristic and optimal static orderings, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.405-418, 1999. ,
The phase transition and the mushy region in constraint satisfaction problems, Proceedings of the European Conference on Artificial Intelligence (ECAI), pp.100-104, 1994. ,
Value ordering for finding all solutions, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.311-316, 2005. ,
Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis, Artificial intelligence, pp.135-196, 1977. ,
Knowledge compilation properties of tree-of-BDDs, Proceedings of the National Conference on Artificial Intelligence (AAAI), p.502, 2007. ,
Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM Journal on computing, pp.566-579, 1984. ,
Bounded backtracking for the valued constraint satisfaction problems, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.709-723, 2003. ,
sharpSAT-counting models with advanced component caching and implicit BCP, Proceedings of the International conference on theory and applications of satisfiability testing (SAT), pp.424-429, 2006. ,
PP is as hard as the polynomial-time hierarchy, SIAM Journal on Computing, pp.865-877, 1991. ,
Associating parts of patterns, Information and Control, pp.583-601, 1966. ,
An algorithm for subgraph isomorphism, Journal of the ACM (JACM), pp.31-42, 1976. ,
Partition search for non-binary constraint satisfaction, Information Sciences, pp.3639-3678, 2007. ,
The complexity of computing the permanent, Theoretical computer science, pp.189-201, 1979. ,
Handbook of constraint programming, pp.245-280, 2006. ,
Problemes de satisfaction de contraintes : production et révision de solution par modifications locales, Proceedings of the International Avignon Workshop, pp.277-286, 1993. ,
Russian doll search for solving constraint optimization problems, Proceedings of the National Conference on Artificial Intelligence (AAAI), pp.181-187, 1996. ,
Improved exponential-time algorithms for treewidth and minimum fill-in, Proceedings of the Latin American Theoritical Informatics Symposium (LA-TIN), pp.800-811, 2006. ,
Search in a small world, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.1172-1177, 1999. ,
SAT v CSP, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp.441-456, 2000. ,
Generating Semantic Descriptions From Drawings of Scenes With Shadows, 1972. ,
Optimizing Simple Tabular Reduction with a Bitwise Representation, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.787-795, 2016. ,
A new approach to model counting, Proceedings of the International conference on theory and applications of satisfiability testing (SAT), pp.324-339, 2005. ,
The structure of graphs not admitting a fixed immersion, Journal of Combinatorial Theory, Series B, pp.47-66, 2015. ,
Computing the minimum fill-in is NP-complete, SIAM Journal on Algebraic Discrete Methods, pp.77-79, 1981. ,
Making AC-3 an optimal algorithm, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp.316-321, 2001. ,