Constraint Programming

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

• Laura Nechita, Newnham College
• Wednesday 10 February 2016, 19:40-20:30
• Wolfson Hall, Churchill College.

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.

This talk is included in these lists:

• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Churchill CompSci Talks
• Interested Talks
• Trust & Technology Initiative - interesting events
• Wolfson Hall, Churchill College
• bld31
• computer science
• ndk22's list
• ob366-ai4er
• rp587
• se393's list

Note that ex-directory lists are not shown.