Doctoral Dissertation Oral Defense, Rebecca Gentzel

Title: Haddock: A Language and Platform for MDD-Based Constraint Programming
Ph.D. Candidate: Rebecca Gentzel
Major Advisor: Dr. Laurent Michel
Associate Advisors: Dr. Willem-Jan van Hoeve, Dr. Ion Mandoiu

Date/Time: Tuesday, July 16th, 2024, 1:00 PM

Location: HBL 1947 and Webex
Meeting link: https://uconn-cmr.webex.com/uconn-cmr/j.php?MTID=ma0bdea3d6ac8cc587dbd8392a2ba0448
Meeting number: 2634 730 1758
Password: d3fT9RZ2WsA

Abstract

Constraint programming provides a generic framework for building and combining propagators for a model. Multi-valued decision diagrams (MDDs) were introduced into constraint programming as an effective alternative to domain propagation. While effective MDD-propagation algorithms have been proposed for various constraints, to date no system exists that can generically compile and combine MDD propagation for arbitrary constraints. To fill this need, this thesis introduces Haddock, a declarative language and architecture for MDD compilation. Haddock supports the specification, implementation, and composition of a broad range of MDD propagators that delivers the strength one expects from MDDs at a fraction of the development effort and with comparable performance for both satisfaction and optimization problems. Additionally, Haddock provides heuristics to empower the user to control the filtering techniques that greatly impact the potency of MDD propagators. This thesis describes the language and the framework architecture, demonstrates how to specify and implement novel MDD propagators, provides example heuristics for filtering as well as the tools to customize these heuristics, and expands to encompass both constraint satisfaction and constraint optimization problems.