Bipartite Encoding: A New Binary Encoding for Solving Non-Binary CSPs

Bipartite Encoding: A New Binary Encoding for Solving Non-Binary CSPs

Ruiwei Wang, Roland H.C. Yap

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 1184-1191. https://doi.org/10.24963/ijcai.2020/165

Constraint Satisfaction Problems (CSPs) are typically solved with Generalized Arc Consistency (GAC). A general CSP can also be encoded into a binary CSP and solved with Arc Consistency (AC). The well-known Hidden Variable Encoding (HVE) is still a state-of-the-art binary encoding for solving CSPs. We propose a new binary encoding, called Bipartite Encoding (BE) which uses the idea of partitioning constraints. A BE encoded CSP can achieve a higher level of consistency than GAC on the original CSP. We give an algorithm for creating compact bipartite encoding for non-binary CSPs. We present a AC propagator on the binary constraints from BE exploiting their special structure. Experiments on a large set of non-binary CSP benchmarks with table constraints using the Wdeg, Activity and Impact heuristics show that BE with our AC propagator can outperform existing state-of-the-art GAC algorithms (CT, STRbit) and binary encodings (HVE with HTAC).
Keywords:
Constraints and SAT: Constraint Satisfaction
Constraints and SAT: Constraints: Modeling, Solvers, Applications