Principles and Practice of Constraint Programming -- CP 2011

Name: Principles and Practice of Constraint Programming -- CP 2011 | 17th International Conference, CP 2011, Perugia, Italy, September 12-16, 2011, Proceedings
Brand: Springer
Price: 106.99 EUR
Availability: OnlineOnly

17th International Conference, CP 2011, Perugia, Italy, September 12-16, 2011, Proceedings

Jimmy Lee(Herausgeber*in)

Springer (Verlag)

Erschienen am 1. September 2011

XXIV, 836 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-23786-7 (ISBN)

106,99 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Title
Preface
Conference Organization
Table of Contents
Invited Talks
Orchestrating Satisfiability Engines
Operations Research and Constraint Programming at Google
Solving Problems with CP: Four Common Pitfalls to Avoid
Introduction
Undivided Model
Rigid Search
Biased Benchmarking
Wrong Abstraction
Conclusion
References
Application Track Papers
A Constraint Seeker: Finding and Ranking Global Constraints from Examples
Motivation
Related Work
Integer Sequences
Constraint Taxonomy
Library Seeker
Electronic Symbol Catalog
Constraint Acquisition
User Experience
Seeker Matches
Generating Candidates
Ranking
Rank Computation Solver
Density Solver
Instance Generation
Constraint Solving Inside the Seeker
Evaluation
Summary and Future Work
References
Bin Repacking Scheduling in Virtualized Datacenters
Introduction
Core Problem Statement
The Repacking and Scheduling Problem
The Scheduling Subproblem
An Automated VM Manager Relying on CP
Side Placement Constraints
Constraint Programming for VM Management
Elements of Solution
Modeling the Core Problem
Modeling the Side Constraints
Solving the VRSP
Evaluation
Related Works
Conclusion
References
Route Finder: Efficiently Finding k Shortest Paths Using Constraint Programming
Problem Description
Business Rules
Why CP?
Related Work
CP Model
Development
General Framework
Decision Variables
Constraints for Path
Business Rules
The Search
Added Value of CP
References
The Design of Cryptographic S-Boxes Using CSPs
The Cipher Design Problem
Examples of SP Networks
The Security Requirements of S-Boxes
Rationale of the CSP Approach to S-Box Design
The CSP Approach
Notations
Variables and Domains for an nm S-Box
The Nonlinearity Constraint S-2
Constraints for Criteria S-4 to S-6
The Global Constraint S-7
The Advantages of the CSP Approach
Conclusion
References
Optimal Carpet Cutting
Introduction
The Carpet Cutting Problem
Static Model
Dealing with Orientations
Stair Carpets
The Model
Dynamic Model
Refining the Models
Search
Experiments
Conclusion
References
A Hybrid Approach for Solving Real-World Nurse Rostering Problems
Introduction
Background
Related Work
Problem Description
Solution Method
Initial Solution Construction
Variable Neighborhood Descent
Neighborhood Reduction
Diversification
Computational Experiments
Test Cases
Experimental Results
Conclusions and Future Work
References
Constraint Programming for Controller Synthesis
The Controller Synthesis Problem
An Informal View
A Formal Definition
A Toy Example
Existing Methods
Formulation as a Constraint Satisfaction Problem
First Formulation
Reachability and Weak Reachability
Second Formulation
Correctness, Completeness, and Optimality
OPL Model
A Real-World Example
Strengths and Weaknesses of the Proposed Approach
References
Research Track Papers
Neuron Constraints to Model Complex Real-World Problems
Introduction
Neural Networks: Background and Definitions
Neuron Constraints
Filtering for Neuron Constraints
A Use Case: Thermal Aware Workload Allocation
Context and Motivation
The Target Problem
Simulation Framework
Workload Allocation as an Optimization Problem
Modeling the Thermal Behavior via a Neural Network
Combinatorial Model and Solution Process
Solution Process
Experimental Results
Conclusions
References
A Constraint Based Approach to Cyclic RCPSP
Introduction
The Problem
Constraint-Based Approach
Model
Constraint Propagation
Search
Experimental Results
Industrial Instances
Evaluating the Solution Quality on Synthetic Benchmarks
Modulo vs. Unfolding Scheduling
Buffer-Size Constraints Tests
Related Work
Conclusions
References
An Efficient Light Solver for Querying the Semantic Web
Introduction
The Semantic Web and the SPARQL Query Language
A CSP Declarative Modeling of SPARQL Queries
Basic Queries
Compound Queries
Filters
A CP Operational Modeling of SPARQL Queries
Castor: A Lightweight Solver for the Semantic Web
Database Schema
Variables and Domains Representation
Constraints and Propagators
Search
Experimental Results
Discussion
References
On Guaranteeing Polynomially Bounded Search Tree Size
Introduction
Background
Ordered Polynomial Tractability
Functional Constraint Networks
Turan Sets
Conclusion
References
A Framework for Decision-Based Consistencies
Introduction
Technical Background
Decision-Based Consistencies
Decisions
Two Classes of First-Order Consistencies
Classes Related to Nogoods of Size 2
Qualitative Study
Relationships between Consistencies
Refinements
Well-Behavedness
Conclusion
References
Hierarchically Nested Convex VCSP
Preliminaries
Hierarchically Nested Convex
Algorithm
Complexity
Renamable Boolean Hierarchically Nested Convex VCSP
Maximality of Hierarchically Nested Convex
Conclusions
References
Tractable Triangles
Introduction
Background
Contributions
Preliminaries
CSP
Max-CSP
VCSP
Conclusions
References
On Minimal Weighted Clones
Introduction
Preliminaries
VCSP
Weighted Relational Clones
Weighted Clones
Weighted Rosenberg
Simple Weighted Clones
Boolean Classification
Conclusions
References
Solving MAXSAT by Solving a Sequence of Simpler SAT Instances
Introduction
Background
Solving Maxsat with Simpler SAT Instances
Realizable Hitting Sets
Implementation Techniques
Related Work
Empirical Results
Conclusion
References
Filtering Algorithms for Discrete Cumulative Problems with Overloads of Resource
Introduction
Definitions and Notations
Practical Problems
Filtering Algorithms
Background
Filtering from Maximum Costs
Lower Bounds of Costs and Objective
Integrating Objective Lower Bounds
Filtering from Minimum Costs
Search Strategies and Experiments
Conclusion
References
Synthesis of Search Algorithms from High-Level CP Models
Introduction
Related Work
The Synthesis Process
Preliminaries
Rules and Recommendations
Rules Library
Symmetry Breaking
Obtaining and Composing Recommendations
A Walk-Through Example
Experimental Results
Conclusion
References
Revisiting the tree Constraint
Introduction
Graph Theory Definitions
The tree Constraint: A Survey
A Basic Decomposition
The DomReachability Constraint
The Original tree Constraint
Linear Time Algorithm for the tree Constraint
Feasibility and Filtering Conditions
Filtering Algorithm
Implementation Details
Experimental Study
Conclusion
References
Half Reification and Flattening
Introduction
Propagation Based Constraint Solving
A Language of Constraints
Flattening with Full Reification
Half Reification
Experiments
Related Work and Conclusion
References
The Parameterized Complexity of Local Consistency
Introduction
Preliminaries
Constraint Networks and Local Consistency Problems
Parameterized Complexity
Tries, Turing Machines, and Gaifman Graphs
k-Consistency Parameterized by k
k-Consistency Parameterized by k+d
k-Consistency Parameterized by k+d+
Conclusion
References
Symmetry Breaking in Numeric Constraint Problems
Introduction
Symmetry-Breaking Constraints for NCSPs
rlex vs lex
Experimental Results
Conclusion and Future Prospects
References
On Minimal Constraint Networks
Introduction
Preliminaries and Basic Definitions
NP Hardness of Computing Minimal Network Solutions
The Symmetry Lemma
Intractability of Computing Solutions
The Case of Bounded Domains
Minimal Network Recognition and Structure Identification
Minimal Network Recognition
Structure Identification and k-Representability
Discussion and Future Research
References
Structural Tractability of Constraint Optimization
Introduction
Contribution
Preliminaries
Formal Framework
Arbitrary Evaluation Functions
Monotone Evaluation Functions
Smooth Evaluation Functions
Beyond Acyclicity and the Tractability Frontier
References
Models and Strategies for Variants of the Job Shop Scheduling Problem
Introduction
Background and Previous Work
Boolean Model
Search Strategy
Job Shop with Earliness/Tardiness Objective
Job Shop Scheduling Problem with Time Lags
Model
Greedy Initialization
Special Case: Job Shop with No-Wait problems
Experimental Evaluation
Job Shop with Earliness/Tardiness Objective
Job Shop Scheduling Problem with positive Time Lags
Job Shop Scheduling Problem with no wait constraints
Conclusions
References
MaxRPC Algorithms Based on Bitwise Operations
Introduction
Background
Exploiting Bitwise Operations to Enforce maxRPC
A New Method of Searching for PC-Witnesses
(l)maxRPC$^bit$, (l)maxRPC$^bit+rm$
Experiments
Conclusions
References
Grid-Based SAT Solving with Iterative Partitioning and Clause Learning
Introduction
Related Work
Preliminaries
Iterative Partitioning with Clause Learning
Partition Trees
Adding Clause Learning
Partitioning Functions
Learned Clause Tagging CDCL Solvers
Assumption-Based Learned Clause Tagging
Flag-Based Learned Clause Tagging
The Main Experimental Results
Comparing the Grid-Based Approaches
Comparison to Parallel SAT Solvers
Conclusions
References
Large Neighborhood Search for Dial-a-Ride Problems
Introduction
Formulation
A Constraint Programming Approach
A Tabu Search Approach
A Variable Neighborhood Approach
The LNS-FFPA Algorithm
Numerical Results
Conclusions and Future Work
References
On Deciding MUS Membership with QBF
Introduction
Preliminaries
Minimal Unsatisfiability and Maximal Satisfiability
Propositional Circumscription
Related Work
Deciding MUS-membership
MUS-membership with QBF
QBF for MUS-membership Using MSS-membership
MUS-membership with Circ-Infer
Algorithms for MUS-membership
Experimental Results
Benchmarks
Results
Conclusions
References
On the Relative Efficiency of DPLL and OBDDs with Axiom and Join
Introduction
Preliminaries
DPLL Does Not Polynomially Simulate OBDD$_aj$
OBDD$_aj$ Does Not Polynomially Simulate DPLL
OBDD$_aj$ Does Not Benefit from the Extension Rule
DPLL and the Extension Rule
Separating DPLL from OBDD$_aj$
Conclusions
References
Min CSP on Four Elements: Moving beyond Submodularity
Introduction
Preliminaries
Weighted pp-Definitions and Expressive Power
Multimorphisms and Submodularity
A New Tractable Class
Endomorphisms, Cores and Constants
A Graph of Partial Multimorphisms
Classification for |D| = 4
Discussion
References
Algorithm Selection and Scheduling
Introduction
Nearest-Neighbor-Based Algorithm Selection
Improving Nearest-Neighbor-Based Solver Selection
Experimental Setup and Evaluation
Building Solver Schedules
Static Schedules
A Column Generation Approach
Dynamic Schedules
Semi-static Solver Schedules
Fixed-Split Selection Schedules
Summary and Discussion
References
Incorporating Variance in Impact-Based Search
Introduction
Impact-Based Search
Impact Variance
Variance
Computing a Variance-Estimate
Numerical Results
Quasigroup Completion
Magic Square
Costas Array
Conclusion
References
A Quadratic Edge-Finding Filtering Algorithm for Cumulative Resource Constraints
Introduction
Cumulative Scheduling Problem
The Edge-Finding Rule
Dominance Properties of the Rules
A New Edge-Finding Algorithm
Overall Complexity
Experimental Results
Conclusion
References
A CSP Solver Focusing on FAC Variables
Introduction
CSPs Technical Background
fac Variables
fac-solver Approach
The SLS Component
Hybrid SLS-GAC Component
MAC-Based Component
Experimental Results
Perspectives and Conclusions
References
Constraint Reasoning and Kernel Clustering for Pattern Decomposition with Scaling
Introduction
Pattern Decomposition for Material Discovery
Problem Description
Motivating Application: Phase Identification in Materials
NP-Completeness
A Constraint Programming Formulation
Handling Errors and Noisy Data
Limitations of the Pure CP Approach: Scaling
Boosting Scalability: Exploiting Kernel-Based Clustering to Guide the CP Formulation
Kernels as Robust Similarity Measures
Clustering and Sample Selection
Scaling CP: Solving Sub-problems and Fusing Solutions
Empirical Validation
Conclusion
References
Solving Qualitative Constraints Involving Landmarks
Introduction
Qualitative Calculi and the Consistency Problem
The Hybrid Consistency Problem of RCC-5
The Hybrid Consistency Problem of RCC-8
Conclusion and Further Discussions
References
Searching for Doubly Self-orthogonal Latin Squares
Introduction
Preliminaries and Notations
Finding a DSOLS Using SAT and CSP
SAT Encoding of the Problem
Classical Constraint Satisfaction Problem (CSP)
An Approach Based on Set System and Exact Cover
Experimental Results
Conclusion
References
QCSP on Partially Reflexive Forests
Introduction
Preliminaries and Definitions
Tractable Trees
Loop-Connected Trees and Majority Polymorphisms
Paths of the Form a0$^a$ Where |a|=a+1
Paths of the Form a1$^b$0$^a$ Where b=1 and |a|=a
The Quasi-Loop-Connected Case
Hard Cases
Pspace-Completeness Results for Paths That Are Not 0-Eccentric
NP-hardness for Remaining Trees
References
The Computational Complexity of Disconnected Cut and 2K$_2$-Partition
Introduction
Vertex Cut Sets
H-Partitions
Graph Covers
Graph Homomorphisms
The Relationships between Questions Q1-Q4
Constraint Satisfaction
Retractions
Surjective Homomorphisms
References
Reducing the Search Space of Resource Constrained DCOPs
Introduction
Background
Resource Constrained DCOP
Pseudo Tree Ignoring Resource Constraints
DPOP with Virtual Variables
Related Works
Reducing Search Spaces
Root Nodes of Resources
Aggregation of Assignments
Global Lower Bounds of Resource Use
Moving Evaluation of Resource Use
Feasible Solutions
Correctness and Complexity
Evaluation
Conclusions
References
Proving Symmetries by Model Transformation
Introduction
Background
Undecidability of Model Symmetries
Basic Strategy
Swapping of Dimension: x[i,j]x[j,i]
Inversion of Domain: x[i,j]n-1-x[i,j]
Proving Symmetries by Model Transformation
Computing s(c)
Substituting Complex Expressions
Equivalence via Presburger Forumlæ
An Exploration of N-Queens
Implementation
Computing s(c)
Substituting Complex Expressions
Producing and Proving Presburger Formulæ
Results
Conclusion
References
Value Ordering for Finding All Solutions: Interactions with Adaptive Variable Ordering
Introduction
Background
Impact of Value Orderings on MAC
State-of-the-Art on Heuristic Interactions
The Role of Value Ordering: New Insights
Impact of Value Orderings on AC
Lazy K-Way Branching
Experimental Results
Conclusions
References
Boolean Equi-propagation for Optimized SAT Encoding
Introduction
Overview
Boolean Equi-propagation
Optimized SAT Encodings Using Equi-propagation
Implementation, Experiments, and Extensions
Related Work and Conclusion
References
CP Models for Maximum Common Subgraph Problems
Introduction
Background
Definitions
Existing Complete Approaches for Solving MCIS and MCPS
Modeling MCIS and MCPS Problems as Soft CSPs
Constraint Propagation
Experimental Results
References
Kangaroo: An Efficient Constraint-Based Local Search System Using Lazy Propagation
Introduction
Constraint-Based Local Search
Kangaroo Terminology
Kangaroo System
Experiments
Conclusion and Future Work
References
Pseudo-Tree-Based Incomplete Algorithm for Distributed Constraint Optimization with Quality Bounds
Introduction
Preliminaries
Bounded Incomplete Algorithm Based on Induced Width
Incomplete Algorithm and p-Optimality
Quality Guarantees
Experimental Evaluation
Conclusion
References
A More Efficient BDD-Based QBF Solver
Introduction
Background
Quantified Boolean Formulas
Binary Decision Diagrams
Search-Based Algorithms
Symbolic Algorithms
New QBF Solver
Enhanced Early Quantification
BDD Constraint Propagation
Variable Ordering Heuristics
Main Algorithm
Experiments
Conclusions and Future Work
References
Constraint Propagation for Efficient Inference in Markov Logic
Introduction
Background
Markov Logic
Constraint Satisfaction and Local Consistency
Constraint Propagation in Markov Logic
Generalized Arc Consistency Algorithm
Extension to Other Cases
Relation to Unit Propagation
Moving Beyond Generalized Arc Consistency
Experiments
Datasets
Results
Note about MC-SAT Convergence
Related Work
Conclusion and Future Work
References
Octagonal Domains for Continuous Constraints
Introduction
Preliminaries
Notations and Definitions
Octagons
Matrix Representation of Octagons
Boxes Representation
Intersection of Boxes
Octagonal CSP
Octagonal Consistency and Propagation
Octagonal Consistency for a Constraint
Propagation Scheme
Solving
Octagonal Split
Precision
Octagonal Solver
Experiments
Implementation
Results
Related Works
Conclusion
References
A Ø(n) Bound-Consistency Algorithm for the Increasing Sum Constraint
Introduction
Sum Constraints in CP
BC Linear Algorithm for Increasing Sum
Conclusion and Future Work
References
Automatic Generation of Constraints for Partial Symmetry Breaking
Introduction
Background
Overview of Group Theory Required for Our Method
Methods of Creating Subset of Symmetry Breaking Constraints
Analysing the Complete Symmetry Group
Generating Stabiliser Chains
Experimental Results
Unconstrained Cycles
Graceful Graphs
BIBD
Plain Row and Column Symmetry
Randomly Generated Sets
Conclusion
References
Beyond QCSP for Solving Control Problems
Introduction
Illustrating Example
Markovian Game-CSP (MGCSP)
Control Model
Reachability Control Problems
Relationship with QCSP/QCSP+
Algorithm
Experiments
Conclusion
References
On Mini-Buckets and the Min-fill Elimination Ordering
Introduction
Background
Graphical Models
Graph Concepts
Bucket Elimination
Mini-Bucket Elimination
Variable Elimination Ordering
Induced Hyper-Graphs and BE
Induced z-Bounded Hyper-graphs and MBE
Empirical Evaluation
Related Work
Conclusions
References
Search Combinators
Introduction
High-Level Search Language
Primitive Search Heuristics
Composite Search Heuristics
Modular Combinator Design
The Message Protocol
State Management
Modular Combinator Implementation
Experiments
Related Work
Conclusion
References
Variable Independence and Resolution Paths for Quantified Boolean Formulas
Introduction
Preliminaries
Regular Q-Resolution
Resolution Paths
Clause-Literal Graphs
Finding Dependency-Related Paths
Empirical Data
Conclusion
References
Pruning Rules for Constrained Optimisation for Conditional Preferences
Introduction
Background Material
A Language of Conditional Preferences
Polynomial Dominance for Conditional Preferences
Constrained Optimisation
Basic Constrained Optimisation Approach
Incorporating Dominance and Non-dominance Conditions
Sufficient Conditions for Dominance
The Root-Dominates Rule
The Deciding-Node Dominance Rule
Projection-Dominance Condition
A Sufficient Condition for Non-dominance
Experimental Testing
Experimental Setup
Discussion of Results
Discussion
References
Checking and Filtering Global Set Constraints
Introduction
Set CSPs
Contributions and Related Work
A Feasibility Checker for the AllDisjoint Constraint
A Primal Filter for Symmetry-Breaking AllDisjoint
A Dual Filter for the Global Atmost-k Constraint
Primal/Dual Filters for Symmetry-Breaking Atmost-k
Experimental Evaluation
Conclusion
References
Author Index

Inhalt (PDF)

Systemvoraussetzungen

Als PDF speichern Als Link merken