toronto

First International Workshop on

Quantification in Constraint Programming

Held in conjunction with

11th International Conference on
Principles and Practice of Constraint Programming, CP-2005

October 1, 2005
Sitges (Barcelona), Spain


 

Overview

Dealing with uncertainty in combinatorial problems is a significant challenge for constraint programming and related areas, such as SAT. An important way of modelling uncertainty is through the use of quantified variables. In a standard CSP all variables can be considered to be existentially quantified. Introducing universally quantified variables extends the standard definition making it possible to model PSPACE-complete problems from areas such as contingency planning, model checking, control design, and game playing. In recent years there has been a significant body of work on extending the traditional CSP and SAT paradigms to handle quantification. The main advances have been achieved in the areas of quantified Boolean formulae (QBF) and quantified CSPs with continuous domains. There is also an increasing interest in complexity/tractability results concerning CSPs with quantified variables. Very recently, quantified CSPs with discrete finite domains have also started to attract attention. In addition, other frameworks for expressing quantification have been proposed in the last few years, with different features and leading to different results. For example, stochastic and uncertain CSPs have been proposed to model and solve real-world problems with uncertainty. So far, research has progressed in these areas somewhat independently of one another. The aim of this workshop is to bring together researchers interested in all aspects of quantification in constraint programming and related areas, and in that way achieve cross-fertilization.

 Back to top ]

Scope

This workshop can be of interest to researchers working in all aspects of quantification in constraint programming and related areas such as SAT. The workshop's aim is to present a forum for researchers interested in quantification, and coming from diverse backgrounds (e.g. constraint satisfaction, SAT, logic, linear programming), to present results, exchange ideas and discuss future directions. Topics of interest include (but are not limited to):

 

  • complexity results
  • problem modelling
  • search and propagation algorithms
  • combining/integrating different frameworks and algorithms
  • benchmark generation and evaluation methodology
  • real-world applications of quantified constraints

 Back to top ]

Submissions

The workshop is open to all members of the CP community. Submitted papers can be up to 15 pages in length, describing work on one or more of the topics relevant to the workshop. Alternatively, a shorter paper (maximum 5 pages) can be submitted, presenting a research statement or perspective on topics relevant to the workshop. All submissions will be reviewed and those that present a significant contribution to the workshop topics will be accepted for publication in the workshop proceedings. The proceedings will be available electronically at the workshop web page and in hardcopy at CP 2005. If necessary for time reasons, only a subset of the papers will be presented. A selection will then be made by the Organizing Committee.

 

We encourage authors to submit papers electronically in postscript or pdf format. Papers should be formatted using the Lecture Notes in Computer Science (LNCS) style. All submissions should include the author's name(s), affiliation, complete mailing address, and email address. Workshop papers will be published in workshop notes as well as on the Web.


Please send your submissions by email to konsterg@aegean.gr using the subject line QCP-2005 Workshop Submission.

Back to top ]

Important Dates

The schedule of important dates for the workshop is as follows:

                                                                                        Paper Submission deadline:         July 4th   EXTENDED DEADLINE!

                                                                                        Notification of acceptance:          July 28th

                                                                                        Deadline for early registration:     August 1st

                                                                                        Camera-ready version deadline:  August 15th

                                                                                        Workshop Date:                         October 1st

 

Accepted Papers

The Achilles' Heel of QBF   Carlos Ansotegui, Carla P. Gomes, Bart Selman

 

Boolean and Interval Propagation for Quantified Constraints   Lucas Bordeaux

 

Exploiting Quantifiers Structure in QBF Reasoning   Enrico Giunchiglia, Massimo Narizzano, Armando Tacchella

 

Modal Intervals Revisited: A Mean-Value Extension for Generalized Intervals   Alexandre Goldsztejn, David Daney,    Michel  Rueher, Patrick Taillibert

 

Constraint Programming with Unrestricted Quantification   David Mitchell, Eugenia Ternovska

 

Consistency for Quantified Constraint Satisfaction Problems   Peter Nightingale

 

Mapping Conformant Planning into SAT through Compilation and Projection   Hector Palacios, Hector Geffner

 

Finding models for quantified Boolean formulae   Igor Stephan

 

Closures of Uncertain Constraint Satisfaction Problems   Neil Yorke-Smith, Carmen Gervet

 

Registration

At least one author of each paper accepted for presentation must attend the workshop. It is possible to register for the workshop only,

i.e. it is *not* necessary to pay the CP/ICLP main conference fee to attend the workshop. Hence, participants must pay the workshop fee, which provides admission to all CP/ICLP workshops.

 

 

Provisional Programme

 

Saturday, October 1st

14:30 14:35

Welcome

Session 1 – Chair: Enrico Giunchiglia

14:35 – 15:00

Boolean and Interval Propagation for Quantified Constraints
Lucas Bordeaux

15:00 15:25

Modal Intervals Revisited: A Mean-Value Extension for Generalized Intervals Alexandre Goldsztejn, David Daney, Michel Rueher, Patrick Taillibert

15:25 – 15:50

Finding models for quantified Boolean formulae
Igor Stephan

15:50 – 16:15

Closures of Uncertain Constraint Satisfaction Problems
Neil Yorke-Smith, Carmen Gervet

16:15 – 16:45

Coffee break

Session 2 – Chair: Ian Gent

16:45 – 17:00

The Achilles' Heel of QBF
Carlos Ansotegui, Carla P. Gomes, Bart Selman

17:00 – 17:15

Exploiting Quantifiers Structure in QBF Reasoning

Enrico Giunchiglia, Massimo Narizzano, Armando Tacchella

17:15 – 17:30

Constraint Programming with Unrestricted Quantification
David Mitchell, Eugenia Ternovska

17:30 – 17:45

Consistency for Quantified Constraint Satisfaction Problems
Peter Nightingale

17:45 – 18:00

Mapping Conformant Planning into SAT through Compilation and Projection Hector Palacios, Hector Geffner

18:00 – 18:30

Discussion

 

Organisation

Organising Committee

Ian  Gent

School of Computer Science

University of St Andrews, UK

Email: ipg@dcs.st-and.ac.uk

Web: http://www.dcs.st-and.ac.uk/~ipg

 

Enrico Giunchiglia

DIST (Dipartimento di Informatica, Sistemistica e Telematica)

Universita di Genova, Italy

Email: giunchiglia@unige.it

Web: http://www.star.dist.unige.it/~enrico/

 

Kostas Stergiou

Department of Information and Communication Systems Engineering

University of the Aegean, Greece

Email: konsterg@aegean.gr

Web: http://www.samos.aegean.gr/icsd/konsterg/

Programme Committee

Frederic Benhamou (Universite de Nantes, France)

Armin Biere (Johannes Kepler University, Austria)

Lucas Bordeaux (Microsoft Cambridge Research Centre, UK)

Hubie Chen (Universitat Pompeu Fabra, Spain)
Ian  Gent (
University of St Andrews, UK)

Enrico Giunchiglia (Universita di Genova, Italy)

Eric Monfroy (Universite de Nantes, France)

Stefan Ratschan (Max-Planck Institut für Informatik, Germany)

Bart Selman (Cornell University, USA)

Joao Marques Silva (Instituto de Engenharia de Sistemas e Computadores, Portugal)      

Neil Yorke-Smith (SRI International, USA)

Kostas Stergiou (University of the Aegean, Greece)
Toby Walsh (University of New South Wales,
Australia)

 

 Back to top ]