product iamge

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

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Download
Search on Amazon

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

The 10th International Conference on the Principles and Practice of Constraint Programming (CP 2003) was held in Toronto, Canada, during September 27 – October 1, 2004. Information about the conference can be found on the Web at http://ai.uwaterloo.ca/~cp2004/ Constraint programming (CP) is about problem modelling, problem solving, programming, optimization, software engineering, databases, visualization, user interfaces, and anything to do with satisfying complex constraints. It reaches into mathematics, operations research, arti?cial intelligence, algorithms, c- plexity, modelling and programming languages, and many aspects of computer science. Moreover, CP is never far from applications, and its successful use in industry and government goes hand in hand with the success of the CP research community. Constraintprogrammingcontinuesto beanexciting,?ourishingandgrowing research?eld,astheannualCPconferenceproceedingsamplywitness.Thisyear, from 158 submissions, we chose 46 to be published in full in the proceedings. Instead of selecting one overall best paper, we picked out four “distinguished” papers – though we were tempted to select at least 12 such papers. In addition we included 16 short papersin the proceedings– these were presentedas posters at CP 2004. This volume includes summaries of the four invited talks of CP 2004. Two speakers from industry were invited. However these were no ordinary industrial representatives,buttwoofthe leadingresearchersinthe CPcommunity:Helmut Simonis of Parc Technologies, until its recent takeover by Cisco Systems; and Jean Francoi ¸ s Puget, Director of Optimization Technology at ILOG. The other two invited speakers are also big movers and shakers in the researchcommunity.

Author(s): Andreas Podelski (auth.), Mark Wallace (eds.)
Series: Lecture Notes in Computer Science 3258
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2004

Language: English
Pages: 826
Tags: Programming Techniques; Programming Languages, Compilers, Interpreters; Logics and Meanings of Programs; Mathematical Logic and Formal Languages; Artificial Intelligence (incl. Robotics); Computer Appl. in Administrative Data Processing

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 -