What can we do in CP but not in SAT or ILP?

Venerdi' 16 Dicembre 2011 - Toby Walsh


Venerdi' 16 Dicembre 2011, alle ore 14:00 in aula 2AB45, il Prof. Toby Walsh (NICTA and University of New South Wales) terra' un seminario dal titolo "What can we do in CP but not in SAT or ILP?".

The talk explores the connections between Integer Linear Programming (ILP), propositional satisfiability (SAT) and Constraint Programming (CP). The focus of the talk is on global constraints like AllDifferent. These are one of the key distinguishing features of constraint programming. I describe recent work on simulating the actions of global constraints with simple decompositions that can be implemented using SAT clauses or ILP models. Based on powerful lower bounds from circuit complexity, I argue that there are, however, some things that cannot be effectively simulated in ILP or SAT. The conclusion is that not everything can be done in SAT or ILP and we do in fact need some of the powerful algorithmic techniques provided by CP.

-Brief bio
Prof. Walsh is one of the top scientists in the areas of Artificial Intelligence and Constraint Programming. He has been program chair of IJCAI (the main international conference for Artificial Intelligence) in 2011, and has published more than 300 papers in major international journals and conferences.

Rif. int. F. Rossi