551. Model Agnostic Solution of CSPs via Deep Learning: A Preliminary Study
- Author
-
Paola Mello, Andrea Galassi, Michele Lombardi, Michela Milano, DIPARTIMENTO DI INFORMATICA - SCIENZA E INGEGNERIA, Facolta' di INGEGNERIA, Da definire, AREA MIN. 09 - Ingegneria industriale e dell'informazione, Willem-Jan van Hoeve, and Galassi Andrea, Lombardi Michele, Mello Paola, Milano Michela
- Subjects
Structure (mathematical logic) ,search ,021103 operations research ,constraints solving ,business.industry ,Computer science ,Process (engineering) ,Deep learning ,0211 other engineering and technologies ,model learning, deep neural networks, constraints solving, search ,02 engineering and technology ,Construct (python library) ,Variable (computer science) ,model learning ,deep neural networks ,Line (geometry) ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Artificial intelligence ,business - Abstract
none 4 no 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. mixed Galassi Andrea, Lombardi Michele, Mello Paola, Milano Michela Galassi Andrea, Lombardi Michele, Mello Paola, Milano Michela
- Published
- 2018