This book constitutes the refereed proceedings of the 17th International Conference on Principles and Practice of Constraint Programming, CP 2011, held in Perugia, Italy, September 12-16, 2011.
The 51 revised full papers and 7 short papers presented together with three invited talks were carefully reviewed and selected from 159 submissions. The papers are organized in topical sections on algorithms, environments, languages, models and systems, applications such as decision making, resource allocation and agreement technologies.
Author(s): Leonardo de Moura (auth.), Jimmy Lee (eds.)
Series: Lecture Notes in Computer Science 6876
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2011
Language: English
Pages: 836
Tags: Algorithm Analysis and Problem Complexity; Mathematical Logic and Formal Languages; Logics and Meanings of Programs; Artificial Intelligence (incl. Robotics); Programming Languages, Compilers, Interpreters; Computation by Abstract Device
Front Matter....Pages -
Orchestrating Satisfiability Engines....Pages 1-1
Operations Research and Constraint Programming at Google....Pages 2-2
Solving Problems with CP: Four Common Pitfalls to Avoid....Pages 3-11
A Constraint Seeker: Finding and Ranking Global Constraints from Examples....Pages 12-26
Bin Repacking Scheduling in Virtualized Datacenters....Pages 27-41
Route Finder: Efficiently Finding k Shortest Paths Using Constraint Programming....Pages 42-53
The Design of Cryptographic S-Boxes Using CSPs....Pages 54-68
Optimal Carpet Cutting....Pages 69-84
A Hybrid Approach for Solving Real-World Nurse Rostering Problems....Pages 85-99
Constraint Programming for Controller Synthesis....Pages 100-114
Neuron Constraints to Model Complex Real-World Problems....Pages 115-129
A Constraint Based Approach to Cyclic RCPSP....Pages 130-144
An Efficient Light Solver for Querying the Semantic Web....Pages 145-159
On Guaranteeing Polynomially Bounded Search Tree Size....Pages 160-171
A Framework for Decision-Based Consistencies....Pages 172-186
Hierarchically Nested Convex VCSP....Pages 187-194
Tractable Triangles....Pages 195-209
On Minimal Weighted Clones....Pages 210-224
Solving MAXSAT by Solving a Sequence of Simpler SAT Instances....Pages 225-239
Filtering Algorithms for Discrete Cumulative Problems with Overloads of Resource....Pages 240-255
Synthesis of Search Algorithms from High-Level CP Models....Pages 256-270
Revisiting the tree Constraint....Pages 271-285
Half Reification and Flattening....Pages 286-301
The Parameterized Complexity of Local Consistency....Pages 302-316
Symmetry Breaking in Numeric Constraint Problems....Pages 317-324
On Minimal Constraint Networks....Pages 325-339
Structural Tractability of Constraint Optimization....Pages 340-355
Models and Strategies for Variants of the Job Shop Scheduling Problem....Pages 356-372
MaxRPC Algorithms Based on Bitwise Operations....Pages 373-384
Grid-Based SAT Solving with Iterative Partitioning and Clause Learning....Pages 385-399
Large Neighborhood Search for Dial-a-Ride Problems....Pages 400-413
On Deciding MUS Membership with QBF....Pages 414-428
On the Relative Efficiency of DPLL and OBDDs with Axiom and Join....Pages 429-437
Min CSP on Four Elements: Moving beyond Submodularity....Pages 438-453
Algorithm Selection and Scheduling....Pages 454-469
Incorporating Variance in Impact-Based Search....Pages 470-477
A Quadratic Edge-Finding Filtering Algorithm for Cumulative Resource Constraints....Pages 478-492
A CSP Solver Focusing on fac Variables....Pages 493-507
Constraint Reasoning and Kernel Clustering for Pattern Decomposition with Scaling....Pages 508-522
Solving Qualitative Constraints Involving Landmarks....Pages 523-537
Searching for Doubly Self-orthogonal Latin Squares....Pages 538-545
QCSP on Partially Reflexive Forests....Pages 546-560
The Computational Complexity of Disconnected Cut and 2 K 2 -Partition....Pages 561-575
Reducing the Search Space of Resource Constrained DCOPs....Pages 576-590
Proving Symmetries by Model Transformation....Pages 591-605
Value Ordering for Finding All Solutions: Interactions with Adaptive Variable Ordering....Pages 606-620
Boolean Equi-propagation for Optimized SAT Encoding....Pages 621-636
CP Models for Maximum Common Subgraph Problems....Pages 637-644
Kangaroo: An Efficient Constraint-Based Local Search System Using Lazy Propagation....Pages 645-659
Pseudo-Tree-Based Incomplete Algorithm for Distributed Constraint Optimization with Quality Bounds....Pages 660-674
A More Efficient BDD-Based QBF Solver....Pages 675-690
Constraint Propagation for Efficient Inference in Markov Logic....Pages 691-705
Octagonal Domains for Continuous Constraints....Pages 706-720
A Θ(n) Bound-Consistency Algorithm for the Increasing Sum Constraint....Pages 721-728
Automatic Generation of Constraints for Partial Symmetry Breaking....Pages 729-743
Beyond QCSP for Solving Control Problems....Pages 744-758
On Mini-Buckets and the Min-fill Elimination Ordering....Pages 759-773
Search Combinators....Pages 774-788
Variable Independence and Resolution Paths for Quantified Boolean Formulas....Pages 789-803
Pruning Rules for Constrained Optimisation for Conditional Preferences....Pages 804-818
Checking and Filtering Global Set Constraints....Pages 819-833
Back Matter....Pages -
