Principles and Practice of Constraint Programming: 14th International Conference, CP 2008, Sydney, Australia, September 14-18, 2008, Proceedings (Lecture Notes in Computer Science, 5202)

This book constitutes the refereed proceedings of the 14th International Conference on Principles and Practice of Constraint Programming, CP 2008, Sydney, Australia, September, 2008. The 27 revised full papers and 23 revised short papers presented together with 6 application papers and the abstracts of one invited lecture were carefully reviewed and selected from 120 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 - Back to the Complexity of Universal Programs....Pages 1-20 A Constraint Programming Approach for Allocation and Scheduling on the CELL Broadband Engine....Pages 21-35 Planning and Scheduling the Operation of a Very Large Oil Pipeline Network....Pages 36-51 Search Strategies for Rectangle Packing....Pages 52-66 Solving a Telecommunications Feature Subscription Configuration Problem....Pages 67-81 Protein Structure Prediction with Large Neighborhood Constraint Programming Search....Pages 82-96 An Application of Constraint Programming to Superblock Instruction Scheduling....Pages 97-111 Classes of Submodular Constraints Expressible by Graph Cuts....Pages 112-127 Optimization of Simple Tabular Reduction for Table Constraints....Pages 128-143 Universal Booleanization of Constraint Models....Pages 144-158 Flow-Based Propagators for the SEQUENCE and Related Global Constraints....Pages 159-174 Guiding Search in QCSP + with Back-Propagation....Pages 175-189 A New Framework for Sharp and Efficient Resolution of NCSP with Manifolds of Solutions....Pages 190-204 A Branch and Bound Algorithm for Numerical MAX-CSP....Pages 205-219 A Geometric Constraint over k -Dimensional Objects and Shapes Subject to Business Rules....Pages 220-234 Cost-Based Domain Filtering for Stochastic Constraint Programming....Pages 235-250 Dichotomic Search Protocols for Constrained Optimization....Pages 251-265 Length-Lex Bounds Consistency for Knapsack Constraints....Pages 266-281 A Framework for Hybrid Tractability Results in Boolean Weighted Constraint Satisfaction Problems....Pages 282-297 From High Girth Graphs to Hard Instances....Pages 298-312 Switching among Non-Weighting, Clause Weighting, and Variable Weighting in Local Search for SAT....Pages 313-326 CPBPV: A Constraint-Programming Framework for Bounded Program Verification....Pages 327-341 Exploiting Common Subexpressions in Numerical CSPs....Pages 342-357 A Soft Constraint of Equality: Complexity and Approximability....Pages 358-371 Structural Tractability of Propagated Constraints....Pages 372-386 Connecting ABT with Arc Consistency....Pages 387-401 Elicitation Strategies for Fuzzy Constraint Problems with Missing Preferences: Algorithms and Experimental Studies....Pages 402-417 Reformulating Positive Table Constraints Using Functional Dependencies....Pages 418-432 Relaxations for Compiled Over-Constrained Problems....Pages 433-447 Approximate Compilation of Constraints into Multivalued Decision Diagrams....Pages 448-462 Quantified Constraint Optimization....Pages 463-477 Exploiting Decomposition in Constraint Optimization Problems....Pages 478-492 A Coinduction Rule for Entailment of Recursively Defined Properties....Pages 493-508 Maintaining Generalized Arc Consistency on Ad Hoc r -Ary Constraints....Pages 509-523 Perfect Constraints Are Tractable....Pages 524-528 Efficiently Solving Problems Where the Solutions Form a Group....Pages 529-533 Approximate Solution Sampling (and Counting) on AND/OR Spaces....Pages 534-538 Model Restarts for Structural Symmetry Breaking....Pages 539-544 An Elimination Algorithm for Functional Constraints....Pages 545-549 Crossword Puzzles as a Constraint Problem....Pages 550-554 Recent Hybrid Techniques for the Multi-Knapsack Problem....Pages 555-559 Edge Matching Puzzles as Hard SAT/CSP Benchmarks....Pages 560-565 Test Strategy Generation Using Quantified CSPs....Pages 566-570 Perfect Derived Propagators....Pages 571-575 Refined Bounds for Instance-Based Search Complexity of Counting and Other #P Problems....Pages 576-581 Transforming Inconsistent Subformulas in MaxSAT Lower Bound Computation....Pages 582-587 Semi-automatic Generation of CHR Solvers for Global Constraints....Pages 588-592 Stochastic Local Search for the Optimal Winner Determination Problem in Combinatorial Auctions....Pages 593-597 Revisiting the Upper Bounding Process in a Safe Branch and Bound Algorithm....Pages 598-602 Computing All Optimal Solutions in Satisfiability Problems with Preferences....Pages 603-607 On the Efficiency of Impact Based Heuristics....Pages 608-612 Probabilistically Estimating Backbones and Variable Bias: Experimental Overview....Pages 613-617 A New Empirical Study of Weak Backdoors....Pages 618-623 Adding Search to Zinc....Pages 624-629 Experimenting with Small Changes in Conflict-Driven Clause Learning Algorithms....Pages 630-634 Search Space Reduction for Constraint Optimization Problems....Pages 635-639 Engineering Stochastic Local Search for the Low Autocorrelation Binary Sequence Problem....Pages 640-645 Back Matter....Pages - This Volume Contains The Proceedings Of The 14th International Conference On Principles And Practice Of Constraint Programming (cp 2008) Held In Sydney, Australia, September 14–18, 2008. The Conference Was Held In Conjunction With The International Conference On Automated Planning And Scheduling (icaps 2008) And The International Conference On Knowledge Representation And R- Soning (kr 2008). Information About The Conference Can Be Found At The W- Sitehttp://www. Unimelb. Edu. Au/cp2008/. Held Annually, The Cp Conference Series Is The Premier International Conference On Constraint Programming. The Conference Focuses On All Aspects Of Computing With Constraints. The Cp Conf- Ence Series Is Organized By The Association For Constraint Programming (acp). Information About The Conferences In The Series Can Be Found On The Web At Http://www. Cs. Ualberta. Ca/~ai/cp/. Information About Acp Can Be Found Athttp://www. A4cp. Org/. Cp 2008 Included Two Calls For Contributions: A Call For Research Papers, - Scribing Novel Contributions In The ?eld, And A Call For Application Papers, - Scribing Applications Of Constraint Technology. For The ?rst Time Authors Could Directly Submit Short Papers For Consideration By The Committee. The Research Track Received 84 Long Submissions And 21 Short Submissions And The Application Track Received 15 Long Submissions. Each Paper Received At Least Three Reviews, Which The Authors Had The Opportunity To See And To React To, Before The Papers And Their Reviews Were Discussed Extensively By The Members Of The Program Committee.