Optimising Constraint Model Selection through Monte Carlo Tree Search and Machine Learning

Constraint Programming is the idea that a problem can be represented by a set of constraints, a logical relation amongst several variables, and producing a solution to the problem involves satisfaction of all of the defined constraints. Constraint Programming has been applied to a large number of fields including optimization problems, computer graphics and verification. However to apply constraint programming to a particular problem or domain, it must first be modelled as a constraint satisfaction or optimisation problem which involves modelling the problem based upon a set of constraints on decision variables that the resulting solution must satisfy.

At St Andrews, a pipeline has been created to simplify the process of constraint modelling and solving where an abstract specification of the problem can be defined in a high level language called Essence. The pipeline then transforms the input Essence specification into a Constraint Programming model through a series of transformations.

This project is about researching different AI techniques such as Monte Carlo Tree Search, Reinforcement and Deep Learning and their application at the Essence level to efficiently identify and transform a model into its optimal equivalence class without domain specific knowledge. Little research in the past has been spent on improving the modelling side of Constraint Programming and this is where big gains in performance can be made. Applying small refinements at this higher level can achieve huge gains at the solver level.