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

约束编程是这样一种思想，即一个问题可以用一组约束来表示，这是几个变量之间的逻辑关系，并且产生问题的解决方案涉及满足所有定义的约束。约束程序设计在优化问题、计算机图形学和验证等领域有着广泛的应用。然而，要将约束编程应用于特定问题或领域，必须首先将其建模为约束满足或优化问题，其涉及基于对所得到的解决方案必须满足的决策变量的一组约束来对问题进行建模。已经创建了一个流水线来简化约束建模和求解的过程，其中可以在高级语言称为Essence。本项目研究不同的人工智能技术，如蒙特卡洛树搜索、强化和深度学习，以及它们在本质层面的应用，以有效地识别和转换模型到其最佳等价类，而无需特定领域的知识。过去很少有研究花在改进约束编程的建模方面，而这正是可以在性能上获得巨大收益的地方。在这个更高的级别上应用小的改进可以在求解器级别上获得巨大的收益。

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.