Published on Tue Jan 03 2012

The RegularGcc Matrix Constraint

Ronald de Haan, Nina Narodytska, Toby Walsh

We study propagation of the RegularGcc global constraint. This ensures that each row of a matrix of decision variables satisfies a Regular constraint. On the negative side, we prove that propagation is NP-hard even under some strong restrictions.

0
0
0
Abstract

We study propagation of the RegularGcc global constraint. This ensures that each row of a matrix of decision variables satisfies a Regular constraint, and each column satisfies a Gcc constraint. On the negative side, we prove that propagation is NP-hard even under some strong restrictions (e.g. just 3 values, just 4 states in the automaton, or just 5 columns to the matrix). On the positive side, we identify two cases where propagation is fixed parameter tractable. In addition, we show how to improve propagation over a simple decomposition into separate Regular and Gcc constraints by identifying some necessary but insufficient conditions for a solution. We enforce these conditions with some additional weighted row automata. Experimental results demonstrate the potential of these methods on some standard benchmark problems.

Fri Mar 06 2009
Artificial Intelligence
The Complexity of Reasoning with Global Constraints
Constraint propagation is one of the techniques central to the success of constraint programming. With global (or non-binary) constraints, the cost of propagation may be much greater than the cost for binary constraints. We study the computational complexity of reasoning with global constraints.
0
0
0
Tue Mar 08 2011
Artificial Intelligence
On Minimal Constraint Networks
The tractability or intractability of computing a solution to such a minimal network was a long standing open question. Dechter conjectured this computation problem to be NP-hard. We prove this conjecture.
0
0
0
Mon Sep 28 2009
Artificial Intelligence
Breaking Generator Symmetry
Dealing with large numbers of symmetries is often problematic. We show that focusing on just generators improves tractability. We also show that it is polynomial in the size of the generating set to eliminate all symmetric solutions.
0
0
0
Thu Mar 12 2020
NLP
Regular Intersection Emptiness of Graph Problems: Finding a Needle in a Haystack of Graphs with the Help of Automata
The Int_reg-problem of a combinatorial problem P asks whether the language L(M) accepted by M contains any positive instance of the problem P. We consider a natural graph encoding so that the language of all graph encodings is regular.
0
0
0
Fri Dec 14 2007
Artificial Intelligence
Decomposition During Search for Propagation-Based Constraint Solvers
DDS is an integration of And/Or tree search into propagation-based constraint solvers. DDS dynamically decomposes sub-problems of a constraint satisfaction problem into independent partial problems, avoiding redundant work.
0
0
0
Wed Apr 13 2011
Artificial Intelligence
Kernels for Global Constraints
Bessiere et al. (AAAI'08) showed that several intractable global constraints can be efficiently propagated when certain natural problem parameters are small. In particular, the complete propagation of a global constraint is fixed-parameter tractable in k.
0
0
0