Finite Domain Programming is a technique for solving combinatorial problems like planning, scheduling, configuration or timetabling. Inevitably, these problems employ disjunctive constraints. A rather new approach to model those constraints is constructive disjunction, whereby common information is lifted from the alternatives, aiming for stronger pruning of the search space. We show where constructive disjunction provides for stronger pruning and where it fails to do so. For several problems, including a real-world college timetabling application, benefits and limitations of constructive disjunction are exemplified. As an experimental platform we use the concurrent constraint language Oz.
Download PDF Show BibTeX
Login to edit