Learning vector quantization for variable ordering in constraint satisfaction problems

A constraint satisfaction problem (CSP) is a generic problem with many applications in different areas of artificial intelligence and operational research. During the search for a solution, the order in which the variables are selected to be instantiated has a tremendous impact in the complexity of the search. Many heuristics exist for ordering these variables, but they are specialized for some types of instances. Hyper-heuristics are methodologies used to choose from a set of heuristics and decide which one to apply given some properties of the instance at hand. In this research, we propose a new type of hyper-heuristic based on a learning vector quantization (LVQ) neural network for variable ordering within CSP. The first part of the investigation describes a methodology to generate LVQ neural networks that are able to map some properties of the instances to one suitable variable ordering heuristic. Later, the networks are created according to such methodology and tested on random and real instances proving that they are a feasible method to improve the performance of search on CSP when compared to single heuristics applied in isolation.

► Variable ordering heuristics are very sensitive to changes of the problem features.
► LVQ can be used to represent hyper-heuristics for variable ordering within CSP.
► LVQ are able to generalize from small instances, to larger ones and perform well.