ECAI-2000 Conference Paper

[full paper]

A Property of Path Inverse Consistency Leading to an Optimal PIC Algorithm

Romuald Debruyne

In constraint networks, the efficiency of a search algorithm is strongly related to the local consistency maintained during search. For a long time, it has been considered that forward checking was the best compromise between the pruning effect and the amount of overhead involved. But recent works, comparing the search algorithms on a large range of networks, show that maintaining arc consistency during search (MAC) outperforms forward checking on large and hard problems. It is conceivable that on very difficult instances, using an even more pruningful local consistency may pay off. To know which local consistency is the most promising, a study comparing both their pruning efficiency and the time needed to achieve them has been done [DE97]. This work shows that PIC1, the path inverse consistency algorithm presented in [FE96], has very bad average and worst case time complexities. In this paper, we give a property of PIC and we propose and evaluate a PIC algorithm based on this property that has an optimal worst case time complexity. Experiments show that maintaining PIC during search outperforms MAC on hard sparses CNs.

Keywords: Constraint Satisfaction

Citation: Romuald Debruyne: A Property of Path Inverse Consistency Leading to an Optimal PIC Algorithm. In W.Horn (ed.): ECAI2000, Proceedings of the 14th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2000, pp.88-92.