Artificial
Intelligence

4.10.1 Systematic Methods for Optimization

Arc consistency can be generalized to optimization problems by allowing pruning of dominated assignments. Suppose c₁,...,c_k are the soft constraints that involve X. Let soft constraint c= c₁+...+c_k. Suppose 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).

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.

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.