A Combined Approach for Constraints over Finite Domains and Arrays
This addresses a domain-specific challenge in software verification by improving constraint solving for arrays, though it appears incremental as it builds on existing solvers.
The paper tackled the problem of effective reasoning over arrays in constraint programming by proposing FDCC, a combined approach using global symbolic reasoning and local consistency filtering. The result showed that FDCC solved more formulas than portfolio combinations of the individual solvers, with reasonable overhead.
Arrays are ubiquitous in the context of software verification. However, effective reasoning over arrays is still rare in CP, as local reasoning is dramatically ill-conditioned for constraints over arrays. In this paper, we propose an approach combining both global symbolic reasoning and local consistency filtering in order to solve constraint systems involving arrays (with accesses, updates and size constraints) and finite-domain constraints over their elements and indexes. Our approach, named FDCC, is based on a combination of a congruence closure algorithm for the standard theory of arrays and a CP solver over finite domains. The tricky part of the work lies in the bi-directional communication mechanism between both solvers. We identify the significant information to share, and design ways to master the communication overhead. Experiments on random instances show that FDCC solves more formulas than any portfolio combination of the two solvers taken in isolation, while overhead is kept reasonable.