Revising hull and box consistency 论文

摘要

Most interval-based solvers in the constraint logic programming framework are based on either hull consistency or box consistency (or a variation of these ones) to narrow domains of variables involved in continuous constraint systems. This paper rst presents HC4, an algorithm to enforce hull consistency without decomposing complex constraints into primitives. Next, an extended denition for box consistency is given and the resulting consistency is shown to subsume hull consistency. Finally, BC4, a new algorithm to eciently enforce box consistency is described, that replaces BC3the original solely Newton-based algorithm to achieve box consistencyby an algorithm based on HC4 and BC3 taking care of the number of occurrences of each variable in a constraint. BC4 is then shown to signicantly outperform both HC3 (the original algorithm enforcing hull consistency by decomposing constraints) and BC3. 1 Introduction Finite representation of numbers precludes computers from exactly solv...