Extrapolating constraint networks by symbolic classification

Prestwich, Steven D.

Extrapolating constraint networks by symbolic classification

Files

dso.pdf(165.3 KB)

Accepted version

Date

2022-07

Authors

Prestwich, Steven D.

Publisher

IJCAI

Abstract

Constraint acquisition (CA) methods aim to learn constraint satisfaction problems (CSPs) from data, thus automating the difficult and error-prone task of constraint modelling. Most CA methods learn CSPs of a certain size from examples of that size, for example an 8-queens CSP from 8-queens solutions. A few methods can learn a CSP from solutions of other sizes, or learn a generalised CSP for all sizes, which is more challenging but also more useful in practice. This paper describes a new approach to learning a CSP: extrapolation from learned CSPs of other sizes. This has the advantage that the training CSPs can be learned by any convenient CA method, thus potentially handling positive-only, negative-only, positive-negative, noisy or unlabelled data. We model the problem as classification, and show that a symbolic classifier based on genetic programming outperforms alternatives such as random forests and deep learning.

Keywords

Constraint acquisition (CA) , Constraint satisfaction problems (CSPs) , Constraint optimisation , Data science , Operations research , Optimisation

Citation

Prestwich, S. D. (2022) 'Extrapolating Constraint Networks by Symbolic Classification ', IJCAI 2022 DSO Workshop: Data science meets optimisation, Messe Wien, Vienna, Austria, 23-29 July, forthcoming publication.