Principles and Practice of Constraint Programming

Name: Principles and Practice of Constraint Programming | 21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings

Gilles Pesant(Herausgeber*in)

Springer (Verlag)

Erschienen am 12. August 2015

XXIV, 747 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-319-23219-5 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Intro
Preface
Tutorials and Workshops
Conference Organization
Invited Talks
Constraint-based Problems and Solutionsin the Global Enterprise
Industrial Success Stories of ASP and CP:What's Still Open?
Synthesis of Constraint Solvers
Contents
Technical Track
Encoding Linear Constraints with Implication Chains to CNF
1 Introduction
2 Preliminaries
2.1 SAT Solving
2.2 Multi Decision Diagrams
3 Pseudo Boolean Constraints and Chains
4 Translating Through MDDs with Chains
4.1 Preliminaries for the Construction
4.2 Algorithm and Properties of the Construction
5 Experiments
6 Conclusion and Future Work
References
Anytime Hybrid Best-First Search with Tree Decomposition for Weighted CSP
1 Introduction
2 Background
3 Hybrid Best-First Search
3.1 Related Work
4 Hybrid Best-First Search and Tree Decompositions
4.1 Using HBFS in BTD
4.2 Related Work
5 Experimental Results
5.1 Proving Optimality
5.2 Anytime Behavior
6 Conclusions
References
Improved Constraint Propagation via Lagrangian Decomposition
1 Introduction
2 Related Work
3 Lagrangian Decomposition
4 Application to Constraint Programming
5 Application: Multiple Alldifferent Constraints
6 Application: Set Covering
7 Conclusion
References
Strengthening Convex Relaxations with Bound Tightening for Power Network Optimization
1 Introduction
2 AC Power Flow
3 The Quadratic Convex (QC) Relaxation
4 Consistency of Constraint Relaxation Networks
4.1 Relation to Concepts in Global Optimization
5 Constraint Relaxation Networks for Power Flows
6 Strength and Performance of the Bound Tightening
7 Application to AC Optimal Power Flow
8 Propagation with Load Uncertainty
9 Conclusion
References
Broken Triangles Revisited
1 Introduction
2 Mixing Arc Consistency and BTP-merging
3 The Order of BTP-mergings
4 Optimal Sequence of BTP-mergings at a Single Variable
5 Virtual Interchangeability and Neighbourhood Substitution
6 Conclusion
References
A Microstructure-Based Family of Tractable Classes for CSPs
1 Introduction
2 Background
3 k-BTP: Definition and Properties
4 Relationship with Some Tractable Classes
5 Experiments
5.1 Instances Belonging to Tractable Classes
5.2 Link Between Efficient Solving and Belonging to Tractable Classes
6 Conclusion
References
The Unary Resource with Transition Times
1 Introduction
2 Background
2.1 Related Work
2.2 Unary Resource Propagators in CP
3 Transition Times Extension Requirements
4 Lower Bound of Transitions Times
5 Extending the -tree with Transition Times
6 Disjunctive Propagation Algorithms with Transition Times
6.1 Extension of Classic Unary Resource Propagation Algorithms
6.2 Detectable Precedences Propagation Example
7 Evaluation
8 Conclusion
References
A Global Constraint for a Tractable Class of Temporal Optimization Problems
1 Introduction
2 Background
2.1 Temporal Constraint Networks
2.2 Constraint Programming (CP)
3 The ExistAllen Constraint
3.1 Basic Filtering: One Relation, One Task, One Interval
3.2 A First Propagator
3.3 A Linear Propagator
3.4 Improvements
4 Evaluation
4.1 Problem Description
4.2 Benchmark
5 Conclusion
References
Exploiting GPUs in Solving (Distributed) Constraint Optimization Problems with Dynamic Programming
1 Introduction
2 Background
2.1 Centralized Constraint Optimization Problems (COPs)
2.2 Distributed Constraint Optimization Problems (DCOPs)
2.3 Graphical Processing Units (GPUs)
3 GPU-Based (Distributed) Bucket Elimination (GPU-(D)BE)
3.1 GPU Data Structures
3.2 Parallel Aggregate and Project Operations
3.3 General Observations
4 Related Work
5 Experimental Results
6 Conclusions and Discussions
References
Conflict Ordering Search for Scheduling Problems
1 Introduction
2 Related Works
3 Guiding Search by Timestamping Conflicts
3.1 Background
3.2 Conflict Ordering
3.3 Restarts and Timestamp Ordering
3.4 Differences with Last Conflict Search
4 Experiments
4.1 Branch-and-Bound
4.2 Branch-and-Bound with Restarts
4.3 Destructive Lower Bounds.
5 Conclusion
References
Simple and Scalable Time-Table Filtering for the Cumulative Constraint
1 Preliminaries
2 Existing Algorithms for Time-Tabling
3 A Linear Time-Table Filtering Algorithm
4 An Efficient O(n2) Time-Table Filtering
5 Experiments
6 Conclusion
References
General Bounding Mechanism for Constraint Programs
1 Introduction
2 Related Work
2.1 Lagrangian Decomposition
2.2 Knapsack and Regular Constraints
3 Proposed Approach
3.1 Lagrangian Decomposition
3.2 The Knapsack Constraint
3.3 The Regular Constraint
3.4 The Subgradient Procedure
4 Computational Results
4.1 Results for MKP
4.2 Results for SSP
5 Conclusions and Future Work
References
Smallest MUS Extraction with Minimal Hitting Set Dualization
1 Introduction
2 Preliminaries
3 Basic Algorithm
4 Additional Details
4.1 Reducing the Number of SAT Calls
4.2 Disjoint MCS Enumeration
4.3 Finding Approximate Solutions
5 Experimental Results
6 Conclusion
References
Upper and Lower Bounds on the Time Complexity of Infinite-Domain CSPs
1 Introduction
2 Preliminaries
2.1 Constraint Satisfaction
2.2 First-Order Definable Relations
3 Fundamental Algorithms
3.1 Branching on Disjuncts
3.2 Sparsification
4 Improved Upper Bounds
4.1 Structure Enumeration
4.2 Equality Constraint Languages
4.3 Temporal Constraint Reasoning
5 Lower Bounds
5.1 Lower Bounds for JEPD Languages
5.2 Lower Bounds for Allen's Interval Algebra
6 Discussion
References
Generalized Totalizer Encoding for Pseudo-Boolean Constraints
1 Introduction
2 Generalized Totalizer Encoding
3 Related Work
4 Implementation and Evaluation
5 Conclusion
References
Smaller Selection Networks for Cardinality Constraints Encoding
1 Introduction
2 Preliminaries
3 Pairwise and Bitonic Selection Networks
4 New Smaller Selection Networks
5 Sizes of New Selection Networks
6 Arc-Consistency of Selection Networks
7 Conclusions
References
PREFIX-PROJECTION Global Constraint for Sequential Pattern Mining
1 Introduction
2 Preliminaries
2.1 Sequential Patterns
2.2 SPM under Constraints
2.3 Projected Databases
2.4 CSP and Global Constraints
3 Related Works
3.1 Ad hoc Methods for SPM
3.2 CP Methods for SPM
4 PREFIX-PROJECTION Global Constraint
4.1 A Concise Encoding
4.2 Definition and Consistency Checking
4.3 Building the Projected Databases
4.4 Filtering
4.5 Encoding of SPM Constraints
5 Experimental Evaluation
6 Conclusion
References
On Tree-Preserving Constraints
1 Introduction
2 Preliminaries
3 Chain-Preserving Constraints
4 Path-Preserving Constraints
5 Tree-Preserving Constraints
5.1 Enforcing Arc- and Path-Consistency Preserves Tree-Preserving
5.2 Partial Path-Consistency
6 Tree-Preserving Constraints and the Scene Labelling Problem
7 Further Discussion and Conclusion
References
Modeling and Solving Project Scheduling with Calendars
1 Introduction
2 Problem Description
3 Models for RCPSP/max-cal
3.1 Model timeidx (Time Indexed Formulation)
3.2 Model 2cap (Doubling Resource Capacity)
3.3 Model addtasks (Adding Split Tasks)
3.4 Model cumucal (Global Calendar Propagator)
3.5 Time Granularity Considerations
4 Experiments and Conclusion
4.1 Comparing Search Strategies
4.2 Comparing Models
4.3 Comparing Solvers
Deterministic Estimation of the Expected Makespan of a POS Under Duration Uncertainty
1 Introduction
2 Expected Makespan with Worst-Case Distribution
3 Estimating Ewc[T(D)]
4 Concluding Remarks
5 Appendix A
References
A Parallel, Backjumping Subgraph Isomorphism Algorithm Using Supplemental Graphs
1 Introduction
2 Definitions, Notation, and a Proposition
3 A New Algorithm
3.1 Preprocessing and Initialisation
3.2 Search and Inference
3.3 Bit- and Thread-Parallelism
4 Experimental Evaluation
4.1 Comparison with Other Solvers
4.2 Parallelism
4.3 Effects of Backjumping
4.4 Comparing All-Different Propagators
5 Conclusion
References
Automated Auxiliary Variable Elimination Through On-the-Fly Propagator Generation
1 Introduction
2 Preliminaries
2.1 MiniZinc and FlatZinc
2.2 Patterns, Occurrences, and Extensions
2.3 Indexicals
3 Our Approach
3.1 Identification of Frequent Patterns
3.2 Pattern Instantiation
3.3 Indexical Propagator Description Generation and Compilation
4 Example: Ship Schedule
5 Experimental Evaluation
6 Discussion
6.1 Related Work
6.2 Properties and Extensions
7 Conclusion
References
Automatically Improving SAT Encoding of Constraint Problems Through Common Subexpression Elimination in Savile Row
1 Introduction
2 CSE for SAT Encoding
3 Experimental Evaluation
4 Conclusion
References
Exact Sampling for Regular and Markov Constraints with Belief Propagation
1 Introduction
1.1 Related Work
2 Sequence Generation with Markov constraints
3 Background on Belief Propagation
4 Belief Propagation for Markov and Regular
5 Examples
6 Evaluation
7 Conclusion
References
Randomness as a Constraint
1 Introduction
2 Entropy Constraints
2.1 Non-uniform Distributions
2.2 Repeated Strings
2.3 Correlated Sources
2.4 Using Entropy Constraints
3 Applications
3.1 Experimental Psychology
3.2 Factory Inspection
4 Related Work
5 Discussion
References
Quasipolynomial Simulation of DNNF by a Non-determinstic Read-Once Branching Program
1 Introduction
2 Proof of Theorem 1
2.1 Proofs of Auxiliary Lemmas for Theorem 1
References
MiniSearch: A Solver-Independent Meta-Search Language for MiniZinc
1 Introduction
2 The MiniSearch language
2.1 MiniSearch Built-Ins Involving the Solver
2.2 MiniSearch Control Built-Ins
2.3 Solution Management
2.4 A Library of Search Strategies
3 MiniSearch Examples
3.1 Lexicographic BaB
3.2 Large Neighbourhood Search (LNS)
3.3 AND/OR Search
3.4 Diverse Solutions
3.5 Interactive Optimisation
4 The MiniSearch Kernel
4.1 The MiniSearch Interpreter
4.2 Emulating Advanced Solver Behaviour
4.3 Built-in Primitives
5 Experiments
5.1 Experimental Setup
5.2 Overhead of Different MiniSearch Interfaces
5.3 Heuristic Search
6 Related Work
7 Conclusion and Future Work
References
Two Clause Learning Approaches for Disjunctive Scheduling
1 Introduction
2 Hybrid CP/SAT Solving
3 A Simple CP Model for Job Shop Scheduling
4 Lazy Generation of Atoms
5 Learning Restricted to Task Ordering
6 Experimental Results
6.1 Empirical Evaluation on the Job Shop Scheduling Problem
6.2 Lower Bound Computation
7 Conclusion
References
Bounding an Optimal Search Path with a Game of Cop and Robber on Graphs
1 Introduction
2 The Optimal Search Path Problem
2.1 Modeling the OSP in Constraint Programming
2.2 The DMEAN Bound from the Literature
3 Bounding the Optimal Search Path Using Search Games on Graphs
3.1 A Game of Cop and Drunk Robber
3.2 Markov Decision Process (MDP) and the OSP Bound
4 Experiments
4.1 Results and Discussion
5 Conclusion
References
Restricted Path Consistency Revisited
1 Introduction
2 Background
3 The RPC3 Algorithm
4 Experiments
5 Conclusion
References
Machine Learning of Bayesian Networks Using Constraint Programming
1 Introduction
2 Background
3 Constraint Programming Approach
3.1 Symmetry-Breaking Constraints (I)
3.2 Symmetry-Breaking Constraints (II)
3.3 Symmetry-Breaking Constraints (III)
3.4 Dominance Constraints (I)
3.5 Dominance Constraints (II)
3.6 Dominance Constraints (III)
3.7 Acyclic Constraint
3.8 Solving the Constraint Model
4 Experimental Evaluation
5 Discussion and Future Work
References
Hybridization of Interval CP and Evolutionary Algorithms for Optimizing Difficult Problems
1 Motivation
2 Differential Evolution
3 Reliable Computations
3.1 Interval Arithmetic
3.2 Global Optimization
3.3 Interval Contractors
4 Charibde: A Cooperative Approach
4.1 Hybridization of Stochastic and Deterministic Techniques
4.2 Differential Evolution
4.3 Interval Branch and Contract
4.4 MaxDist: A New Exploration Strategy
5 Experimental Results
6 Conclusion
References
A General Framework for Reordering Agents Asynchronously in Distributed CSP
1 Introduction
2 Background
2.1 Distributed Constraint Satisfaction Problem
2.2 Asynchronous Backtracking - ABT
2.3 No-goods and Explanations
2.4 Agile Asynchronous Backtracking
3 Generalized AgileABT
3.1 Neighborhood Based Variable Ordering Heuristics
3.2 Conflict-Directed Variable Ordering Heuristic
3.3 Theoretical Analysis
4 Empirical Analysis
4.1 Uniform Binary Random DisCSPs
4.2 Distributed Graph Coloring Problems
4.3 Composed Random Instances
4.4 Discussion
5 Related Work
6 Conclusion
References
Automatically Generating Streamlined Constraint Models with Essence and Conjure
1 Introduction
2 Related Work
3 Background: Essence
4 From Conjectures to Streamlined Specifications
4.1 Exploiting Essence Domain Annotations
4.2 Conjecture-Forming Rules
4.3 Experimental Analysis
5 Identifying Effective Combinations of Conjectures
6 Discussion: Generating Streamliners in Practice
7 Conclusion
A Problem Descriptions
References
Application Track
Constraint-Based Local Search for Finding Node-Disjoint Bounded-Paths in Optical Access Networks
1 Introduction
2 Constraint-Based Local Search
2.1 Node-Disjointness
3 Empirical Evaluation
4 Conclusions and Future Work
References
Open Packing for Facade-Layout Synthesis Under a General Purpose Solver
1 Introduction
2 Retrofit Industrialization
2.1 Elements
2.2 Problem Features
2.3 Assumptions
2.4 Cost Function
3 Facade-Layout Synthesis as a CSP
3.1 Variables
3.2 Business Constraints
3.3 Symmetry-Breaking Constraints
4 Implementation
4.1 An Open Constraint for Rectangle Non-Overlapping (C3)
4.2 A Constraint Dedicated to Frame Covering (C4)
4.3 Embedding Symmetry-Breaking
5 The Search Heuristic
6 Evaluation
6.1 A Two-Step Approach
6.2 Impact of Symmetry Breaking
6.3 Search Comparison
7 Conclusions
References
Power Capping in High Performance Computing Systems
1 Introduction
2 System Description and Motivations for Using CP
3 Problem Definition
4 The PRB Approach
5 Hybrid Approach
5.1 Scheduling Problem
5.2 Allocation Problem
5.3 Interaction between the Stages
6 Added Value of CP
6.1 Evaluation of Our Models
7 Conclusions
References
A Constraint-Based Approach to the Differential Harvest Problem
1 Introduction
2 The Differential Harvest Problem
3 Constraint Programming for the DHP
3.1 The Step Model
3.2 The Precedence model
Variables.
Constraints.
Symmetry Breaking.
4 Experimental Results
5 Discussion
5.1 Comparison with an ILP Formulation
5.2 Complements to the Model
6 Conclusion
References
Constrained Minimum Sum of Squares Clustering by Constraint Programming
1 Introduction
2 Preliminaries
2.1 Constrained Clustering
2.2 Related Work
3 Constraint Programming Model
3.1 Constraints
3.2 Search Strategy
4 Filtering Algorithm for WCSS
4.1 Lower Bound Computation
4.2 Filtering Algorithm
5 Experiments
5.1 Optimizing WCSS in Presence of User Constraints
5.2 Comparisons with COP-kmeans and RBBA
6 Conclusion
References
A Constraint Programming Approach for Non-preemptive Evacuation Scheduling
1 Introduction
2 Problem Description
3 The Constraint Programming Model
3.1 Decision Variables
3.2 Constraints
3.3 The Constraint-Based Scheduling Models
3.4 Problem Decomposition
3.5 Dominance Relationships
3.6 Additional Constraints to a Real-World Evacuation Scheduling Problem
3.7 Complexity of Phased Evacuations with Convergent Paths
3.8 The Search Procedure
4 Experimental Results
5 Conclusion
References
Solving Segment Routing Problems with Hybrid Constraint Programming Techniques
1 Introduction
2 The General Segment Routing Problem
3 Segment Routing Path Variables
3.1 Shortcomings of Classical Path Representations
3.2 Segment Routing Path Variables
3.3 Implementation
4 Constraints on SR-Path Variables
4.1 The Channeling Constraint
4.2 The Length Constraint
4.3 The ServiceChaining Constraint
4.4 The DAG Constraint
4.5 The MaxCost Constraint
5 Hybrid Optimization
6 Experiments and Results
7 Conclusion
Modeling Universal Instruction Selection
1 Introduction
2 Graph-Based Instruction Selection
3 Representations for Universal Instruction Selection
4 A Constraint Model for Universal Instruction Selection
5 Experimental Evaluation
6 Related Work
7 Conclusions and Future Work
References
Optimizing the Cloud Service Experience Using Constraint Programming
1 Introduction
2 Service Center Optimization: Agent Matching
3 Why CP?
4 Added Value of CP
5 Solution Approach
5.1 The Constraint Model
5.2 The Search Heuristic
5.3 A Note on the Filtering Power of GCC
6 Related Work
7 Numerical Results
8 Conclusion
References
Find Your Way Back: Mobility Profile Mining with Constraints
1 Introduction
2 Drawbacks of the Pure Data Mining Approach
3 Constraint Model
4 Model Implementation
4.1 Minion Model
4.2 Optimising the Clustering
4.3 Scalability
5 Experimental Evaluation
5.1 Dataset
5.2 Evaluation of Results
5.3 Qualitative Evaluation
6 Conclusion and Future Work
References
Joint Vehicle and Crew Routing and Scheduling
1 Introduction
2 Problem Description
3 A Two-Stage Method for the JVCRSP
4 A Mixed Integer Program for the JVCRSP
5 A Constraint Program for the JVCRSP
5.1 Feasibility and Bounding of Crew Routes
5.2 Symmetry-Breaking within Locations
5.3 The Search Procedure
6 Experimental Results
7 Related Work
8 Conclusion
Constructing Sailing Match Race Schedules: Round-Robin Pairing Lists
1 Introduction
2 Problem Definition: Round-Robin Pairing Lists
3 The Constraint Models
3.1 Stage 1: Minimizing Boat Changes
3.2 Stage 2: Minimizing Imbalances
3.3 Stage 3: Renaming Skippers
3.4 Stage 4: Orienting Matches
4 Sample Schedules
5 Discussion
6 Conclusion
References
Design and Evaluation of a Constraint-Based Energy Saving and Scheduling Recommender System
1 Introduction
2 AUTHENTIC Smart Home Project
3 Requirements
4 Constraint-Based Recommender System
4.1 System Overview
4.2 Data Preprocessing (Data Analysis Module)
4.3 Appliance Use Optimisation Module (Solver)
5 Scheduling Module
6 Performance Evaluation
6.1 Solver Performance
6.2 Scheduler Performance
7 Related Work
8 Conclusions and Future Work
References
Scheduling Running Modes of Satellite Instruments Using Constraint-Based Local Search
1 Problem Description
2 Problem Modeling
3 Specific Problem Encoding
3.1 Problem Complexity Versus Allowed Running Times
3.2 Specific Manipulation of Topological Orders
3.3 Specific Encoding of the Thermal Resource Constraint
3.4 Specific Management of Some Hard Constraints
4 A Multi-phase Local Search Algorithm
5 Experiments
6 Conclusion
References
Erratum to: Modeling Universal Instruction Selection
Abstracts of Papers Fast Tracked to Constraints Journal
Using Finite Transducers for Describing and Synthesising Structural Time-Series Constraints
Projection, Consistency, and George Boole
On Computing Minimal Independent Support and Its Applications to Sampling and Counting (Extended Abstract)
References
General Game Playing with Stochastic CSP
Visual Search Tree Profiling
Long-Haul Fleet Mix and Routing Optimisation with Constraint Programming and Large Neighbourhood Search
Abstracts of Published Journal Track Papers
On the Reification of Global Constraints (Abstract)
MDD Propagation for Sequence Constraints
Discrete Optimization with Decision Diagrams
A Hybrid Approach Combining Local Search and Constraint Programming for a Large Scale Energy Management Problem
References
Representing and Solving Finite-Domain Constraint Problems using Systems of Polynomials (Extended Abstract)
A Quadratic Extended Edge-Finding Filtering Algorithm for Cumulative Resource Constraints
Achieving Domain Consistency and Counting Solutions for Dispersion Constraints
References
meSAT: Multiple Encodings of CSP to SAT
Constraint programming for LNG ship scheduling and inventory management (Abstract)
Revisiting the Limits of MAP Inference by MWSS on Perfect Graphs
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken