Interval propagation and search on directed acyclic graphs for numerical constraint solving

• Published in: Journal of global optimization 2009-12, Vol.45 (4), p.499-531
• Main Authors: Vu, Xuan-Ha, Schichl, Hermann, Sam-Haroud, Djamila
• Format: Article
• Language: English
• Subjects: Algorithms; Computer Science; Graphs; Logic programming; Mathematical problems; Mathematics; Mathematics and Statistics; Operations Research/Decision Theory; Optimization; Real Functions; Studies; Variables
• ISSN: 0925-5001; 1573-2916
• DOI: 10.1007/s10898-008-9386-7

The fundamentals of interval analysis on directed acyclic graphs (DAGs) for global optimization and constraint propagation have recently been proposed in Schichl and Neumaier (J. Global Optim. 33, 541–562, 2005). For representing numerical problems, the authors use DAGs whose nodes are subexpressions and whose directed edges are computational flows. Compared to tree-based representations [Benhamou et al. Proceedings of the International Conference on Logic Programming (ICLP’99), pp. 230–244. Las Cruces, USA (1999)], DAGs offer the essential advantage of more accurately handling the influence of subexpressions shared by several constraints on the overall system during propagation. In this paper we show how interval constraint propagation and search on DAGs can be made practical and efficient by: (1) flexibly choosing the nodes on which propagations must be performed, and (2) working with partial subgraphs of the initial DAG rather than with the entire graph. We propose a new interval constraint propagation technique which exploits the influence of subexpressions on all the constraints together rather than on individual constraints. We then show how the new propagation technique can be integrated into branch-and-prune search to solve numerical constraint satisfaction problems. This algorithm is able to outperform its obvious contenders, as shown by the experiments.