Open Contractible Global Constraints

Open forms of global constraints allow the addition of new variables to an argument during the execution of a constraint program. Such forms are needed for difficult constraint programming problems where problem construction and problem solving are interleaved. However, in general, filtering that is sound for a global constraint can be unsound when the constraint is open. This paper provides a simple characterization, called contractibility, of the constraints where filtering remains sound when the constraint is open. With this characterization we can easily determine whether a constraint is contractible or not. In the latter case, we can use it to derive the strongest contractible approximation to the constraint. We demonstrate how specific algorithms for some closed contractible constraints are easily adapted to open constraints.

Michael Maher