Projects per year
Abstract
Combinatorial optimisation has numerous practi-
cal applications, such as planning, logistics, or cir-
cuit design. Problems such as these can be solved
by approaches such as Boolean Satisfiability (SAT)
or Constraint Programming (CP). Solver perfor-
mance is affected significantly by the model cho-
sen 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 manu-
ally. Recent work introduced an automatic tab-
ulation using a set of hand-designed heuristics to
identify constraints to tabulate. However, the per-
formance of these heuristics varies across problem
classes and solvers. Recent work has shown learn-
ing techniques to be increasingly useful in the con-
text of automatic model reformulation. The goal
of this study is to understand whether it is possi-
ble 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.
cal applications, such as planning, logistics, or cir-
cuit design. Problems such as these can be solved
by approaches such as Boolean Satisfiability (SAT)
or Constraint Programming (CP). Solver perfor-
mance is affected significantly by the model cho-
sen 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 manu-
ally. Recent work introduced an automatic tab-
ulation using a set of hand-designed heuristics to
identify constraints to tabulate. However, the per-
formance of these heuristics varies across problem
classes and solvers. Recent work has shown learn-
ing techniques to be increasingly useful in the con-
text of automatic model reformulation. The goal
of this study is to understand whether it is possi-
ble 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 |
| Publisher | IJCAI/AAAI |
| Pages | 1902-1910 |
| Number of pages | 9 |
| ISBN (Electronic) | 978-1-956792-03-4 |
| DOIs | |
| Publication status | Published - Aug 2023 |
| Event | IJCAI 2023, the 32nd International Joint Conference on Artificial Intelligence - , Macao Duration: 19 Aug 2023 → 25 Aug 2023 |
Conference
| Conference | IJCAI 2023, the 32nd International Joint Conference on Artificial Intelligence |
|---|---|
| Country/Territory | Macao |
| Period | 19/08/23 → 25/08/23 |
Bibliographical note
This is an author-produced version of the published paper. Uploaded in accordance with the University’s Research Publications and Open Access policy.Projects
- 1 Active
-
Solver Feedback Loops for Automated Constraint Modelling
1/04/22 → 3/04/25
Project: Research project (funded) › Research