Model agnostic solution of CSPs via deep learning: a preliminary study. (English) Zbl 06982396

Galassi, Andrea; Lombardi, Michele; Mello, Paola; Milano, Michela

van Hoeve, Willem-Jan (ed.), Integration of constraint programming, artificial intelligence, and operations research. 15th international conference, CPAIOR 2018, Delft, The Netherlands, June 26–29, 2018. Proceedings. Cham: Springer (ISBN 978-3-319-93030-5/pbk; 978-3-319-93031-2/ebook). Lecture Notes in Computer Science 10848, 254-262 (2018).

Summary: 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.
For the entire collection see [Zbl 1388.68011].

MSC:

68T20	Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27	Combinatorial optimization