Constraint Programming

This subject is not offered in 2009.

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.

For the purposes of considering request for Reasonable Adjustments under the Disability Standards for Education (Cwth 2005), and Student Support and Engagement Policy, academic requirements for this subject are articulated in the Subject Overview, Learning Outcomes, Assessment and Generic Skills sections of this entry.

It is University policy to take all reasonable steps to minimise the impact of disability upon academic study, and reasonable adjustments will be made to enhance a student's participation in the University's programs. Students who feel their disability may impact on meeting the requirements of this subject are encouraged to discuss this matter with a Faculty Student Adviser and Student Equity and Disability Support: http://services.unimelb.edu.au/disability

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 decision 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.

On completion students should be able to:

• explain the role of constraint solving and search in solving combinatorial problems;
• model complex combinatorial problems as constraint programs;
• evaluate the suitability of a particular model to solving a problem; and
• program effective search strategies for combinatorial problems.

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.

This subject is not available as a breadth subject.

On completion of this subject students should:

• be able to undertake problem identification, formulation and solution;
• have a capacity for independent critical thought, rational inquiry and self-directed learning; and
• have a profound respect for truth and intellectual integrity, and for the ethics of scholarship.

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