| Course code | CSCI5240 |
| Course title | Combinatorial Search and Optimization with Constraints 基於限制的組合搜索與優化 |
| Course description | Students will be exposed to various constraint-based combinatorial search and optimization techniques that arise in artificial intelligence, operations research, etc. Topics include, but are not limited to, local propagation, consistency algorithms, Boolean constraint solving, numerical constraint solving, linear programming, search, and their applications. Blended-mode class section is available for this course. Please refer to the “Class Notes” of the blended-mode class section for details. 學生將會學習到各基於限制的組合搜索與優化技術在人工智能，運 籌學等。課題包括﹝但不僅限於﹞局部傳播，相容性算法，布爾限制解法，數值限制解法，線性規劃，搜索及其應用。 |
| Unit(s) | 3 |
| Course level | Postgraduate |
| Semester | 1 or 2 |
| Grading basis | Graded |
| Grade Descriptors | A/A-: EXCELLENT – exceptionally good performance and far exceeding expectation in all or most of the course learning outcomes; demonstration of superior understanding of the subject matter, the ability to analyze problems and apply extensive knowledge, and skillful use of concepts and materials to derive proper solutions. B+/B/B-: GOOD – good performance in all course learning outcomes and exceeding expectation in some of them; demonstration of good understanding of the subject matter and the ability to use proper concepts and materials to solve most of the problems encountered. C+/C/C-: FAIR – adequate performance and meeting expectation in all course learning outcomes; demonstration of adequate understanding of the subject matter and the ability to solve simple problems. D+/D: MARGINAL – performance barely meets the expectation in the essential course learning outcomes; demonstration of partial understanding of the subject matter and the ability to solve simple problems. F: FAILURE – performance does not meet the expectation in the essential course learning outcomes; demonstration of serious deficiencies and the need to retake the course. |
| Learning outcomes | At the end of the course of studies, students will have acquired the ability to 1. understand of Constraint Satisfaction Problems (CSPs). 2. formulate a real-life problem into a CSP. 3. understand of various constraint solving techniques for CSPs in a particular domain. 4. understand of the tree-search techniques for solving general CSPs. 5. understand of the various local consistency notions and their associated enforcement algorithms. 6. understand of how local consistency algorithms can be combined with tree search. 7. understand of stochastic local search algorithms. 8. make use of existing constraint solving tools to solve CSPs. |
| Assessment (for reference only) |
Lab reports: 40% Presentation: 30% Essays: 30% |
| Recommended Reading List | 1. Programming with Constraints: An Introduction, Kim Marriott and Peter J. Stuckey, The MIT Press, 1998 2. Principles of Constraint Programming, Krzysztof R. Apt, Cambridge University Press, 2003 |
| CSCIN programme learning outcomes | Course mapping |
| Upon completion of their studies, students will be able to: | |
| 1. identify, formulate, and solve computer science problems (K/S); | TP |
| 2. design, implement, test, and evaluate a computer system, component, or algorithm to meet desired needs (K/S); |
TP |
| 3. receive the broad education necessary to understand the impact of computer science solutions in a global and societal context (K/V); | T |
| 4. communicate effectively (S/V); |
P |
| 5. succeed in research or industry related to computer science (K/S/V); |
T |
| 6. have solid knowledge in computer science and engineering, including programming and languages, algorithms, theory, databases, etc. (K/S); | TP |
| 7. integrate well into and contribute to the local society and the global community related to computer science (K/S/V); | |
| 8. practise high standard of professional ethics (V); | |
| 9. draw on and integrate knowledge from many related areas (K/S/V); |
T |
| Remarks: K = Knowledge outcomes; S = Skills outcomes; V = Values and attitude outcomes; T = Teach; P = Practice; M = Measured | |