International Workshop on Reformulating Constraint Satisfaction Problems: Towards Systematisation and Automation

Call for Participation

International Workshop on
Reformulating Constraint Satisfaction Problems

Towards Systematisation and Automation

To be held at the
8th International Conference on Principles and Practice of Constraint Programming (CP 2002)
Cornell University, Ithaca, NY, USA
8 September 2002

Many companies have scheduling, assignment, supply chain and other problems that could be solved with a constraint programming toolkit. Although the solution of these problems is of vital commercial importance, constraint programming toolkits are not widely used because there is insufficient expertise available to model problems as constraint programs.

This formulation bottleneck can be reduced by the development of systems that can take a problem specification from a non-expert and automatically reformulate it into a form that can be solved efficiently. The facilities and capabilities of such a system might include

a high-level language for specifying constraint satisfaction problems,
a compiler to translate high level specifications to executable models,
a module system that facilitates the modelling of large-scale and complex CSPs and reformulation methods that can exploit models constructed in this manner,
the construction of a more abstract formulation whose solution can aid in solving the original problem,
the generation of implied constraints,
the detection and breaking symmetry,
the removal of redundant constraints,
the transformation of constraints,
the translation into Boolean satisfiability, and
the execution of large-scale changes of representation such as changing the choice of variables.

Researchers in the field of constraint programming have written numerous papers showing how particular complex problems can be formulated as a constraint program. We now have sufficient examples from which to abstract generalisations that ultimately can be systematised and embedded in automated reformulation systems. This ``International Workshop on Reformulating Constraint Satisfaction Problems: Towards Systematisation and Automation'' has been convened to provide a forum for researchers who share the goal of making such a reformulation system a reality.

The Workshop

This will be held on the afternoon of 8 September 2002 and is open to anyone interested in the topic. The event will have a strong workshop flavour, with ample time allocated to discussion. All workshop participants must pay the CP-2002 workshop registration fee. The tentative timetable for the workshop is

13:30 Invited Talk
- Reformulation: A Practical View
  Helmut Simonis
- Discussion: 10 minutes
14:20
- Matrix Modelling: Exploiting Common Patterns in Constraint Programming
  Pierre Flener, Alan M. Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel and Toby Walsh
- Towards Model Reformulation at Multiple Levels of Abstraction
  Alan M. Frisch, Brahim Hnich, Ian Miguel, Barbara M. Smith and Toby Walsh
- Discussion: 7 minutes
15:00 Coffee
15:30
- On the Pruning Behaviour of Minimal Combined Models for Permutation CSPs
  C.W. Choi and J.H.M. Lee
- Algebraic Properties of CSP Model Operators
  Y.C. Law and J.H.M. Lee
- Discussion: 7 minutes
16:10
- Capturing Constraint Programming Experience: A Case-Based Approach
  James Little, Cormac Gebruers, Derek Bridge and Eugene Freuder
- Discussion: 5 minutes
16:35
- Automatically Converting SAT Encodings of CSPs
  Lyndon Drake, Ian Gent and Toby Walsh
- Discussion: 5 minutes
17:00 Workshop ends

Proceedings

The proceedings are available electronically. Hard copies will be distributed at the workshop to all participants.

Programme Committee

Alan M. Frisch (Chair), University of York, United Kingdom. (frisch@cs.york.ac.uk)
Marco Cadoli, Universita` di Roma "La Sapienza", Italy. (cadoli@dis.uniroma1.it)
Tom Ellman, Vassar College, USA. (ellman@cs.vassar.edu)
Pierre Flener, Uppsala University, Sweden. (pierref@csd.uu.se)
Eugene Freuder, University College Cork, Ireland. (e.freuder@4c.ucc.ie)
Jimmy Lee, The Chinese University of Hong Kong, Hong Kong SAR, China. (jlee@cse.cuhk.edu.hk)
Ian Miguel, University of York, United Kingdom. (ianm@cs.york.ac.uk)
Patrick Prosser, Glasgow University, United Kingdom. (pat@dcs.gla.ac.uk)
Toby Walsh, University College Cork, Ireland. (tw@4c.ucc.ie)