A Systematic Approach to MDD-Based Constraint Programming.pdf.pdf' (347.74 kB)
Download file

A Systematic Approach to MDD-Based Constraint Programming

Download (347.74 kB)
journal contribution
posted on 01.07.2012, 00:00 by Samid Hoda, Willem-Jan Van HoeveWillem-Jan Van Hoeve, John N. Hooker
Fixed-width MDDs were introduced recently as a more refined alternative for the domain store to represent partial solutions to CSPs. In this work, we present a systematic approach to MDD-based constraint programming. First, we introduce a generic scheme for constraint propagation in MDDs. We show that all previously known propagation algorithms for MDDs can be expressed using this scheme. Moreover, we use the scheme to produce algorithms for a number of other constraints, including Among, Element, and unary resource constraints. Finally, we discuss an implementation of our MDD-based CP solver, and provide experimental evidence of the benefits of MDD-based constraint programming.

History

Publisher Statement

All Rights Reserved

Date

01/07/2012

Usage metrics

Exports