The 19th International Conference on
Principles and Practice of
Constraint Programming
Uppsala, Sweden
September 16-20, 2013

CSPSAT'13: Third International Workshop on the Cross-Fertilization Between CSP and SAT

Overview and Scope

Constraint Satisfaction Problems (CSPs) and Boolean Satisfiability Problems (SAT) have much in common. However, they also differ in many important aspects, resulting 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 this gap and encouraging cross-fertilization between the two communities, in terms of problems, ideas, techniques, and results.

This year's workshop is the third in the series, following successful occasions in SAT'11 and SAT'12. Starting at 2013, we plan to alternate this workshop between the CP and SAT conferences.

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., satisfiability modulo theories, pseudo-Boolean) and their relations to both CSP and SAT.
  • Applications: ways to determine which framework works best for which application.
  • Additional related topics.

Submissions

Authors should prepare their papers in the LNCS/LNAI format, following Springer's instructions. Submissions can be of one of the following types:

  • Full papers, maximum of 15 pages excluding references.
  • Short papers, maximum of 5 pages excluding references.

Authors should indicate whether the submitted work has been published or accepted for publication elsewhere. Priority will be given to original full papers and to important work recently presented in other venues. Each submission should identify one contact author, and provide the email address and phone number of this author. Papers and abstracts should be submitted via EasyChair: 

CSPSAT 2013 Submission at EasyChair

All submissions 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 work and the available time for presentations. At least one author of each accepted submission must attend the workshop. Original papers will be published on the workshop website following the workshop.

Important Dates

  • Deadline for abstract submissions: June 24, 2013
  • Deadline for paper submissions: July 1, 2013
  • Notifications to authors: July 25, 2013
  • Camera-ready copy submission: August 31, 2013
  • CSPSAT workshop: September 16, 2013

Tutorial

Steve Prestwich, 4C, U. College Cork, Ireland
Topic: Using CP to generate SAT files

Accepted Papers

Christian Artigues, Emmanuel Hebrard, Valentin Mayer-Eichberger, Mohamed Siala, and Toby Walsh,
SAT and Hybrid models of the Car-Sequencing problem

Gilles Pesant,
On the Relationship Between Strong Backdoors and Instance Difficulty in Unsatisfiable Structured CSPs

Ian Gent,
Optimal Implementation of Watched Literals and More General Techniques

Program

15:05 - 15:30     Christian Artigues, Emmanuel Hebrard, Valentin Mayer-Eichberger, Mohamed Siala, and Toby Walsh,
                        SAT and Hybrid models of the Car-Sequencing problem
15:30 - 16:00     coffee break
16:00 - 16:55     Tutorial: Steve Prestwich, Using CP to generate SAT files
16:55 - 17:10     break
17:10 - 17:35     Gilles Pesant,
                        On the Relationship Between Strong Backdoors and Instance Difficulty in Unsatisfiable Structured CSPs
17:35 - 18:00     Ian Gent,
                        Optimal Implementation of Watched Literals and More General Techniques

Organizers

Yael Ben-Haim, IBM Research
+972-4-829-6263
yaelbh@il.ibm.com

Yehuda Naveh, IBM Research
+972-4-829-6381
naveh@il.ibm.com

Program Committee

Fahiem Bacchus, U. Toronto, Canada
Yael Ben-Haim, IBM Research, Israel
Nadia Creignou, LIF, France
Alan Frisch, U. York, UK
Enrico Giunchiglia, U. Genova, Italy
Ian Miguel, U. St. Andrews, UK
Yehuda Naveh, IBM Research, Israel
Steve Prestwich, 4C, U. College Cork, Ireland
Meinolf Sellmann, IBM Research, USA
Bart Selman, Cornell University, USA
Ofer Strichman, Technion, Israel
Toby Walsh, NICTA, Australia