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

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 -