CE884 Constraint Satisfaction For Decision Making, 2012-2013

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. This module will introduce the basic techniques in constraint satisfaction, with emphasis on their applications to real world problems. 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: Ao Han
Distinguished Guest Lecture: Dr James Borrett, Global Optimal Ltd, Visiting Fellow, School of Computer Science and Electronic Engineering (Handout)

Timetables:

• Lectures: Mondays 16:00-17:50pm, Room 6.345 (the first lecture will take place on Monday 14 January 2013)
• Classes: Fridays 16:00-16:50 Room 5.300 B
  (Old time and place was: Fridays 13:00-13:50pm Room 6.345)
• Distinguished Lecture: 16:00-17:50pm, Monday 11 February 2013, Room 6.345

Slides and Notes: Moodle

• Course contents and expectation New
• Overview lecture (pdf)
• Problem Reduction (pdf)
• Complete Search Methods (pdf)
• Stochastic Search (pdf)
• Problem Formulation Guide

Exercises and Assignments (on-line submission only):

Assignment 2012-13: Project Selection Problem -- the problem is to select a portfolio of projects to maximize revenue
• Assignment 1: problem formulation specification / spreadsheet
• Assignment 2: problem solving specification / (same spreadsheet as in Assignment 1)

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