1st Workshop on Constraint Reasoning and Graphical Structures

A Workshop affiliated with 16th International Conference on Principles and Practices of Constraint Programming (CP-2010)

September 6-10, 2010, St Andrews, Scotland, United Kingdom

Workshop Schedule:
14:00 - 15:00   Invited Talk by John Hooker. Multivalued Decision Diagrams and What They Can Do for You
15:00 - 15:25   Tarik Hadzic and Helmut Simonis. Reasoning about Reliability and Cost using Decision Diagrams and Syntax Trees
15:25 - 15:50   Radu Marinescu. Best-First vs. Depth-First AND/OR Search for Multi-objective Constraint Optimization
15:50 - 16:20   Tea break
16:20 - 16:45   Natalia Flerova and Rina Dechter. M best solutions over Graphical Models
16:45 - 17:10   Lars Otten and Rina Dechter. Parallelizing Branch and Bound for Graphical Models with Cost Function-based Load Balancing
17:10 - 17:35   Philippe J├ęgou and Cyril Terrioux. Structural Consistency: A New Filtering Approach for Constraint Networks
17:35 - 18:00   Francisco Azevedo and Joao Gomes-Mota. Electrical grid modelling for overhead maintenance cycle optimisation
Invited Talk:
Multivalued Decision Diagrams and What They Can Do for You

J. N. Hooker
Carnegie Mellon University

I will present a conceptual overview of multivalued decision diagrams (MDDs) and potential applications to optimization and constraint solving. After a introduction to decision diagrams and their historical use for circuit analysis, I will illustrate how MDDs can be used as a constraint store in constraint programming, a relaxation in optimization, a restriction for purposes of a feasibility heuristic, a guide to branching, and a transparent data structure for explanation and postoptimality analysis. MDDs can also efficiently represent certain constraints exactly, such as those with dynamic programming structure. I will describe a generalization to nonserial MDDs and their connection with nonserial dynamic programming, tree width, induced width, and related concepts.

Workshop Chairs
Tarik Hadzic, University College Cork, Ireland
Radu Marinescu, IBM, Ireland

Important dates
Paper Submission:     extended deadline June 27th 2010
Author Notification:   July 27th, 2010
Final Papers:             August 11th, 2010

Paper submission
Submit your paper here (EasyChair)


Program Committee
Berthe Y. Choueiry,  University of Nebraska-Lincoln, USA
Adnan Darwiche,  University of California, Los Angeles (UCLA), USA
Rina Dechter,  University of California, Irvine (UCI), USA
Helene Fargier,  IRIT, Universite Paul Sabatier, France
Tarik Hadzic,   University College Cork, Ireland
Radu Marinescu,  IBM, Ireland
Robert Mateescu,  Microsoft Research, UK
Barry O'Sullivan,  University College Cork, Ireland
Roland Yap,  National University of Singapore, Singapore
Toby Walsh,  NICTA, University of New South Wales, Australia
Nic Wilson,  University College Cork, Ireland

Overview: Graphical structures have been successfully utilized to solve a number of computationally challenging problems many of which can be expressed as constraint models. In particular, the problems related to decision support such as probabilistic reasoning or configuration have been addressed through compiling the models into computationally efficient graphical representations, such as various special kinds of NNFs, tree-automata, AND/OR graph representations and decision diagrams or by using a local computation on join trees (including variable/bucket elimination).

Furthermore, the same graphical structures are increasingly used in a classical constraint programming context: to improve the efficiency of search for a feasible solution or finding an optimal solution. This has been achieved for example by exploiting AND/OR decomposition in constraint graphs, enhancing propagation of global constraints through preprocessing into decision diagrams, or enhancing communication between constraints by expanding the constraint store. On the other side, search-based approaches (such as satisfiability solvers) are recently being used as a compilation mechanism for constructing various forms of graphical structures, sometimes significantly outperforming standard compilation methods.

Goal: The primary focus of this workshop will be on the use of graphical approaches in enabling structural properties of constraint models to be exploited for a number of tasks, such as constraint propagation, solution counting, reasoning with soft constraints and preferences, inference under uncertainty, and configuration. In addition, the workshop welcomes contributions that exploit constraint-reasoning techniques to enhance construction and manipulation of graphical structures.

Submission: The workshop is open to all members of the CP and AI communities. Submitted papers can be up to 15 pages in length describing original work on one or more of the topics relevant to the workshop. Alternatively, shorter papers (up to 8 pages) are also encouraged, presenting preliminary work, a research statement or perspective on topics relevant to the workshop. All submissions will be thoroughly reviewed and those that present a significant contribution will be accepted for publication in the workshop proceedings. According to the conference rules at least one author of each accepted submission is expected to attend the workshop, and all workshop participants are expected to pay the workshop fee. We encourage the authors to submit papers in PDF format. Papers should be formatted using the Springer Lectures in Computer Science (LNCS) style. All submissions should include the author's name, affiliation, complete mailing address, and email address. The EasyChair submission page can be found at http://www.easychair.org/conferences/?conf=crags2010