Solving Combinatorial Search Problems Using DP, CP, IP, and SAT
Start: 10/18/2012 1:30 pm
End: 10/18/2012 3:00 pm
Dr. Neng-Fa Zhou
Department of Computer and Information Science
CUNY Brooklyn College& Graduate Center
In this talk, I'll introduce several features of B-Prolog for solving combinatorial search problems including tabling, Constraint Programming (CP), Integer Programming (IP), and SAT. The idea of tabling in logic programming is to memorize answers to calls and use the answers to resolve subsequent variant calls. This resembles the Dynamic Programming (DP) idea of reusing answers of overlapping sub-problems and, naturally, tabling is amenable to DP solutions. CP, IP, and SAT are three different techniques for solving constraint satisfaction and optimization problems: CP uses constraint propagation to prune search spaces and heuristics to guide search; IP relies on LP relaxation and branch-and-cut to find optimal integer solutions; SAT solvers perform unit propagation, conflict-driven clause learning, and back-jumping to prune search spaces. B-Prolog efficiently supports tabling and CP at its core; it also offers an SAT compiler for constraints and an interface to LP/MIP solvers such as CPLEX. These tools and the language constructs such as loops and list comprehensions have made B-Prolog a powerful system for describing and solving combinatorial search problems.
About the Speaker: Neng-Fa Zhou is Professor of Computer Science at the City University of New York (Brooklyn College& Graduate Center). He has been an active researcher in programming language systems for twenty years. He has authored over thirty papers on programming languages, constraint-solving, graphics, and machine learning systems published in journals (ACM TOPLAS, Journal of Logic Programming, Theory and Practice of Logic Programming, Journal of Functional and Logic Programming, and Software Practice and Experience) and major conferences. His papers on compilation of logic programs, constraint solving, and tabling have received a number of citations. He is the principal designer and implementor of the B-Prolog system, a fast CLP system that has a large number of users in both academia and industry. He has reviewed articles for all major journals and conferences in his area of research and has served on the program committees of many important conferences. He has participated in several solver competitions, including CSP, ASP, Minizinc Challenge, and Prolog Programming Contest, and has won several prizes.
Dr. Zhou received a B.S. degree in Computer Science from Nanjing University, China, in 1984 and M.S. and Ph.D. degrees in Computer Science and Engineering from Kyushu University, Japan, in 1988 and 1991, respectively. Before joining CUNY, he was with Kyushu Institute of Technology from 1991–1999. He had visiting positions at Yale University (1997), University of Alberta (1998), Tokyo Institute of Technology (2002), and Monash University/University of Melbourne (2005).
Department Conference Room