§16§This volume contains the papers presented at CP 2009: The 15th International Conference on Principles and Practice of Constraint Programming. It was held from September 20-24, 2009 at the Rectory of the New University of Lisbon, Portugal. Everyone involved with the conference thanks our sponsors for their support. There were 128 submissions to the research track, of which 53 were accepted for a rate of 41.4%. Each submission was reviewed by three reviewers, with a small number of additional reviews obtained in exceptional cases. Each review waseitherbyaProgrammeCommitteemember,orbyacolleagueinvitedtohelp by a committee member thanks to their particular expertise. Papers submitted as long papers were accepted at full length or not at all. It is important to note that papers submitted as short papers were held to the same high standards of qualityas long papers. There is thus no distinction in these proceedings between long and short papers, except of course the number of pages they §16§ occupy. As it happens, the acceptancerates of short and long papers wereverysimilar indeed. Therewere13submissionstotheapplicationtrack,ofwhich8wereaccepted, fora rateof61.5%.Papersunderwentthe samereviewprocessasregularpapers, and there was not a separate committee for reviewing application track papers. However, papers in the application track were not required to be original or novel research, but to be original and novel as an application of constraints. §04§: An Alternative to Double Lex.- Closing the Open Shop: Contradicting Conventional Wisdom.- Reasoning about Optimal Collections of Solutions.- Constraints of Difference and Equality: A Complete Taxonomic Characterisation.- Synthesizing Filtering Algorithms for Global Chance-Constraints.- An Interpolation Method for CLP Traversal.- Same-Relation Constraints.- Dialectic Search.- Restricted Global Grammar Constraints.- Conflict Resolution.- Propagator Groups.- Efficient Generic Search Heuristics within the EMBP Framework.- Failed Value Consistencies for Constraint Satisfaction.- A Precedence Constraint Posting Approach for the RCPSP with Time Lags and Variable Durations.- SOGgy Constraints: Soft Open Global Constraints.- Exploiting Problem Decomposition in Multi-objective Constraint Optimization.- Search Space Extraction.- Coalition Structure Generation Utilizing Compact Characteristic Function Representations.- Compiling All Possible Conflicts of a CSP.- On the Power of Clause-Learn §04§ing SAT Solvers with Restarts.- Slice Encoding for Constraint-Based Planning.- Evolving Parameterised Policies for Stochastic Constraint Programming.- Maintaining State in Propagation Solvers.- Cost-Driven Interactive CSP with Constraint Relaxation.- Weakly Monotonic Propagators.- Constraint-Based Optimal Testing Using DNNF Graphs.- Why Cumulative Decomposition Is Not as Bad as It Sounds.- On Decomposing Knapsack Constraints for Length-Lex Bounds Consistency.- Realtime Online Solving of Quantified CSPs.- Constraint-Based Local Search for the Automatic Generation of Architectural Tests.- Edge Finding Filtering Algorithm for Discrete Cumulative Resources in .- Evaluation of Length-Lex Set Variables.- The Complexity of Valued Constraint Models.
