## Principles and Practice of Constraint Programming - CP 2004: 10th International Conference, CP 2004, Toronto, Canada, September 27 - October 2004, Proceedings, Volume 10The 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. |

### What people are saying - Write a review

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

### Contents

Constraints in Program Analysis and Verification | 1 |

Simplicity of Use | 5 |

Algorithmic Adventures at the Interface of Computer Science Statistical Physics and Combinatorics | 9 |

Challenges for Constraint Programming in Networking | 13 |

Consistency and Random Constraint Satisfaction Models with a High Constraint Tightness | 17 |

Statistical Regimes Across Constrainedness Regions | 32 |

ConstraintBased Combinators for Local Search | 47 |

Unary Resource Constraint with Optional Activities | 62 |

Preprocessing Techniques for Distributed Constraint Optimization | 706 |

Variable Ordering Heuristics Show Promise | 711 |

The Tractability of Global Constraints | 716 |

Support Inference for Generic Filtering | 721 |

Strong CostBased Filtering for Lagrange Decomposition Applied to Network Design | 726 |

The Impact of ANDOR Search Spaces on Constraint Satisfaction and Counting | 731 |

A General Extension of Constraint Propagation for Constraint Optimization | 737 |

How Much Backtracking Does It Take to Color Random Graphs? Rigorous Results on Heavy Tails | 742 |

Constraint Propagation as a Proof System | 77 |

BacktrackFree Search for RealTime Constraint Satisfaction | 92 |

Deriving Filtering Algorithms from Constraint Checkers | 107 |

Leveraging the Learning Power of Examples in Automated Constraint Acquisition | 123 |

Disjoint Partition and Intersection Constraints for Set and Multiset Variables | 138 |

Decomposition and Learning for a Hard Real Time Task Allocation Problem | 153 |

Quantified Constraint Satisfaction and 2Semilattice Polymorphisms | 168 |

Smart LookAhead Arc Consistency and the Pursuit of CSP Tractability | 182 |

Modeling Solution Quality by Extreme Value Theory | 197 |

A Complete Characterization of Complexity for Boolean Constraint Optimization Problems | 212 |

Financial Portfolio Optimisation | 227 |

Bounding the Resource Availability of Partially Ordered Events with Constant Resource Impact | 242 |

Monotone Literals and Learning in QBF Reasoning | 260 |

Streamlined Constraint Reasoning | 274 |

A Domain Consistency Algorithm for the Stretch Constraint | 290 |

A Hybrid Method for Planning and Scheduling | 305 |

CountingBased LookAhead Schemes for Constraint Satisfaction | 317 |

Completable Partial Solutions in Constraint Programming and ConstraintBased Scheduling | 332 |

Set Domain Propagation Using ROBDDs | 347 |

Global Constraints for Integer and Set Value Precedence | 362 |

Quality of LPBased Approximations for Highly Combinatorial Problems | 377 |

Constraint Satisfaction in Semistructured Data Graphs | 393 |

Strategies for Global Optimization of Temporal Preferences | 408 |

A Candidate List Strategy with a Simple Diversification Device | 423 |

Beyond the ClausestoVariables Ratio | 438 |

Symbolic Decision Procedures for QBF | 453 |

Propagation Guided Large Neighborhood Search | 468 |

A Regular Language Membership Constraint for Finite Sequences of Variables | 482 |

Generating Robust Partial Order Schedules | 496 |

Full Dynamic Substitutability by SAT Encoding | 512 |

Improved Bound Computation in Presence of Several Clique Constraints | 527 |

Improved Algorithms for the Global Cardinality Constraint | 542 |

ImpactBased Search Strategies for Constraint Programming | 557 |

The Cardinality Matrix Constraint | 572 |

Controllability of Soft Temporal Constraint Problems | 588 |

Hybrid Set Domains to Strengthen Constraint Propagation and Reduce Symmetries | 604 |

Speeding Up Constraint Propagation | 619 |

Theoretical Foundations of CPBased Lagrangian Relaxation | 634 |

A Constraint for Bin Packing | 648 |

Solving Nonclausal Formulas with DPLL Search | 663 |

A Hyperarc Consistency Algorithm for the Soft Alldifferent Constraint | 679 |

Efficient Strategies for Weighted Maximum Satisfiability | 690 |

Solving the Crane Scheduling Problem Using Intelligent Search Schemes | 747 |

Algorithms for Quantified Constraint Satisfaction Problems | 752 |

Preliminary Results | 757 |

OnDemand Bound Computation for BestFirst Constraint Optimization | 762 |

A New Algorithm for Maintaining Arc Consistency After Constraint Retraction | 767 |

Computing the Frequency of Partial Orders | 772 |

On Tightness of Constraints | 777 |

Concurrent Dynamic Backtracking for Distributed CSPs | 782 |

Set Variables and Local Search | 788 |

NKings for Dynamic Systems | 789 |

Relation Variables in Qualitative Spatial Reasoning | 790 |

Synchronous Asynchronous and Hybrid Algorithms for DisCSP | 791 |

LongTerm Learning for Algorithm Control | 792 |

Solution Extraction with the Critical Path in GraphplanBased Optimal Temporal Planning | 793 |

Machine Learning for Portfolio Selection Using Structure at the Instance Level | 794 |

Local Search with Maximal Independent Sets | 795 |

A Dynamic Restart Strategy for Randomized BT Search | 796 |

A BDDBased Approach to Interactive Conﬁguration | 797 |

Extending Supersolutions | 798 |

Choosing Efficient Representations of Abstract Variables | 799 |

A Hypergraph Separator Based Variable Ordering Heuristic for Solving Real World SAT | 800 |

Exploiting Symmetries via Permutations for PC Board Manufacturing | 801 |

Combining Local Search with Maintaining Arc Consistency and a ConﬂictBased Statistics | 802 |

Programming Robotic Devices with a Timed Concurrent Constraint Language | 803 |

Heuristics for the Distributed Breakout Algorithm | 804 |

Explanations and Numeric CSPs | 805 |

Softly Constrained CP Nets | 806 |

Online Constraint Solving and Rectangle Packing | 807 |

Modelling Chemical Reactions Using Constraint Programming and Molecular Graphs | 808 |

Constraining SpecialPurpose Domain Types | 809 |

A Constraint Based Planning Architecture | 810 |

Applying Constraint Satisfaction Techniques to 3D Camera Control | 811 |

AEO Server and AEO Studio | 812 |

A CP Application for Reconfiguring a Power Distribution Network for Power Losses Reduction | 813 |

A ConstraintBased Planner Applied to Data Processing Domains | 815 |

A C++ Library for Fast BacktrackFree Interactive Product Conﬁguration | 816 |

A ConstraintBased System for Hiring and Managing Graduate Teaching Assistants | 817 |

A WebBased Meeting Scheduling Solver With Privacy Guarantees Without Trusted Servers | 818 |

A ConstraintBased Graphics Library for BProlog | 819 |

820 | |

### Common terms and phrases

applied approach arc consistency Artificial Intelligence assignment Berlin Heidelberg 2004 binary Boolean cardinality clauses combinatorial complexity consider constraint language constraint network Constraint Programming constraint propagation constraint satisfaction problem corresponding cost CSP(B defined denote domain DPLL dynamic efficient encoding example filtering algorithm finite formula function given global constraints graph graph coloring heuristic implementation integer interval iterations labeled Latin square Lemma linear LNCS local search lower bound LP relaxation max-SAT method multiset node NP-hard number of variables OBDDs optimal solution performance polynomial problem instances procedure Proof pruning QCSP quantified random CSP resource ROBDD runtime satisfiability scheduling search space search tree sequence set variables solver solving Springer-Verlag Berlin Heidelberg STPPU straint strategy structure subproblem subset symmetry tasks techniques temporal Theorem tractable tuple unit propagation variable ordering version space