Arc consistency simplifies the network by removing values from the domains of variables. A complementary method is variable elimination (VE), which simplifies the network by removing variables.

The idea of VE is to remove the variables one by one. When removing a variable $X$, VE constructs a new constraint on some of the remaining variables reflecting the effects of $X$ on the other variables. This new constraint replaces all of the constraints that involve $X$, forming a reduced network that does not involve $X$. VE provides a way to construct a solution to the CSP that contains $X$ from a solution to the reduced CSP.

The following algorithm is described using the relational algebra operations of join and project.

When eliminating $X$, the influence of $X$ on the remaining variables is through the constraint relations that involve $X$. First, the algorithm collects all of the constraints that involve $X$. Let the join of all of these relations be the relation $r_X(X,\overline{Y})$, where $\overline{Y}$ is the set of other variables in the scope of $r_X$. Thus $\overline{Y}$ is the set of all variables that are neighbors of $X$ in the constraint graph. The algorithm then projects $r_X$ onto $\overline{Y}$; this relation replaces all of the relations that involve $X$. The algorithm thus creates a reduced CSP that involves one less variable, which it solves recursively. Once it has a solution for the reduced CSP, it extends that solution to a solution for the original CSP by joining the solution with $r_X$.

When only one variable is left, it returns the domain elements that are consistent with the constraints on this variable.

Figure 4.7 gives a recursive algorithm for variable elimination, $VE\mathrm{\_}CSP$, to find all solutions for a CSP.

The base case of the recursion occurs when only one variable is left. The constraints are on one variable, giving the set of allowable values for that variable. The values for that variable are the intersection of the sets for each constraint.

In the non-base case, a variable $X$ is selected for elimination (line 10). To eliminate variable $X$, the algorithm propagates the effect of $X$ onto those variables that $X$ is directly related to. This is achieved by joining all of the relations in which $X$ is involved (line 12) and then projecting $X$ out of the resulting relation (line 13). Thus, a simplified problem (with one less variable) has been created that can be solved recursively. To get the possible values for $X$, the algorithm joins the solution of the simplified problem with the relation $R$ that defines the effect of $X$. If any value of $R$ in this algorithm contains no tuples, there are no solutions.

If you only wanted to find one solution, instead of returning $R\bowtie S$, the algorithm can return one element of the join. No matter which element it returns, that element is guaranteed to be part of a solution.

The order in which the variables are selected at line 10 is called the elimination ordering. The elimination ordering does not affect the correctness of the algorithm, but it may affect efficiency.

The intermediate structure – which variables the intermediate constraints are over – depends only on the graph structure of the constraint network and the elimination order. The maximum number of variables in the scope of an intermediate factor for a variable ordering is the treewidth of the graph for that variable ordering. The treewidth of a graph is the minimum treewidth for all orderings. The time complexity of variable elimination for finding one solution or counting the number of solutions is exponential in the treewidth and linear in the number of variables. The space is exponential in the treewidth. This can be compared to depth-first search [see Section 4.2], where the time is exponential in the number of variables, but the space is linear in the number of variables. The time complexity of the task for enumerating the solutions can be greater than this if there are many solutions.

Finding an elimination ordering that results in the smallest treewidth is NP-hard. However, some good heuristics exist. The two most common are:

• •

  Min-factor. At each stage, select the variable that results in the smallest factors being created at that stage.

• •

  Minimum deficiency or minimum fill. At each stage, select a variable that has the fewest pair variables in the new constraint that were not together in a constraint before the variable was eliminated. The deficiency of a variable $X$ is the number of pairs of variables that are in a constraint with $X$ that are not in another constraint with each other. The intuition is that it is okay to remove a variable that results in a large relation as long as it does not make the network more complicated.

The minimum deficiency has usually been found empirically to give a smaller treewidth than min-factor, but it is more difficult to compute.

VE can also be combined with GAC; whenever VE removes a variable, arc consistency can be used to further simplify the problem. This approach can result in smaller intermediate tables. For example, following eliminating one of the variables in Example 4.20, arc consistency will result in empty domains (even if there were many other variables and constraints).