CE884 Constraint Satisfaction For Decision Making, 2011-2012

Overview (see quick tutorial on constraint satisfaction)

Started in late 1980s, this is, as far as we know, the first module in constraint satisfaction in UK. Constraint satisfaction is about decision-making. It is about making a large number of decisions, satisfying complex constraints. It is at the heart of computer science. Students in artificial intelligence, operations research and applications (such as scheduling and computational finance) should benefit from taking this module.

Lecturer: Professor Edward Tsang / x2774 / Skype: bracil.net
Class tutor: Professor Edward Tsang /
Distinguished Guest Lecture: Dr James Borrett, Global Optimal Ltd, Visiting Fellow, School of Computer Science and Electronic Engineering, Tuesday 7 February 2012 (Handout)

Timetables:

• Lectures: Tuesdays 14:00-15:50pm, Lab 5 (the first lecture will take place on Tuesday 17 January 2012)
• Classes: Wednesdays 09:00-09:50pm Lab 5 (the first class will take place on Wednesday 1 February 2012)

Slides and Notes:

• Overview lecture (pdf)
• Problem Reduction (pdf)
• Complete Search Methods (pdf)
• Stochastic Search (pdf)
• Problem Formulation Guide

Exercises and Assignments (on-line submission only):

• Assignments:
• Assignment 1 (problem formulation); deadline: Friday 24 February 2012 (week 21) 11:59:59
• Assignment 2 (algorithms and optional implementation); deadline: Friday 23 March 2012 (week 25) 11:59:59

References:

• E P K Tsang, Foundations of Constraint Satisfaction, Academic Press, 1993 (On-line)
• F Rossi, P van Beek & T Walsh (ed), Handbook of Constraint Programming, Elsevier, 2006
• Rashidi, H. and Tsang, E.P.K., Vehicle Scheduling in Port Automation, VDM Verlag, 2010 , demonstrating constraint satisfaction formulations in port automation)
• Edgar Galvan's class material, 2006-07
• http://www.bracil.net/CSP links to other major research sites

Software:

• Backmarking Algorithm by Luis Vargas, 2002-03 (Installation shield, 23MB)
• Learning Nogoods Algorithm by Cesareo Gutierrez Casorran, 2002-03 (Java programs, 176K)
• Constraint solving system ZDC developed in the CACP Project at University of Essex

Student Supports:

• For technical consultation, please contact Edward Tsang, course supervisor
• For non-academic problems, advices are available from Professional Counselling services