## 4.10 Optimization

Instead of just having possible worlds satisfy constraints or not, we often have a **preference** relation over possible worlds, and we want
a best possible world according to the preference. The preference is often to minimize some error.

An **optimization problem** is given

- a set of variables, each with an associated domain;
- an
**objective function**that maps total assignments to real numbers; and - an
**optimality criterion**, which is typically to find a total assignment that minimizes or maximizes the objective function.

The aim is to find a total assignment that is optimal according to the optimality criterion. For concreteness, we assume that the optimality criterion is to minimize the objective function.

A **constrained optimization
problem** is an optimization problem that also has hard constraints specifying which variable assignments
are possible.
The aim is to find a best assignment that satisfies the hard constraints.

A huge literature exists on optimization. There are many techniques for particular forms of constrained optimization problems. For example, linear programming is the class of constrained optimization where the variables are real valued, the objective function is a linear function of the variables, and the hard constraints are linear inequalities. We do not cover these specific techniques. Although they have many applications, they have limited applicability in the space of all optimization problems. We do cover some general techniques that allow more general objective functions. However, if the problem you are interested in solving falls into one of the classes for which there are more specific algorithms, or can be transformed into one, it is generally better to use those techniques than the general algorithms presented here.

In a **constraint optimization problem**, the objective function
is factored into a set of functions of subsets of the variables
called soft constraints. A **soft constraint** assigns a cost for each
assignment of values to some subset of the variables. The value of the objective
function on a total assignment is the sum of
the costs given by the soft
constraints on that total assignment. A typical optimality criterion is to minimize the
objective function.

Like a hard constraint, a soft
constraint has a **scope** that is a set of variables. A soft
constraint is a function from the domains of the variables in its
scope into a real number, called its **evaluation**. Thus, given an assignment of a value to
each variable in its scope, this function returns a real number.

**Example 4.29:**Suppose a number of delivery activities must be scheduled, similar to Example 4.8, but, instead of hard constraints, there are preferences on times for the activities. The soft constraints are costs associated with combinations of times. The aim is to find a schedule with the minimum total sum of the costs.Suppose variables

*A*,

*C*,

*D*, and

*E*have domain

*{1,2}*, and variable

*B*has domain

*{1,2,3}*. The soft constraints are

*c*:

_{1}
A | B | Cost |

1 | 1 | 5 |

1 | 2 | 2 |

1 | 3 | 2 |

2 | 1 | 0 |

2 | 2 | 4 |

2 | 3 | 3 |

*c _{2}*:

B | C | Cost |

1 | 1 | 5 |

1 | 2 | 2 |

2 | 1 | 0 |

2 | 2 | 4 |

3 | 1 | 2 |

3 | 2 | 0 |

*c _{3}*:

B | D | Cost |

1 | 1 | 3 |

1 | 2 | 0 |

2 | 1 | 2 |

2 | 2 | 2 |

3 | 1 | 2 |

3 | 2 | 4 |

Thus, the scope of *c _{1}* is

*{A,B}*, the scope of

*c*is

_{2}*{B,C}*, and the scope of

*c*is

_{3}*{B,D}*. Suppose there are also constraints

*c*and

_{4}(C,E)*c*.

_{5}(D,E)An assignment to some of the variables in a soft constraint
results in a soft constraint that is a
function of the other variables. In the preceding example, *c _{1}(A=1)* is a function of

*B*, which when applied to

*B=2*evaluates to 2.

Given a total assignment, the evaluation of the total assignment is the sum of the evaluations of the soft constraints applied to the total assignment. One way to formalize this is to define operations on the soft constraints. Soft constraints can be added pointwise. The sum of two soft constraints is a soft constraint with scope that is the union of their scopes. The value of any assignment to the scope is the sum of the two functions on that assignment.

**Example 4.30:**Consider functions

*c*and

_{1}*c*in the previous example.

_{2}*c*is a function with scope

_{1}+c_{2}*{A,B,C}*, given by

*c*:

_{1}+c_{2}
A | B | C | Cost |

1 | 1 | 1 | 10 |

1 | 1 | 2 | 7 |

1 | 2 | 1 | 2 |

... | ... | ... | ... |

The second value is computed as follows:

(c _{1}+c_{2})(A=1,B=1,C=2) =c _{1}(A=1,B=1)+c_{2}(B=1,C=2)=5+2 =7

One way to find the optimal assignment, corresponding to
**generate and test**, is to compute the sum of the soft
constraints and to choose an assignment with minimum value. Later we
consider other, more efficient, algorithms for optimization.

Hard constraints can be modeled as having a cost of infinity for violating a constraint. As long as the cost of an assignment is finite, it does not violate a hard constraint. An alternative is to use a large number - larger than the sum of the soft constraints could be - as the cost of violating a hard constraint. Then optimization can be used to find a solution with the fewest number of violated hard constraints and, among those, one with the lowest cost.

Optimization problems have one difficulty that goes beyond constraint satisfaction problems. It is difficult to know whether an assignment is optimal. Whereas, for a CSP, an algorithm can check whether an assignment is a solution by just considering the assignment and the constraints, in optimization problems an algorithm can only determine if an assignment is optimal by comparing it to other assignments.

Many of the methods for solving hard constraints can be extended to optimization problems, as outlined in the following sections.