IBM Research

LSCS 2005 Workshop


Call for Papers and Participation

Second International Workshop on Local Search Techniques in Constraint Satisfaction
in conjunction with CP 2005

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, 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. This payment provides admission to all CP/ICLP workshops. Payment of the CP/ICLP main conference fees is NOT required for participation in 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 01, 2005
Notifications to authors July 27, 2005
Deadline for early registration to CP and LSCS August 01, 2005
Camera-ready copy August 05, 2005
Post-deadline abstract submissions September 09, 2005
Post-deadline notifications September 16, 2005
LSCS'05 workshop October 01, 2005

Invited Speaker

Joerg Hoffmann (Max Planck Institute, Germany)
Title: Utilizing Problem Structure in Planning: A Local Search Approach

Accepted Papers

  1. "A Simple Hybrid GRASP-Evolutionary Algorithm for CSPs",
    Manuel Cebrian and Ivan Dotu, U. Autonoma de Madrid, Spain

  2. "Multi-Point Constructive Search: Extended Remix",
    J. Christopher Beck, U. Toronto, Canada

  3. "Random Subset Optimization",
    Boi Faltings and Quang-Huy Nguyen, EPFL, Switzerland

  4. "A New Iterative Local-Search Method for Constraint Satisfaction Problems",
    N. Bouhmala, Vestfold U., Norway

  5. "A Propagation/Local Search Hybrid for Distributed Optimization",
    Adrian Petcu and Boi Faltings, EPFL, Switzerland

  6. "Extending Iterative Flattening Search",
    Angelo Oddi, Nicola Policella, Amedeo Cesta (INRC, Italy) and Stephen Smith (Carnegie Mellon U., USA)


14:30-14:40 Andrea Roli and Yehuda Naveh, Workshop Opening
14:40-15:00 Manuel Cebrian and Ivan Dotu, "A Simple Hybrid GRASP-Evolutionary Algorithm for CSPs"
15:00-15:30 J.Christopher Beck, "Multi-Point Constructive Search: Extended Remix"
15:30-15:45 Post deadline abstract: Angelo Oddi, Nicola Policella, Amedeo Cesta and Stephen Smith, "Extending iterative flattening search"
15:45-16:15 Boi Faltings and Quang-Huy Nguyen, "Random Subset Optimization"
16:15-16:45 Coffee-break
16:45-17:35 Invited talk: Joerg Hoffmann, "Utilizing Problem Structure in Planning: A Local Search Approach"
17:35-17:55 Noureddine Bouhmala, "A New Iterative Local-Search Method for Constraint Satisfaction Problems"
17:55-18:25 Adrian Petcu and Boi Faltings, "A Propagation/Local Search Hybrid for Distributed Optimization"
18:25-18:30 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

1st Workshop (2004)

Organizing Committee

Program Committee

  • Christian Blum, UPC, Spain
  • Yehuda Naveh, IBM Research, Israel
  • Justin Pearson, Uppsala U, Sweden
  • Gilles Pesant, Polytechnique Montreal, Canada
  • Steve Prestwich, 4C, Ireland
  • Andrea Roli, U G. D'Annunzio, Italy
  • Meinolf Sellmann, Brown U, USA
  • Bart Selman, Cornell, USA
  • Thomas Stuetzle, TU Darmstadt, Germany
  • Pascal Van Hentenryck, Brown U, USA
  • Toby Walsh, NICTA & UNSW, Australia