433-433 Constraint Programming

Credit may not be gained for both 433-433 Constraint Programming and 433-633 Constraint Programming.

Study at the third-year level in at least four of the following areas: artificial intelligence, computer design, database systems, graphics, interactive system design, networks and communications, operating systems, programming languages, software engineering, and theory of computation.

Constraint Programming is used to solve constraint satisfaction problems such as scheduling and allocation, which are of vital importance to modern business. Increasingly the discipline is replacing operations research, as a generic approach to solving management decisionn problems.

Topics covered include: constraints - valuations, modelling, constraint satisfactin, Gaussian elimination, Simplex and other constraint solvers; constraint simplification, projection and optimisation; finite constraint domains: constraint satisfaction problems, backtracking solvers, node and arc consistency, bounds consistency, generalised consistency methods; constraint logic programs: user-defined constraints, rules, evaluation, derivation trees, the CLP scheme; simple modelling: choice, iteration, optimisation; using data structures: records, lists, binary trees, hierarchical modelling; search control: rule ordering, literal ordering, redundant constraints, minimisation; programming with finite domain constraints: domains, labelling; advanced programming techniques: combined symbolic and arithmetic reasoning, programming optimisation, negation, dynamic scheduling.

Project work during semester expected to take 36 hours (30%) and a 3-hour end of semester written exam (70%). To pass the subject students must obtain at least 50% overall, 15/30 on projects and 35/70 in the examination.