CE884 Constraint Satisfaction For Decision Making, 2015-2016

Overview (see quick tutorial on constraint satisfaction)

Constraint satisfaction is about decision-making. It is about making a large number of decisions, satisfying complex constraints. Constraint techniques have been employed by many companies, including IBM, British Telecom, British Airway. This module will introduce the basic techniques in constraint satisfaction, with emphasis on its applications to real world problems such as logistics and finance. Constraint satisfaction is the core of computer science. Students in artificial intelligence, operations research, computational finance, etc. should all benefit from taking this module.

Started in late 1980s, this is, as far as we know, the first module in constraint satisfaction in UK.

Lecturer: Professor Edward Tsang / x2774 / Skype: bracil.net

Timetables:

• Tuesdays 9-11am 2.409

Slides and Notes:

• Course contents and expectation
• Overview lecture (pdf)
• Problem Formulation Guide
• Problem Reduction (pdf)
• Complete Search Methods (pdf, revised 2014.03.18)
• Stochastic Search (pdf, revised 2014.03.18)
• Case study: BT's workforce scheduling problem

Exercises and Assignments (on-line submission only):

• Assignments: download here

References:

• E P K Tsang, Foundations of Constraint Satisfaction, Academic Press, 1993, Edited by Thom Fruehwirth, Books on Demand, 2014
• 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, 2nd Edition, CRC Press, 2015, 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 administrative support, contact the General Office / Room 4.514 / Phone: +44 1206 872256 / Email at essex.ac.uk: csee-schooloffice
• For non-academic problems, advices are available from Professional Counselling services