Using directed acyclic graphs to coordinate propagation and search for numerical constraint satisfaction problems

The paper of H. Schichl & A. Neumaier has given the fundamentals of interval analysis on DAGs for global optimization and constraint propagation. We show in This work how constraint propagation on DAGs can be made efficient and practical by: (i) working on partial DAG representations; and (ii) enabling the flexible choice of the interval inclusion functions during propagation. We then propose a new simple algorithm, which coordinates constraint propagation and exhaustive search for solving numerical constraint satisfaction problems. The experiments carried out on different problems show that the new approach outperforms previously available propagation techniques by an order of magnitude or more in speed, while being roughly the same quality w.r.t. enclosure properties.