Dear All


Solving Combinatorial Search Problems Using DP, CP, IP, and SAT

Start: 10/18/2012 1:30 pm
End: 10/18/2012 3:00 pm
Departmental Colloquium
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 19911999. 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


best regards,