One way to find the minimal assignment, corresponding to generate and test, is to compute the sum of the soft constraints and to select an assignment with minimum value. This is infeasible for large problems.

Arc consistency can be generalized to optimization problems by allowing pruning of dominated assignments. Suppose $c_1,\mathrm{\dots },c_k$ are the soft constraints that involve $X$. Let $c=c_1+\mathrm{\dots }+c_k$. Suppose $Y_1,\mathrm{\dots },Y_m$ 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_1,\mathrm{\dots },y_k$ of $Y_1,\mathrm{\dots },Y_m$, some value $v^{\prime }$ of $X$ exists such that . Pruning strictly dominated values does not remove a minimal 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 may greatly simplify the problem but does not, by itself, always solve the problem.

Domain splitting is used to build a search tree. A node is an assignment of a value to a subset of the variables. The neighbors of a node are obtained by selecting a variable $X$ that is not assigned in the node to split; there is a neighbor of the node for 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 due to hard constraints or to domination. The arc cost is the evaluation of the soft constraints that are able to be evaluated. A goal node is one where all of the variables are assigned.

By assigning costs as soon as a soft constraint is able to be evaluated, search algorithms such as $A^{*}$ or branch-and-bound can be used to find a minimal solution. These methods require each arc cost to be non-negative. To achieve this, the lowest cost in each soft constraint – even if it is negative – is subtracted from each of the costs in the soft constraint. This cost then needs to be added to the cost of a final solution.

Variable elimination can also be used for soft constraints. 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$. Compute, $T$, 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=\text{scope}(T)\setminus \{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.12 gives pseudocode for the variable elimination with soft constraints (VE_SC) algorithm. The elimination ordering can be given a priori or may be computed on the fly, for example, using the elimination ordering heuristics discussed for VE_CSP. It is possible to implement VE_SC without storing $T$ and by only constructing an extensional representation of $N$.

The complexity of VE_SC 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.