### 4.10.1 Systematic Methods for Optimization

Arc consistency can be generalized to optimization problems by
allowing pruning of dominated assignments. Suppose *c _{1},...,c_{k}* are
the soft constraints that involve

*X*. Let soft constraint

*c= c*. Suppose

_{1}+...+c_{k}*Y*are the variables, other than

*X*, that are involved in

*c*. A value

*v*for variable

*X*is

**strictly dominated**if, for all values

*y*of

*Y*, some value

*v'*of

*X*exists such that

*c(X=v',Y=y) < c(X=v,Y=y)*. Pruning strictly dominated values does not remove an optimal solution. The pruning of domains can be done repeatedly, as in the GAC algorithm.

**Weakly dominated** has the same definition
as strictly dominated, but with "less than" replaced by "less than
or equal to." If only one solution is required, weakly dominated
values can be pruned sequentially. Which weakly dominated values are
removed may affect which optimal solution is found, but removing
a weakly dominated value does not remove all optimal solutions. As
with arc consistency for hard constraints, pruning (strictly or
weakly) dominated values can greatly simplify the problem but does
not, by itself, always solve the problem.

Domain splitting can be used to build a search tree. Domain splitting picks some variable *X*
and considers each value of *X*. Assigning a value to *X* allows the
constraints that involve *X* to be simplified and
values for other variables to be pruned. In particular,
pruning weakly dominated values means that, when there is
only one variable left, a best value for that variable can be
computed.
Repeated domain splitting can build a search tree, as in Figure 4.1, but with values at the leaves. By assigning costs when they can be determined, search
algorithms such as *A ^{*}* or branch-and-bound can be used to find an optimal solution.

Domain splitting can be improved via two techniques. First, if, under a
split on *X*, an assignment
to another variable does not depend on the value of *X*, the
computation for that variable can be shared among the subtrees for
the values of *X*; the value can be computed once and cached. Second,
if removing a set of variables would disconnect the constraint graph, then when those
variables have been assigned values, the disconnected
components can be solved independently.

**Variable elimination** is the dynamic programming variant of domain
splitting. The variables are eliminated one at a time.
A variable *X* is eliminated as follows. Let *R* be the set of constraints that involve
*X*. *T* is a new constraint whose scope is the union of the scopes of the
constraints in *R* and whose value is the sum of the values of *R*. Let
*V=scope(T) \ {X}*. For each value of the
variables in *V*, select a value of *X*
that minimizes *T*, resulting in a new soft
constraint, *N*, with scope *V*. The constraint
*N* replaces the constraints in *R*. This results in a new problem, with fewer variables and
a new set of constraints, which can be solved recursively. A
solution, *S*, to the reduced problem is an assignment to the
variables in *V*. Thus, *T(S)*, the constraint *T* under the assignment *S*, is a function of *X*. An optimal value for *X* is
obtained by choosing a value that results in the minimum value of
*T(S)*.

**Procedure**VE_SC(

*Vs,Fs*)

2:

**Inputs**

3:

*Vs*: set of variables

4:

*Fs*: set of constraints

**Output**

5: an optimal assignment to

*Vs*.

6:

**if**(

*Vs*contains a single element or

*Fs*contains a single constraint)

**then**

7: let

*F*be the sum of the constraints in

*Fs*

8:

**return**assignment with minimum value in

*F*

9:

**else**

10: select

*X∈Vs*according to some elimination ordering

11:

*R={F ∈Fs: F involves X}*

12: let

*T*be the sum of the constraints in

*R*

13:

*N ←min*

_{X}T14:

*S←VE_SC(Vs \ {X}, Fs \ R∪{N})*

15:

*X*

_{opt}←argmin_{X}T(S)16:

**return**

*S ∪{X=X*

_{opt}}17:

Figure 4.11 gives pseudocode for the VE
algorithm. The elimination ordering can be given a priori or
can be computed on the fly, for example, using the
elimination ordering heuristics discussed for CSP VE. It is possible to implement this
without storing *T* and only by constructing an extensional representation
of *N*.

**Example 4.31:**Consider Example 4.29. First consider eliminating

*A*. It appears in only one constraint,

*c*. Eliminating

_{1}(A,B)*A*gives

*c*:

_{6}(B) =argmin_{A}c_{1}(A,B)
B | Cost |

1 | 0 |

2 | 2 |

3 | 2 |

The constraint *c _{1}(A,B)* is replaced by

*c*.

_{6}(B)Suppose *B* is eliminated next. *B* appears in three constraints: *c _{2}(B,C)*,

*c*, and

_{3}(B,D)*c*. These three constraints are added, giving

_{6}(B)*c*:

_{2}(B,C) + c_{3}(B,D) + c_{6}(B)
B | C | D | Cost |

1 | 1 | 1 | 8 |

1 | 1 | 2 | 5 |

... | |||

2 | 1 | 1 | 4 |

2 | 1 | 2 | 4 |

... | |||

3 | 1 | 1 | 6 |

3 | 1 | 2 | 8 |

The constraints *c _{2}*,

*c*, and

_{3}*c*are replaced by

_{6}*c*:

_{7}(C,D)=min_{B}(c_{2}(B,C) + c_{3}(B,D) + c_{6}(B))
C | D | Cost |

1 | 1 | 4 |

1 | 2 | 4 |

... |

There are now three remaining constraints: *c _{4}(C,E)*,

*C*, and

_{5}(D,E)*c*. These can be optimized recursively.

_{7}(C,D)Suppose the recursive call returns the solution *C=1*, *D=2*,
*E=2*. An optimal value for *B* is the value that gives the minimum
in *c _{2}(B,C=1) + c_{3}(B,D=2) + c_{6}(B)*, which is

*B=2*.

From *c _{1}(A,B)*, the value of

*A*that minimizes

*c*is

_{1}(A,B=2)*A=1*. Thus, an optimal solution is

*A=1*,

*B=2*,

*C=1*,

*D=2*,

*E=2*.

The complexity of VE depends on
the structure of the constraint graph, as it does with hard constraints. Sparse graphs may result in small
intermediate constraints in VE algorithms, including *VE_SC*. Densely connected graphs result in large
intermediate constraints.