Box-set consistency for interval-based constraint problems

ABSTRACT

As opposed to finite domain CSPs, arc consistency cannot be enforced, in general, on CSPs over the reals, including very simple instances. In contrast, a stronger property, the so-called box-set consistency, that requires a no-split condition in addition to arc consistency, can be obtained on a much larger number of problems.To obtain this property, we devise a lazy algorithm that combines hull consistency filtering, interval union projection, and intelligent domain splitting. It can be applied to any numerical CSP, and achieves box-set consistency if constraints are redundancy-free in terms of variables. This holds even if the problem is not intervalconvex. The main contribution of our approach lies in the way we bypass the non-convexity issue, which so far was a synonym for either a loss of accuracy or an unbounded growth of label size.We prove the correctness of our algorithm and through experimental results, we show that, as compared to a strategy based on a standard bisection, it may lead to gains while never producing an overhead.

REFERENCES

• 1: Frédéric Benhamou , Frédéric Goualard , Laurent Granvilliers , Jean-François Puget, Revising hull and box consistency, Proceedings of the 1999 international conference on Logic programming, p.230-244, November 1999, Las Cruces, New Mexico, United States
• 2: F. Benhamou , D. McAllester , P. van Hentenryck, CLP(intervals) revisited, Proceedings of the 1994 International Symposium on Logic programming, p.124-138, November 1994, Symposia, Melbourne
• 3: F. Benhamou and W. Older. Applying interval arithmetic to real, integer and boolean constraints. Journal of Logic Programming, 32:1--24, 1997.
• 4: G. Chabert, G. Trombettoni, and B. Neveu. New light on arc consistency over continous domains. Research Report RR-5365, Institut National de Recherche en Informatique et en Automatique, 2004.
• 5: R. Dechter , J. Pearl, Network-based heuristics for constraint-satisfaction problems, Artificial Intelligence, v.34 n.1, p.1-38, Dec. 1987 [doi>10.1016/0004-3702(87)90002-6]
• 6: F. Delobel, H. Collavizza, and M. Rueher. Comparing partial consistencies. In Reliable Computing, pages 213--228. Kluwer, 1999.
• 7: Boi Faltings, Arc-consistency for continuous variables, Artificial Intelligence, v.65 n.2, p.363-376, Feb. 1994 [doi>10.1016/0004-3702(94)90022-1]
• 8: Eugene C. Freuder, A Sufficient Condition for Backtrack-Free Search, Journal of the ACM (JACM), v.29 n.1, p.24-32, Jan. 1982 [doi>10.1145/322290.322292]
• 9: Eero Hyvönen, Constraint reasoning based on interval arithmetic: the tolerance propagation approach, Artificial Intelligence, v.58 n.1-3, p.71-112, Dec. 1992 [doi>10.1016/0004-3702(92)90005-I]
• 10: C. Jermann, G. Trombettoni, and B. Neveu. Inter-block backtracking: Exploiting the structure in continuous csps. In 2nd International Workshop on Global Constrained Optimization and Constraint Satisfaction (Cocos'03), 2003.
• 11: O. Lhomme. Consistency techniques for numeric csps. In Proc. of the 13th IJCAI, pages 232--238, 1993.
• 12: O. Lhomme. Contribution à la résolution de contraintes sur les reels par propagation d'intervalles. Phd thesis, University of Nice-Sophia Antipolis, 1994.
• 13: Jorge J. Moré , Burton S. Garbow , Kenneth E. Hillstrom, Testing Unconstrained Optimization Software, ACM Transactions on Mathematical Software (TOMS), v.7 n.1, p.17-41, March 1981 [doi>10.1145/355934.355936]