Using Directed Acyclic Graphs to Coordinate Propagation and Search for Numerical Constraint Satisfaction Problems
The pioneering paper by H. Schichl and A. Neumaier has founded the fundamentals of interval analysis on DAGs for global optimization, including a fundamental of constraint propagation. In this paper, we extend the constraint propagation technique for solving numerical constraint satisfaction problems. In particular, we propose an advanced constraint propagation technique, which makes the constraint propagation practical and efficient, and a method to coordinate constraint propagation and exhaustive search, which uses a single DAG for each problem. The experiments carried out on various 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 with respect to enclosure properties.
IC_TECH_REPORT_200448.pdf
openaccess
509.16 KB
Adobe PDF
80e022ad8db6b0870e33a2e089d59603