IBM Research

LSCS 2007 Workshop


Call for Papers and Participation

Fourth International Workshop on Local Search Techniques in Constraint Satisfaction
in conjunction with CP 2007

Providence, RI, USA
September 23, 2007

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 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 27, 2007
Notifications to authors July 23, 2007
Camera-ready copy August 7, 2007
Post-deadline abstract submissions August 24, 2007
Post-deadline notifications September 07, 2007
LSCS'07 workshop September 23, 2007

Invited Speaker

Bart Selman, Cornell University
Title: High Dimensional Search Spaces: New Insights into Local Search for SAT


14:00-14:30 Switching Criterion for Intensification and Diversification in Local Search for SAT,
Wanxia Wei, Chu Min Li, and Harry Zhang (UNB, Canada and U. Picardie, France)
14:30-15:00 Constraint Directed Variable Neighbourhood Search,
Alastair Andrew, John Levine, and Derek Long (U. Strathclyde, UK)
15:00-15:30 Revisiting Constraint-Directed Search,
Magnus Ågren, Pierre Flener, and Justin Pearson (Uppsala, Sweden and Sabanci U, Turkey)
15:30-16:00 Break
16:00-17:00 Invited talk - High Dimensional Search Spaces: New Insights into Local Search for SAT,
Bart Selman (Cornell, USA)
17:00-17:30 The Promise of Polynomial-based Local Search to Boost Boolean MAX-CSP Solvers,
Christine D. Hang, Ahmed Abdelmeged, Daniel Rinehart, Karl J. Lieberherr (NEU, USA)


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, University of Toronto, Canada
  • Luca Di Gaspero, University of Udine, Italy
  • Pierre Flener, Sabanci University, Turkey, and Uppsala University, Sweden
  • William Havens, Simon Fraser University, Canada
  • Yehuda Naveh, IBM Research, Israel
  • Justin Pearson, Uppsala University, Sweden
  • Steve Prestwich, 4C, Ireland
  • Andrea Roli, University of Bologna, Italy
  • Andrea Schaerf, University of Udine, Italy
  • Meinolf Sellmann, Brown University, USA
  • Bart Selman, Cornell University, USA
  • Thomas Stuetzle, University of Libre de Bruxelles, Belgium
  • Pascal Van Hentenryck, Brown University, USA
  • Toby Walsh, NICTA & UNSW, Australia