IBM Research

LSCS 2006 Workshop


Call for Papers and Participation

Third International Workshop on Local Search Techniques in Constraint Satisfaction in conjunction with CP 2006

Overview and Scope

LSCS is an annual workshop devoted to local search techniques in constraint satisfaction. This workshop focuses on all aspects of local search techniques, including: design and implementation of new algorithms, hybrid stochastic-systematic search, winning heuristics, modeling for local-search, global constraints, flexibility and robustness, learning methods, and specific applications. The workshop will provide an informal environment for discussions about recent results in these and related areas. It is open to all members of the CP community.

Papers are solicited from the above areas or from any other area related to local search in constraint satisfaction. In addition to contributed papers, we will have one invited lecture and will also provide opportunities for short presentations of post-deadline important results.


Authors should prepare their full papers in the CP format, by following the Springer instructions. The maximum is 15 pages. Extended abstracts of post-deadline important results should be no longer than two pages, including figures and references.

Papers and abstracts submitted to the workshop will be reviewed by at least two members of the program committee. 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. All workshop participants must pay the workshop's fees.

Submissions should be made electronically, by sending papers or post-deadline abstracts in PDF format to: Yehuda Naveh (

Each submission should identify one contact author, and provide the email address and phone number of this author. Contact authors should expect an acknowledgment of receipt within two business days of submission.

Important Dates

Deadline for paper submissions June 25, 2006
Notifications to authors July 20, 2006
Camera-ready copy July 30, 2006
Post-deadline abstract submissions September 03, 2006
Post-deadline notifications September 11, 2006
LSCS'06 workshop September 25, 2006

Invited Speaker

Pascal van Hentenryck (Brown University, USA)
Title: Growing Comet


Program PDF version for printing (33 KB)

09:00-09:10 Workshop Opening,
Yehuda Naveh and Andrea Roli
09:10-09:35 Combining Adaptive Noise and Look-Ahead in Local Search for SAT,
Chu Min Li, Wanxia Wei and Harry Zhang
09:35-10:00 Modelling Clique Problems for SAT Local Search,
Steven Prestwich
10:00-10:25 An Empirical Study of Multi-Point Constructive Search for Constraint Satisfaction,
Ivan Heckman and J. Christopher Beck
10:25-11:00 Coffee Break
11:00-11:50 Invited talk: Growing Comet,
Pascal Van Hentenryck
11:50-12:15 Boosting SLS Performance by Incorporating Resolution-based Preprocessor,
Anbulagan, Duc Nghia Pham, John Slaney and Abdul Sattar
12:15-12:30 Post deadline abstract: Generic Incremental Algorithms for Local Search,
Magnus °Agren, Pierre Flener and Justin Pearson
12:30-12:35 Workshop Closing


The proceedings will include accepted full papers. They will be distributed on-site to the workshop participants, and will also be available on-line (after the workshop) on this web page.
Post-deadline abstracts will only appear in the on-line version.

Previous LSCSs

Organizing Committee

Program Committee

  • Chris Beck, U Toronto, Canada
  • Luca di Gaspero, Universita di Udine, Italy
  • Yehuda Naveh, IBM Research, Israel
  • Justin Pearson, Uppsala U, Sweden
  • Steve Prestwich, 4C, Ireland
  • Andrea Roli, U G. D'Annunzio, Italy
  • Meinolf Sellmann, Brown U, USA
  • Andrea Schaerf, Universita di Udine, Italy
  • Bart Selman, Cornell, USA
  • Thomas Stuetzle, TU Darmstadt, Germany
  • Pascal Van Hentenryck, Brown U, USA
  • Toby Walsh, NICTA & UNSW, Australia