Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).

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
c1:
A B Cost
1 1 5
1 2 2
1 3 2
2 1 0
2 2 4
2 3 3
 

c2:

B C Cost
1 1 5
1 2 2
2 1 0
2 2 4
3 1 2
3 2 0
 

c3:

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 c1 is {A,B}, the scope of c2 is {B,C}, and the scope of c3 is {B,D}. Suppose there are also constraints c4(C,E) and c5(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, c1(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 c1 and c2 in the previous example. c1+c2 is a function with scope {A,B,C}, given by
c1+c2:
A B C Cost
1 1 1 10
1 1 2 7
1 2 1 2
... ... ... ...

The second value is computed as follows:

(c1+c2)(A=1,B=1,C=2)
=c1(A=1,B=1)+c2(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.