Principles and Practice of Constraint Programming – CP 2007: 13th International Conference, CP 2007, Providence, RI, USA, September 23-27, 2007. Proceedings

Fahiem Bacchus (auth.), Christian Bessière (eds.)3540749691, 9783540749691

The 13th International Conference on Principles and Practice of Constraint Programming (CP 2007) was held in Providence, RI, USA, September 23–27, 2007, in conjunction with the International Conference on Automated Pl- ning and Scheduling (ICAPS). 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 conference – ries is organized by the Association for Constraint Programming (ACP). – formation 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 2007 launched two calls for contributions: a call for research papers, describing novel contributions in the ?eld, and a call for application papers, describing applications of constraint technology in the industrial world. The research track received 143 submissions and the application track received 22 submissions. Research papers were reviewed under a double-blind scheme. They received three reviews that the authors had the opportunity to see and to react tobeforethepapersandtheirreviewswerediscussedextensivelybythemembers of the ProgramCommittee. Application papers werereviewedby a separate- plication Committee. The Program Committee and the Application Committee then selected 43 researchpapers and 9 application papers to be published in full inthe proceedings,andanadditional14researchpapersto be publishedas short papers. The full papers were presented at the conference in two parallel tracks and the short papers were presented in a poster session.

---

Table of contents :
Front Matter….Pages –
Caching in Backtracking Search….Pages 1-1
Of Mousetraps and Men: A Cautionary Tale….Pages 2-2
Estimation of the Minimal Duration of an Attitude Change for an Autonomous Agile Earth-Observing Satellite….Pages 3-17
Solving an Air Conditioning System Problem in an Embodiment Design Context Using Constraint Satisfaction Techniques….Pages 18-32
Solving the Salinity Control Problem in a Potable Water System….Pages 33-48
Exploring Different Constraint-Based Modelings for Program Verification….Pages 49-63
An Application of Constraint Programming to Generating Detailed Operations Schedules for Steel Manufacturing….Pages 64-76
An Efficient Model and Strategy for the Steel Mill Slab Design Problem….Pages 77-89
Constraint-Based Temporal Reasoning for E-Learning with LODE ….Pages 90-104
Scheduling for Cellular Manufacturing….Pages 105-117
A Constraint Store Based on Multivalued Decision Diagrams….Pages 118-132
GAC Via Unit Propagation….Pages 133-147
Solution Directed Backjumping for QCSP….Pages 148-163
Reformulating CSPs for Scalability with Application to Geospatial Reasoning….Pages 164-179
A Generic Geometrical Constraint Kernel in Space and Time for Handling Polymorphic k -Dimensional Objects….Pages 180-194
Local Symmetry Breaking During Search in CSPs….Pages 195-209
Encodings of the Sequence Constraint….Pages 210-224
On Inconsistent Clause-Subsets for Max-SAT Solving….Pages 225-240
An Abstract Interpretation Based Combinator for Modelling While Loops in Constraint Programming….Pages 241-255
Tradeoffs in the Complexity of Backdoor Detection….Pages 256-270
Model-Driven Visualizations of Constraint-Based Local Search….Pages 271-285
Dealing with Incomplete Preferences in Soft Constraint Problems….Pages 286-300
Efficient Computation of Minimal Point Algebra Constraints by Metagraph Closure….Pages 301-316
MUST: Provide a Finer-Grained Explanation of Unsatisfiability….Pages 317-331
An Integrated White+Black Box Approach for Designing and Tuning Stochastic Local Search….Pages 332-347
Limitations of Restricted Branching in Clause Learning….Pages 348-363
Dynamic Management of Heuristics for Solving Structured CSPs….Pages 364-378
A Compression Algorithm for Large Arity Extensional Constraints….Pages 379-393
Valid Inequality Based Lower Bounds for WCSP….Pages 394-408
Advisors for Incremental Propagation….Pages 409-422
Breaking Symmetry of Interchangeable Variables and Values….Pages 423-437
Path Consistency by Dual Consistency….Pages 438-452
Exploiting Past and Future: Pruning by Inconsistent Partial State Dominance….Pages 453-467
Scheduling Conditional Task Graphs….Pages 468-482
Towards Robust CNF Encodings of Cardinality Constraints….Pages 483-497
AND/OR Multi-valued Decision Diagrams for Constraint Optimization….Pages 498-513
Parallelizing Constraint Programs Transparently….Pages 514-528
MiniZinc: Towards a Standard CP Modelling Language….Pages 529-543
Propagation = Lazy Clause Generation….Pages 544-558
Boosting Probabilistic Choice Operators….Pages 559-573
A Multi-engine Solver for Quantified Boolean Formulas….Pages 574-589
Decomposing Global Grammar Constraints….Pages 590-604
Structural Relaxations by Variable Renaming and Their Compilation for Solving MinCostSAT….Pages 605-619
Bound-Consistent Deviation Constraint….Pages 620-634
Constructive Interval Disjunction….Pages 635-650
An LP-Based Heuristic for Optimal Planning….Pages 651-665
A Cost-Based Model and Algorithms for Interleaving Solving and Elicitation of CSPs….Pages 666-680
On Universal Restart Strategies for Backtracking Search….Pages 681-695
Hierarchical Hardness Models for SAT….Pages 696-711
SATzilla-07 : The Design and Analysis of an Algorithm Portfolio for SAT….Pages 712-727
Filtering for Subgraph Isomorphism….Pages 728-742
Solution Counting Algorithms for Constraint-Centered Search Heuristics….Pages 743-757
Min-Domain Ordering for Asynchronous Backtracking….Pages 758-772
Answer Set Optimization for and/or Composition of CP-Nets: A Security Scenario….Pages 773-781
Uncertainty in Bipolar Preference Problems….Pages 782-789
An Analysis of Slow Convergence in Interval Propagation….Pages 790-797
The Expressive Power of Valued Constraints: Hierarchies and Collapses….Pages 798-805
Eligible and Frozen Constraints for Solving Temporal Qualitative Constraint Networks….Pages 806-814
The Log-Support Encoding of CSP into SAT….Pages 815-822
Groupoids and Conditional Symmetry….Pages 823-830
Sampling Strategies and Variable Selection in Weighted Degree Heuristics….Pages 831-838
A Case for Simple SAT Solvers….Pages 839-846
CP-Based Local Branching….Pages 847-855
Strong Controllability of Disjunctive Temporal Problems with Uncertainty….Pages 856-863
Exploiting Single-Cycle Symmetries in Branch-and-Prune algorithms….Pages 864-871
Constraint Symmetry for the Soft CSP….Pages 872-879
Breaking Value Symmetry….Pages 880-887
Back Matter….Pages –