By the same authors

Exploiting short supports for improved encoding of arbitrary constraints into SAT

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

Full text download(s)

Published copy (DOI)

Author(s)

Department/unit(s)

Publication details

Title of host publicationPrinciples and Practice of Constraint Programming
DateAccepted/In press - 6 Jun 2016
DateE-pub ahead of print - 23 Aug 2016
DatePublished (current) - 5 Sep 2016
Pages3-12
Number of pages10
PublisherSPRINGER
Place of PublicationNetherlands
EditorsMichael Rueher
Original languageEnglish
ISBN (Electronic)9783319449531
ISBN (Print)9783319449524

Publication series

NameLecture Notes in Computer Science
PublisherSpringer

Abstract

Encoding to SAT and applying a highly efficient modern SAT solver is an increasingly popular method of solving finite-domain constraint problems. In this paper we study encodings of arbitrary constraints where unit propagation on the encoding provides strong reasoning. Specifically, unit propagation on the encoding simulates generalised arc consistency on the original constraint. To create compact and efficient encodings we use the concept of short support. Short support has been successfully applied to create efficient propagation algorithms for arbitrary constraints. A short support of a constraint is similar to a satisfying tuple however a short support is not required to assign every variable in scope. Some variables are left free to take any value. In some cases a short support representation is smaller than the table of satisfying tuples by an exponential factor. We present two encodings based on short supports and evaluate them on a set of benchmark problems, demonstrating a substantial improvement over the state of the art.

Bibliographical note

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.

Discover related content

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

View graph of relations