Principles and Practice of Constraint Programming

1. Front Matter

   PDF

2. Invited Lecture

   1. Back to the Complexity of Universal Programs

      • Alain Colmerauer

      Pages 1-20

3. Applications Track Long Papers

   1. A Constraint Programming Approach for Allocation and Scheduling on the CELL Broadband Engine

      • Luca Benini, Michele Lombardi, Michela Milano, Martino Ruggiero

      Pages 21-35

   2. Planning and Scheduling the Operation of a Very Large Oil Pipeline Network

      • Arnaldo V. Moura, Cid C. de Souza, Andre A. Cire, Tony M. T. Lopes

      Pages 36-51

   3. Search Strategies for Rectangle Packing

      • Helmut Simonis, Barry O’Sullivan

      Pages 52-66

   4. Solving a Telecommunications Feature Subscription Configuration Problem

      • David Lesaint, Deepak Mehta, Barry O’Sullivan, Luis Quesada, Nic Wilson

      Pages 67-81

   5. Protein Structure Prediction with Large Neighborhood Constraint Programming Search

      • Ivan Dotu, Manuel Cebrián, Pascal Van Hentenryck, Peter Clote

      Pages 82-96

   6. An Application of Constraint Programming to Superblock Instruction Scheduling

      • Abid M. Malik, Michael Chase, Tyrel Russell, Peter van Beek

      Pages 97-111

4. Research Track Long Papers

   1. Classes of Submodular Constraints Expressible by Graph Cuts

      • Stanislav Živný, Peter G. Jeavons

      Pages 112-127

   2. Optimization of Simple Tabular Reduction for Table Constraints

      • Christophe Lecoutre

      Pages 128-143

   3. Universal Booleanization of Constraint Models

      • Jinbo Huang

      Pages 144-158

   4. Flow-Based Propagators for the SEQUENCE and Related Global Constraints

      • Michael Maher, Nina Narodytska, Claude-Guy Quimper, Toby Walsh

      Pages 159-174

   5. Guiding Search in QCSP +  with Back-Propagation

      • Guillaume Verger, Christian Bessiere

      Pages 175-189

   6. A New Framework for Sharp and Efficient Resolution of NCSP with Manifolds of Solutions

      • Alexandre Goldsztejn, Laurent Granvilliers

      Pages 190-204

   7. A Branch and Bound Algorithm for Numerical MAX-CSP

      • Jean-Marie Normand, Alexandre Goldsztejn, Marc Christie, Frédéric Benhamou

      Pages 205-219

   8. A Geometric Constraint over k-Dimensional Objects and Shapes Subject to Business Rules

      • Mats Carlsson, Nicolas Beldiceanu, Julien Martin

      Pages 220-234

   9. Cost-Based Domain Filtering for Stochastic Constraint Programming

      • Roberto Rossi, S. Armagan Tarim, Brahim Hnich, Steven Prestwich

      Pages 235-250

   10. Dichotomic Search Protocols for Constrained Optimization

       • Meinolf Sellmann, Serdar Kadioglu

       Pages 251-265

   11. Length-Lex Bounds Consistency for Knapsack Constraints

       • Yuri Malitsky, Meinolf Sellmann, Willem-Jan van Hoeve

       Pages 266-281

   12. A Framework for Hybrid Tractability Results in Boolean Weighted Constraint Satisfaction Problems

       • T. K. Satish Kumar

       Pages 282-297

This 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.

• CSP heuristics
• Constraint
• SAT solvers
• algorithms
• approximability
• complexity
• con
• constraint logic programming
• knapsack
• protein structure
• qcsp
• rectangle packing
• submodular constraints
• superblock instruction scheduling
• table constraints

Policies and ethics