Automatic discovery and exploitation of promising subproblems for tabulation

Ozgur Akgun; Ian Philip Gent; Christopher Anthony Jefferson; Ian James Miguel; Peter William Nightingale; András Z. Salamon

doi:10.1007/978-3-319-98334-9_1

Automatic discovery and exploitation of promising subproblems for tabulation

Ozgur Akgun, Ian Philip Gent, Christopher Anthony Jefferson, Ian James Miguel, Peter William Nightingale, András Z. Salamon

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The performance of a constraint model can often be improved by converting a subproblem into a single table constraint. In this paper we study heuristics for identifying promising subproblems. We propose a small set of heuristics to identify common cases such as expressions that will propagate weakly. The process of discovering promising subproblems and tabulating them is entirely automated in the tool Savile Row. A cache is implemented to avoid tabulating equivalent subproblems many times. We give a simple algorithm to generate table constraints directly from a constraint expression in Savile Row. We demonstrate good performance on the benchmark problems used in earlier work on tabulation, and also for several new problem classes.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming
Subtitle of host publication	24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings
Editors	John Hooker
Publisher	Springer
Pages	3-12
ISBN (Electronic)	9783319983349
ISBN (Print)	9783319983332
DOIs	https://doi.org/10.1007/978-3-319-98334-9_1
Publication status	Published - 2018
Event	24th International Conference on Principles and Practice of Constraint Programming (CP 2018) - Euratechnologies, Lille, France Duration: 27 Aug 2018 → 31 Aug 2018 Conference number: 24 http://cp2018.a4cp.org/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	11008
ISSN (Print)	0302-9743

Conference

Conference	24th International Conference on Principles and Practice of Constraint Programming (CP 2018)
Abbreviated title	CP 2018
Country/Territory	France
City	Lille
Period	27/08/18 → 31/08/18
Internet address	http://cp2018.a4cp.org/

Access to Document

10.1007/978-3-319-98334-9_1

CP2018-Tabulation-CRC
© 2018, Springer Nature Switzerland AG. This work has been made available online in accordance with the publisher’s policies. This is the author created accepted version manuscript following peer review and as such may differ slightly from the final published version. The final published version of this work is available at https://doi.org/10.1007/978-3-319-98334-9_1
Accepted author manuscript, 292 KB

Modelling and Optimisation with Graphs: Modelling and Optimisation with Graphs
Jefferson, C. A. (PI) & Akgun, O. (CoI)
EPSRC
1/07/17 → 31/10/20
Project: Standard
University Research Fellowship 2013: University Research Fellowship 2013
Jefferson, C. A. (PI)
The Royal Society
1/10/13 → 30/09/18
Project: Fellowship

Ozgur Akgun
- ozgur.akgunst-andrews.acuk
- School of Computer Science - Senior Lecturer, Director of Impact
- Centre for Interdisciplinary Research in Computational Algebra
Person: Academic
Christopher Anthony Jefferson
- caj21st-andrews.acuk
Person: Academic

Automatic discovery and exploitation of promising subproblems for tabulation (dataset)
Akgun, O. (Creator), Gent, I. P. (Creator), Jefferson, C. A. (Creator), Miguel, I. J. (Creator), Nightingale, P. W. (Creator) & Salamon, A. Z. (Creator), GitHub, 3 Jul 2018
https://github.com/stacs-cp/cp2018-tabulation
Dataset

Cite this

Akgun, O., Gent, I. P., Jefferson, C. A., Miguel, I. J., Nightingale, P. W., & Salamon, A. Z. (2018). Automatic discovery and exploitation of promising subproblems for tabulation. In J. Hooker (Ed.), Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings (pp. 3-12). (Lecture Notes in Computer Science; Vol. 11008). Springer. https://doi.org/10.1007/978-3-319-98334-9_1

Akgun, Ozgur ; Gent, Ian Philip ; Jefferson, Christopher Anthony et al. / Automatic discovery and exploitation of promising subproblems for tabulation. Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings. editor / John Hooker. Springer, 2018. pp. 3-12 (Lecture Notes in Computer Science).

@inproceedings{b170a1edfb03483a860a1e1482829944,

title = "Automatic discovery and exploitation of promising subproblems for tabulation",

abstract = "The performance of a constraint model can often be improved by converting a subproblem into a single table constraint. In this paper we study heuristics for identifying promising subproblems. We propose a small set of heuristics to identify common cases such as expressions that will propagate weakly. The process of discovering promising subproblems and tabulating them is entirely automated in the tool Savile Row. A cache is implemented to avoid tabulating equivalent subproblems many times. We give a simple algorithm to generate table constraints directly from a constraint expression in Savile Row. We demonstrate good performance on the benchmark problems used in earlier work on tabulation, and also for several new problem classes. ",

author = "Ozgur Akgun and Gent, {Ian Philip} and Jefferson, {Christopher Anthony} and Miguel, {Ian James} and Nightingale, {Peter William} and Salamon, {Andr{\'a}s Z.}",

note = "Funding: EP/P015638/1 and EP/P026842/1. Dr Jefferson holds a Royal Society University Research Fellowship.; 24th International Conference on Principles and Practice of Constraint Programming (CP 2018), CP 2018 ; Conference date: 27-08-2018 Through 31-08-2018",

year = "2018",

doi = "10.1007/978-3-319-98334-9_1",

language = "English",

isbn = "9783319983332",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "3--12",

editor = "John Hooker",

booktitle = "Principles and Practice of Constraint Programming",

address = "Netherlands",

url = "http://cp2018.a4cp.org/",

}

Akgun, O , Gent, IP , Jefferson, CA , Miguel, IJ, Nightingale, PW & Salamon, AZ 2018, Automatic discovery and exploitation of promising subproblems for tabulation. in J Hooker (ed.), Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings. Lecture Notes in Computer Science, vol. 11008, Springer, pp. 3-12, 24th International Conference on Principles and Practice of Constraint Programming (CP 2018), Lille, France, 27/08/18. https://doi.org/10.1007/978-3-319-98334-9_1

Automatic discovery and exploitation of promising subproblems for tabulation. / Akgun, Ozgur ; Gent, Ian Philip ; Jefferson, Christopher Anthony et al.
Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings. ed. / John Hooker. Springer, 2018. p. 3-12 (Lecture Notes in Computer Science; Vol. 11008).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Automatic discovery and exploitation of promising subproblems for tabulation

AU - Akgun, Ozgur

AU - Gent, Ian Philip

AU - Jefferson, Christopher Anthony

AU - Miguel, Ian James

AU - Nightingale, Peter William

AU - Salamon, András Z.

N1 - Conference code: 24

PY - 2018

Y1 - 2018

N2 - The performance of a constraint model can often be improved by converting a subproblem into a single table constraint. In this paper we study heuristics for identifying promising subproblems. We propose a small set of heuristics to identify common cases such as expressions that will propagate weakly. The process of discovering promising subproblems and tabulating them is entirely automated in the tool Savile Row. A cache is implemented to avoid tabulating equivalent subproblems many times. We give a simple algorithm to generate table constraints directly from a constraint expression in Savile Row. We demonstrate good performance on the benchmark problems used in earlier work on tabulation, and also for several new problem classes.

AB - The performance of a constraint model can often be improved by converting a subproblem into a single table constraint. In this paper we study heuristics for identifying promising subproblems. We propose a small set of heuristics to identify common cases such as expressions that will propagate weakly. The process of discovering promising subproblems and tabulating them is entirely automated in the tool Savile Row. A cache is implemented to avoid tabulating equivalent subproblems many times. We give a simple algorithm to generate table constraints directly from a constraint expression in Savile Row. We demonstrate good performance on the benchmark problems used in earlier work on tabulation, and also for several new problem classes.

U2 - 10.1007/978-3-319-98334-9_1

DO - 10.1007/978-3-319-98334-9_1

M3 - Conference contribution

SN - 9783319983332

T3 - Lecture Notes in Computer Science

SP - 3

EP - 12

BT - Principles and Practice of Constraint Programming

A2 - Hooker, John

PB - Springer

T2 - 24th International Conference on Principles and Practice of Constraint Programming (CP 2018)

Y2 - 27 August 2018 through 31 August 2018

ER -

Akgun O , Gent IP , Jefferson CA , Miguel IJ, Nightingale PW, Salamon AZ. Automatic discovery and exploitation of promising subproblems for tabulation. In Hooker J, editor, Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings. Springer. 2018. p. 3-12. (Lecture Notes in Computer Science). Epub 2018 Aug 23. doi: 10.1007/978-3-319-98334-9_1

Automatic discovery and exploitation of promising subproblems for tabulation

Abstract

Publication series

Conference

Access to Document

Fingerprint

Projects

Modelling and Optimisation with Graphs: Modelling and Optimisation with Graphs

University Research Fellowship 2013: University Research Fellowship 2013

Profiles

Ozgur Akgun

Christopher Anthony Jefferson

Datasets

Automatic discovery and exploitation of promising subproblems for tabulation (dataset)

Cite this