Learning when to use automatic tabulation in constraint model reformulation

Carlo Cena, Ozgur Akgun, Zeynep Kiziltan, Ian James Miguel, Peter Nightingale, Felix Ulrich-Oltean

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publicationProceedings of the 32nd International Joint Conference on Artificial Intelligence, IJCAI 2023
Subtitle of host publicationMacao, SAR
EditorsEdith Elkind
PublisherInternational Joint Conferences on Artificial Intelligence
Pages1902-1910
Number of pages9
ISBN (Electronic)9781956792034
DOIs
Publication statusPublished - 25 Aug 2023
Event32nd International Joint Conference on Artificial Intelligence, IJCAI 2023 - Macao, China
Duration: 19 Aug 202325 Aug 2023

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
Volume2023-August
ISSN (Print)1045-0823

Conference

Conference32nd International Joint Conference on Artificial Intelligence, IJCAI 2023
Country/TerritoryChina
CityMacao
Period19/08/2325/08/23

Keywords

  • Constraint Satisfaction and Optimization: CSO: Modeling
  • Constraint Satisfaction and Optimization: CSO: Solvers and tools
  • Machine Learning: ML: Classification

Fingerprint

Dive into the research topics of 'Learning when to use automatic tabulation in constraint model reformulation'. Together they form a unique fingerprint.

Cite this