Principles and Practice of Constraint Programming - CP 2012 : 18th International Conference, CP 2012, Québec City, QC, Canada, October 8-12, 2012, Proceedings

This book constitutes the thoroughly refereed post-conference proceedings of the 18th International Conference on Principles and Practice of Constraint Programming (CP 2012), held in Québec, Canada, in October 2012. The 68 revised full papers were carefully selected from 186 submissions. Beside the technical program, the conference featured two special tracks. The former was the traditional application track, which focused on industrial and academic uses of constraint technology and its comparison and integration with other optimization techniques (MIP, local search, SAT, etc.) The second track, featured for the first time in 2012, concentrated on multidisciplinary papers: cross-cutting methodology and challenging applications collecting papers that link CP technology with other techniques like machine learning, data mining, game theory, simulation, knowledge compilation, visualization, control theory, and robotics. In addition, the track focused on challenging application fields with a high social impact such as CP for life sciences, sustainability, energy efficiency, web, social sciences, finance, and verification. Front Matter....Pages - Constraint Programming and a Usability Quest....Pages 1-1 Optimization Challenges in Smart Grid Operations....Pages 2-3 Where Are the Interesting Problems?....Pages 4-5 A Generic Method for Identifying and Exploiting Dominance Relations....Pages 6-22 Scheduling Scientific Experiments on the Rosetta/Philae Mission....Pages 23-37 Max-Sur-CSP on Two Elements....Pages 38-54 An Optimal Arc Consistency Algorithm for a Chain of Atmost Constraints with Cardinality....Pages 55-69 Conflict Directed Lazy Decomposition....Pages 70-85 Improving SAT-Based Weighted MaxSAT Solvers....Pages 86-101 Distributed Tree Decomposition with Privacy....Pages 102-117 Refining Restarts Strategies for SAT and UNSAT....Pages 118-126 Boosting Local Consistency Algorithms over Floating-Point Numbers....Pages 127-140 A Model Seeker: Extracting Global Constraint Models from Positive Examples....Pages 141-157 On Computing Minimal Equivalent Subformulas....Pages 158-174 Including Soft Global Constraints in DCOPs....Pages 175-190 The Weighted Average Constraint....Pages 191-206 Weibull-Based Benchmarks for Bin Packing....Pages 207-222 Space-Time Tradeoffs for the Regular Constraint....Pages 223-237 Inter-instance Nogood Learning in Constraint Programming....Pages 238-247 Solving Temporal Problems Using SMT: Strong Controllability....Pages 248-264 A Characterisation of the Complexity of Forbidding Subproblems in Binary Max-CSP....Pages 265-273 Optimisation Modelling for Software Developers....Pages 274-289 Adaptive Bisection of Numerical CSPs....Pages 290-298 Resource Constrained Shortest Paths with a Super Additive Objective Function....Pages 299-315 Relating Proof Complexity Measures and Practical Hardness of SAT....Pages 316-331 The S eq B in Constraint Revisited....Pages 332-347 Eigenvector Centrality in Industrial SAT Instances....Pages 348-356 Classifying and Propagating Parity Constraints....Pages 357-372 Consistencies for Ultra-Weak Solutions in Minimax Weighted CSPs Using the Duality Principle....Pages 373-389 Propagating Soft Table Constraints....Pages 390-405 WCSP Integration of Soft Neighborhood Substitutability....Pages 406-421 Increasing Symmetry Breaking by Preserving Target Symmetries....Pages 422-438 A Scalable Sweep Algorithm for the cumulative Constraint....Pages 439-454 A New Encoding from MinSAT into MaxSAT....Pages 455-463 Solving Minimal Constraint Networks in Qualitative Spatial and Temporal Reasoning....Pages 464-479 Containment, Equivalence and Coreness from CSP to QCSP and Beyond....Pages 480-495 An Optimal Filtering Algorithm for Table Constraints....Pages 496-511 Parallel SAT Solver Selection and Scheduling....Pages 512-526 Constraint Satisfaction over Bit-Vectors....Pages 527-543 Towards Solver-Independent Propagators....Pages 544-560 Interactive Algorithm for Multi-Objective Constraint Optimization....Pages 561-576 Focus : A Constraint for Concentrating High Costs....Pages 577-592 Refining Abstract Interpretation Based Value Analysis with Constraint Programming Techniques....Pages 593-607 Time-Dependent Simple Temporal Networks....Pages 608-623 Improved Bounded Max-Sum for Distributed Constraint Optimization....Pages 624-632 A Hybrid MIP/CP Approach for Multi-activity Shift Scheduling....Pages 633-646 Contributions to the Theory of Practical Quantified Boolean Formula Solving....Pages 647-663 Breaking Variable Symmetry in Almost Injective Problems....Pages 664-671 Understanding, Improving and Parallelizing MUS Finding Using Model Rotation....Pages 672-687 Revisiting Neighborhood Inverse Consistency on Binary CSPs....Pages 688-703 Syntactically Characterizing Local-to-Global Consistency in ORD-Horn....Pages 704-719 A Hybrid Paradigm for Adaptive Parallel Search....Pages 720-734 A Constraint Programming Approach for the Traveling Purchaser Problem....Pages 735-749 Constraint-Based Register Allocation and Instruction Scheduling....Pages 750-766 Maximising the Net Present Value of Large Resource-Constrained Projects....Pages 767-781 Comparing Solution Methods for the Machine Reassignment Problem....Pages 782-797 A Boolean Model for Enumerating Minimal Siphons and Traps in Petri Nets....Pages 798-814 Cardinality Reasoning for Bin-Packing Constraint: Application to a Tank Allocation Problem....Pages 815-822 The Offshore Resources Scheduling Problem: Detailing a Constraint Programming Approach....Pages 823-839 Computational Protein Design as a Cost Function Network Optimization Problem....Pages 840-849 A Filtering Technique for Fragment Assembly- Based Proteins Loop Modeling with Constraints....Pages 850-866 A Branch and Prune Algorithm for the Computation of Generalized Aspects of Parallel Robots....Pages 867-882 The Semigroups of Order 10....Pages 883-899 Exploring Chemistry Using SMT....Pages 900-915 A Pseudo-Boolean Set Covering Machine....Pages 916-924 Finding a Nash Equilibrium by Asynchronous Backtracking....Pages 925-940 Reasoning over Biological Networks Using Maximum Satisfiability....Pages 941-956 Properties of Energy-Price Forecasts for Scheduling....Pages 957-972 Aggregating Conditionally Lexicographic Preferences on Multi-issue Domains....Pages 973-987 Constraint Programming for Path Planning with Uncertainty....Pages 988-1003 Feature Term Subsumption Using Constraint Programming with Basic Variable Symmetry....Pages 1004-1012 Back Matter....Pages -