Combining Variable Ordering Heuristics for Improving Search Algorithms Performance

Authors: Abdolreza Hatamlou, Yusef Farhang, Mohammad Reza Meybodi

Abstract:

Variable ordering heuristics are used in constraint satisfaction algorithms. Different characteristics of various variable ordering heuristics are complementary. Therefore we have tried to get the advantages of all heuristics to improve search algorithms performance for solving constraint satisfaction problems. This paper considers combinations based on products and quotients, and then a newer form of combination based on weighted sums of ratings from a set of base heuristics, some of which result in definite improvements in performance.

Keywords: Constraint Satisfaction Problems, Variable Ordering Heuristics, Combination, Search Algorithms

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1056715

References:

[1] E. Tsang. Foundations of Constraint Satisfaction. Academic Press, 1993.
[2] K. Marriot, P. J. Stuckey. Programming with Constraints: An Introduction. The MIT Press, 1998.
[3] Z. Michalewicz and D. B. Fogel. How to Solve It: Modern Heuristics. Springer-Verlag, 2000.
[4] C Stefan Vo?. Meta-heuristics: State of the art. In Alexander Nareyek, editor, Lcal search for planning and scheduling: revisited papers, pages 1 23. Springer-Verlag LNCS 2148, 2001.