Machine Learning for Constraint Programming

Sammanfattning: It is well established that designing good heuristics for solving Constraint Programming models requires years of domain experience and a huge amount of trial and error. In this thesis project, we conduct an empirical study of whether Machine Learning and Deep Learning techniques have the potential to help the design of constraint solving heuristics.Specifically, this thesis project examines the potential of Machine Learning and Deep Learning models for the regression task of predicting the makespan and solving time of a Job-Shop Scheduling Problem without actually solving the given Job-Shop Scheduling Problem instance. Several Machine Learning models are tested with manually designed features as input. Different Deep Learning architectures are explored with either just the Job-Shop Scheduling Problem instance as input or with an additional input of the previously designed features.××Results of the experiments justify the potential of several proposed models in predicting the makespan and solving time. For predicting the makespan (unit: machine time unit), the best Random Forest regression model achieves a Mean Squared Error of 0.78 on the test set. The best Deep Learning model achieves a Mean Squared Error of 0.74 on the test set. For predicting the solving time (unit: milliseconds) of a Job-Shop Scheduling Problem, the best Random Forest regression model achieves a Mean Squared Error of 2.12 107 on the test set. The best Deep Learning model achieves a Mean Squared Error of 5.19 107 on the test set.Discussions of the reason behind the difference of different Machine Learning and Deep Learning models are provided and future directions are proposed.