4.5 Variable Elimination

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 rX(X,Y¯), where Y¯ is the set of other variables in the scope of rX. Thus Y¯ is the set of all variables that are neighbors of X in the constraint graph. The algorithm then projects rX onto 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 rX.

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

Example 4.22.

Consider a CSP that contains the variables A, B, and C, each with domain {1,2,3,4}. Suppose the constraints that involve B are A<B and B<C. There may be many other variables, but if B does not have any constraints in common with these variables, eliminating B will not impose any new constraints on these other variables. To remove B, first join on the relations that involve B:

1 2
1 3
1 4
2 3
2 4
3 4

  B C 1 2 1 3 1 4 2 3 2 4 3 4  =  A B C 1 2 3 1 2 4 1 3 4 2 3 4

To get the relation on A and C induced by B, project this join onto A and C, which gives

1 3
1 4
2 4

This relation on A and C contains all of the information about the constraints on B that affect the solutions of the rest of the network.

The original constraints on B are replaced with the new constraint on A and C. VE then solves the rest of the network, which is now simpler because it does not involve the variable B. To generate one or all solutions, the algorithm remembers the joined relation on A,B,C to construct a solution that involves B from a solution to the reduced network.

Figure 4.7 gives a recursive algorithm for variable elimination, VE_CSP, to find all solutions for a CSP.

1: procedure VE_CSP(Vs,Cs)
2:      Inputs
3:          Vs: a set of variables
4:          Cs: a set of constraints on Vs      
5:      Output
6:          a relation containing all of the consistent variable assignments
7:      if Vs contains just one element then
8:          return the join of all relations in Cs
9:      else
10:          select variable X to eliminate
11:          CX:={CCs:C involves X}
12:          R := join of all of the constraints in CX
13:          NR := R projected onto the variables other than X
14:          S:=VE_CSP(Vs{X},(CsCX){NR})
15:          return RS      
Figure 4.7: Variable elimination for finding all solutions to 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.

Example 4.23.

Consider the constraints of Example 4.9, shown in Figure 4.5. If the variables are selected in the elimination order A, C, D, E, the algorithm has the following sequence of constraints being joined (CX in the algorithm) and new constraint created (NR in the algorithm) where, for example, c1(B,D,E) is a new constraint on variables {B,D,E}:

Variable Eliminated Constraints Joined New Constraint
A AB, A=D, E<A c1(B,D,E)
C BC, C<D, E<C c2(B,D,E)
D E<D, BD, c1(B,D,E), c2(B,D,E) c3(B,E)
E E<B, c3(B,E) c4(B)

The legal assignment(s) for B is given in c4(B).

The elimination order B, C, A, E has the following constraints joined and new constraints:

Variable Eliminated Constraints Joined New Constraint
B AB, BD, BC, E<B c5(A,C,D,E)
C C<D, E<C , c5(A,C,D,E) c6(A,D,E)
A A=D, E<A, c6(B,D,E) c7(D,E)
E E<D, c7(D,E) c8(D)

These elimination orderings result in the same set of answers.

If you only wanted to find one solution, instead of returning RS, 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).