Skip to main content
SpringerLink
Log in

Using conflict and support counts for variable and value ordering in CSPs

  • Published:
Applied Intelligence Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Notes

  1. There are special cases where CSPs are solved in polynomial time, for instance, the case where the related constraint network is a tree [14].

  2. The source code used for the experiments is available at: http://www2.cs.uregina.ca/yong200k.

  3. 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

  1. 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

    Article  Google Scholar 

  2. 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

    Article  Google Scholar 

  3. Bacchus F (2000) Extending forward checking. In: Principles and practice of constraint programming–CP 2000. Springer, pp 35–51

  4. Balafoutis T, Stergiou K Experimental evaluation of modern variable selection strategies in constraint satisfaction problems

  5. Balafoutis T, Stergiou K (2010) Conflict directed variable selection strategies for constraint satisfaction problems. In: Hellenic conference on artificial intelligence. Springer, pp 29–38

  6. 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

  7. Bayardo R J Jr, Schrag R (1997) Using csp look-back techniques to solve real-world sat instances. In: AAAI 1997, pp 203–208

  8. Bessière C (1994) Arc-consistency and arc-consistency again. Artif Intell 65:179–190

    Article  Google Scholar 

  9. Bessière C, Freuder E, Regin J (1995) Using inference to reduce arc consistency computation. In: IJCAI’95. Montréal, Canada, pp 592–598

  10. 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

    Article  MathSciNet  MATH  Google Scholar 

  11. 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

    Article  MathSciNet  MATH  Google Scholar 

  12. 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

  13. 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

  14. Dechter R (2003) Constraint processing. Morgan Kaufmann

  15. 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

  16. 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

  17. Gomes C, Walsh T (2006) Randomness and structure. Handbook Const Program 35:639–664

    Article  Google Scholar 

  18. Grimes D, Wallace RJ (2007) Learning to identify global bottlenecks in constraint satisfaction search. In: FLAIRS 2007, pp 592–597

  19. Haralick R, Elliott G (1980) Increasing tree search efficiency for constraint satisfaction problems. Artif Intel. 14:263–313

    Article  Google Scholar 

  20. 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

    Article  Google Scholar 

  21. 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)

  22. Lecoutre C (2013) Series of CSP instances. http://www.cril.univ-artois.fr/lecoutre/benchmarks.html

  23. 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

  24. Mackworth AK (1977) Consistency in networks of relations. Artif Intell 8:99–118

    Article  MATH  Google Scholar 

  25. 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

  26. Mohr R, Henderson T (1986) Arc and path consistency revisited. Artif Intell 28:225–233

    Article  Google Scholar 

  27. Mouhoub M (2009) Dynamic arc consistency for csps. KES J 13(2):45–58. https://doi.org/10.3233/JAD-2009-0173

    Article  Google Scholar 

  28. 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

  29. Mouhoub M, Sukpan A (2008) Managing temporal constraints with preferences. Spatial Cogn Comput 8 (1-2):131–149. https://doi.org/10.1080/13875860801930407

    Article  Google Scholar 

  30. Wallace RJ, Freuder E (1992) Ordering heuristics for arc consistency algorithms. In: Proc. Ninth Canad Conf on AI. Vancouver, pp 163–169

  31. 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/

  32. Xu K, Li W (2000) Exact phase transitions in random constraint satisfaction problems. J Artif Intell Res

  33. 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

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Regina, Regina, Saskatchewan, Canada

    Ket Wei Yong & Malek Mouhoub

Authors
  1. Ket Wei Yong
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Malek Mouhoub
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Malek Mouhoub.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-017-1094-x

Keywords

Search

Navigation