Testing Unsatisfiability of Constraint Satisfaction Problems via Tensor Products
This work addresses the challenge of efficiently proving unsatisfiability for constraint satisfaction problems, which is incremental as it builds on existing microstructure methods by introducing tensor decomposition.
The paper tackles the problem of proving unsatisfiability in constraint satisfaction problems (CSPs) by developing a stochastic local search method that decomposes the microstructure into graph tensors, resulting in proofs of unsatisfiability in half the time without quality loss and another decomposition being twenty times faster and effective 30% of the time compared to prior methods.
We study the design of stochastic local search methods to prove unsatisfiability of a constraint satisfaction problem (CSP). For a binary CSP, such methods have been designed using the microstructure of the CSP. Here, we develop a method to decompose the microstructure into graph tensors. We show how to use the tensor decomposition to compute a proof of unsatisfiability efficiently and in parallel. We also offer substantial empirical evidence that our approach improves the praxis. For instance, one decomposition yields proofs of unsatisfiability in half the time without sacrificing the quality. Another decomposition is twenty times faster and effective three-tenths of the times compared to the prior method. Our method is applicable to arbitrary CSPs using the well known dual and hidden variable transformations from an arbitrary CSP to a binary CSP.