Consistency for soft constraints

Supervisor

Suitable for

Abstract

Constraint satisfaction problems consist of a collection of variables which must be assigned values subject to certain constraints. The usual methods for solving such problems efficiently involve various ways of pruning possible values from the domains of the variables, based on various notions of "consistency". Some problems involve "soft" constraints, which do not specify exactly which combinations of values are possible and which are not, but only the costs of different combinations. The task is then to find the assignment of values which minimizes the total cost. For these problems it is much harder to prune values during the search, but there is beginning to be some research on notions of consistency for soft constraints. For example, a recent paper by Lee and Leung explains how to achieve soft arc-consistency on certain forms of constraints - see http://ijcai.org/papers09/Papers/IJCAI09-099.pdf.

The project would involve investigating the notion of consistency for soft constraints, and then designing efficient algorithms to prune values for various useful forms of soft constraint by applying various notions of consistency. Such algorithms could be incorporated into the workbench for soft constraints being developed in Toulouse, which is called Toulbar - see http://carlit.toulouse.inra.fr/cgi-bin/awki.cgi/ToolBarIntro.