Principles and Practice of Constraint Programming - CP 2006

This book constitutes the refereed proceedings of the 12th International Conference on Principles and Practice of Constraint Programming, CP 2006, held in Nantes, France in September 2006.

The 42 revised full papers and 21 revised short papers presented together with extended abstracts of four invited talks were carefully reviewed and selected from 142 submissions. All current issues of computing with constraints are addressed.

Inhalt

Invited Papers.- Global Optimization of Probabilistically Constrained Linear Programs.- Algorithms and Constraint Programming.- Interval Analysis and Robotics.- Constraint Based Resilience Analysis.- Regular Papers.- Infinite Qualitative Simulations by Means of Constraint Programming.- Algorithms for Stochastic CSPs.- Graph Properties Based Filtering.- The ROOTS Constraint.- CoJava: Optimization Modeling by Nondeterministic Simulation.- An Algebraic Characterisation of Complexity for Valued Constraint.- Typed Guarded Decompositions for Constraint Satisfaction.- Propagation in CSP and SAT.- The Minimum Spanning Tree Constraint.- Impact of Censored Sampling on the Performance of Restart Strategies.- Watched Literals for Constraint Propagation in Minion.- Inner and Outer Approximations of Existentially Quantified Equality Constraints.- Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms.- Adaptive Clause Weight Redistribution.- Localization of an Underwater Robot Using Interval Constraint Propagation.- Approximability of Integer Programming with Generalised Constraints.- When Constraint Programming and Local Search Solve the Scheduling Problem of Electricité de France Nuclear Power Plant Outages.- Generalized Arc Consistency for Positive Table Constraints.- Stochastic Allocation and Scheduling for Conditional Task Graphs in MPSoCs.- Boosting Open CSPs.- Compiling Constraint Networks into AND/OR Multi-valued Decision Diagrams (AOMDDs).- Distributed Constraint-Based Local Search.- High-Level Nondeterministic Abstractions in C++.- A Structural Characterization of Temporal Dynamic Controllability.- When Interval Analysis Helps Inter-block Backtracking.- Randomization in Constraint Programming for Airline Planning.- Towards an Efficient SAT Encoding for Temporal Reasoning.- Decomposition of Multi-operator Queries on Semiring-Based Graphical Models.- Dynamic Lex Constraints.- Generalizing AllDifferent: The SomeDifferent Constraint.- Mini-bucket Elimination with Bucket Propagation.- Constraint Satisfaction with Bounded Treewidth Revisited.- Preprocessing QBF.- The Theory of Grammar Constraints.- Constraint Programming Models for Graceful Graphs.- A Simple Distribution-Free Approach to the Max k-Armed Bandit Problem.- Generating Propagators for Finite Set Constraints.- Compiling Finite Linear CSP into SAT.- Differentiable Invariants.- Revisiting the Sequence Constraint.- BlockSolve: A Bottom-Up Approach for Solving Quantified CSPs.- General Symmetry Breaking Constraints.- Poster Papers.- Inferring Variable Conflicts for Local Search.- Reasoning by Dominance in Not-Equals Binary Constraint Networks.- Distributed Stable Matching Problems with Ties and Incomplete Lists.- Soft Arc Consistency Applied to Optimal Planning.- A Note on Low Autocorrelation Binary Sequences.- Relaxations and Explanations for Quantified Constraint Satisfaction Problems.- Static and Dynamic Structural Symmetry Breaking.- The Modelling Language Zinc.- A Filter for the Circuit Constraint.- A New Algorithm for Sampling CSP Solutions Uniformly at Random.- Sports League Scheduling: Enumerative Search for Prob026 from CSPLib.- Dynamic Symmetry Breaking Restarted.- The Effect of Constraint Representation on Structural Tractability.- Failure Analysis in Backtrack Search for Constraint Satisfaction.- Heavy-Tailed Runtime Distributions: Heuristics, Models and Optimal Refutations.- An Extension of Complexity Bounds and Dynamic Heuristics for Tree-Decompositions of CSP.- Clique Inference Process for Solving Max-CSP.- Global Grammar Constraints.- Constraint Propagation for Domain Bounding in Distributed Task Scheduling.- Interactive Distributed Configuration.- Retroactive Ordering for Dynamic Backtracking.