Combinatorial optimisation has numerous practical applications, such as planning, logistics, or circuit design. Problems such as these can be solved by approaches such as Boolean Satisfiability (SAT) or Constraint Programming (CP). Solver performance is affected significantly by the model chosen to represent a given problem, which has led to the study of model reformulation. One such method is tabulation: rewriting the expression of some of the model constraints in terms of a single “table” constraint. Successfully applying this process means identifying expressions amenable to trans- formation, which has typically been done manually. Recent work introduced an automatic tabulation using a set of hand-designed heuristics to identify constraints to tabulate. However, the performance of these heuristics varies across problem classes and solvers. Recent work has shown learning techniques to be increasingly useful in the context of automatic model reformulation. The goal of this study is to understand whether it is possible to improve the performance of such heuristics, by learning a model to predict whether or not to activate them for a given instance. Experimental results suggest that a random forest classifier is the most robust choice, improving the performance of four different SAT and CP solvers.

Learning When to Use Automatic Tabulation in Constraint Model Reformulation / Cena, Carlo; Akgün, Özgür; Kiziltan, Zeynep; Miguel, Ian; Nightingale, Peter; Ulrich-Oltean, Felix. - ELETTRONICO. - (2023), pp. 1902-1910. (Intervento presentato al convegno Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI 2023) tenutosi a Macao, SAR nel 19-25 August 2023) [10.24963/ijcai.2023/211].

Learning When to Use Automatic Tabulation in Constraint Model Reformulation

Cena, Carlo
Primo
;
Kiziltan, Zeynep
Secondo
;
2023

Abstract

Combinatorial optimisation has numerous practical applications, such as planning, logistics, or circuit design. Problems such as these can be solved by approaches such as Boolean Satisfiability (SAT) or Constraint Programming (CP). Solver performance is affected significantly by the model chosen to represent a given problem, which has led to the study of model reformulation. One such method is tabulation: rewriting the expression of some of the model constraints in terms of a single “table” constraint. Successfully applying this process means identifying expressions amenable to trans- formation, which has typically been done manually. Recent work introduced an automatic tabulation using a set of hand-designed heuristics to identify constraints to tabulate. However, the performance of these heuristics varies across problem classes and solvers. Recent work has shown learning techniques to be increasingly useful in the context of automatic model reformulation. The goal of this study is to understand whether it is possible to improve the performance of such heuristics, by learning a model to predict whether or not to activate them for a given instance. Experimental results suggest that a random forest classifier is the most robust choice, improving the performance of four different SAT and CP solvers.
2023
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI 2023)
1902
1910
Learning When to Use Automatic Tabulation in Constraint Model Reformulation / Cena, Carlo; Akgün, Özgür; Kiziltan, Zeynep; Miguel, Ian; Nightingale, Peter; Ulrich-Oltean, Felix. - ELETTRONICO. - (2023), pp. 1902-1910. (Intervento presentato al convegno Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI 2023) tenutosi a Macao, SAR nel 19-25 August 2023) [10.24963/ijcai.2023/211].
Cena, Carlo; Akgün, Özgür; Kiziltan, Zeynep; Miguel, Ian; Nightingale, Peter; Ulrich-Oltean, Felix
File in questo prodotto:
File Dimensione Formato  
0211.pdf

accesso aperto

Tipo: Versione (PDF) editoriale
Licenza: Licenza per accesso libero gratuito
Dimensione 181.35 kB
Formato Adobe PDF
181.35 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/11585/954594
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact