3.7.173. Open constraint

A constraint from which all its variables are not completely known when the constraint is postedΒ [HoeveRegin06]. In many situations, such as configuration, planning, orΒ scheduling of process dependant activities, the variables of a constraint are not completely known initially when the constraint is posted. Instead, they are revealed during the search process Β [Bartak03], [FaltingsMachoGonzalez02], [FaltingsMachoGonzalez05]. In practice, an additional argument of the constraint (a set variable or a set of 0-1 variables) provides the initial set of potential variables (the lower bound in the context of a set variable). In Bartak's modelΒ [Bartak03], an open constraint admits a sequence of domain variables V 1 V 2 β‹―V m (mβ‰₯1) as well as an additional variable C which gives the index of the last variable that effectively belongs to the constraint (i.e., variables V C+1 ,V C+2 ,β‹―,V m are discarded). This is for instance the case for the πšœπš’πš£πšŽ_πš–πšŠπš‘_πšœπšπšŠπš›πšπš’πš—πš_𝚜𝚎𝚚_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint.

Within the context of open constraints, the notion of contractibility was introduced inΒ [Maher09c] in order to characterise a global constraint for which any pruning rule that removes a value from one of its variable (or which enforces any type of condition) can be reused in the context of the corresponding open global constraint (i.e., the pruning rule still makes valid deductions in the context of the open case). Intuitively, many global constraints which impose a kind of at most condition are contractible, while this is typically not the case for global constraints which enforce a kind of at least condition.

See also the keywords open automaton constraint, contractible, and extensible.