Principles and Practice of Constraint Programming - CP 2004: 10th International Conference, CP 2004, Toronto, Canada, September 27 - October 2004, ProceedingsMark Wallace The 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. |
Contents
Invited Papers | 1 |
Algorithmic Adventures at the Interface of Computer Science | 9 |
Distinguished Papers | 17 |
Statistical Regimes Across Constrainedness Regions | 32 |
17 | 38 |
ConstraintBased Combinators for Local | 47 |
Full Papers | 77 |
BacktrackFree Search for RealTime Constraint Satisfaction | 92 |
Symbolic Decision Procedures for QBF | 453 |
Propagation Guided Large Neighborhood Search | 468 |
A Regular Language Membership Constraint | 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 |
Deriving Filtering Algorithms from Constraint Checkers | 107 |
Leveraging the Learning Power of Examples | 123 |
Disjoint Partition and Intersection Constraints | 138 |
Decomposition and Learning | 153 |
Quantified Constraint Satisfaction and 2Semilattice Polymorphisms | 168 |
Smart LookAhead Arc Consistency | 182 |
A Complete Characterization of Complexity | 212 |
92 | 223 |
Financial Portfolio Optimisation | 227 |
107 | 241 |
Bounding the Resource Availability of Partially Ordered Events | 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 | 332 |
Set Domain Propagation Using ROBDDs | 347 |
Global Constraints for Integer and Set Value Precedence | 362 |
Quality of LPBased Approximations | 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 |
The Cardinality Matrix Constraint | 572 |
Controllability of Soft Temporal Constraint Problems | 588 |
Hybrid Set Domains to Strengthen Constraint Propagation | 604 |
Speeding Up Constraint Propagation | 619 |
Theoretical Foundations of CPBased Lagrangian Relaxation | 634 |
A Constraint for Bin Packing | 648 |
Solving Nonclausal Formulas with DPLL Christian Thiffault Fahiem Bacchus and Toby Walsh Search | 663 |
A Hyperarc Consistency Algorithm for the Soft Alldifferent Constraint | 679 |
Efficient Strategies for Weighted Maximum Satisfiability Zhao Xing and Weixiong Zhang | 690 |
Short Papers | 706 |
The Tractability of Global Constraints | 716 |
Strong CostBased Filtering for Lagrange Decomposition | 726 |
A General Extension of Constraint Propagation | 737 |
Solving the Crane Scheduling Problem Using Intelligent Search Schemes | 747 |
A New Algorithm for Maintaining Arc Consistency | 767 |
On Tightness of Constraints | 777 |
Doctoral Papers | 788 |
Relation Variables in Qualitative Spatial Reasoning | 790 |
A Dynamic Restart Strategy for Randomized BT Search Venkata Praveen Guddeti | 796 |
Combining Local Search | 802 |
Softly Constrained CP Nets | 806 |
A ConstraintBased Graphics Library for BProlog | 819 |
Other editions - View all
Principles and Practice of Constraint Programming - CP 2004: 10th ... Mark Wallace Limited preview - 2005 |
Principles and Practice of Constraint Programming - CP 2004: 10th ... Mark Wallace No preview available - 2004 |
Common terms and phrases
approach arc consistency Artificial Intelligence assignment Berlin Heidelberg 2004 BIBD binary Boolean bound consistency cardinality clauses combinatorial complexity CONACQ consider constraint language constraint network Constraint Programming constraint propagation constraint satisfaction problem corresponding cost CSP(B defined denote distribution domain DPLL dynamic efficient encoding example FCDisjoint filtering algorithm finite formula function given global constraints graph graph coloring heuristic homomorphism implementation integer intersection interval iterations Latin square lb(X Lemma linear LNCS lower bound LP relaxation max-SAT method multimorphism multiset node NP-hard OBDDs optimal solution performance polynomial portfolio problem instances procedure Proof pruning QCSP quantified relational structure resource ROBDD runtime satisfying scheduling search space search tree Section sequence set variables solver solving Springer-Verlag Berlin Heidelberg straint strategy subproblem subset symmetry tasks techniques Theorem tractable tuple ub(X unit propagation upper bound variable ordering version space