Projects per year
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 language | English |
---|---|
Title of host publication | Proceedings of the 32nd International Joint Conference on Artificial Intelligence, IJCAI 2023 |
Subtitle of host publication | Macao, SAR |
Editors | Edith Elkind |
Publisher | International Joint Conferences on Artificial Intelligence |
Pages | 1902-1910 |
Number of pages | 9 |
ISBN (Electronic) | 9781956792034 |
DOIs | |
Publication status | Published - 25 Aug 2023 |
Event | 32nd International Joint Conference on Artificial Intelligence, IJCAI 2023 - Macao, China Duration: 19 Aug 2023 → 25 Aug 2023 |
Publication series
Name | IJCAI International Joint Conference on Artificial Intelligence |
---|---|
Volume | 2023-August |
ISSN (Print) | 1045-0823 |
Conference
Conference | 32nd International Joint Conference on Artificial Intelligence, IJCAI 2023 |
---|---|
Country/Territory | China |
City | Macao |
Period | 19/08/23 → 25/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.Projects
- 1 Active