Constraint Satisfaction Problems (CSP) is a field of artificial intelligence (AI) that helps solve real-life problems by specifying (or modeling) the legal solution structure, rather than implementing algorithms that solve these problems. IBM’s CSP solving system declares the solution model using a propriety modeling language (first-order-logic rules) over diverse types of variables. In this talk, I introduce the field of CSP and present different applications that use this technique. I will briefly explain the internal algorithm and some heuristics that deal with this NP-Complete problem, showing some basic building blocks of the modeling language. Following this background, I cover some interesting directions in CSPs such as solving optimization problems with constraints, how to get a random solution or many solutions for the same problem, solving problems that have unbounded vectors of CSPs classes, scaling up CSPs to create a big database, and how to reduce solving time with parallel computing.
Erez Bilgory, Eyal Bin, and Avi Ziv, “Solving Constraint Satisfaction Problems Containing Vectors of Unknown Size”, in Proc. CP 2017 Principles and Practice of Constraint Programming 23rd International Conference, CP 2017 Melbourne, VIC, Australia, August 28 – September 1, 2017
Eyal Bin is a research staff member at the IBM Research lab in Haifa, leading the CSP activity for security and privacy. He joined IBM in 1991 and for the past 18 years has been focused on the research and development of CSPs. Over the years, he initiated, defined, and implemented the CSP modeling language and the corresponding engine
algorithms that are being used today in several IBM products. Eyal earned his BSc and MSc degrees in Electrical Engineering (Computers engineering) from the Technion – Israel Institute of Technology. He has authored numerous patents and publications around CSPs and it continues to remain his favorite type of problem.