International Workshop on Constraint Solving
under Change and Uncertainty

A CP2005 workshop
Sitges, Spain
October 1st, 2005

[Description] [Invited talk] [Submission] [Attendance] [Dates] [Organisers] [Committee]

NEW: Proceedings

NEW: Provisional Schedule

NEW: Invited talk

Description of the workshop

Solving constraint satisfaction or optimization problems under change and uncertainty is a significant issue for many practical applications, including planning, scheduling, resource allocation, and design. Solutions must be produced despite uncertain data. New solutions must be produced because of changes in the problem. In contrast, most constraint solving methods and tools have been developed under the assumption of certain and static problems. This workshop is aimed at answering questions about the ways in which constraint technology should evolve to take into account the fact that problems are often uncertain and dynamic.

To focus the workshop on answering these questions, we request short position papers (between 2 and 5 pages) which discuss the challenges in reasoning about change and uncertainty, or present opinions about the directions along which this technology should evolve to take account of change and uncertainty, or present difficulties encountered when trying to apply constraint technology to problems that involve uncertainty and change.

Some examples of questions and issues we would like position papers to address are given below:
  • why are you interested in combining constraints, change, and uncertainty?
  • outline description of application problems you have in mind
  • main features of the problems in terms of constraints, change, and uncertainty
  • main requirements in terms of system answer
  • first approaches in terms of modelling and solving
  • main strengths and weaknesses of these approaches
  • wish list for new approaches, new modelling frameworks, and new solving algorithms
  • arguments for and against modifying solving algorithms versus modifying problem modelling to take into account changes and uncertainties
  • arguments for and against producing solutions and modifying them in case of changes versus looking for robust, contingent, or flexible solutions
  • arguments for and against exact uncertainty calculus versus scenario sampling
  • descriptions of alternative approaches, not necessarily based on constraint modelling e.g. stochastic programming, Markov decision problems, Bayesian networks, influence diagrams etc.
  • relationship of constraint solving under change and uncertainty with other sub-fields of constraint solving - e.g. soft constraints, distributed constraints, interactive solving etc.
  • proposals for real-world benchmarks
  • proposals for artificial problem generators
Because we do not want to limit this debate to the constraint solving community (mainly SAT and CSP people), we strongly encourage participation from researchers coming from other communities, including Operations Research, Integer linear programming, Stochastic programming, Uncertainty in artificial intelligence, Markov decision processes, Influence diagrams, Uncertainty in planning and scheduling, Resource and time-bounded reasoning ...

With a new shape, this workshop continues the series of CP workshops on online solving under change and uncertainty, in particular the Online-2003 CP2003 workshop and the Changes'04 CP2004 workshop.

We hope to accept all submissions that describe a coherent position with respect to the topic of the workshop. From the position papers, we will invite a small number of speakers to give a full-length talk, based on the contribution to the topic, and on the extent to which it should stimulate discussion. We also expect to invite one or two other talks from related areas. All accepted submissions will appear in the working notes of the workshop.

Invited Talk

The workshop will feature an invited talk by Rina Dechter:

On Mixed Probabilistic and Deterministic Graphical Models

The talk will address algorithms for reasoning over knowledge-bases that can express both uncertain information and hard constraints. The need to accommodate both types of information is motivated by real-life applications, especially those involving planning and decision-making. Specifically, I will focus on the "mixed network", a new framework which integrates probabilistic networks and constraint networks.

Submission guidelines

Final papers for the workshop notes will be limited to 5 pages in the Springer Verlag LNCS style (font size 10). We recommend submissions should be in the proper format to save time. Please email all submissions as either postscript, MS Word 6.0, or pdf to Ken Brown ( by the submission deadline. Each submission should have a title page with the name, address, and email address for each author. One of the authors should be identified as the contact author.

Attendance Details

At least one author of each accepted submission must attend the workshop. All workshop attendees must pay the CP workshop participation fee, which provides entry to all CP and ICLP workshops. Attendance at CP2005 or ICLP 2005 is not necessary.

Important Dates

Submission: Monday 4th July
Notification: Friday 29th July (date brought forward)
CP early registration deadline: Monday 1st August
Final versions: Friday 26th August
Workshop: Saturday 1st October

Workshop Organisers

Ken Brown, 4C, Ireland, k.brown @ Primary contact
Gérard Verfaillie, ONERA, Toulouse, France, Gerard.Verfaillie @

Advisory Committee

Chris Beck, University of Toronto, Canada
Neil Yorke-Smith, SRI International, USA