TabID: Automatic Identification and Tabulation of Subproblems in Constraint Models

Özgür Akgün; Ian P. Gent; Christopher Jefferson; Zeynep Kiziltan; Ian Miguel; Peter Nightingale; András Z. Salamon; Felix Ulrich-Oltean

doi:10.1613/jair.1.17032

TabID: Automatic Identification and Tabulation of Subproblems in Constraint Models

Özgür Akgün, Ian P. Gent, Christopher Jefferson, Zeynep Kiziltan, Ian Miguel, Peter Nightingale, András Z. Salamon, Felix Ulrich-Oltean

Computing

Research output: Contribution to journal › Article › peer-review

5 Downloads (Pure)

Abstract

The performance of a constraint model can often be improved by converting a subproblem into a single table constraint (referred to as tabulation). Finding subproblems to tabulate is traditionally a manual and time-intensive process, even for expert modellers. This paper presents TabID, an entirely automated method to identify promising subproblems for tabulation in constraint programming. We introduce a diverse set of heuristics designed to identify promising candidates for tabulation, aiming to improve solver performance. These heuristics are intended to encapsulate various factors that contribute to useful tabulation. We also present additional checks to limit the potential drawbacks of suboptimal tabulation.

Original language	English
Pages (from-to)	1999-2056
Number of pages	58
Journal	Journal of Artificial Intelligence Research
Volume	82
DOIs	https://doi.org/10.1613/jair.1.17032
Publication status	Published - 30 Mar 2025

ASJC Scopus subject areas

Artificial Intelligence

Access to Document

10.1613/jair.1.17032Licence: CC BY

Final published version
2025 The Authors. Published by AI Access Foundation under Creative Commons Attribution License CC BY 4.0.
Final published version, 4.48 MBLicence: CC BY

Cite this

@article{dba96705c2cd4d24b59cbb580e26404f,

title = "TabID: Automatic Identification and Tabulation of Subproblems in Constraint Models",

abstract = "The performance of a constraint model can often be improved by converting a subproblem into a single table constraint (referred to as tabulation). Finding subproblems to tabulate is traditionally a manual and time-intensive process, even for expert modellers. This paper presents TabID, an entirely automated method to identify promising subproblems for tabulation in constraint programming. We introduce a diverse set of heuristics designed to identify promising candidates for tabulation, aiming to improve solver performance. These heuristics are intended to encapsulate various factors that contribute to useful tabulation. We also present additional checks to limit the potential drawbacks of suboptimal tabulation.",

author = "{\"O}zg{\"u}r Akg{\"u}n and Gent, \{Ian P.\} and Christopher Jefferson and Zeynep Kiziltan and Ian Miguel and Peter Nightingale and Salamon, \{Andr{\'a}s Z.\} and Felix Ulrich-Oltean",

note = "Publisher Copyright: {\textcopyright}2025 The Authors.",

year = "2025",

month = mar,

day = "30",

doi = "10.1613/jair.1.17032",

language = "English",

volume = "82",

pages = "1999--2056",

}

TY - JOUR

T1 - TabID

T2 - Automatic Identification and Tabulation of Subproblems in Constraint Models

AU - Akgün, Özgür

AU - Gent, Ian P.

AU - Jefferson, Christopher

AU - Kiziltan, Zeynep

AU - Miguel, Ian

AU - Nightingale, Peter

AU - Salamon, András Z.

AU - Ulrich-Oltean, Felix

PY - 2025/3/30

Y1 - 2025/3/30

N2 - The performance of a constraint model can often be improved by converting a subproblem into a single table constraint (referred to as tabulation). Finding subproblems to tabulate is traditionally a manual and time-intensive process, even for expert modellers. This paper presents TabID, an entirely automated method to identify promising subproblems for tabulation in constraint programming. We introduce a diverse set of heuristics designed to identify promising candidates for tabulation, aiming to improve solver performance. These heuristics are intended to encapsulate various factors that contribute to useful tabulation. We also present additional checks to limit the potential drawbacks of suboptimal tabulation.

AB - The performance of a constraint model can often be improved by converting a subproblem into a single table constraint (referred to as tabulation). Finding subproblems to tabulate is traditionally a manual and time-intensive process, even for expert modellers. This paper presents TabID, an entirely automated method to identify promising subproblems for tabulation in constraint programming. We introduce a diverse set of heuristics designed to identify promising candidates for tabulation, aiming to improve solver performance. These heuristics are intended to encapsulate various factors that contribute to useful tabulation. We also present additional checks to limit the potential drawbacks of suboptimal tabulation.

UR - http://www.scopus.com/inward/record.url?scp=105001998761&partnerID=8YFLogxK

U2 - 10.1613/jair.1.17032

DO - 10.1613/jair.1.17032

M3 - Article

AN - SCOPUS:105001998761

SN - 1076-9757

VL - 82

SP - 1999

EP - 2056

JO - Journal of Artificial Intelligence Research

JF - Journal of Artificial Intelligence Research

ER -

TabID: Automatic Identification and Tabulation of Subproblems in Constraint Models

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this