Ann Arbor

CSPSAT 2011 Workshop


Call for Papers and Participation

First International Workshop on the Cross-Fertilization Between CSP and SAT
in conjunction with SAT 2011

Ann Arbor, Michigan, USA
June 18, 2011

Overview and Scope

Constraint Satisfaction Problems (CSP's) and Boolean Satisfiability Problems (SAT) have much in common. However, they also differ in many important aspects, which result in major differences in solution techniques. More importantly, the CSP and SAT communities, while to some extent interacting with each other, are mostly separate communities with separate conferences and meetings. This workshop is designed as a venue for bridging the gap and for cross-fertilization between the two communities, in terms of ideas, problems, techniques, and results. The structure of the workshop will include free time for interaction between speakers and participants, thus allowing for further transfer of ideas between the two communities.

This workshop is designed to be the first in a series of annual workshops, alternating between the CP and SAT conferences. As the last related workshop was already five years ago (Youssef Hamadi and Lucas Bordeaux, "Integration of SAT and CP techniques", in conjunction with CP'06), time is now ripe to establish an annual workshop covering this active topic.

Topics in the scope of the workshop include:
  • Adaptation of CSP techniques to SAT problems
  • Adaptation of SAT techniques to CSP's
  • Efficient translations and encodings from one framework to the other
  • Heterogeneous CSP/SAT problems
  • Hybrid CSP/SAT solvers
  • Local search in CSP and SAT
  • Parallelization and real-time competition between CSP and SAT solvers, cross-talk between the solvers
  • Commonalities and differences in the theory of CSP and SAT solving
  • Intermediate problems (e.g., SMT, PB) and their relations to both CSP and SAT
  • Applications: ways to determine which framework works best for which application
  • Additional related topics


Authors should prepare their full papers in the LNCS/LNAI format, by following Springer instructions. The maximum is 15 pages. Title and abstract in plain text are due a week before the paper submission deadline. Each submission should identify one contact author, and provide the email address and phone number of this author. Submission of papers and abstracts is via EasyChair:

Papers submitted to the workshop will be reviewed by at least two members of the program committee or their delegates. Decisions about acceptance or rejection will be made considering both the merit of the paper and the available time for presentations. At least one author of each accepted submission must attend the workshop.

Important Dates

Abstracts due April 17, 2011
Deadline for paper submissions April 24, 2011
Notifications to authors May 8, 2011
Camera-ready copy June 5, 2011
CSPSAT Workshop June 18, 2011

Invited Speaker

"PCS: a proof-producing CSP solver",
Ofer Strichman


13:15-13:20 Opening
13:20-13:55 "General Nogood-Learning Framework for Pseudo-Boolean Multi-Valued SAT (Extended Abstract)",
Siddhartha Jain, Ashish Sabharwal, and Meinolf Sellmann
13:55-14:30 "Improving Local Search for SAT and Weighted MAX-2-SAT by Configuration Checking",
Shaowei Cai, Kaile Su, and Abdul Sattar
14:30-15:00 Coffee break
15:00-16:00 Invited talk - "PCS: a proof-producing CSP solver",
Ofer Strichman
(Abstract, Presentation)
16:00-16:30 Coffee break
16:30-17:05 "Proposal of a compact and efficient SAT encoding using a numeral system of any base",
Tomoya Tanjo, Naoyuki Tamura, and Mutsunori Banbara
17:05-17:40 "Quadratic Direct Encoding vs. Linear Order Encoding A One out of N Transformation on CNF",
Norbert Manthey and Peter Steinke

Organizing Committee

Program Committee

  • Fahiem Bacchus, U. Toronto, Canada
  • Yael Ben-Haim, IBM Research, Israel
  • Lucas Bordeaux, Microsoft Research, UK
  • Alan Frisch, U. York, UK
  • Enrico Giunchiglia, U. Genova, Italy
  • Youssef Hamadi, Microsoft Research, UK
  • Ian Miguel, U. St. Andrews, UK
  • Yehuda Naveh, IBM Research, Israel
  • Steven Prestwich, U. College Cork, Ireland
  • Meinolf Sellmann, IBM Research, USA
  • Ofer Strichman, Technion, Israel
  • Toby Walsh, NICTA, Australia