VariableElimination (F, O)
//F = {f1**, . . . , f**m} *is the set of functions to be maximized;*
//O *stores the elimination order.*
For i = 1 to number of variables:
//Select the next variable to be eliminated.

Let l = O(i) ;
//Select the relevant functions.

Let e1**, . . . , e**L be the functions in F whose scope contains Xl.

//Maximize over current variable Xl.

Define a new function e **= max**xl PL
j=1 ej ; note that Scope[e] =
∪
L
j=1Scope[ej ] − {Xl}.

//Update set of functions.

Update the set of functions F = F ∪ {e} \ {e1**, . . . , e**L}.

//Now, all functions have empty scope and their sum is the maximum value of f1 + **· · ·** + fm.

Return the maximum value Pei∈F ei.

Figure 4: Variable elimination procedure for computing the maximum value f1 + **· · ·** + fm, where each fi**is a restricted scope function.**
having one fewer variable. Next, we eliminate another variable, say X3**, with the resulting**
expression reducing to:
max x1,x2 f1(x1, x2) + e2(x1, x2),

$$e_{2}(x_{1},x_{2})=\operatorname*{max}_{x_{3}}[f_{2}(x_{1},x_{3})+e_{1}(x_{2},x_{3})].$$
$$w h e r e\;,$$
Finally, we define
$$e_{3}=\operatorname*{max}_{x_{1},x_{2}}f_{1}(x_{1},x_{2})+e_{2}(x_{1},x_{2}).$$

The result at this point is a number, which is the desired maximum over x1, . . . , x4**. While**
the naive approach of enumerating all states requires 63 **arithmetic operations if all variables** are binary, using variable elimination we only need to perform 23 **operations.**
The general variable elimination algorithm is described in **Figure 4. The inputs to**
the algorithm are the functions to be maximized F = {f1, . . . , fm} **and an elimination**
ordering O on the variables, where O(i) returns the i**th variable to be eliminated. As in**
the example above, for each variable Xl **to be eliminated, we select the relevant functions**
e1, . . . , eL, those whose scope contains Xl. These functions are removed from the set F and we introduce a new function e **= max**xl PL
j=1 ej **. At this point, the scope of the functions in**
F no longer depends on Xl, that is, Xl **has been 'eliminated'. This procedure is repeated**
until all variables have been eliminated. The remaining functions in F **thus have empty**
scope. The desired maximum is therefore given by the sum of these remaining functions.

The computational cost of this algorithm is linear in the number of new "function values" introduced in the elimination process. More precisely, consider the computation of a new function e whose scope is Z. To compute this function, we need to compute |**Dom[**Z]| different values. The cost of the algorithm is linear in the overall number of these values, introduced throughout the execution. As shown by Dechter (1999), this cost is exponential