Principles and Practice of Constraint Programming – CP 2004: 10th International Conference, CP 2004, Toronto, Canada, September 27 -October 1, 2004. Proceedings

Front Matter....Pages -
Constraints in Program Analysis and Verification....Pages 1-4
Constraint Programming Next Challenge: Simplicity of Use....Pages 5-8
Algorithmic Adventures at the Interface of Computer Science, Statistical Physics, and Combinatorics....Pages 9-12
Challenges for Constraint Programming in Networking....Pages 13-16
Consistency and Random Constraint Satisfaction Models with a High Constraint Tightness....Pages 17-31
Statistical Regimes Across Constrainedness Regions....Pages 32-46
Constraint-Based Combinators for Local Search....Pages 47-61
Unary Resource Constraint with Optional Activities....Pages 62-76
Constraint Propagation as a Proof System....Pages 77-91
Backtrack-Free Search for Real-Time Constraint Satisfaction....Pages 92-106
Deriving Filtering Algorithms from Constraint Checkers....Pages 107-122
Leveraging the Learning Power of Examples in Automated Constraint Acquisition....Pages 123-137
Disjoint, Partition and Intersection Constraints for Set and Multiset Variables....Pages 138-152
Decomposition and Learning for a Hard Real Time Task Allocation Problem....Pages 153-167
Quantified Constraint Satisfaction and 2-Semilattice Polymorphisms....Pages 168-181
(Smart) Look-Ahead Arc Consistency and the Pursuit of CSP Tractability....Pages 182-196
Heuristic Selection for Stochastic Search Optimization: Modeling Solution Quality by Extreme Value Theory....Pages 197-211
A Complete Characterization of Complexity for Boolean Constraint Optimization Problems....Pages 212-226
Financial Portfolio Optimisation....Pages 227-241
Bounding the Resource Availability of Partially Ordered Events with Constant Resource Impact....Pages 242-259
Monotone Literals and Learning in QBF Reasoning....Pages 260-273
Streamlined Constraint Reasoning....Pages 274-289
A Domain Consistency Algorithm for the Stretch Constraint....Pages 290-304
A Hybrid Method for Planning and Scheduling....Pages 305-316
Counting-Based Look-Ahead Schemes for Constraint Satisfaction....Pages 317-331
Completable Partial Solutions in Constraint Programming and Constraint-Based Scheduling....Pages 332-346
Set Domain Propagation Using ROBDDs....Pages 347-361
Global Constraints for Integer and Set Value Precedence....Pages 362-376
Quality of LP-Based Approximations for Highly Combinatorial Problems....Pages 377-392
Constraint Satisfaction in Semi-structured Data Graphs....Pages 393-407
Strategies for Global Optimization of Temporal Preferences....Pages 408-422
 ID Walk : A Candidate List Strategy with a Simple Diversification Device....Pages 423-437
Understanding Random SAT: Beyond the Clauses-to-Variables Ratio....Pages 438-452
Symbolic Decision Procedures for QBF....Pages 453-467
Propagation Guided Large Neighborhood Search....Pages 468-481
A Regular Language Membership Constraint for Finite Sequences of Variables....Pages 482-495
Generating Robust Partial Order Schedules....Pages 496-511
Full Dynamic Substitutability by SAT Encoding....Pages 512-526
Improved Bound Computation in Presence of Several Clique Constraints....Pages 527-541
Improved Algorithms for the Global Cardinality Constraint....Pages 542-556
Impact-Based Search Strategies for Constraint Programming....Pages 557-571
The Cardinality Matrix Constraint....Pages 572-587
Controllability of Soft Temporal Constraint Problems....Pages 588-603
Hybrid Set Domains to Strengthen Constraint Propagation and Reduce Symmetries....Pages 604-618
Speeding Up Constraint Propagation....Pages 619-633
Theoretical Foundations of CP-Based Lagrangian Relaxation....Pages 634-647
A Constraint for Bin Packing....Pages 648-662
Solving Non-clausal Formulas with DPLL Search....Pages 663-678
A Hyper-arc Consistency Algorithm for the Soft Alldifferent Constraint....Pages 679-689
Efficient Strategies for (Weighted) Maximum Satisfiability....Pages 690-705
Preprocessing Techniques for Distributed Constraint Optimization....Pages 706-710
Variable Ordering Heuristics Show Promise....Pages 711-715
The Tractability of Global Constraints....Pages 716-720
Support Inference for Generic Filtering....Pages 721-725
Strong Cost-Based Filtering for Lagrange Decomposition Applied to Network Design....Pages 726-730
The Impact of AND/OR Search Spaces on Constraint Satisfaction and Counting....Pages 731-736
A General Extension of Constraint Propagation for Constraint Optimization....Pages 737-741
How Much Backtracking Does It Take to Color Random Graphs? Rigorous Results on Heavy Tails....Pages 742-746
Solving the Crane Scheduling Problem Using Intelligent Search Schemes....Pages 747-751
Algorithms for Quantified Constraint Satisfaction Problems....Pages 752-756
Improving the Applicability of Adaptive Consistency: Preliminary Results....Pages 757-761
On-Demand Bound Computation for Best-First Constraint Optimization....Pages 762-766
A New Algorithm for Maintaining Arc Consistency After Constraint Retraction....Pages 767-771
Computing the Frequency of Partial Orders....Pages 772-776
On Tightness of Constraints....Pages 777-781
Concurrent Dynamic Backtracking for Distributed CSPs....Pages 782-787
Set Variables and Local Search....Pages 788-788
 N –Kings for Dynamic Systems....Pages 789-789
Relation Variables in Qualitative Spatial Reasoning....Pages 790-790
Synchronous, Asynchronous and Hybrid Algorithms for DisCSP....Pages 791-791
Long-Term Learning for Algorithm Control....Pages 792-792
Solution Extraction with the “Critical Path” in Graphplan-Based Optimal Temporal Planning....Pages 793-793
Machine Learning for Portfolio Selection Using Structure at the Instance Level....Pages 794-794
Local Search with Maximal Independent Sets....Pages 795-795
A Dynamic Restart Strategy for Randomized BT Search....Pages 796-796
A BDD-Based Approach to Interactive Configuration....Pages 797-797
Extending Super-solutions....Pages 798-798
Choosing Efficient Representations of Abstract Variables....Pages 799-799
A Hypergraph Separator Based Variable Ordering Heuristic for Solving Real World SAT....Pages 800-800
Exploiting Symmetries via Permutations for PC Board Manufacturing....Pages 801-801
Iterative Forward Search Algorithm: Combining Local Search with Maintaining Arc Consistency and a Conflict-Based Statistics....Pages 802-802
Programming Robotic Devices with a Timed Concurrent Constraint Language....Pages 803-803
Heuristics for the Distributed Breakout Algorithm....Pages 804-804
Explanations and Numeric CSPs....Pages 805-805
Softly Constrained CP Nets....Pages 806-806
Online Constraint Solving and Rectangle Packing....Pages 807-807
Modelling Chemical Reactions Using Constraint Programming and Molecular Graphs....Pages 808-808
Constraining Special-Purpose Domain Types....Pages 809-809
PLASMA: A Constraint Based Planning Architecture....Pages 810-810
Applying Constraint Satisfaction Techniques to 3D Camera Control....Pages 811-811
Adaptive Enterprise Optimization Framework: AEO Server and AEO Studio....Pages 812-812
 CRE2 : A CP Application for Reconfiguring a Power Distribution Network for Power Losses Reduction....Pages 813-814
A Constraint-Based Planner Applied to Data Processing Domains....Pages 815-815
CLab: A C++ Library for Fast Backtrack-Free Interactive Product Configuration....Pages 816-816
A Constraint-Based System for Hiring and Managing Graduate Teaching Assistants....Pages 817-817
A Web-Based Meeting Scheduling Solver With Privacy Guarantees, Without Trusted Servers....Pages 818-818
A Constraint-Based Graphics Library for B-Prolog....Pages 819-819
Back Matter....Pages -