Revisiting Constraint Solving – From Non-Binary to Binary
Speaker:
Professor Roland Yap
National University of Singapore (NUS)
| Zoom: | https://cuhk.zoom.us/j/94749652768
Meeting ID: 947 4965 2768 (Students must login with CUHK account, i.e., @link.cuhk.edu.hk, for valid attendance record) |
Abstract:
Solving finite domain constraints, e.g., Constraint Satisfaction Problems (CSP), is an intractable problem which nevertheless is one of practical significance. Due to the intractability, in practice, inference techniques usually local consistencies are used which combine neatly with search heuristics. In general, a constraint may either be a binary or non-binary relation and the typical consistency used is either Arc Consistency (for binary) and Generalised Arc Consistency (for non-binary). The natural form for many constraints is as a non-binary constraint (having more than two variables). However, it is known that binary CSPs are also NP-complete. For a long time, most efforts have been placed on non-binary techniques as they were believed to be more efficient.
In this talk, we will revisit the question of binary vs non-binary. We show why the reason behind why binary approaches were believed to be inefficient. Then we show that this belief is mistaken and binary approaches through better encodings and algorithms can outperform existing non-binary techniques. We will discuss improvements to old encodings as well as present new encodings and associated algorithms.
Biography:
Roland Yap is an Associate Professor in the Department of Computer Science, National University of Singapore, Singapore. He received his PhD from Monash University, Australia. He has pioneering work in the development of Constraint Logic Programming languages and the field of Constraint Programming. Together with Christian Bessiere, Jean-Charles Régin, and Yuanlin Zhang, their work on (Generalized) Arc Consistency was awarded the AI Journal Classic Paper Award in 2022. His current research interests include AI, Big Data, Constraints, Operating Systems, Programming Languages, Security and Social Networks.
Enquiries:
Professor Jimmy Lee (jlee@cse.cuhk.edu.hk)
Mr. WONG O-Bong (obong@cse.cuhk.edu.hk)