Principles and Practice of Constraint Programming - CP 2004

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.

Inhalt

Invited Papers.- Constraints in Program Analysis and Verification.- Constraint Programming Next Challenge: Simplicity of Use.- Algorithmic Adventures at the Interface of Computer Science, Statistical Physics, and Combinatorics.- Challenges for Constraint Programming in Networking.- Distinguished Papers.- Consistency and Random Constraint Satisfaction Models with a High Constraint Tightness.- Statistical Regimes Across Constrainedness Regions.- Constraint-Based Combinators for Local Search.- Unary Resource Constraint with Optional Activities.- Full Papers.- Constraint Propagation as a Proof System.- Backtrack-Free Search for Real-Time Constraint Satisfaction.- Deriving Filtering Algorithms from Constraint Checkers.- Leveraging the Learning Power of Examples in Automated Constraint Acquisition.- Disjoint, Partition and Intersection Constraints for Set and Multiset Variables.- Decomposition and Learning for a Hard Real Time Task Allocation Problem.- Quantified Constraint Satisfaction and 2-Semilattice Polymorphisms.- (Smart) Look-Ahead Arc Consistency and the Pursuit of CSP Tractability.- Heuristic Selection for Stochastic Search Optimization: Modeling Solution Quality by Extreme Value Theory.- A Complete Characterization of Complexity for Boolean Constraint Optimization Problems.- Financial Portfolio Optimisation.- Bounding the Resource Availability of Partially Ordered Events with Constant Resource Impact.- Monotone Literals and Learning in QBF Reasoning.- Streamlined Constraint Reasoning.- A Domain Consistency Algorithm for the Stretch Constraint.- A Hybrid Method for Planning and Scheduling.- Counting-Based Look-Ahead Schemes for Constraint Satisfaction.- Completable Partial Solutions in Constraint Programming and Constraint-Based Scheduling.- Set Domain Propagation Using ROBDDs.- Global Constraints for Integer and Set Value Precedence.- Quality of LP-Based Approximations for Highly Combinatorial Problems.- Constraint Satisfaction in Semi-structured Data Graphs.- Strategies for Global Optimization of Temporal Preferences.- ID Walk: A Candidate List Strategy with a Simple Diversification Device.- Understanding Random SAT: Beyond the Clauses-to-Variables Ratio.- Symbolic Decision Procedures for QBF.- Propagation Guided Large Neighborhood Search.- A Regular Language Membership Constraint for Finite Sequences of Variables.- Generating Robust Partial Order Schedules.- Full Dynamic Substitutability by SAT Encoding.- Improved Bound Computation in Presence of Several Clique Constraints.- Improved Algorithms for the Global Cardinality Constraint.- Impact-Based Search Strategies for Constraint Programming.- The Cardinality Matrix Constraint.- Controllability of Soft Temporal Constraint Problems.- Hybrid Set Domains to Strengthen Constraint Propagation and Reduce Symmetries.- Speeding Up Constraint Propagation.- Theoretical Foundations of CP-Based Lagrangian Relaxation.- A Constraint for Bin Packing.- Solving Non-clausal Formulas with DPLL Search.- A Hyper-arc Consistency Algorithm for the Soft Alldifferent Constraint.- Efficient Strategies for (Weighted) Maximum Satisfiability.- Short Papers.- Preprocessing Techniques for Distributed Constraint Optimization.- Variable Ordering Heuristics Show Promise.- The Tractability of Global Constraints.- Support Inference for Generic Filtering.- Strong Cost-Based Filtering for Lagrange Decomposition Applied to Network Design.- The Impact of AND/OR Search Spaces on Constraint Satisfaction and Counting.- A General Extension of Constraint Propagation for Constraint Optimization.- How Much Backtracking Does It Take to Color Random Graphs? Rigorous Results on Heavy Tails.- Solving the Crane Scheduling Problem Using Intelligent Search Schemes.- Algorithms for Quantified Constraint Satisfaction Problems.- Improving the Applicability of Adaptive Consistency: Preliminary Results.- On-Demand Bound Computation for Best-First Constraint Optimization.- A New Algorithm for Maintaining Arc Consistency After Constraint Retraction.- Computing the Frequency of Partial Orders.- On Tightness of Constraints.- Concurrent Dynamic Backtracking for Distributed CSPs.- Doctoral Papers.- Set Variables and Local Search.- N-Kings for Dynamic Systems.- Relation Variables in Qualitative Spatial Reasoning.- Synchronous, Asynchronous and Hybrid Algorithms for DisCSP.- Long-Term Learning for Algorithm Control.- Solution Extraction with the "Critical Path" in Graphplan-Based Optimal Temporal Planning.- Machine Learning for Portfolio Selection Using Structure at the Instance Level.- Local Search with Maximal Independent Sets.- A Dynamic Restart Strategy for Randomized BT Search.- A BDD-Based Approach to Interactive Configuration.- Extending Super-solutions.- Choosing Efficient Representations of Abstract Variables.- A Hypergraph Separator Based Variable Ordering Heuristic for Solving Real World SAT.- Exploiting Symmetries via Permutations for PC Board Manufacturing.- Iterative Forward Search Algorithm: Combining Local Search with Maintaining Arc Consistency and a Conflict-Based Statistics.- Programming Robotic Devices with a Timed Concurrent Constraint Language.- Heuristics for the Distributed Breakout Algorithm.- Explanations and Numeric CSPs.- Softly Constrained CP Nets.- Online Constraint Solving and Rectangle Packing.- Modelling Chemical Reactions Using Constraint Programming and Molecular Graphs.- Constraining Special-Purpose Domain Types.- Demonstrations.- PLASMA: A Constraint Based Planning Architecture.- Applying Constraint Satisfaction Techniques to 3D Camera Control.- Adaptive Enterprise Optimization Framework: AEO Server and AEO Studio.- CRE2: A CP Application for Reconfiguring a Power Distribution Network for Power Losses Reduction.- A Constraint-Based Planner Applied to Data Processing Domains.- CLab: A C++ Library for Fast Backtrack-Free Interactive Product Configuration.- A Constraint-Based System for Hiring and Managing Graduate Teaching Assistants.- A Web-Based Meeting Scheduling Solver With Privacy Guarantees, Without Trusted Servers.- A Constraint-Based Graphics Library for B-Prolog.