Invited Lecture -- Back to the Complexity of Universal Programs -- Applications Track Long Papers -- A Constraint Programming Approach for Allocation and Scheduling on the CELL Broadband Engine -- Planning and Scheduling the Operation of a Very Large Oil Pipeline Network -- Search Strategies for Rectangle Packing -- Solving a Telecommunications Feature Subscription Configuration Problem -- Protein Structure Prediction with Large Neighborhood Constraint Programming Search -- An Application of Constraint Programming to Superblock Instruction Scheduling -- Research Track Long Papers -- Classes of Submodular Constraints Expressible by Graph Cuts -- Optimization of Simple Tabular Reduction for Table Constraints -- Universal Booleanization of Constraint Models -- Flow-Based Propagators for the SEQUENCE and Related Global Constraints -- Guiding Search in QCSP?+? with Back-Propagation -- A New Framework for Sharp and Efficient Resolution of NCSP with Manifolds of Solutions -- A Branch and Bound Algorithm for Numerical MAX-CSP -- A Geometric Constraint over k-Dimensional Objects and Shapes Subject to Business Rules -- Cost-Based Domain Filtering for Stochastic Constraint Programming -- Dichotomic Search Protocols for Constrained Optimization -- Length-Lex Bounds Consistency for Knapsack Constraints -- A Framework for Hybrid Tractability Results in Boolean Weighted Constraint Satisfaction Problems -- From High Girth Graphs to Hard Instances -- Switching among Non-Weighting, Clause Weighting, and Variable Weighting in Local Search for SAT -- CPBPV: A Constraint-Programming Framework for Bounded Program Verification -- Exploiting Common Subexpressions in Numerical CSPs -- A Soft Constraint of Equality: Complexity and Approximability -- Structural Tractability of Propagated Constraints -- Connecting ABT with Arc Consistency -- Elicitation Strategies for Fuzzy Constraint Problems with Missing Preferences: Algorithms and Experimental Studies -- Reformulating Positive Table Constraints Using Functional Dependencies -- Relaxations for Compiled Over-Constrained Problems -- Approximate Compilation of Constraints into Multivalued Decision Diagrams -- Quantified Constraint Optimization -- Exploiting Decomposition in Constraint Optimization Problems -- A Coinduction Rule for Entailment of Recursively Defined Properties -- Maintaining Generalized Arc Consistency on Ad Hoc r-Ary Constraints -- Research Track Short Papers -- Perfect Constraints Are Tractable -- Efficiently Solving Problems Where the Solutions Form a Group -- Approximate Solution Sampling (and Counting) on AND/OR Spaces -- Model Restarts for Structural Symmetry Breaking -- An Elimination Algorithm for Functional Constraints -- Crossword Puzzles as a Constraint Problem -- Recent Hybrid Techniques for the Multi-Knapsack Problem -- Edge Matching Puzzles as Hard SAT/CSP Benchmarks -- Test Strategy Generation Using Quantified CSPs -- Perfect Derived Propagators -- Refined Bounds for Instance-Based Search Complexity of Counting and Other #P Problems -- Transforming Inconsistent Subformulas in MaxSAT Lower Bound Computation -- Semi-automatic Generation of CHR Solvers for Global Constraints -- Stochastic Local Search for the Optimal Winner Determination Problem in Combinatorial Auctions -- Revisiting the Upper Bounding Process in a Safe Branch and Bound Algorithm -- Computing All Optimal Solutions in Satisfiability Problems with Preferences -- On the Efficiency of Impact Based Heuristics -- Probabilistically Estimating Backbones and Variable Bias: Experimental Overview -- A New Empirical Study of Weak Backdoors -- Adding Search to Zinc -- Experimenting with Small Changes in Conflict-Driven Clause Learning Algorithms -- Search Space Reduction for Constraint Optimization Problems -- Engineering Stochastic Local Search for the Low Autocorrelation Binary Sequence Problem.