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.

TitleSatisfiability, Knowledge Compilation and the Journey Towards Universal Reasoning Engines
AuthorsAdnan Darwiche
Presentation[PDF]

Invited Talk: John Hooker

This talk was a joint invited talk with ICAPS 2008.

TitleHow To Relax
AuthorsJohn Hooker
Presentation[PDF]

Invited Talk: Alain Colmerauer

TitleBack to the Complexity of Universal Programs
AuthorAlain Colmerauer
DOI10.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.

TitleMy Happy Constribution to Constraint Programming
AuthorsAlain 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.

TitleEfficient Propagators for Global Constraints
AuthorsClaude-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.

TitleA New Framework for Sharp and Efficient Resolution of NCSP with Manifolds of Solutions
AuthorsAlexandre Goldsztejn and Laurent Granvilliers
DOI10.1007/978-3-540-85958-1_13
Presentation[PDF]

The following paper was awarded the ACP prize for the best student paper.

TitleA Branch and Bound Algorithm for Numerical MAX-CSP
AuthorsJean-Marie Normand, Alexandre Goldsztejn, Marc Christie and Frédéric Benhamou
DOI10.1007/978-3-540-85958-1_14
Presentation[PDF]

TitleExploiting Common Subexpressions in Numerical CSPs
AuthorsIgnacio Araya, Bertrand Neveu and Gilles Trombettoni
DOI10.1007/978-3-540-85958-1_23
Presentation[PDF]

Applications 1

TitleProtein Structure Prediction with Large Neighborhood Constraint Programming Search
AuthorsIvan Dotu, Manuel Cebrián, Pascal Van Hentenryck and Peter Clote
DOI10.1007/978-3-540-85958-1_6
Presentation[PDF]

TitleSolving a Telecommunications Feature Subscription Configuration Problem
AuthorsDavid Lesaint, Deepak Mehta, Barry O'Sullivan, Luis Quesada and Nic Wilson
DOI10.1007/978-3-540-85958-1_5
Presentation[PDF]

TitleA Constraint Programming Approach for Allocation and Scheduling on the CELL Broadband Engine
AuthorsLuca Benini, Michele Lombardi, Michela Milano and Martino Ruggiero
DOI10.1007/978-3-540-85958-1_2
Presentation[PDF]

QCSP

TitleGuiding Search in QCSP+ with Back-Propagation
AuthorsGuillaume Verger and Christian Bessiere
DOI10.1007/978-3-540-85958-1_12
Presentation[PDF]

TitleQuantified Constraint Optimization
AuthorsMarco Benedetti, Arnaud Lallouet and Jérémie Vautard
DOI10.1007/978-3-540-85958-1_31
Presentation[PDF]

Verification

TitleCPBPV: A Constraint-Programming Framework for Bounded Program Verification
AuthorsHélène Collavizza, Michel Rueher and Pascal Van Hentenryck
DOI10.1007/978-3-540-85958-1_22
Presentation[PDF]

TitleA Coinduction Rule for Entailment of Recursively Defined Properties
AuthorsJoxan Jaffar, Andrew E. Santosa and Räzvan Voicu
DOI10.1007/978-3-540-85958-1_33
Presentation[PDF]

Advanced Propagation

TitleApproximate Compilation of Constraints into Multivalued Decision Diagrams
AuthorsTarik Hadzic, John N. Hooker, Barry O'Sullivan and Peter Tiedemann
DOI10.1007/978-3-540-85958-1_30
Presentation[PDF]

TitleCost-Based Domain Filtering for Stochastic Constraint Programming
AuthorsRoberto Rossi, S. Armagan Tarim, Brahim Hnich and Steven Prestwich
DOI10.1007/978-3-540-85958-1_16
Presentation[PDF]

TitleConnecting ABT with Arc Consistency
AuthorsIsmel Brito and Pedro Meseguer
DOI10.1007/978-3-540-85958-1_26
Presentation[PDF]

Applications 2

The following paper was awarded the prize for the best applications paper.

TitlePlanning and Scheduling the Operation of a Very Large Oil Pipeline Network
AuthorsArnaldo V. Moura, Cid C. de Souza, Andre A. Cire and Tony M. T. Lopes
DOI10.1007/978-3-540-85958-1_3
Presentation[PDF]

TitleAn Application of Constraint Programming to Superblock Instruction Scheduling
AuthorsAbid M. Malik, Michael Chase, Tyrel Russell and Peter van Beek
DOI10.1007/978-3-540-85958-1_7
Presentation[PDF]
Supp. Mat.Software and Benchmark Instances

TitleSearch Strategies for Rectangle Packing
AuthorsHelmut Simonis and Barry O'Sullivan
DOI10.1007/978-3-540-85958-1_4
Presentation[PDF]

Table Constraints

TitleReformulating Positive Table Constraints Using Functional Dependencies
AuthorsHadrien Cambazard and Barry O'Sullivan
DOI10.1007/978-3-540-85958-1_28
Presentation[PDF]

TitleOptimization of Simple Tabular Reduction for Table Constraints
AuthorChristophe Lecoutre
DOI10.1007/978-3-540-85958-1_9
Presentation[PDF]

TitleMaintaining Generalized Arc Consistency on Ad Hoc r -Ary Constraints
AuthorsKenil C. K. Cheng and Roland H. C. Yap
DOI10.1007/978-3-540-85958-1_34
Presentation[PPT][PDF]

Tractability

TitleClasses of Submodular Constraints Expressible by Graph Cuts
AuthorsStanislav Zivny and Peter G. Jeavons
DOI10.1007/978-3-540-85958-1_8
Presentation[PDF]

TitleStructural Tractability of Propagated Constraints
AuthorsMartin J. Green and Christopher Jefferson
DOI10.1007/978-3-540-85958-1_25
Presentation[PDF]

TitleA Framework for Hybrid Tractability Results in Boolean Weighted Constraint Satisfaction Problems
AuthorT. K. Satish Kumar
DOI10.1007/978-3-540-85958-1_19
Presentation[N/A]

Optimization

TitleDichotomic Search Protocols for Constrained Optimization
AuthorsMeinolf Sellmann and Serdar Kadioglu
DOI10.1007/978-3-540-85958-1_17
Presentation[PDF]

TitleExploiting Decomposition in Constraint Optimization Problems
AuthorsMatthew Kitching and Fahiem Bacchus
DOI10.1007/978-3-540-85958-1_32
Presentation[N/A]

Global Constraints

TitleFlow-Based Propagators for the SEQUENCE and Related Global Constraints
AuthorsMichael Maher, Nina Narodytska, Claude-Guy Quimper and Toby Walsh
DOI10.1007/978-3-540-85958-1_11
Presentation[PDF][PPT]

TitleLength-Lex Bounds Consistency for Knapsack Constraints
AuthorsYuri Malitsky, Meinolf Sellmann and Willem-Jan van Hoeve
DOI10.1007/978-3-540-85958-1_18
Presentation[PDF]

TitleA Geometric Constraint over k -Dimensional Objects and Shapes Subject to Business Rules
AuthorsMats Carlsson, Nicolas Beldiceanu and Julien Martin
DOI10.1007/978-3-540-85958-1_15
Presentation[PDF]

Soft, Fuzzy and Weighted CSP

TitleA Soft Constraint of Equality: Complexity and Approximability
AuthorsEmmanuel Hebrard, Barry O'Sullivan and Igor Razgon
DOI10.1007/978-3-540-85958-1_24
Presentation[PDF]

TitleRelaxations for Compiled Over-Constrained Problems
AuthorsAlexandre Papadopoulos and Barry O'Sullivan
DOI10.1007/978-3-540-85958-1_29
Presentation[PDF]

TitleElicitation Strategies for Fuzzy Constraint Problems with Missing Preferences: Algorithms and Experimental Studies
AuthorsMirco Gelain, Maria Silvia Pini, Francesca Rossi, K. Brent Venable and Toby Walsh
DOI10.1007/978-3-540-85958-1_27
Presentation[PDF]

SAT

TitleSwitching among Non-Weighting, Clause Weighting, and Variable Weighting in Local Search for SAT
AuthorsWanxia Wei, Chu Min Li and Harry Zhang
DOI10.1007/978-3-540-85958-1_21
Presentation[PPT][PDF]
Supp. Mat.Errata

TitleFrom High Girth Graphs to Hard Instances
AuthorsCarlos Ansótegui, Ramón Béjar, César Fernàndez and Carles Mateu
DOI10.1007/978-3-540-85958-1_20
Presentation[PDF]

TitleUniversal Booleanization of Constraint Models
AuthorJinbo Huang
DOI10.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.

TitleA New Empirical Study of Weak Backdoors
AuthorsPeter Gregory, Maria Fox and Derek Long
DOI10.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.

TitleAdding Search to Zinc
AuthorsReza Rafeh, Kim Marriott, Maria Garcia de la Banda, Nicholas Nethercote and Mark Wallace
DOI10.1007/978-3-540-85958-1_54
Presentation[PDF]

TitleAn Elimination Algorithm for Functional Constraints
AuthorsYuanlin Zhang, Roland H. C. Yap, Chendong Li and Satyanarayana Marisetti
DOI10.1007/978-3-540-85958-1_39
Presentation[PDF]

TitleApproximate Solution Sampling (and Counting) on AND/OR Spaces
AuthorsVibhav Gogate and Rina Dechter
DOI10.1007/978-3-540-85958-1_37
Presentation[PDF]
Supp. Mat.[Extended version PDF]

TitleComputing All Optimal Solutions in Satisfiability Problems with Preferences
AuthorsEmanuele Di Rosa, Enrico Giunchiglia and Marco Maratea
DOI10.1007/978-3-540-85958-1_50
Presentation[PDF]

TitleCrossword Puzzles as a Constraint Problem
AuthorsAnbulagan and Adi Botea
DOI10.1007/978-3-540-85958-1_40
Presentation[PDF]

TitleEdge Matching Puzzles as Hard SAT/CSP Benchmarks
AuthorsCarlos Ansótegui, Ramón Béjar, César Fernàndez and Carles Mateu
DOI10.1007/978-3-540-85958-1_42
Presentation[PDF]

TitleEfficiently Solving Problems Where the Solutions Form a Group
AuthorsKaren E. Petrie and Christopher Jefferson
DOI10.1007/978-3-540-85958-1_36
Presentation[PDF]

TitleEngineering Stochastic Local Search for the Low Autocorrelation Binary Sequence Problem
AuthorsSteven Halim, Roland H. C. Yap and Felix Halim
DOI10.1007/978-3-540-85958-1_57
Presentation[PDF]

TitleExperimenting with Small Changes in Conflict-Driven Clause Learning Algorithms
AuthorsGilles Audemard and Laurent Simon
DOI10.1007/978-3-540-85958-1_55
Presentation[PDF]

TitleModel Restarts for Structural Symmetry Breaking
AuthorsDaniel Heller, Aurojit Panda, Meinolf Sellmann and Justin Yip
DOI10.1007/978-3-540-85958-1_38
Presentation[PDF]
Supp. Mat.[Slides for SymCon talk PDF]

TitleOn the Efficiency of Impact Based Heuristics
AuthorsMarco Correia and Pedro Barahona
DOI10.1007/978-3-540-85958-1_51
Presentation[PDF]

TitlePerfect Constraints Are Tractable
AuthorsAndrás Z. Salamon and Peter G. Jeavons
DOI10.1007/978-3-540-85958-1_35
Presentation[PDF]

TitlePerfect Derived Propagators
AuthorsChristian Schulte and Guido Tack
DOI10.1007/978-3-540-85958-1_44
Presentation[PDF]
Supp. Mat.Long Version

TitleProbabilistically Estimating Backbone and Variable Bias: Experimental Overview
AuthorsEric I. Hsu, Christian J. Muise, J. Christopher Beck and Sheila A. McIlraith
DOI10.1007/978-3-540-85958-1_52
Presentation[PDF]
Supp. Mat.Extended version of the paper [PDF]

TitleRecent Hybrid Techniques for the Multi-Knapsack Problem
AuthorsCarlos Diego Rodrigues, Philippe Michelon and Manoel B. Campêlo
DOI10.1007/978-3-540-85958-1_41
Presentation[PDF]

TitleRefined Bounds for Instance-Based Search Complexity of Counting and Other #P Problems
AuthorsLars Otten and Rina Dechter
DOI10.1007/978-3-540-85958-1_45
Presentation[PDF]
Supp. Mat.Extended version of paper [PDF]

TitleRevisiting the Upper Bounding Process in a Safe Branch and Bound Algorithm
AuthorsAlexandre Goldsztejn, Yahia Lebbah, Claude Michel and Michel Rueher
DOI10.1007/978-3-540-85958-1_49
Presentation[PDF]

TitleSearch Space Reduction for Constraint Optimization Problems
AuthorsKenil C. K. Cheng and Roland H. C. Yap
DOI10.1007/978-3-540-85958-1_56
Presentation[PPT][PDF]

TitleSemi-automatic Generation of CHR Solvers for Global Constraints
AuthorFrank Raiser
DOI10.1007/978-3-540-85958-1_47
Presentation[N/A]

TitleStochastic Local Search for the Optimal Winner Determination Problem in Combinatorial Auctions
AuthorsDalila Boughaci, Belaid Benhamou and Habiba Drias
DOI10.1007/978-3-540-85958-1_48
Presentation[PPT]

TitleTest Strategy Generation Using Quantified CSPs
AuthorsMartin Sachenbacher and Paul Maier
DOI10.1007/978-3-540-85958-1_43
Presentation[PDF]
Supp. Mat.Extended version

TitleTransforming Inconsistent Subformulas in MaxSAT Lower Bound Computation
AuthorsChu Min Li, Felip Manyà, Nouredine Ould Mohamedou and Jordi Planes
DOI10.1007/978-3-540-85958-1_46
Presentation[PDF]