## Principles and Practice of Constraint Programming - CP 2003: 9th International Conference, CP 2003, Kinsale, Ireland, September 29 - October 3, 2003, Proceedings, Volume 9This 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Recent Progress in Propositional Reasoning and Search | 1 |

A New Application Area for Search Algorithms | 19 |

Languages versus Packages for Constraint Problem Solving | 37 |

Constraint Patterns | 53 |

Control Abstractions for Local Search | 65 |

Improved Algorithms for Counting Solutions in Constraint Satisfaction Problems | 81 |

Boosting Chaffs Performance by Incorporating CSP Heuristics | 96 |

Efﬁcient CNF Encoding of Boolean Cardinality Constraints | 108 |

Improved Algorithms for Maxrestricted Path Consistency | 858 |

CPIP Techniques for the Bid Evaluation in Combinatorial Auctions | 863 |

A TwoLevel Search Strategy for Packing Unequal Circles into a Circle Container | 868 |

Unrestricted Nogood Recording in CSP Search | 873 |

Constraints over Ontologies | 878 |

Using Constraints for Exploring Catalogs | 883 |

Intermediate Learned Consistencies | 889 |

A Method for Bounding the Solution to COPs | 894 |

A TwoStage Hybrid Algorithm for Pickup and Delivery Vehicle Routing Problems with Time Windows | 123 |

Solving Finite Domain Constraint Hierarchies by Local Consistency and Tree Search | 138 |

A Constraint Programming Application to Staff Scheduling in Health Care | 153 |

ConstraintBased Optimization with the Minimax Decision Criterion | 168 |

An Algebraic Approach to Multisorted Constraints | 183 |

Periodic Constraint Satisfaction Problems | 199 |

Box Constraint Collections for Adhoc Constraints | 214 |

Propagation Redundancy in Redundant Modelling | 229 |

Complexity and Multimorphisms | 244 |

Constraint Satisfaction Differential Problems | 259 |

A Wealth of SAT Distributions with Planted Assignments | 274 |

Redundant Modeling for the QuasiGroup Completion Problem | 288 |

Open Constraint Optimization | 303 |

Constraints for Breaking More Row and Column Symmetries | 318 |

Generic SBDD Using Computational Group Theory | 333 |

Using Stochastic Local Search to Solve Quantiﬁed Boolean Formulae | 348 |

Solving MaxSAT as Weighted CSP | 363 |

Constraint Reasoning over Strings | 377 |

Tractability by Approximating Constraint Languages | 392 |

A Hybrid Constraint Programming and Semideﬁnite Programming Approach for the Stable Set Problem | 407 |

A ConstraintAided Conceptual Design Environment for Autodesk Inventor | 422 |

Fast Bound Consistency for the Global Cardinality Constraint | 437 |

Propagating NAry RigidBody Constraints | 452 |

Solving Still Life with Soft Constraints and Bucket Elimination | 466 |

Exploiting Multidirectionality in CoarseGrained Arc Consistency Algorithms | 480 |

LocalSearch Techniques for Propositional Logic Extended with Cardinality Constraints | 495 |

DiscrepancyBased Additive Bounding for the AllDifferent Constraint | 510 |

A Synthesis of Constraint Satisfaction and Constraint Solving | 525 |

Resolution and Constraint Satisfaction | 555 |

Generating High Quality Schedules for a Spacecraft Memory Downlink Problem | 570 |

Symmetry Breaking Using Stabilizers | 585 |

An Efficient Bounds Consistency Algorithm for the Global Cardinality Constraint | 600 |

Using Constraint Programming to Solve the Maximum Clique Problem | 634 |

Greater Efficiency for Conditional Constraint Satisfaction | 649 |

Incremental Computation of ResourceEnvelopes in ProducerConsumer Models | 664 |

Approximated Consistency for Knapsack Constraints | 679 |

CostBased Filtering for Shorter Path Constraints | 694 |

Bounded Backtracking for the Valued Constraint Satisfaction Problems | 709 |

Consistency and Propagation with Multiset Constraints | 724 |

Pruning while Sweeping over Task Intervals | 739 |

Improving Backtrack Search for Solving the TCSP | 754 |

Certainty Closure A Framework for Reliable Constraint Reasoning with Uncertainty | 769 |

Constraints for Probabilistic Reasoning in Logic Programming | 784 |

Constraint Programming for Modelling and Solving Modal Satisﬁability | 795 |

Distributed Forward Checking | 801 |

A New Class of Binary CSPs ArcConsistency Is a Decision for which Procedure | 807 |

Semiautomatic Modeling by Constraint Acquisition | 812 |

A Case Study on JobShop Scheduling Problems with Earliness and Tardiness Costs | 817 |

Using the Breakout Algorithm to Identify Hard and Unsolvable Subproblems | 822 |

Scheduling in the Face of Uncertain Resource Consumption and Utility | 832 |

Supertree Construction with Constraint Programming | 837 |

InEffectiveness of LookAhead Techniques in a Modern SAT Solver | 842 |

A Constraint Logic Programming and Local Search Integration Framework to Solve Combinatorial Search Problems | 847 |

A Canonicity Test for Conﬁguration | 853 |

Boosting as a Metaphor for Algorithm Design | 899 |

An Efficient Filtering Algorithm for Disjunction of Constraints | 904 |

An Open Library for INcomplete Combinatorial OPtimization | 909 |

A Composition Algorithm for Very Hard Graph 3Colorability Instances | 914 |

Efficient Representation of Discrete Sets for Constraint Programming | 920 |

Applying Interchangeability Techniques to the Distributed Breakout Algorithm | 925 |

Symmetry Breaking in Graceful Graphs | 930 |

Tree Local Search | 935 |

A SATBased Approach to Multiple Sequence Alignment | 940 |

Maintaining Dominance Consistency | 945 |

Terminating Decision Algorithms Optimally | 950 |

Scene Reconstruction Based on Constraints | 956 |

A New Approach to Solving SATEncoded Binary CSPs | 962 |

A Multiagent Approach to Constraint Satisfaction | 963 |

Semantic Decomposition for Solving Distance Constraints | 964 |

Using Constraint Programming and Simulation for Execution Monitoring and OnLine Rescheduling with Uncertainty | 966 |

On the Enhancement of the Informed Backtracking Algorithm | 967 |

Extending CLP with Metaheuristics | 968 |

Self Conﬁguring Constraint Programming Systems | 969 |

Interactive Tradeoff Generation | 970 |

Introducing esra a Relational Language for Modelling Combinatorial Problems Abstract | 971 |

Abstracting Constraints Using Constraints | 972 |

Sensitivity Analysis in CSPs | 973 |

Solution Stability in Constraint Satisfaction Problems | 974 |

An Euclidean Distance Global Constraint | 975 |

Algorithmic Mechanism Design and Constraints | 976 |

New Global Soft Constraints Dedicated to Preference Binary Relations | 977 |

Optimising the Representation and Evaluation of Semiring Combination Constraints | 978 |

Symmetry Breaking Ordering Constraints | 979 |

Observation of Constraint Programs | 980 |

Search Programming | 981 |

Exploiting Microstructure in CSPs | 982 |

Using CaseBased Reasoning to Write Constraint Programs | 983 |

Reformulation Techniques for a Class of Permutation Problems | 984 |

An Easy to Use Symmetry Breaking System | 985 |

Interactivity in Constraint Programming | 986 |

Identifying Inconsistent CSPs by Relaxation | 987 |

Useful Explanations | 988 |

Teacher and Learner Proﬁles for Constraint Acquisition | 989 |

Comparison of Symmetry Breaking Methods | 990 |

Improved Branch and Bound Algorithms for Max2SAT and Weighted Max2SAT | 991 |

Search for Mathematical Objects | 992 |

Explanations for Global Constraints | 993 |

Watching Clauses in Quantiﬁed Boolean Formulae | 994 |

Distributed ConstraintBased Railway Simulation | 995 |

Dynamic Step Size Adjustment in Iterative Deepening Search | 996 |

Learning Good Variable Orderings | 997 |

An Adaptive Controller for RealTime Resolution of the Vehicle Routing Problem | 998 |

αDynamic Controllability of Simple Temporal Problems with Preferences and Uncertainty | 999 |

Computing Explanations for Global Scheduling Constraints | 1000 |

Analysis and Simulation | 1001 |

A CoordinationEnabled Abstract BranchandPrune Tree Search Engine | 1002 |

Author Index | 1003 |

### Other editions - View all

Principles and Practice of Constraint Programming - CP 2003: 9th ... Francesca Rossi Limited preview - 2003 |

Principles and Practice of Constraint Programming - CP 2003: 9th ..., Volume 9 Francesca Rossi No preview available - 2003 |

### Common terms and phrases

agents applied approach arc consistency Artificial Intelligence assignment atom backtracking Berlin Heidelberg 2003 binary Boolean checks clauses closure column combinatorial complexity Computer Science configuration consider constraint language constraint network Constraint Programming constraint propagation constraint satisfaction problem corresponding cost CPLEX defined Definition denote edge efficient encoding example finite domain formula function given global graph heuristic implementation instances instantiation integer interval iteration Lemma linear LNCS local search lower bound matrix metaheuristics method multiset node nogood NP-complete NP-hard operation optimal paper parameters path performance permutation PLcc polynomial Practice of Constraint Proc procedure Proof properties propositional pruning random relations relaxation represent Rossi SAT solvers satisfiability SBDD scheduling Section semidefinite programming sequence solution solving Springer-Verlag Berlin Heidelberg straint structure subproblems subset symmetry breaking techniques Theorem tractable tree tuple unit propagation variables WalkSAT