Enhancing numerical constraint propagation using multiple inclusion representations

摘要

Building tight and conservative enclosures of the solution set is of crucial importance in the design of efficient complete solvers for numerical constraint satisfaction problems (NCSPs). This paper proposes a novel generic algorithm enabling the cooperative use, during constraint propagation, of multiple enclosure techniques. The new algorithm brings into the constraint propagation framework the strength of techniques coming from different areas such as interval arithmetic, affine arithmetic, and mathematical programming. It is based on the directed acyclic graph (DAG) representation of NCSPs whose flexibility and expressiveness facilitates the design of fine-grained combination strategies for general factorable systems. The paper presents several possible combination strategies for creating practical instances of the generic algorithm. The experiments reported on a particular instance using interval constraint propagation, interval arithmetic, affine arithmetic, and linear programming illustrate the flexibility and efficiency of the approach.