Abstract
Reformulating constraint satisfaction problems (CSPs) in lower arity is a common procedure when computing consistency. Lower arity CSPs are simpler to treat than high arity CSPs. Several consistency algorithms have exponential complexity in the CSP’s arity, others only work on low arity CSPs. Much work in constraint satisfaction has concentrated on binary CSPs, since in a theoretical view any CSP ...
Abstract
Reformulating constraint satisfaction problems (CSPs) in lower arity is a common procedure when computing consistency. Lower arity CSPs are simpler to treat than high arity CSPs. Several consistency algorithms have exponential complexity in the CSP’s arity, others only work on low arity CSPs. Much work in constraint satisfaction has concentrated on binary CSPs, since in a theoretical view any CSP on discrete domains can be reformulated in binary form. Although this is not true for numeric CSPs the constraints of which are equalities and inequalities specified using mathematical expressions, it has been shown that rewriting such CSPs in terms of ternary constraints is possible as long as only unary and binary operators occur in the mathematical expressions. Nevertheless, very few methods to actually perform this task automatically have been suggested so far, the reformulation is often done by hand. In this paper we present algorithms to rewrite numeric CSPs in terms of ternary constraints by introducing auxiliary variables. Since the complexity of consistency algorithms also depends on the number of variables involved, we suggest heuristics, to keep the number of introduced auxiliary variables low and to eliminate unnecessary variables from the original CSP.
Altmetric