Cited By
View all- Tay NBotzheim JKubota N(2018)Weighted Constraint Satisfaction for Smart Home Automation and OptimizationAdvances in Artificial Intelligence10.1155/2016/29595082016(1)Online publication date: 12-Dec-2018
Experimental matching of instances to heuristics for constraint satisfaction problems
Authors: 
Jorge Humberto Moreno-Scott, José Carlos Ortiz-Bayliss, Hugo Terashima-Marín, Santiago Enrique Conant-PablosAuthors Info & Claims
Article No.: 37, Page 37
Abstract
Constraint satisfaction problems are of special interest for the artificial intelligence and operations research community due to their many applications. Although heuristics involved in solving these problems have largely been studied in the past, little is known about the relation between instances and the respective performance of the heuristics used to solve them. This paper focuses on both the exploration of the instance space to identify relations between instances and good performing heuristics and how to use such relations to improve the search. Firstly, the document describes a methodology to explore the instance space of constraint satisfaction problems and evaluate the corresponding performance of six variable ordering heuristics for such instances in order to find regions on the instance space where some heuristics outperform the others. Analyzing such regions favors the understanding of how these heuristics work and contribute to their improvement. Secondly, we use the information gathered from the first stage to predict the most suitable heuristic to use according to the features of the instance currently being solved. This approach proved to be competitive when compared against the heuristics applied in isolation on both randomly generated and structured instances of constraint satisfaction problems.
References
[1]
S. L. Epstein, E. C. Freuder, R. Wallace, A. Morozov, and B. Samuels, "The adaptive constraint engine," in Principles and Practice of Constraint Programming--CP 2002: 8th International Conference, CP 2002 Ithaca, NY, USA, September 9-13, 2002 Proceedings, vol. 2470 of Lecture Notes in Computer Science, pp. 525-542, Springer, Berlin, Germany, 2002.
[2]
E. O'Mahony, E. Hebrard, A. Holland, C. Nugent, and B. O'Sullivan, "Using case-based reasoning in an algorithm portfolio for constraint solving," in Proceedings of the 19th Irish Conference on Artificial Intelligence and Cognitive Science, Cork, Ireland, August 2008.
[3]
S. Petrovic and R. Qu, "Case-based reasoning as a heuristic selector in a hyper-heuristic for course timetabling problems," in Proceedings of the 6th International Conference on Knowledge-Based Intelligent Information Engineering Systems and Applied Technologies (KES '02), vol. 82, pp. 336-340, September 2002.
[4]
B. Crawford, R. Soto, C. Castro, and E. Monfroy, "A hyperheuristic approach for dynamic enumeration strategy selection in constraint satisfaction," in New Challenges on Bioinspired Applications, vol. 6687 of Lecture Notes in Computer Science, pp. 295-304, Springer, Berlin, Germany, 2011.
[5]
J. C. Ortiz-Bayliss, H. Terashima-Marín, and S. E. Conant-Pablos, "Learning vector quantization for variable ordering in constraint satisfaction problems," Pattern Recognition Letters, vol. 34, no. 4, pp. 423-432, 2013.
[6]
R. Soto, B. Crawford, E. Monfroy, and V. Bustos, "Using autonomous search for generating good enumeration strategy blends in constraint programming," in Computational Science and Its Applications--ICCSA 2012: 12th International Conference, Salvador de Bahia, Brazil, June 18-21, 2012, Proceedings, Part III, vol. 7335 of Lecture Notes in Computer Science, pp. 607- 617, Springer, Berlin, Germany, 2012.
[7]
Y. Malitsky, "Evolving instance-specific algorithm configuration," in Instance-Specific Algorithm Configuration, pp. 93-105, Springer, Basel, Switzerland, 2014.
[8]
P. Hell and J. Nešetril, "Colouring, constraint satisfaction, and complexity," Computer Science Review, vol. 2, no. 3, pp. 143-163, 2008.
[9]
N. Dunkin and S. Allen, "Frequency assignment problems: representations and solutions," Tech. Rep. CSD-TR-97-14, University of London, 1997.
[10]
J. A. Berlier and J. M. McCollum, "Aconstraint satisfaction algorithm for microcontroller selection and pin assignment," in Proceedings of the IEEE SoutheastCon, pp. 348-351, IEEE, Concord, NC, USA, March 2010.
[11]
J. R. Bitner and E. M. Reingold, "Backtrack programming techniques," Communications of the ACM, vol. 18, no. 11, pp. 651- 656, 1975.
[12]
N. Jussien and O. Lhomme, "Local search with constraint propagation and conflict-based heuristics," in Proceedings of the 17th National Conference on Artificial Intelligence and 12th Conference on Innovative Applications of Artificial Intelligence, pp. 169- 174, AAAI Press, MIT Press, Austin, Tex, USA, July-August 2000.
[13]
J. R. Rice, "The algorithm selection problem," Advances in Computers, vol. 15, pp. 65-118, 1976.
[14]
T. Stützle and S. Fernandes, "New benchmark instances for the qap and the experimental analysis of algorithms," in Evolutionary Computation in Combinatorial Optimization, J. Gottlieb and G. Raidl, Eds., vol. 3004 of Lecture Notes in Computer Science, pp. 199-209, Springer, Berlin, Germany, 2004.
[15]
K. A. Smith-Miles, "Towards insightful algorithm selection for optimisation using meta-learning concepts," in Proceedings of the IEEE International Joint Conference on Neural Networks (IJCNN '08), pp. 4118-4124, IEEE, Hong Kong, June 2008.
[16]
K. A. Smith-Miles, R. J. James, J. W. Giffin, and Y. Tu, "A knowledge discovery approach to understanding relationships between scheduling problem structure and heuristic performance," in Learning and Intelligent Optimization, T. Stützle, Ed., vol. 5851 of Lecture Notes in Computer Science, pp. 89-103, Springer, Berlin, Germany, 2009.
[17]
K. Smith-Miles, D. Baatar, B. Wreford, and R. Lewis, "Towards objective measures of algorithm performance across instance space," Computers and Operations Research, vol. 45, pp. 12-24, 2014.
[18]
B. Bischl, O. Mersmann, H. Trautmann, and M. Preuß, "Algorithm selection based on exploratory landscape analysis and cost-sensitive learning," in Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation (GECCO '12), pp. 313-320, ACM, Philadelphia, Pa, USA, July 2012.
[19]
E. López-Camacho, H. Terashima-Marín, G. Ochoa, and S. E. Conant-Pablos, "Understanding the structure of bin packing problems through principal component analysis," International Journal of Production Economics, vol. 145, no. 2, pp. 488-499, 2013.
[20]
E. Tsang and A. Kwan, "Mapping constraint satisfaction problems to algorithms and heuristics," Tech. Rep. CSM-198, Department of Computer Sciences, University of Essex, 1993.
[21]
J. C. Ortiz-Bayliss, H. Terashima-Marin, P. Ross, J. I. Fuentes-Rosado, and M. Valenzuela-Rend, "A neuroevolutionary approach to produce general hyper-heuristics for the dynamic variable ordering in hard binary constraint satisfaction problems," in Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation (GECCO '09), pp. 1811-1812, Montreal, Canada, July 2009.
[22]
J. H. Moreno-Scott, J. C. Ortiz-Bayliss, H. Terashima-Marín, and S. E. Conant-Pablos, "Challenging heuristics: evolving binary constraint satisfaction problems," in Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation (GECCO '12), pp. 409-416, ACM, New York, NY, USA, July 2012.
[23]
K. Smith-Miles, J. van Hemert, and X. Y. Lim, "Understanding TSP difficulty by learning from evolved instances," in Learning and Intelligent Optimization, C. Blum and R. Battiti, Eds., vol. 6073 of Lecture Notes in Computer Science, pp. 266-280, Springer, Berlin, Germany, 2010.
[24]
K. Smith-Miles and J. van Hemert, "Discovering the suitability of optimisation algorithms by learning from evolved instances," Annals of Mathematics and Artificial Intelligence, vol. 61, no. 2, pp. 87-104, 2011.
[25]
J. I. van Hemert, "Evolving binary constraint satisfaction problem instances that are difficult to solve," in Proceedings of the IEEE Congress on Evolutionary Computation (CEC '03), vol. 2, pp. 1267-1273, IEEE, December 2003.
[26]
J. I. Van Hemert, "Evolving combinatorial problem instances that are difficult to solve," Evolutionary Computation, vol. 14, no. 4, pp. 433-462, 2006.
[27]
F. Boussemart, F. Hemery, and C. Lecoutre, "Revision ordering heuristics for the constraint satisfaction problem," in Proceedings of the 1st International Workshop on Constraint Propagation and Implementation (CPAI '04), pp. 9-43, Toronto, Canada, September 2004.
[28]
I. P. Gent, E. MacIntyre, P. Prosser, B. M. Smith, and T. Walsh, "An empirical study of dynamic variable ordering heuristics for the constraint satisfaction problem," in Principles and Practice of Constraint Programming--CP96: Second International Conference, CP96 Cambridge, MA, USA, August 19-22, 1996 Proceedings, vol. 1118 of Lecture Notes in Computer Science, pp. 179-193, Springer, Berlin, Germany, 1996.
[29]
R. J. Wallace, "Analysis of heuristic synergies," in Recent Advances in Constraints, B. Hnich, M. Carlsson, F. Fages, and F. Rossi, Eds., vol. 3978 of Lecture Notes in Computer Science, pp. 73-87, Springer, Berlin, Germany, 2006.
[30]
R. M. Haralick and G. L. Elliott, "Increasing tree search efficiency for constraint satisfaction problems," in Proceedings of the 6th International Joint Conference on Artificial Intelligence, vol. 1, pp. 356-364, Morgan Kaufmann, San Francisco, Calif, USA, 1979.
[31]
R. Dechter and I. Meiri, "Experimental evaluation of preprocessing algorithms for constraint satisfaction problems," Artificial Intelligence, vol. 68, no. 2, pp. 211-241, 1994.
[32]
D. Brélaz, "New methods to color the vertices of a graph," Communications of the ACM, vol. 22, no. 4, pp. 251-256, 1979.
[33]
H. Terashima-Marín, J. C. Ortiz-Bayliss, P. Ross, and M. Valenzuela-Rendón, "Hyper-heuristics for the dynamic variable ordering in constraint satisfaction problems," in Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation (GECCO '08), pp. 571-578, ACM, Atlanta, Ga, USA, July 2008.
[34]
J. G. Gaschnig, "A general backtrack algorithm that eliminates most redundant tests," in Proceedings of the 5th International Joint Conference on Artificial Intelligence (IJCAI '77), vol. 1, p. 457, Morgan Kaufmann, Cambridge, Mass, USA, August 1977.
[35]
E. C. Freuder, "Synthesizing constraint expressions," Communications of the ACM, vol. 21, no. 11, pp. 958-966, 1978.
[36]
D. Achlioptas, C. Gomes, H. Kautz, and B. Selman, "Generating satisfiable problem instances," in Proceedings of the 17th National Conference on Artificial Intelligence (AAAI '00), pp. 256-301, Austin, Tex, USA, July-August 2000.
[37]
J. Culberson, "Hidden solutions, tell-tales, heuristics and antiheuristics," in Proceedings of the Workshop on Empirical Methods in Artificial Intelligence (IJCAI '01), H. Hoos and T. Stuëtzle, Eds., pp. 9-14, 2001.
[38]
I. Rish and D. Frost, "Statistical analysis of backtracking on inconsistent CSPs," in Principles and Practice of Constraint Programming--CP97, G. Smolka, Ed., vol. 1330 of Lecture Notes in Computer Science, pp. 150-162, Springer, Berlin, Germany, 1997.
[39]
B. M. Smith, "Locating the phase transition in binary constraint satisfaction problems," Artificial Intelligence, vol. 81, no. 1-2, pp. 155-181, 1996.
[40]
D. Achlioptas, M. S. O. Molloy, L. M. Kirousis, Y. C. Stamatiou, E. Kranakis, and D. Krizanc, "Random constraint satisfaction: a more accurate picture," Constraints, vol. 6, no. 4, pp. 329-344, 2001.
[41]
E. MacIntyre, P. Prosser, B. M. Smith, and E. MacIntyre, "Random constraint satisfaction: theory meets practice," in Principles and Practice of Constraint Programming--CP98: 4th International Conference, CP98 Pisa, Italy, October 26-30, 1998 Proceedings, vol. 1520 of Lecture Notes in Computer Science, pp. 325-339, Springer, Berlin, Germany, 1998.
[42]
K. Xu and W. Li, "Many hard examples in exact phase transitions," Theoretical Computer Science, vol. 355, no. 3, pp. 291-302, 2006.
[43]
P. Prosser, "Hybrid algorithms for the constraint satisfaction problem," Computational Intelligence, vol. 9, no. 3, pp. 268-299, 1993.
[44]
B. M. Smith, "Constructing an asymptotic phase transition in random binary constraint satisfaction problems," Theoretical Computer Science, vol. 265, no. 1-2, pp. 265-283, 2001.
[45]
Y. Fan and J. Shen, "On the phase transitions of random k-constraint satisfaction problems," Artificial Intelligence, vol. 175, no. 3-4, pp. 914-927, 2011.
[46]
C. Lecoutre, F. Boussemart, and F. Hemery, "Backjump-based techniques versus conflict-directed heuristics," in Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence (ICTAI '04), pp. 549-557, Boca Raton, Fla, USA, November 2004.
[47]
L. Michel and P. Van Hentenryck, "Activity-based search for black-box constraint programming solvers," in Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems, N. Beldiceanu, N. Jussien, and É. Pinson, Eds., vol. 7298 of Lecture Notes in Computer Science, pp. 228- 243, Springer, Berlin, Germany, 2012.
[48]
F. Boussemart, F. Hemery, C. Lecoutre, and L. Sais, "Boosting systematic search by weighting constraints," in Proceedings of the European Conference on Artificial Intelligence (ECAI '04), pp. 146-150, IOS Press, 2004.
- Experimental matching of instances to heuristics for constraint satisfaction problems
Recommendations
Integrating heuristics for constraint satisfaction problems: a case study
AAAI'93: Proceedings of the eleventh national conference on Artificial intelligenceThis paper describes a set of experiments with a system that synthesizes constraint satisfaction programs. The system, MULTI-TAC, is a CSP "expert" that can specialize a library of generic algorithms and methods for a particular application. MULTI-TAC ...
Efficient and experimental meta-heuristics for MAX-SAT problems
WEA'05: Proceedings of the 4th international conference on Experimental and Efficient AlgorithmsMany problems in combinatorial optimization are NP-Hard. This has forced researchers to explore meta-heuristic techniques for dealing with this class of complex problems and finding an acceptable solution in reasonable time. The satisfiability problem, ...
Grammar-based generation of variable-selection heuristics for constraint satisfaction problems
We propose a grammar-based genetic programming framework that generates variable-selection heuristics for solving constraint satisfaction problems. This approach can be considered as a generation hyper-heuristic. A grammar to express heuristics is ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Hindawi Limited
London, United Kingdom
Publication History
Published: 01 January 2016
Accepted: 27 December 2015
Revised: 16 December 2015
Received: 29 September 2015
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 34Total Downloads
- Downloads (Last 12 months)17
- Downloads (Last 6 weeks)3
Reflects downloads up to 18 Dec 2024
Other Metrics
Citations
Cited By
View all- Tay NBotzheim JKubota N(2018)Weighted Constraint Satisfaction for Smart Home Automation and OptimizationAdvances in Artificial Intelligence10.1155/2016/29595082016(1)Online publication date: 12-Dec-2018
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in