CP2008 Post Proceedings
This is the post proceedings of the
14th International Conference on Principles and
Practice of Constraint Programming. The post proceedings contains the
presentations for the papers as they appeared at the conference as well as
links to supplementary material, when supplied by the authors. The
presentations are organized as they appeared in the conference.
The conference proceedings
are published by Springer Verlag in the
Lecture Notes in Computer Science
series as LNCS 5202. It is available online: see
information about it
or access the
online version.
Special Presentations
Invited Talk: Adnan Darwiche
This talk was a joint invited talk with KR 2008.
| Title | Satisfiability, Knowledge Compilation and the Journey Towards Universal Reasoning Engines |
| Authors | Adnan Darwiche |
| Presentation | [PDF] |
Invited Talk: John Hooker
This talk was a joint invited talk with ICAPS 2008.
| Title | How To Relax |
| Authors | John Hooker |
| Presentation | [PDF] |
Invited Talk: Alain Colmerauer
| Title | Back to the Complexity of Universal Programs |
| Author | Alain Colmerauer |
| DOI | 10.1007/978-3-540-85958-1_1 |
| Presentation | [PDF] |
ACP Research Excellence Award: Alain Colmerauer
Alain Colmerauer one of the founding fathers of the field, and indeed
the person with the strongest claim to have actually invented constraint
programming, was awarded the ACP award for research excellence. He made this
presentation in accepting his award.
| Title | My Happy Constribution to Constraint Programming |
| Authors | Alain Colmerauer |
| Presentation | [PDF] |
ACP Best Thesis Award: Claude-Guy Quimper
The inaugural award from the ACP, for the best thesis
in constraint programming was awarded to Clause-Guy Quimper.
This is the presentation he made.
| Title | Efficient Propagators for Global Constraints |
| Authors | Claude-Guy Quimper |
| Presentation | [PDF] |
Long papers
There were 33 long papers presented in 30 minute slots at the conference.
There were 27 research papers and 6 applications papers.
The papers were organized into sessions of 2 and 3 papers, and are presented
here in this organization.
Numerical CSPs
The following paper was awarded the prize for the
best research paper.
| Title | A New Framework for Sharp and Efficient Resolution of NCSP with Manifolds of Solutions |
| Authors | Alexandre Goldsztejn and Laurent Granvilliers |
| DOI | 10.1007/978-3-540-85958-1_13 |
| Presentation | [PDF] |
The following paper was awarded the ACP prize for the
best student paper.
| Title | A Branch and Bound Algorithm for Numerical MAX-CSP |
| Authors | Jean-Marie Normand, Alexandre Goldsztejn, Marc Christie and Frédéric Benhamou |
| DOI | 10.1007/978-3-540-85958-1_14 |
| Presentation | [PDF] |
| Title | Exploiting Common Subexpressions in Numerical CSPs |
| Authors | Ignacio Araya, Bertrand Neveu and Gilles Trombettoni |
| DOI | 10.1007/978-3-540-85958-1_23 |
| Presentation | [PDF] |
Applications 1
| Title | Protein Structure Prediction with Large Neighborhood Constraint Programming Search |
| Authors | Ivan Dotu, Manuel Cebrián, Pascal Van Hentenryck and Peter Clote |
| DOI | 10.1007/978-3-540-85958-1_6 |
| Presentation | [PDF] |
| Title | Solving a Telecommunications Feature Subscription Configuration Problem |
| Authors | David Lesaint, Deepak Mehta, Barry O'Sullivan, Luis Quesada and Nic Wilson |
| DOI | 10.1007/978-3-540-85958-1_5 |
| Presentation | [PDF] |
| Title | A Constraint Programming Approach for Allocation and Scheduling on the CELL Broadband Engine |
| Authors | Luca Benini, Michele Lombardi, Michela Milano and Martino Ruggiero |
| DOI | 10.1007/978-3-540-85958-1_2 |
| Presentation | [PDF] |
QCSP
| Title | Guiding Search in QCSP+ with Back-Propagation |
| Authors | Guillaume Verger and Christian Bessiere |
| DOI | 10.1007/978-3-540-85958-1_12 |
| Presentation | [PDF] |
| Title | Quantified Constraint Optimization |
| Authors | Marco Benedetti, Arnaud Lallouet and Jérémie Vautard |
| DOI | 10.1007/978-3-540-85958-1_31 |
| Presentation | [PDF] |
Verification
| Title | CPBPV: A Constraint-Programming Framework for Bounded Program Verification |
| Authors | Hélène Collavizza, Michel Rueher and Pascal Van Hentenryck |
| DOI | 10.1007/978-3-540-85958-1_22 |
| Presentation | [PDF] |
| Title | A Coinduction Rule for Entailment of Recursively Defined Properties |
| Authors | Joxan Jaffar, Andrew E. Santosa and Räzvan Voicu |
| DOI | 10.1007/978-3-540-85958-1_33 |
| Presentation | [PDF] |
Advanced Propagation
| Title | Approximate Compilation of Constraints into Multivalued Decision Diagrams |
| Authors | Tarik Hadzic, John N. Hooker, Barry O'Sullivan and Peter Tiedemann |
| DOI | 10.1007/978-3-540-85958-1_30 |
| Presentation | [PDF] |
| Title | Cost-Based Domain Filtering for Stochastic Constraint Programming |
| Authors | Roberto Rossi, S. Armagan Tarim, Brahim Hnich and Steven Prestwich |
| DOI | 10.1007/978-3-540-85958-1_16 |
| Presentation | [PDF] |
| Title | Connecting ABT with Arc Consistency |
| Authors | Ismel Brito and Pedro Meseguer |
| DOI | 10.1007/978-3-540-85958-1_26 |
| Presentation | [PDF] |
Applications 2
The following paper was awarded the prize for the
best applications paper.
| Title | Planning and Scheduling the Operation of a Very Large Oil Pipeline Network |
| Authors | Arnaldo V. Moura, Cid C. de Souza, Andre A. Cire and Tony M. T. Lopes |
| DOI | 10.1007/978-3-540-85958-1_3 |
| Presentation | [PDF] |
| Title | An Application of Constraint Programming to Superblock Instruction Scheduling |
| Authors | Abid M. Malik, Michael Chase, Tyrel Russell and Peter van Beek |
| DOI | 10.1007/978-3-540-85958-1_7 |
| Presentation | [PDF] |
| Supp. Mat. | Software and Benchmark Instances |
| Title | Search Strategies for Rectangle Packing |
| Authors | Helmut Simonis and Barry O'Sullivan |
| DOI | 10.1007/978-3-540-85958-1_4 |
| Presentation | [PDF] |
Table Constraints
| Title | Reformulating Positive Table Constraints Using Functional Dependencies |
| Authors | Hadrien Cambazard and Barry O'Sullivan |
| DOI | 10.1007/978-3-540-85958-1_28 |
| Presentation | [PDF] |
| Title | Optimization of Simple Tabular Reduction for Table Constraints |
| Author | Christophe Lecoutre |
| DOI | 10.1007/978-3-540-85958-1_9 |
| Presentation | [PDF] |
| Title | Maintaining Generalized Arc Consistency on Ad Hoc r -Ary Constraints |
| Authors | Kenil C. K. Cheng and Roland H. C. Yap |
| DOI | 10.1007/978-3-540-85958-1_34 |
| Presentation | [PPT][PDF] |
Tractability
| Title | Classes of Submodular Constraints Expressible by Graph Cuts |
| Authors | Stanislav Zivny and Peter G. Jeavons |
| DOI | 10.1007/978-3-540-85958-1_8 |
| Presentation | [PDF] |
| Title | Structural Tractability of Propagated Constraints |
| Authors | Martin J. Green and Christopher Jefferson |
| DOI | 10.1007/978-3-540-85958-1_25 |
| Presentation | [PDF] |
| Title | A Framework for Hybrid Tractability Results in Boolean Weighted Constraint Satisfaction Problems |
| Author | T. K. Satish Kumar |
| DOI | 10.1007/978-3-540-85958-1_19 |
| Presentation | [N/A] |
Optimization
| Title | Dichotomic Search Protocols for Constrained Optimization |
| Authors | Meinolf Sellmann and Serdar Kadioglu |
| DOI | 10.1007/978-3-540-85958-1_17 |
| Presentation | [PDF] |
| Title | Exploiting Decomposition in Constraint Optimization Problems |
| Authors | Matthew Kitching and Fahiem Bacchus |
| DOI | 10.1007/978-3-540-85958-1_32 |
| Presentation | [N/A] |
Global Constraints
| Title | Flow-Based Propagators for the SEQUENCE and Related Global Constraints |
| Authors | Michael Maher, Nina Narodytska, Claude-Guy Quimper and Toby Walsh |
| DOI | 10.1007/978-3-540-85958-1_11 |
| Presentation | [PDF][PPT] |
| Title | Length-Lex Bounds Consistency for Knapsack Constraints |
| Authors | Yuri Malitsky, Meinolf Sellmann and Willem-Jan van Hoeve |
| DOI | 10.1007/978-3-540-85958-1_18 |
| Presentation | [PDF] |
| Title | A Geometric Constraint over k -Dimensional Objects and Shapes Subject to Business Rules |
| Authors | Mats Carlsson, Nicolas Beldiceanu and Julien Martin |
| DOI | 10.1007/978-3-540-85958-1_15 |
| Presentation | [PDF] |
Soft, Fuzzy and Weighted CSP
| Title | A Soft Constraint of Equality: Complexity and Approximability |
| Authors | Emmanuel Hebrard, Barry O'Sullivan and Igor Razgon |
| DOI | 10.1007/978-3-540-85958-1_24 |
| Presentation | [PDF] |
| Title | Relaxations for Compiled Over-Constrained Problems |
| Authors | Alexandre Papadopoulos and Barry O'Sullivan |
| DOI | 10.1007/978-3-540-85958-1_29 |
| Presentation | [PDF] |
| Title | Elicitation Strategies for Fuzzy Constraint Problems with Missing Preferences: Algorithms and Experimental Studies |
| Authors | Mirco Gelain, Maria Silvia Pini, Francesca Rossi, K. Brent Venable and Toby Walsh |
| DOI | 10.1007/978-3-540-85958-1_27 |
| Presentation | [PDF] |
SAT
| Title | Switching among Non-Weighting, Clause Weighting, and Variable Weighting in Local Search for SAT |
| Authors | Wanxia Wei, Chu Min Li and Harry Zhang |
| DOI | 10.1007/978-3-540-85958-1_21 |
| Presentation | [PPT][PDF] |
| Supp. Mat. | Errata |
| Title | From High Girth Graphs to Hard Instances |
| Authors | Carlos Ansótegui, Ramón Béjar, César Fernàndez and Carles Mateu |
| DOI | 10.1007/978-3-540-85958-1_20 |
| Presentation | [PDF] |
| Title | Universal Booleanization of Constraint Models |
| Author | Jinbo Huang |
| DOI | 10.1007/978-3-540-85958-1_10 |
| Presentation | [PDF] |
Short Papers
There were 23 short research papers, which were presented during a
poster session, together with posters from ICAPS 2008. They are listed
here in alphabetical order of title.
| Title | A New Empirical Study of Weak Backdoors |
| Authors | Peter Gregory, Maria Fox and Derek Long |
| DOI | 10.1007/978-3-540-85958-1_53 |
| Presentation | [N/A] |
The following paper was awarded the prize for the
best poster
by voting by the conference attendees.
| Title | Adding Search to Zinc |
| Authors | Reza Rafeh, Kim Marriott, Maria Garcia de la Banda, Nicholas Nethercote and Mark Wallace |
| DOI | 10.1007/978-3-540-85958-1_54 |
| Presentation | [PDF] |
| Title | An Elimination Algorithm for Functional Constraints |
| Authors | Yuanlin Zhang, Roland H. C. Yap, Chendong Li and Satyanarayana Marisetti |
| DOI | 10.1007/978-3-540-85958-1_39 |
| Presentation | [PDF] |
| Title | Approximate Solution Sampling (and Counting) on AND/OR Spaces |
| Authors | Vibhav Gogate and Rina Dechter |
| DOI | 10.1007/978-3-540-85958-1_37 |
| Presentation | [PDF] |
| Supp. Mat. | [Extended version PDF] |
| Title | Computing All Optimal Solutions in Satisfiability Problems with Preferences |
| Authors | Emanuele Di Rosa, Enrico Giunchiglia and Marco Maratea |
| DOI | 10.1007/978-3-540-85958-1_50 |
| Presentation | [PDF] |
| Title | Crossword Puzzles as a Constraint Problem |
| Authors | Anbulagan and Adi Botea |
| DOI | 10.1007/978-3-540-85958-1_40 |
| Presentation | [PDF] |
| Title | Edge Matching Puzzles as Hard SAT/CSP Benchmarks |
| Authors | Carlos Ansótegui, Ramón Béjar, César Fernàndez and Carles Mateu |
| DOI | 10.1007/978-3-540-85958-1_42 |
| Presentation | [PDF] |
| Title | Efficiently Solving Problems Where the Solutions Form a Group |
| Authors | Karen E. Petrie and Christopher Jefferson |
| DOI | 10.1007/978-3-540-85958-1_36 |
| Presentation | [PDF] |
| Title | Engineering Stochastic Local Search for the Low Autocorrelation Binary Sequence Problem |
| Authors | Steven Halim, Roland H. C. Yap and Felix Halim |
| DOI | 10.1007/978-3-540-85958-1_57 |
| Presentation | [PDF] |
| Title | Experimenting with Small Changes in Conflict-Driven Clause Learning Algorithms |
| Authors | Gilles Audemard and Laurent Simon |
| DOI | 10.1007/978-3-540-85958-1_55 |
| Presentation | [PDF] |
| Title | Model Restarts for Structural Symmetry Breaking |
| Authors | Daniel Heller, Aurojit Panda, Meinolf Sellmann and Justin Yip |
| DOI | 10.1007/978-3-540-85958-1_38 |
| Presentation | [PDF] |
| Supp. Mat. | [Slides for SymCon talk PDF] |
| Title | On the Efficiency of Impact Based Heuristics |
| Authors | Marco Correia and Pedro Barahona |
| DOI | 10.1007/978-3-540-85958-1_51 |
| Presentation | [PDF] |
| Title | Perfect Constraints Are Tractable |
| Authors | András Z. Salamon and Peter G. Jeavons |
| DOI | 10.1007/978-3-540-85958-1_35 |
| Presentation | [PDF] |
| Title | Perfect Derived Propagators |
| Authors | Christian Schulte and Guido Tack |
| DOI | 10.1007/978-3-540-85958-1_44 |
| Presentation | [PDF] |
| Supp. Mat. | Long Version |
| Title | Probabilistically Estimating Backbone and Variable Bias: Experimental Overview |
| Authors | Eric I. Hsu, Christian J. Muise, J. Christopher Beck and Sheila A. McIlraith |
| DOI | 10.1007/978-3-540-85958-1_52 |
| Presentation | [PDF] |
| Supp. Mat. | Extended version of the paper [PDF] |
| Title | Recent Hybrid Techniques for the Multi-Knapsack Problem |
| Authors | Carlos Diego Rodrigues, Philippe Michelon and Manoel B. Campêlo |
| DOI | 10.1007/978-3-540-85958-1_41 |
| Presentation | [PDF] |
| Title | Refined Bounds for Instance-Based Search Complexity of Counting and Other #P Problems |
| Authors | Lars Otten and Rina Dechter |
| DOI | 10.1007/978-3-540-85958-1_45 |
| Presentation | [PDF] |
| Supp. Mat. | Extended version of paper [PDF] |
| Title | Revisiting the Upper Bounding Process in a Safe Branch and Bound Algorithm |
| Authors | Alexandre Goldsztejn, Yahia Lebbah, Claude Michel and Michel Rueher |
| DOI | 10.1007/978-3-540-85958-1_49 |
| Presentation | [PDF] |
| Title | Search Space Reduction for Constraint Optimization Problems |
| Authors | Kenil C. K. Cheng and Roland H. C. Yap |
| DOI | 10.1007/978-3-540-85958-1_56 |
| Presentation | [PPT][PDF] |
| Title | Semi-automatic Generation of CHR Solvers for Global Constraints |
| Author | Frank Raiser |
| DOI | 10.1007/978-3-540-85958-1_47 |
| Presentation | [N/A] |
| Title | Stochastic Local Search for the Optimal Winner Determination Problem in Combinatorial Auctions |
| Authors | Dalila Boughaci, Belaid Benhamou and Habiba Drias |
| DOI | 10.1007/978-3-540-85958-1_48 |
| Presentation | [PPT] |
| Title | Test Strategy Generation Using Quantified CSPs |
| Authors | Martin Sachenbacher and Paul Maier |
| DOI | 10.1007/978-3-540-85958-1_43 |
| Presentation | [PDF] |
| Supp. Mat. | Extended version |
| Title | Transforming Inconsistent Subformulas in MaxSAT Lower Bound Computation |
| Authors | Chu Min Li, Felip Manyà, Nouredine Ould Mohamedou and Jordi Planes |
| DOI | 10.1007/978-3-540-85958-1_46 |
| Presentation | [PDF] |