Skip to main content

Model Agnostic Solution of CSPs via Deep Learning: A Preliminary Study

TitleModel Agnostic Solution of CSPs via Deep Learning: A Preliminary Study
Publication TypeConference Paper
Year of Publication2018
AuthorsGalassi, A., M. Lombardi, P. Mello, and M. Milano
Editorvan Hoeve, W. - J.
Conference NameIntegration of Constraint Programming, Artificial Intelligence, and Operations Research
Date Published06/2018
PublisherSpringer International Publishing
Conference LocationCham
ISBN Number978-3-319-93031-2

Deep Neural Networks (DNNs) have been shaking the AI scene, for their ability to excel at Machine Learning tasks without relying on complex, hand-crafted, features. Here, we probe whether a DNN can learn how to construct solutions of a CSP, without any explicit symbolic information about the problem constraints. We train a DNN to extend a feasible solution by making a single, globally consistent, variable assignment. The training is done over intermediate steps of the construction of feasible solutions. From a scientific standpoint, we are interested in whether a DNN can learn the structure of a combinatorial problem, even when trained on (arbitrarily chosen) construction sequences of feasible solutions. In practice, the network could also be used to guide a search process, e.g. to take into account (soft) constraints that are implicit in past solutions or hard to capture in a traditional declarative model. This research line is still at an early stage, and a number of complex issues remain open. Nevertheless, we already have intriguing results on the classical Partial Latin Square and N-Queen completion problems.

Publicly Accessible Resources: