Automatic discovery and exploitation of promising subproblems for tabulation

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

8 Citations (Scopus)
1 Downloads (Pure)

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 languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings
EditorsJohn Hooker
PublisherSpringer
Pages3-12
ISBN (Electronic)9783319983349
ISBN (Print)9783319983332
DOIs
Publication statusPublished - 2018
Event24th International Conference on Principles and Practice of Constraint Programming (CP 2018) - Euratechnologies, Lille, France
Duration: 27 Aug 201831 Aug 2018
Conference number: 24
http://cp2018.a4cp.org/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11008
ISSN (Print)0302-9743

Conference

Conference24th International Conference on Principles and Practice of Constraint Programming (CP 2018)
Abbreviated titleCP 2018
Country/TerritoryFrance
CityLille
Period27/08/1831/08/18
Internet address

Fingerprint

Dive into the research topics of 'Automatic discovery and exploitation of promising subproblems for tabulation'. Together they form a unique fingerprint.

Cite this