Learning MAX-SAT from Contextual Examples for Combinatorial Optimisation
Abstract
Combinatorial optimization problems are ubiquitous in artificial intelligence. Designing the underlying models, however, requires substantial expertise, which is a limiting factor in practice. The models typically consist of hard and soft constraints, or combine hard constraints with a preference function. We introduce a novel setting for learning combinatorial optimisation problems from contextual examples. These positive and negative examples show – in a particular context – whether the solutions are good enough or not. We develop our framework using the MAX-SAT formalism. We provide learnability results within the realizable and agnostic settings, as well as hassle, an implementation based on syntax-guided synthesis and showcase its promise on recovering synthetic and benchmark instances from examples.
Cite
Text
Kumar et al. "Learning MAX-SAT from Contextual Examples for Combinatorial Optimisation." AAAI Conference on Artificial Intelligence, 2020. doi:10.1609/AAAI.V34I04.5877Markdown
[Kumar et al. "Learning MAX-SAT from Contextual Examples for Combinatorial Optimisation." AAAI Conference on Artificial Intelligence, 2020.](https://mlanthology.org/aaai/2020/kumar2020aaai-learning/) doi:10.1609/AAAI.V34I04.5877BibTeX
@inproceedings{kumar2020aaai-learning,
title = {{Learning MAX-SAT from Contextual Examples for Combinatorial Optimisation}},
author = {Kumar, Mohit and Kolb, Samuel and Teso, Stefano and De Raedt, Luc},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2020},
pages = {4493-4500},
doi = {10.1609/AAAI.V34I04.5877},
url = {https://mlanthology.org/aaai/2020/kumar2020aaai-learning/}
}