Principles and Practice of Constraint Programming – CP 2003: 9th International Conference, CP 2003, Kinsale, Ireland, September 29 – October 3, 2003. Proceedings

Henry Kautz, Bart Selman (auth.), Francesca Rossi (eds.)3540202021, 9783540202028

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.

---

Table of contents :
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 –