(11th-May-2020)
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.
Systematic Methods for Optimization
Arc consistency can be generalized to optimization problems by allowing pruning of dominated assignments. Suppose c1,...,ck are the soft constraints that involve X. Let soft constraint c= c1+...+ck. 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.
Local Search for Optimization
Local search is directly applicable to optimization problems, using the objective function of the optimization problem as the evaluation function of the local search. The algorithm runs for a certain amount of time (perhaps including random restarts to explore other parts of the search space), always keeping the best assignment found thus far, and returning this as its answer.
Commenti