Seminar by Prof. Jimmy H.M. Lee, Department of Computer Science and Engineering, The Chinese University of Hong Kong

TITLE: Recent Advances in Global Cost functions Propagation in Cost Function Networks


Cost function networks (or Weighted Constraint Satisfaction Problems) is a framework for handling soft requirements or preferences in over-constrained problems so as to obtain useful partial solutions. We differentiate between soft constraints and cost functions, and then delineate the implications on the stronger consistencies achievable with cost functions. While the basic technique for solving weighted constraint satisfaction problems (WCSPs) relies on a form of branch and-bound search, standard consistency notions and techniques (AC*, FDAC*, and EDAC*) for only unary, binary, and ternary constraints were developed initially to help prune the search space. We explain the difficulties in incorporating global cost functions, which are usually with high arity but with special semantics, into CFNs efficiently to help model real-life complex problems. We introduce the class of flow-based projection-safe global cost functions and give polynomial time algorithms for enforcing the generalized versions of AC* (GAC*) and FDAC* (FDGAC*).  Doing the same for the stronger EDAC* is less straightforward since enforcing EDAC* on cost functions sharing more than 2 variables will lead to oscillation. We propose a weak version of EDAC* and generalize it to weak EDGAC* for global cost functions. We also show that weak EDGAC* can be enforced in polynomial time for projection-safe constraints. Extensive experimentation confirms the efficiency of our proposal. Time permitting, we shed light on possibilities beyond flow-based projection-safety.


Jimmy Lee read both his BMath (Hons) and MMath degrees at the University of Waterloo during 1983 to 1988, and completed his doctoral studies at the University of Victoria in 1992. Upon graduation, he joined The Chinese University of Hong Kong, where he is now Professor in the Department of Computer Science and Engineering. His research focuses on the theory and practice of constraint satisfaction and optimization with applications in scheduling, resource allocation, and combinatorial problems.  Jimmy is on the editorial boards of the Journal of Discrete Algorithms, the CONSTRAINTS journal, and the Journal of AI Research.  He 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. Inspired by his many former good teachers from elementary school to universities, Jimmy's passion for teaching garnered him the Vice-Chancellor's Exemplary Teaching Award in 2005.rober

Monday, June 10, 2013,
14:00 to 15:00
SICS, room Knuth, Electrum
Isafjordsgatan 22/Kistagången 16