Combining Set Variable Representations

Within constraint programming, a number of different representations have been used for set variables. Many of these representations are based on combining together existing representations. To understand such combinations, we provide a formal definition of this notion of combination, and of the synchronisation between representations. We characterize two types of combinations, define bound consistency on these combinations and provide some tractability results. Finally, we compare the strength of the different combinations, positioning existing representations within our taxonomy. This systematic approach opens the door to interesting new representations of set variables. Our results apply also to multiset variable representations.