LSCS 2008 Workshop


Call for Papers and Participation

Fifth International Workshop on Local Search Techniques in Constraint Satisfaction
in conjunction with CP 2008

Sydney, Australia
September 15, 2008
Collocated with ModRef'08

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.

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 LNCS/LNAI 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.

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 July 14, 2008
Notifications to authors August 14, 2008
Camera-ready copy August 21, 2008
Post-deadline abstract submissions August 24, 2008
Post-deadline notifications August 31, 2008
LSCS'08 workshop September 15, 2008

Invited Speaker

Meinolf Sellmann, Brown University, USA
Topic: Learning and Local Search
Note: Some pictures in the presentation were taken from the cited papers.


09:00 - 10:00 Invited talk: The Connection of Local Search and Learning (LSCS'08),
Meinolf Sellmann, Brown University, USA
10:00 - 10:30 Coffee Break
10:30 - 11:00 The Many Roads Leading to Rome: Solving Zinc Models by Various Solvers (ModRef'08),
Ralph Becket, Sebastian Brand, Mark Brown, Gregory J. Duck, Thibaut Feydy, Julien Fischer, Jinbo Huang, Kim Marriott, Nicholas Nethercote, Jakob Puchinger, Reza Rafeh, Peter J. Stuckey, and Mark G. Wallace
11:00 - 11:30 Automatically Detecting Neighbourhood Constraint Interactions using Comet (LSCS'08),
Alastair Andrew and John Levine (U. Strathclyde, UK)
11:30 - 12:00 Constructive vs Perturbative Local Search for General Integer Linear Programming (LSCS'08),
Stefania Verachi and Steven Prestwich (Cork University College, Ireland)
12:00 - 12:30 A Versatile Intermediate Language for Answer Set Programming (NMR'08),
Martin Gebser, Tomi Janhunen, Max Ostrowski, Torsten Schaub, and Sven Thiele
12:30 - 13:30 Lunch
13:30 - 14:00 Efficient Propagation of Disjunctive Constraints using Watched Literals (ModRef'08),
Christopher Jefferson and Karen E. Petrie
11:00 - 11:30 Generalizing Backdoors (LSCS'08),
Roberto Rossi, Steven Prestwich, S. Armagan Tarim, and Brahim Hnich (Cork University College, Ireland, Hacettepe U., Turkey, Izmir U., Turkey)
14:30 - 15:00 Kakuro as a Constraint Problem (ModRef'08),
Helmut Simonis
15:00 - 15:30 Closing & Refreshments


Only on-line version of CP Workshop proceedings are available this year. For the LSCS proceedings, follow the links to papers in the 'program' section above.

Previous LSCSs

Organizing Committee

Program Committee

  • Magnus Agren, SICS, Sweden
  • Chris Beck, U Toronto, Canada
  • Bella Dubrov, IBM Research, Israel
  • Pierre Flener, Uppsala U, Sweden
  • Laurent Michel, U Connecticut, USA
  • Yehuda Naveh, IBM Research, Israel
  • Justin Pearson, Uppsala U, Sweden
  • Steve Prestwich, 4C, Ireland
  • Andrea Roli, U Bologna, Italy
  • Andrea Schaerf, U Udine, Italy
  • Meinolf Sellmann, Brown U, USA
  • Bart Selman, Cornell U, USA
  • Thomas Stuetzle, U Libre de Bruxelles, Belgium
  • Pascal Van Hentenryck, Brown U, USA