Relation Domain
A Relation Domain is a Structured Domain that can hangle graph decision variables.
- AKA: Domain of Relation Decision Variables.
- Example(s):
- …
- Counter-Example(s):
- See: Constraint Programming, Relation Constraint System, Set Relation, Function Domain, Relational Algebra.
References
2013
- (Sabogal et al., 2013) ⇒ Gustavo Adolfo Gutierrez Sabogal, Peter Van Roy, and Sascha Van Cauwelaert. (2013). “Implementation of the Relation Domain for Constraint Programming.” In: Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming (TRICS 2013).
- QUOTE: The idea of a relation domain was proposed in 6. In 14, relations are used as a powerful modeling mechanism. Functions are particular cases of binary relations and were introduced in [15] to model CSPs. Interestingly, these models were translated into conventional constraint domains (i.e. integers and sets) before being tackled by solvers. The main difference with these works include handling relations of any arity and supporting them in the solver without any translation. Relational algebra has been combined with constraint programming to solve express combinatorial problems in [16], a local search approach is then used to solve the models.
There have been other structured domains that are related with relations. Graph decision variables were introduced by Regin in [17] and later studied by Dooms (CP(Graph)) [18, 19]. Graphs can be considered binary relations on the set of nodes. That equivalence makes possible the use of the relation domain to handle graphs.
The finite set domain introduced by Gervet and Puget in [20, 21] is also related to relations. A set is equivalent to a unary relation(...)
The approach of using BDDs to represent information in constraint programming is not new. Hawkins et al. propose their use to represent set decision variables and set constraints in [22]. That work is related to this one in several forms. First, we use BDDs to approximate the domain of relation variables by using the subset bounds approach introduced in [20, 21]. Second, primitive constraints on sets and integers can be represented as relation values. However, the approach taken by this work focuses on manipulating relations using the operations of the relational algebra. It is important to differentiate the use of decision diagrams as proposed in this work from the work of Andersen et al. in [23]. That work uses Multi Valued Decision Diagrams (a BDD extension) to represent the constraint store. Our proposal is limited to the use of BDDs to represent the domain of relation decision variables
- QUOTE: The idea of a relation domain was proposed in 6. In 14, relations are used as a powerful modeling mechanism. Functions are particular cases of binary relations and were introduced in [15] to model CSPs. Interestingly, these models were translated into conventional constraint domains (i.e. integers and sets) before being tackled by solvers. The main difference with these works include handling relations of any arity and supporting them in the solver without any translation. Relational algebra has been combined with constraint programming to solve express combinatorial problems in [16], a local search approach is then used to solve the models.