Abstract
Restricted path consistency (RPC) is a strong local consistency for binary constraints that was proposed 20 years ago and was identified as a promising alternative to arc consistency (AC) in an early experimental study of local consistencies for binary constraints. However, and in contrast to other strong local consistencies such as SAC and maxRPC, it has been neglected since then. In this paper we revisit RPC. First, we propose RPC3, a new lightweight RPC algorithm that is very easy to implement and can be efficiently applied throughout search. Then we perform a wide experimental study of RPC3 and a light version that achieves an approximation of RPC, comparing them to state-of-the-art AC and maxRPC algorithms. Experimental results clearly show that restricted RPC is by far more efficient than both AC and maxRPC when applied throughout search. These results strongly suggest that it is time to reconsider the established perception that MAC is the best general purpose method for solving binary CSPs.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Balafoutis, T., Paparrizou, A., Stergiou, K., Walsh, T.: New algorithms for max restricted path consistency. Constraints 16(4), 372–406 (2011)
Balafrej, A., Bessiere, C., Bouyakh, E., Trombettoni, G.: Adaptive singleton-based consistencies. In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, pp. 2601–2607 (2014)
Barták, R., Erben, R.: A new algorithm for singleton arc consistency. In: Proceedings of the Seventeenth International Florida Artificial Intelligence, pp. 257–262 (2004)
Berlandier, P.: Improving domain filtering using restricted path consistency. In: Proceedings of IEEE CAIA 1995, pp. 32–37 (1995)
Bessiere, C., Cardon, S., Debruyne, R., Lecoutre, C.: Efficient Algorithms for Singleton Arc Consistency. Constraints 16, 25–53 (2011)
Boussemart, F., Hemery, F., Lecoutre, C., Sais, L.: Boosting systematic search by weighting constraints. In: Proceedings of ECAI 2004, Valencia, Spain (2004)
Debruyne, R., Bessière, C.: From restricted path consistency to max-restricted path consistency. In: Smolka, G. (ed.) CP 1997. LNCS, vol. 1330, pp. 312–326. Springer, Heidelberg (1997)
Debruyne, R., Bessière, C.: Domain Filtering Consistencies. JAIR 14, 205–230 (2001)
Grandoni, F., Italiano, G.F.: Improved algorithms for max-restricted path consistency. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 858–862. Springer, Heidelberg (2003)
Lecoutre, C., Hemery, F.: A study of residual supports in arc cosistency. In: Proceedings of IJCAI 2007, pp. 125–130 (2007)
Lecoutre, C., Prosser, P.: Maintaining singleton arc consistency. In: 3rd International Workshop on Constraint Propagation and Implementation (CPAI 2006), pp. 47–61 (2006)
Likitvivatanavong, C., Zhang, Y., Bowen, J., Shannon, S., Freuder, E.: Arc consistency during search. In: Proceedings of IJCAI 2007, pp. 137–142 (2007)
Prosser, P., Stergiou, K., Walsh, T.: Singleton consistencies. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 353–368. Springer, Heidelberg (2000)
Vion, J., Debruyne, R.: Light algorithms for maintaining max-RPC during search. In: Proceedings of SARA 2009 (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Stergiou, K. (2015). Restricted Path Consistency Revisited. In: Pesant, G. (eds) Principles and Practice of Constraint Programming. CP 2015. Lecture Notes in Computer Science(), vol 9255. Springer, Cham. https://doi.org/10.1007/978-3-319-23219-5_30
Download citation
DOI: https://doi.org/10.1007/978-3-319-23219-5_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-23218-8
Online ISBN: 978-3-319-23219-5
eBook Packages: Computer ScienceComputer Science (R0)