SODA

Sweep as a generic pruning technique applied to constraint relaxation

Beldiceanu, Nicolas and Carlsson, Mats (2001) Sweep as a generic pruning technique applied to constraint relaxation. In: Soft'01 workshop at CP'2001, International conference on Principles and Practice of Constraint Programming, 1 Dec 2001, Paphos, Cyprus.

[img]
Preview
PDF
102Kb
[img]
Preview
Postscript
621Kb

Abstract

We introduce a new generic filtering algorithm for handling constraint relaxation within constraint programming. More precisely, we first present a generic pruning technique, which is useful for a special case of the cardinality operator where all the constraints have at least two variables in common. This method is based on a generalisation of a sweep algorithm, which handles a conjunction of constraints to the case where one just knows the minimum and maximum number of constraints that have to hold. The main benefit of this new technique comes from the fact that, even if we don't know which, and exactly how many constraints, will hold in the final solution, we can still prune the variables of those constraints right from the beginning according to the minimum and maximum number of constraints that have to hold. We then show how to extend the previous sweep algorithm in order to handle preferences among constraints. Finally, we specialise this technique to an extension of the non-overlapping rectangles constraint, where we permit controlling how many non-overlapping constraints should hold. This allows handling over-constrained placement problems and provides constraint propagation even if some non-overlapping constraints have to be relaxed.

Item Type:Conference or Workshop Item (Paper)
ID Code:3070
Deposited By:INVALID USER
Deposited On:07 Aug 2008
Last Modified:18 Nov 2009 16:17

Repository Staff Only: item control page