Learning MAX-SAT from Contextual Examples for Combinatorial Optimisation


  • Mohit Kumar KU Leuven
  • Samuel Kolb KU Leuven
  • Stefano Teso University of Trento
  • Luc De Raedt KU Leuven




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.




How to Cite

Kumar, M., Kolb, S., Teso, S., & De Raedt, L. (2020). Learning MAX-SAT from Contextual Examples for Combinatorial Optimisation. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04), 4493-4500. https://doi.org/10.1609/aaai.v34i04.5877



AAAI Technical Track: Machine Learning