University of Cambridge > > Churchill CompSci Talks > Constraint Programming

Constraint Programming

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Matthew Ireland.

Constraint programming (CP) is a form of declarative programming which is used for solving large, combinatorial problems especially in areas of planning and scheduling. It consists of identifying feasible solutions out of a very large set of candidate solutions, where the problem can be modeled in terms of arbitrary constraints. CP has many applications in many different domains: computer graphics (to express geometric coherence in the case of scene analysis), natural language processing (e.g. construction of efficient parsers), database systems, molecular biology (DNA sequencing), business, etc. This talk will first introduce the basic notions of CP and then focus on the solving aspect, in particular, symmetry breaking, consistency enforcement algorithms and global constraints. Symmetry breaking is a technique for reducing the search space, but it relies on the presence of symmetry in the solutions. Consistency enforcement, on the other hand, is an orthogonal technique that achieves the same goal and is applicable to more general CSPs. Both of these techniques exploit special structures in CSPs to reduce solving time. An alternative approach is to identify global constraints, namely constraints that are present and repeatedly used in a wide variety of constraint problems. We shall explore how the ideas of global constraints and special purpose consistency enforcement can be combined to form the basis of efficient and modern constraint solvers.

This talk is part of the Churchill CompSci Talks series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity