Principles and practice of constraint programming, CP 2009 : 15th international conference, CP 2009 Lisbon, Portugal, September 20-24, 2009 : proceedings

Annotation This book constitutes the refereed proceedings of the 15th International Conference on Principles and Practice of Constraint Programming, CP 2009, held in Lisbon, Portugal in September 2009. The 61 revised full papers presented together with the abstracts of three invited talks were carefully reviewed and selected from 141 submissions. All current issues of computing with constraints are addressed, ranging from methodological and foundational aspects - using algorithms, environments, languages, models and systems - to solving real-world problems in various application fields Front Matter....Pages - Constraint-Based Schedulers, Do They Really Work?....Pages 1-1 Challenges for Constraint Reasoning and Optimization in Computational Sustainability....Pages 2-4 Observations on Symmetry Breaking....Pages 5-5 Generating Optimal Stowage Plans for Container Vessel Bays....Pages 6-20 Real-Time Tabu Search for Video Tracking Association....Pages 21-34 Pin Assignment Using Stochastic Local Search Constraint Programming....Pages 35-49 Modelling Equidistant Frequency Permutation Arrays: An Application of Constraints to Mathematics....Pages 50-64 Scheduling the CB1000 Nanoproteomic Analysis System with Python, Tailor, and Minion....Pages 65-72 Solving Nurse Rostering Problems Using Soft Global Constraints....Pages 73-87 Online Selection of Quorum Systems for RAMBO Reconfiguration....Pages 88-103 A Hybrid Constraint Model for the Routing and Wavelength Assignment Problem....Pages 104-118 Memoisation for Constraint-Based Local Search....Pages 119-126 On the Structure of Industrial SAT Instances....Pages 127-141 A Gender-Based Genetic Algorithm for the Automatic Configuration of Algorithms....Pages 142-157 Filtering Numerical CSPs Using Well-Constrained Subsystems....Pages 158-172 Minimising Decision Tree Size as Combinatorial Optimisation....Pages 173-187 Hull Consistency under Monotonicity....Pages 188-195 A Constraint on the Number of Distinct Vectors with Application to Localization....Pages 196-210 Approximating Weighted Max-SAT Problems by Compensating for Relaxations....Pages 211-225 Confidence-Based Work Stealing in Parallel Constraint Programming....Pages 226-241 Minimizing the Maximum Number of Open Stacks by Customer Search....Pages 242-257 Using Relaxations in Maximum Density Still Life....Pages 258-273 Constraint-Based Graph Matching....Pages 274-288 Constraint Representations and Structural Tractability....Pages 289-303 Asynchronous Inter-Level Forward-Checking for DisCSPs....Pages 304-318 From Model-Checking to Temporal Logic Constraint Solving....Pages 319-334 Exploiting Problem Structure for Solution Counting....Pages 335-343 Solving a Location-Allocation Problem with Logic-Based Benders’ Decomposition....Pages 344-351 Lazy Clause Generation Reengineered....Pages 352-366 The Proper Treatment of Undefinedness in Constraint Languages....Pages 367-382 Search Spaces for Min-Perturbation Repair....Pages 383-390 Snake Lex: An Alternative to Double Lex....Pages 391-399 Closing the Open Shop: Contradicting Conventional Wisdom....Pages 400-408 Reasoning about Optimal Collections of Solutions....Pages 409-423 Constraints of Difference and Equality: A Complete Taxonomic Characterisation....Pages 424-438 Synthesizing Filtering Algorithms for Global Chance-Constraints....Pages 439-453 An Interpolation Method for CLP Traversal....Pages 454-469 Same-Relation Constraints....Pages 470-485 Dialectic Search....Pages 486-500 Restricted Global Grammar Constraints....Pages 501-508 Conflict Resolution....Pages 509-523 Propagator Groups....Pages 524-538 Efficient Generic Search Heuristics within the EMBP Framework....Pages 539-553 Failed Value Consistencies for Constraint Satisfaction....Pages 554-568 A Precedence Constraint Posting Approach for the RCPSP with Time Lags and Variable Durations....Pages 569-583 SOGgy Constraints: Soft Open Global Constraints....Pages 584-591 Exploiting Problem Decomposition in Multi-objective Constraint Optimization....Pages 592-607 Search Space Extraction....Pages 608-622 Coalition Structure Generation Utilizing Compact Characteristic Function Representations....Pages 623-638 Compiling All Possible Conflicts of a CSP....Pages 639-653 On the Power of Clause-Learning SAT Solvers with Restarts....Pages 654-668 Slice Encoding for Constraint-Based Planning....Pages 669-683 Evolving Parameterised Policies for Stochastic Constraint Programming....Pages 684-691 Maintaining State in Propagation Solvers....Pages 692-706 Cost-Driven Interactive CSP with Constraint Relaxation....Pages 707-722 Weakly Monotonic Propagators....Pages 723-730 Constraint-Based Optimal Testing Using DNNF Graphs....Pages 731-745 Why Cumulative Decomposition Is Not as Bad as It Sounds....Pages 746-761 On Decomposing Knapsack Constraints for Length-Lex Bounds Consistency....Pages 762-770 Realtime Online Solving of Quantified CSPs....Pages 771-786 Constraint-Based Local Search for the Automatic Generation of Architectural Tests....Pages 787-801 Edge Finding Filtering Algorithm for Discrete Cumulative Resources in ${\mathcal O}(kn {\rm log} n)$ ....Pages 802-816 Evaluation of Length-Lex Set Variables....Pages 817-832 The Complexity of Valued Constraint Models....Pages 833-841 Back Matter....Pages - 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 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.