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.

Learning MAX-SAT from Contextual Examples for Combinatorial Optimisation / Kumar, Mohit; Kolb, Samuel; Teso, Stefano; De Raedt, Luc. - STAMPA. - (2020), pp. 4493-4500. (Intervento presentato al convegno AAAI tenutosi a New York City - USA nel 7- 12 February 2020) [10.1609/aaai.v34i04.5877].

Learning MAX-SAT from Contextual Examples for Combinatorial Optimisation

Kolb, Samuel;Teso, Stefano;
2020-01-01

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.
2020
Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI-20)
New York
AAAI Press
Kumar, Mohit; Kolb, Samuel; Teso, Stefano; De Raedt, Luc
Learning MAX-SAT from Contextual Examples for Combinatorial Optimisation / Kumar, Mohit; Kolb, Samuel; Teso, Stefano; De Raedt, Luc. - STAMPA. - (2020), pp. 4493-4500. (Intervento presentato al convegno AAAI tenutosi a New York City - USA nel 7- 12 February 2020) [10.1609/aaai.v34i04.5877].
File in questo prodotto:
File Dimensione Formato  
AAAI-KumarM.7298.pdf

accesso aperto

Descrizione: first online
Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 318.29 kB
Formato Adobe PDF
318.29 kB Adobe PDF Visualizza/Apri
5877-Article Text-9102-1-10-20200513.pdf

accesso aperto

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 544.94 kB
Formato Adobe PDF
544.94 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/290513
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 5
social impact