Background: Activity-based dynamic preference constraint satisfaction

A hard constraint satisfaction problem (CSP) is a tuple $\langle\mathbf{X},\mathbf{D},\mathbf{C}\rangle$, where

• $\mathbf{X} = \{x_1,\ldots,x_n\}$ is a vector of n attributes,
• $\mathbf{D} = \{D_{x_1},\ldots,D_{x_n}\}$ is a vector containing exactly one domain for each attribute in $\mathbf{X}$. Each domain $D_x\in\mathbf{D}$ is a set of values $\{d_{i1},\ldots,d_{in_i}\}$ that may be assigned to the attribute corresponding to the domain.
• $\mathbf{C}$ is a set of compatibility constraints. A compatibility constraint $c_{\{x_i,\ldots,x_j\}}\in\mathbf{C}$ defines a relation over a subset of the domains $D_{x_i}, ..., D_{x_j}$, and hence $c_{\{x_i,\ldots,x_j\}}\subseteq D_{x_i}\times\ldots\times D_{x_j}$.

A solution to a hard constraint satisfaction problem is any tuple $\langle x_1:d_{x_1},\ldots,x_n:d_{x_n}\rangle$ such that

• each attribute is assigned a value from its domain: $\forall x_i\in\mathbf{X}, d_{x_i}\in D_{x_i}$, and
• all compatibility constraints are satisfied: $\forall x_{\{x_i,\ldots,x_j\}}\in\mathbf{C}, \langle d_{x_i},\ldots,d_{x_j}\rangle\in c_{\{x_i,\ldots,x_j\}}$.

An activity-based dynamic CSP (aDCSP), originally proposed in by Mittal and Falkenhainer [31], extends conventional CSPs with the notion of activity of attributes. In an aDCSP, not all attributes are necessarily assigned in a solution, but only the active ones. As such, each attribute is either active and assigned a value or inactive:

$$\forall x_i\in\mathbf{X}, \big(\exists d_{x_i}\in D_{x_i}, x_i:d_{x_i}\big)\leftrightarrow (x_i)$$

The activity of attributes in an aDCSP is governed by activity constraints that enforce under which assignments of attributes, an assignment to another attribute is relevant or possible. This information is important because it not only dictates for which attributes a value must be searched, but also the set of compatibility constraints that must be satisfied. Clearly, only the compatibility constraints $c_{\{x_i,\ldots,x_j\}}\in\mathbf{C}$ for which all attributes $x_i,\ldots,x_j$ are active must be satisfied, and a hard CSP is a sub-type of aDCSP in which all attributes are always active.

In summary, an activity-based dynamic constraint satisfaction problem (aDCSP) is a tuple $\langle\mathbf{X},\mathbf{D},\mathbf{C},\mathbf{A}\rangle$, where

• $\langle\mathbf{X},\mathbf{D},\mathbf{C}\rangle$ is a hard CSP, and
• $\mathbf{A}$ is a set of activity constraints. An activity constraint restricts the sets of attribute-value assignments under which an attribute is active or inactive:

  $$a_{x_i,\{x_j,\ldots,x_k\}}\thickspace\subseteq\thickspace D_{x_j}\times\ldots\times D_{x_k}\times\{ (x_i),\neg (x_i)\}$$

  
  
  where $x_i\not\in\{x_j,\ldots,x_k\}$.

A solution to an activity-based dynamic constraint satisfaction problem is any tuple $\langle x_1:d_{x_1},\ldots,x_l:d_{x_l}\rangle$ such that

• the attributes that are part of the solution are assigned a value from their domain: $\forall x_i\in\{x_1,\ldots,x_l\},d_{x_i}\in D_{x_i}$,
• all activity constraints are satisfied:

  $$\begin{split}&\forall a_{x_i,\{x_j,\ldots,x_k\}}\in\mathbf{A}... ...ive}(x_i)\rangle\in a_{x_i,\{x_j,\ldots,x_k\}}\big) \end{split}$$

  
  
  and
• all compatibility constraints are satisfied:

  $$\forall c_{\{x_i,\ldots,x_j\}}\in\mathbf{C}, \neg (x_i)\vee\ldots\vee\neg (x_j)\vee\langle d_{x_i},\ldots,d_{x_j}\rangle\in c_{\{x_i,\ldots,x_j\}}$$