## Principles and Practice of Constraint Programming: 14th International Conference, CP 2008, Sydney, Australia, September 14-18, 2008, ProceedingsThis volume contains the proceedings of the 14th International Conference on Principles and Practice of Constraint Programming (CP 2008) held in Sydney, Australia, September 14–18, 2008. The conference was held in conjunction with the International Conference on Automated Planning and Scheduling (ICAPS 2008) and the International Conference on Knowledge Representation and R- soning (KR 2008). Information about the conference can be found at the w- sitehttp://www. unimelb. edu. au/cp2008/. Held annually, the CP conference series is the premier international conference on constraint programming. The conference focuses on all aspects of computing with constraints. The CP conf- ence series is organized by the Association for Constraint Programming (ACP). Information about the conferences in the series can be found on the Web at http://www. cs. ualberta. ca/~ai/cp/. Information about ACP can be found athttp://www. a4cp. org/. CP 2008 included two calls for contributions: a call for research papers, - scribing novel contributions in the ?eld, and a call for application papers, - scribing applications of constraint technology. For the ?rst time authors could directly submit short papers for consideration by the committee. The research track received 84 long submissions and 21 short submissions and the application track received 15 long submissions. Each paper received at least three reviews, which the authors had the opportunity to see and to react to, before the papers and their reviews were discussed extensively by the members of the Program Committee. |

### What people are saying - Write a review

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

### Contents

Back to the Complexity of Universal Programs | 1 |

A Constraint Programming Approach for Allocation and Scheduling on the CELL Broadband Engine | 21 |

Planning and Scheduling the Operation of a Very Large Oil Pipeline Network | 36 |

Search Strategies for Rectangle Packing | 52 |

Solving a Telecommunications Feature Subscription Conﬁguration Problem | 67 |

Protein Structure Prediction with Large Neighborhood Constraint Programming Search | 82 |

An Application of Constraint Programming to Superblock Instruction Scheduling | 97 |

Classes of Submodular Constraints Expressible by Graph Cuts | 112 |

Quantiﬁed Constraint Optimization | 463 |

Exploiting Decomposition in Constraint Optimization Problems | 478 |

A Coinduction Rule for Entailment of Recursively Deﬁned Properties | 493 |

Maintaining Generalized Arc Consistency on Ad Hoc rAry Constraints | 509 |

Perfect Constraints Are Tractable | 524 |

Effciently Solving Problems Where the Solutions Form a Group | 529 |

Approximate Solution Sampling and Counting on ANDOR Spaces | 534 |

Model Restarts for Structural Symmetry Breaking | 539 |

Optimization of Simple Tabular Reduction for Table Constraints | 128 |

Universal Booleanization of Constraint Models | 144 |

FlowBased Propagators for the SEQUENCE and Related Global Constraints | 159 |

Guiding Search in QCSP+ with BackPropagation | 175 |

A New Framework for Sharp and Efficient Resolution of NCSP with Manifolds of Solutions | 190 |

A Branch and Bound Algorithm for Numerical MAXCSP | 205 |

A Geometric Constraint over kDimensional Objects and Shapes Subject to Business Rules | 220 |

CostBased Domain Filtering for Stochastic Constraint Programming | 235 |

Dichotomic Search Protocols for Constrained Optimization | 251 |

LengthLex Bounds Consistency for Knapsack Constraints | 266 |

A Framework for Hybrid Tractability Results in Boolean Weighted Constraint Satisfaction Problems | 282 |

From High Girth Graphs to Hard Instances | 298 |

Switching among NonWeighting Clause Weighting and Variable Weighting in Local Search for SAT | 313 |

A ConstraintProgramming Framework for Bounded Program Veriﬁcation | 327 |

Exploiting Common Subexpressions in Numerical CSPs | 342 |

Complexity and Approximability | 358 |

Structural Tractability of Propagated Constraints | 372 |

Connecting ABT with Arc Consistency | 387 |

Algorithms and Experimental Studies | 402 |

Reformulating Positive Table Constraints Using Functional Dependencies | 418 |

Relaxations for Compiled OverConstrained Problems | 433 |

Approximate Compilation of Constraints into Multivalued Decision Diagrams | 448 |

An Elimination Algorithm for Functional Constraints | 545 |

Crossword Puzzles as a Constraint Problem | 550 |

Recent Hybrid Techniques for the MultiKnapsack Problem | 555 |

Edge Matching Puzzles as Hard SATCSP Benchmarks | 560 |

Test Strategy Generation Using Quantiﬁed CSPs | 566 |

Perfect Derived Propagators | 571 |

Reﬁned Bounds for InstanceBased Search Complexity of Counting and Other P Problems | 576 |

Transforming Inconsistent Subformulas in MaxSAT Lower Bound Computation | 582 |

Semiautomatic Generation of CHR Solvers for Global Constraints | 588 |

Stochastic Local Search for the Optimal Winner Determination Problem in Combinatorial Auctions | 593 |

Revisiting the Upper Bounding Process in a Safe Branch and Bound Algorithm | 598 |

Computing All Optimal Solutions in Satisﬁability Problems with Preferences | 603 |

On the Efficiency of Impact Based Heuristics | 608 |

Probabilistically Estimating Backbones and Variable Bias Experimental Overview | 613 |

A New Empirical Study of Weak Backdoors | 618 |

Adding Search to Zinc | 624 |

Experimenting with Small Changes in ConﬂictDriven Clause Learning Algorithms | 630 |

Search Space Reduction for Constraint Optimization Problems | 635 |

Engineering Stochastic Local Search for the Low Autocorrelation Binary Sequence Problem | 640 |

Author Index | 646 |

### Other editions - View all

Principles and Practice of Constraint Programming: 14th International ... Peter J. Stuckey No preview available - 2009 |

### Common terms and phrases

AAAI applied approach arc consistency arity Artiﬁcial Intelligence assignment backtracking benchmarks Berlin Heidelberg 2008 binary bipartite graph Boolean Boolean domain branch and bound clause weights compilation complete compute conﬁguration consider constraint network constraint programming constraint satisfaction problems corresponding cost function CPBPV CSP instances decomposition deﬁned Deﬁnition denote diﬀerent edge eﬃcient encoding example ﬁnd ﬁnding ﬁnite ﬁrst ﬁxed ﬂow given global constraints graph Heidelberg heuristic implementation integer interval knapsack linear LNCS local search lower bound maximal method minimal NCVW nodes nogood NP-hard operations optimal solution P.J. Stuckey parallelepiped parallelepiped domains parameters performance pipeline polynomial proof propagation pruning QCSP QCSP+ quantiﬁed random recursive relaxation representation satisﬁed scheduling search space search tree sequence solved solver speciﬁc Springer stochastic straint strategy structure submodular subset superblock table constraints techniques Theorem tractable tuples upper bound vertex WCSP