By the same authors

Automatic discovery and exploitation of promising subproblems for tabulation

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

Author(s)

Department/unit(s)

Publication details

Title of host publicationPrinciples and Practice of Constraint Programming
DateAccepted/In press - 15 Jun 2018
DateE-pub ahead of print - 23 Aug 2018
DatePublished (current) - 27 Aug 2018
Pages3-12
Number of pages10
PublisherSpringer
Place of PublicationNetherlands
EditorsJohn Hooker
Original languageEnglish
ISBN (Electronic)9783319983349
ISBN (Print)9783319983332

Publication series

NameLecture Notes in Computer Science
PublisherSpringer

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.

Bibliographical note

© Springer Nature Switzerland AG 2018. This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details.

Funding: EP/P015638/1 and EP/P026842/1. Dr Jefferson holds a Royal Society University Research Fellowship.

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations