Name: Willem-Jan van Hoeve
University: Carnegie Mellon University
Date: November 2, 2007
Time: 1:30 to 3:00 pm
Location: 388 Posner Hall
Title: Algorithms in Constraint Programming: the Sequence Constraint
Abstract:
Constraint Programming is a powerful and flexible paradigm to model and solve combinatorial problems. In contrast to traditional optimization techniques that reason on the problem as a whole, constraint programming reasons on tractable substructures of the problem individually. More specifically, the search space is reduced by filtering out inconsistent domain values from the variable domains. The challenge is to find efficient filtering algorithms for combinatorial structures that occur frequently in applications. In this talk we consider a combinatorial structure known as the “sequence constraint”, that appears in many applications, such as car manufacturing and nurse rostering. After its introduction in 1988 several filtering algorithms have been proposed for it, none of which removed all possible inconsistent domain values, however. We present three filtering algorithms, including the first algorithm that achieves complete filtering in polynomial time for this constraint. We also provide experimental results, showing the effectiveness of our filtering algorithms in practice. This is joint work with Gilles Pesant, Louis-Martin Rousseau and Ashish Sabharwal. It was awarded as best paper at the annual conference on constraint programming CP 2006 (out of 142 submissions).