Abstract
A Constraint Satisfaction Problem (CSP) is a very powerful framework for representing and solving constraint problems. Solving a CSP often requires searching for a solution in a large search space. Very often, much of the search efforts are wasted on the part of the search space that does not lead to a solution. Therefore, many search algorithms and heuristic techniques have been proposed to solve CSPs efficiently by guiding the search and reducing its size. Variable and value ordering techniques are among the most efficient ones as past experiments have shown that these heuristics can significantly improve the search performance and lead to the solution sooner. One such heuristic works by gathering information during search to guide subsequent decisions when selecting variables. More precisely, this heuristic gathers and records information about failures in the form of constraint weight during constraint propagation. In this paper, we propose a variant of this heuristic where the weight of a constraint is also based on the conflict and support counts, of each variable attached to this constraint, gathered during constraint propagation. We also propose a dynamic value ordering heuristic based on the support and conflict count information. Experiments have been conducted on random, quasi-random, pattern and real world instances. The test results show that the proposed variable ordering heuristic performs well in the cases of hard random and quasi-random instances. The test results also show that combining the proposed variable and value ordering heuristics can improve the performance significantly for some difficult problems.
Similar content being viewed by others
Notes
There are special cases where CSPs are solved in polynomial time, for instance, the case where the related constraint network is a tree [14].
The source code used for the experiments is available at: http://www2.cs.uregina.ca/yong200k.
Note that any non-binary discrete CSP instance can be transformed into an equivalent binary CSP by using the dual graph translation or the hidden variable translation.
References
Abbasian R, Mouhoub M (2013) A hierarchical parallel genetic approach for the graph coloring problem. Appl Intell 39(3):510–528. https://doi.org/10.1007/s10489-013-0429-5
Alanazi E, Mouhoub M (2016) Variable ordering and constraint propagation for constrained cp-nets. Appl Intell 44(2):437–448. https://doi.org/10.1007/s10489-015-0708-4
Bacchus F (2000) Extending forward checking. In: Principles and practice of constraint programming–CP 2000. Springer, pp 35–51
Balafoutis T, Stergiou K Experimental evaluation of modern variable selection strategies in constraint satisfaction problems
Balafoutis T, Stergiou K (2010) Conflict directed variable selection strategies for constraint satisfaction problems. In: Hellenic conference on artificial intelligence. Springer, pp 29–38
Bayardo RJ Jr, Schrag RC (1997) Using csp look-back techniques to solve real-world sat instances. In: Proceedings of the Fourteenth national conference on artificial intelligence and ninth conference on innovative applications of artificial intelligence, AAAI’97/IAAI’97. AAAI Press, pp 203–208. http://dl.acm.org/citation.cfm?id=1867406.1867438
Bayardo R J Jr, Schrag R (1997) Using csp look-back techniques to solve real-world sat instances. In: AAAI 1997, pp 203–208
Bessière C (1994) Arc-consistency and arc-consistency again. Artif Intell 65:179–190
Bessière C, Freuder E, Regin J (1995) Using inference to reduce arc consistency computation. In: IJCAI’95. Montréal, Canada, pp 592–598
Bessiėre C, Rėgin J, Yap RHC, Zhang Y (2005) An optimal coarse-grained arc consistency algorithm. Artif Intell 165(2):165–185. https://doi.org/10.1016/j.artint.2005.02.004
Bessière C, Régin J C, Yap RH, Zhang Y (2005) An optimal coarse-grained arc consistency algorithm. Artif Intell 165(2):165–185
Boussemart F, Hemery F, Lecoutre C (2005) Description and representation of the problems selected for the first international constraint satisfaction solver competition. Tech. rep. Inproceedings of CPAI’05 workshop held with CP’05
Boussemart F, Hemery F, Lecoutre C, Sais L (2004) Boosting systematic search by weighting constraints. In: de Mȧntaras RL, Saitta L (eds) Proceedings of the 16th Eureopean conference on artificial intelligence, ECAI’2004, including prestigious applicants of intelligent systems, PAIS 2004. IOS Press, Valencia, pp 146–150
Dechter R (2003) Constraint processing. Morgan Kaufmann
Freuder EC, Quinn MJ (1985) Taking advantage of stable sets of variables in constraint satisfaction problems. In: Joshi AK (ed) Proceedings of the 9th international joint conference on artificial intelligence. Morgan Kaufmann, Los Angeles, pp 1076–1078
Frost DH, Dechter R (1995) Look-ahead value ordering for constraint satisfaction problems. In: Proceedings of the Fourteenth international joint conference on artificial intelligence, IJCAI 95, pp 572–578
Gomes C, Walsh T (2006) Randomness and structure. Handbook Const Program 35:639–664
Grimes D, Wallace RJ (2007) Learning to identify global bottlenecks in constraint satisfaction search. In: FLAIRS 2007, pp 592–597
Haralick R, Elliott G (1980) Increasing tree search efficiency for constraint satisfaction problems. Artif Intel. 14:263–313
Hmer A, Mouhoub M (2016) A multi-phase hybrid metaheuristics approach for the exam timetabling. Int J Comput Intell Appl 15(4):1–22. https://doi.org/10.1142/S1469026816500231
Karim MR, Mouhoub M (2014) Coevolutionary genetic algorithm for variable ordering in csps. In: Proceedings of the IEEE congress on evolutionary computation, CEC 2014. IEEE, Beijing, pp pp. 2716–2723, DOI https://doi.org/10.1109/CEC.2014.6900262, (to appear in print)
Lecoutre C (2013) Series of CSP instances. http://www.cril.univ-artois.fr/lecoutre/benchmarks.html
Lecoutre C, Boussemart F, Hemery F (2004) Backjump-based techniques versus conflict-directed heuristics. In: 16th IEEE International conference on tools with artificial intelligence, 2004. ICTAI 2004. IEEE, pp 549–557
Mackworth AK (1977) Consistency in networks of relations. Artif Intell 8:99–118
Mehta D, van Dongen MRC (2005) Static value ordering heuristics for constraint satisfaction problems. In: van Dongen (ed) Proceedings of the second international workshop on constraint propagation and implementation, pp. 49–62
Mohr R, Henderson T (1986) Arc and path consistency revisited. Artif Intell 28:225–233
Mouhoub M (2009) Dynamic arc consistency for csps. KES J 13(2):45–58. https://doi.org/10.3233/JAD-2009-0173
Mouhoub M, Jashmi BJ (2011) Heuristic techniques for variable and value ordering in csps. In: Krasnogor N, Lanzi PL (eds) GECCO. ACM, pp 457–464
Mouhoub M, Sukpan A (2008) Managing temporal constraints with preferences. Spatial Cogn Comput 8 (1-2):131–149. https://doi.org/10.1080/13875860801930407
Wallace RJ, Freuder E (1992) Ordering heuristics for arc consistency algorithms. In: Proc. Ninth Canad Conf on AI. Vancouver, pp 163–169
Xu K (2015) Forced satisfiable csp and sat benchmarks of model rb - hiding solutions with growing domains. Retrieved on June 25, 2017, from http://vlsicad.eecs.umich.edu/BK/Slots/cache/www.nls-de.buaa.edu.cn/kexu/
Xu K, Li W (2000) Exact phase transitions in random constraint satisfaction problems. J Artif Intell Res
Zhang Y, Yap RHC (2001) Making ac-3 an optimal algorithm. In: Seventeenth international joint conference on artificial intelligence (IJCAI’01), Seattle, pp 316–321
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Yong, K.W., Mouhoub, M. Using conflict and support counts for variable and value ordering in CSPs. Appl Intell 48, 2487–2500 (2018). https://doi.org/10.1007/s10489-017-1094-x
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10489-017-1094-x