Principles and Practice of Constraint Programming - CP 2003: 9th International Conference, CP 2003, Kinsale, Ireland, September 29 - October 3, 2003, Proceedings (Lecture Notes in Computer Science)

This volume contains the proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP 2003), held in Kinsale, Ireland, from September 29 to October 3, 2003. Detailed information about the CP 2003 conference can be found at the URL http://www.cs.ucc.ie/cp2003/ The CP conferences are held annually and provide an international forum for the latest results on all aspects of constraint programming. Previous CP conferences were held in Cassis (France) in 1995, in Cambridge (USA) in 1996, in Schloss Hagenberg (Austria) in 1997, in Pisa (Italy) in 1998, in Alexandria (USA) in 1999, in Singapore in 2000, in Paphos (Cyprus) in 2001, and in Ithaca (USA) in 2002. Like previous CP conferences, CP 2003 again showed the interdisciplinary nature of computing with constraints, and also its usefulness in many problem domains and applications. Constraint programming, with its solvers, languages, theoretical results, and applications, has become a widely recognized paradigm to model and solve successfully many real-life problems, and to reason about problems in many research areas. Front Matter....Pages - Ten Challenges Redux : Recent Progress in Propositional Reasoning and Search....Pages 1-18 Automated Mechanism Design: A New Application Area for Search Algorithms....Pages 19-36 Languages versus Packages for Constraint Problem Solving....Pages 37-52 Constraint Patterns....Pages 53-64 Control Abstractions for Local Search....Pages 65-80 Improved Algorithms for Counting Solutions in Constraint Satisfaction Problems....Pages 81-95 Boosting Chaff’s Performance by Incorporating CSP Heuristics....Pages 96-107 Efficient CNF Encoding of Boolean Cardinality Constraints....Pages 108-122 A Two-Stage Hybrid Algorithm for Pickup and Delivery Vehicle Routing Problems with Time Windows....Pages 123-137 Solving Finite Domain Constraint Hierarchies by Local Consistency and Tree Search....Pages 138-152 hibiscus : A Constraint Programming Application to Staff Scheduling in Health Care....Pages 153-167 Constraint-Based Optimization with the Minimax Decision Criterion....Pages 168-182 An Algebraic Approach to Multi-sorted Constraints....Pages 183-198 Periodic Constraint Satisfaction Problems: Polynomial-Time Algorithms....Pages 199-213 Box Constraint Collections for Adhoc Constraints....Pages 214-228 Propagation Redundancy in Redundant Modelling....Pages 229-243 Soft Constraints: Complexity and Multimorphisms....Pages 244-258 Constraint Satisfaction Differential Problems....Pages 259-273 A Wealth of SAT Distributions with Planted Assignments....Pages 274-287 Redundant Modeling for the QuasiGroup Completion Problem....Pages 288-302 Open Constraint Optimization....Pages 303-317 Constraints for Breaking More Row and Column Symmetries....Pages 318-332 Generic SBDD Using Computational Group Theory....Pages 333-347 Using Stochastic Local Search to Solve Quantified Boolean Formulae....Pages 348-362 Solving Max-SAT as Weighted CSP....Pages 363-376 Constraint Reasoning over Strings....Pages 377-391 Tractability by Approximating Constraint Languages....Pages 392-406 A Hybrid Constraint Programming and Semidefinite Programming Approach for the Stable Set Problem....Pages 407-421 A Constraint-Aided Conceptual Design Environment for Autodesk Inventor....Pages 422-436 Fast Bound Consistency for the Global Cardinality Constraint....Pages 437-451 Propagating N-Ary Rigid-Body Constraints....Pages 452-465 Solving ‘Still Life’ with Soft Constraints and Bucket Elimination....Pages 466-479 Exploiting Multidirectionality in Coarse-Grained Arc Consistency Algorithms....Pages 480-494 Local-Search Techniques for Propositional Logic Extended with Cardinality Constraints....Pages 495-509 Discrepancy-Based Additive Bounding for the AllDifferent Constraint....Pages 510-524 A Synthesis of Constraint Satisfaction and Constraint Solving....Pages 525-539 Maintaining Longest Paths Incrementally....Pages 540-554 Resolution and Constraint Satisfaction....Pages 555-569 Generating High Quality Schedules for a Spacecraft Memory Downlink Problem....Pages 570-584 Symmetry Breaking Using Stabilizers....Pages 585-599 An Efficient Bounds Consistency Algorithm for the Global Cardinality Constraint....Pages 600-614 Solving Existentially Quantified Constraints with One Equality and Arbitrarily Many Inequalities....Pages 615-633 Using Constraint Programming to Solve the Maximum Clique Problem....Pages 634-648 Greater Efficiency for Conditional Constraint Satisfaction....Pages 649-663 Incremental Computation of Resource-Envelopes in Producer-Consumer Models....Pages 664-678 Approximated Consistency for Knapsack Constraints....Pages 679-693 Cost-Based Filtering for Shorter Path Constraints....Pages 694-708 Bounded Backtracking for the Valued Constraint Satisfaction Problems....Pages 709-723 Consistency and Propagation with Multiset Constraints: A Formal Viewpoint....Pages 724-738 Pruning while Sweeping over Task Intervals....Pages 739-753 Improving Backtrack Search for Solving the TCSP....Pages 754-768 Certainty Closure....Pages 769-783 clp(pdf(y)): Constraints for Probabilistic Reasoning in Logic Programming....Pages 784-788 To Be or Not to Be ... a Global Constraint....Pages 789-794 Constraint Programming for Modelling and Solving Modal Satisfiability....Pages 795-800 Distributed Forward Checking....Pages 801-806 A New Class of Binary CSPs for which Arc-Consistency Is a Decision Procedure....Pages 807-811 Semi-automatic Modeling by Constraint Acquisition....Pages 812-816 Structured vs. Unstructured Large Neighborhood Search: A Case Study on Job-Shop Scheduling Problems with Earliness and Tardiness Costs....Pages 817-821 Using the Breakout Algorithm to Identify Hard and Unsolvable Subproblems....Pages 822-826 Toy(FD): Sketch of Operational Semantics....Pages 827-831 Scheduling in the Face of Uncertain Resource Consumption and Utility....Pages 832-836 Supertree Construction with Constraint Programming....Pages 837-841 (In)Effectiveness of Look-Ahead Techniques in a Modern SAT Solver....Pages 842-846 Reduce and Assign: A Constraint Logic Programming and Local Search Integration Framework to Solve Combinatorial Search Problems....Pages 847-852 A Canonicity Test for Configuration....Pages 853-857 Improved Algorithms for Max-restricted Path Consistency....Pages 858-862 CP-IP Techniques for the Bid Evaluation in Combinatorial Auctions....Pages 863-867 A Two-Level Search Strategy for Packing Unequal Circles into a Circle Container....Pages 868-872 Unrestricted Nogood Recording in CSP Search....Pages 873-877 Constraints over Ontologies....Pages 878-882 Using Constraints for Exploring Catalogs....Pages 883-888 Intermediate (Learned) Consistencies....Pages 889-893 Semi-independent Partitioning: A Method for Bounding the Solution to COP’s....Pages 894-898 Boosting as a Metaphor for Algorithm Design....Pages 899-903 An Efficient Filtering Algorithm for Disjunction of Constraints....Pages 904-908 INCOP: An Open Library for INcomplete Combinatorial OPtimization....Pages 909-913 A Composition Algorithm for Very Hard Graph 3-Colorability Instances....Pages 914-919 Efficient Representation of Discrete Sets for Constraint Programming....Pages 920-924 Applying Interchangeability Techniques to the Distributed Breakout Algorithm....Pages 925-929 Symmetry Breaking in Graceful Graphs....Pages 930-934 Tree Local Search....Pages 935-939 A SAT-Based Approach to Multiple Sequence Alignment....Pages 940-944 Maintaining Dominance Consistency....Pages 945-949 Terminating Decision Algorithms Optimally....Pages 950-955 Scene Reconstruction Based on Constraints: Details on the Equation System Decomposition....Pages 956-961 A New Approach to Solving SAT-Encoded Binary CSPs....Pages 962-962 FeReRA: A Multi-agent Approach to Constraint Satisfaction....Pages 963-963 Semantic Decomposition for Solving Distance Constraints....Pages 964-965 Using Constraint Programming and Simulation for Execution Monitoring and On-Line Rescheduling with Uncertainty....Pages 966-966 On the Enhancement of the Informed Backtracking Algorithm....Pages 967-967 Extending CLP with Metaheuristics....Pages 968-968 Self Configuring Constraint Programming Systems....Pages 969-969 Interactive Tradeoff Generation....Pages 970-970 Introducing esra , a Relational Language for Modelling Combinatorial Problems (Abstract)....Pages 971-971 Abstracting Constraints Using Constraints....Pages 972-972 Sensitivity Analysis in CSPs....Pages 973-973 Solution Stability in Constraint Satisfaction Problems....Pages 974-974 distn : An Euclidean Distance Global Constraint....Pages 975-975 Algorithmic Mechanism Design and Constraints....Pages 976-976 Preference Constraints: New Global Soft Constraints Dedicated to Preference Binary Relations....Pages 977-977 Optimising the Representation and Evaluation of Semiring Combination Constraints....Pages 978-978 Symmetry Breaking Ordering Constraints....Pages 979-979 Observation of Constraint Programs....Pages 980-980 Search Programming....Pages 981-981 Exploiting Microstructure in CSPs....Pages 982-982 Using Case-Based Reasoning to Write Constraint Programs....Pages 983-983 Reformulation Techniques for a Class of Permutation Problems....Pages 984-984 NuSBDS: An Easy to Use Symmetry Breaking System....Pages 985-985 Interactivity in Constraint Programming....Pages 986-986 Identifying Inconsistent CSPs by Relaxation....Pages 987-987 Useful Explanations....Pages 988-988 Teacher and Learner Profiles for Constraint Acquisition....Pages 989-989 Comparison of Symmetry Breaking Methods....Pages 990-990 Improved Branch and Bound Algorithms for Max-2-SAT and Weighted Max-2-SAT....Pages 991-991 Search for Mathematical Objects....Pages 992-992 Explanations for Global Constraints....Pages 993-993 Watching Clauses in Quantified Boolean Formulae....Pages 994-994 Distributed Constraint-Based Railway Simulation....Pages 995-995 Dynamic Step Size Adjustment in Iterative Deepening Search....Pages 996-996 Learning Good Variable Orderings....Pages 997-997 An Adaptive Controller for Real-Time Resolution of the Vehicle Routing Problem....Pages 998-998 α -Dynamic Controllability of Simple Temporal Problems with Preferences and Uncertainty....Pages 999-999 Computing Explanations for Global Scheduling Constraints....Pages 1000-1000 Restart Strategies: Analysis and Simulation....Pages 1001-1001 OpenSolver: A Coordination-Enabled Abstract Branch-and-Prune Tree Search Engine....Pages 1002-1002 Back Matter....Pages - This book constitutes the refereed proceedings of the 9th International Conference on Principles and Practice of Constraint Programming, CP 2003, held in Kinsale, Ireland in September/October 2003. The 48 revised full papers and 34 revised short papers presented together with 4 invited papers and 40 abstracts of contributions to the CP 2003 doctoral program were carefully reviewed and selected from 181 submissions. A wealth of recent results in computing with constraints is addressed ranging from foundational and methodological issues to solving real-world problems in a variety of application fields