Title: Symmetry Breaking in Constraint Satisfaction and Optimization

Speaker: Prof. Jimmy Ho Man Lee  

Time: 3:00 pm, Monday, July 10, 2017

Venue: Room 334, Building 5, Institute of Software, Chinese Academy of Sciences

Abstract:

Constraint satisfaction and optimization problems occur in many real-life applications, such as scheduling, binpacking, transport routing and resource allocation.  Such problems are NP-hard in general.  The mainstream constraint-solving mechanisms encompass systematic exploration of search trees augmented with various degrees of constraint propagation to prune the search space.  Symmetries are transformations that map a CSP solution into another solution (and also from non-solutions to non-solutions).  Visiting symmetrical equivalents of traversed subtrees is fruitless.  In many cases, all symmetrical variants of every deadend encountered during the search must be explored before a solution can be found.  The goal of symmetry breaking is to avoid traversing the symmetrical equivalents of visited search nodes, so as to increase solution efficiency.

Symmetries can be broken statically or dynamically.  Static methods alter the original problem by adding new constraints to eliminate symmetric solutions, e.g. the LexLeader method. In contrast, dynamic methods modify the search procedure to exclude exploration of symmetric regions, e.g. Symmetry Breaking During Search (SBDS).   Even though dynamic methods have several advantages over static methods, its overhead is too large in general to make it practical.  As evidenced by Walsh's Spotlight Talk at AAAI-2012, most recent successful symmetry breaking work has been static in nature.  In this talk, we share our experience of a series of work in recent years that revive the competitiveness of dynamic methods by showing how to break more composition symmetries efficiently and reduce overheads.

Bio:

Jimmy Lee graduated on the Dean's Honours List with an Honours BMath degree, majoring both in Applied Mathematics and Computer Science, from the University of Waterloo, Canada, in 1987. He completed his doctoral study in the area of constraint logic programming from the University of Victoria, Canada, in 1992, and then joined the Chinese University of Hong Kong (CUHK). He is now a Professor in the Department of Computer Science and Engineering, and a Professor (by courtesy) in the Department of Systems Engineering and Engineering Management of CUHK. Jimmy's research focuses on the theory and practice of constraint satisfaction and optimization with applications in combinatorial optimization, scheduling, and resource allocation.

Jimmy is on the editorial boards of the Journal of Artificial Intelligence Research, the Artificial Intelligence Review, and Research and Practice in Technology Enhanced Learning. He was on the editorial board of the CONSTRAINTS journal and of the Journal of Discrete Algorithms. He was a founding editor of the Constraint Programming News. Jimmy was an elected member of the Executive Committee of the Association for Constraint Programming during 2006-09, and served as the Secretary of the Association from 2006 to 2012. He is a Doctoral Consortium Co-Chair and Senior PC member of IJCAI 2017, a Senior PC member of AI 2017, CP 2017, and a PC member of AAAI 2017. Jimmy was the Program Chair of CP 2011.