The 20th International Conference on
Principles and Practice of
Constraint Programming
Lyon, France
8-12 September 2014

Schedule

  • Program (pdf)

Tuesday 9th, September 2014

08:45 - Welcome (Plenary) , Chair: Barry O’Sullivan

09:00 - Invited Talk 1 (Plenary) , Chair: Ken Brown

Vijay Saraswat, IBM T.J. Watson Research Center. The Concurrent Constraint Programming Research Programmes – Redux. Abstract. Twenty years ago, in 1995, I was honored to be one of the first invited speakers at PPCP. Much has changed in the computational world since then: we have seen the penetration of the Internet in every aspect of human life; the establishment of the multi-core era; the arrival of the petaflop era in high performance computing; the rise of big data, analytics and machine learning; and the emergence of the cloud (the planet-wide computer) as the new infrastructure. With this backdrop, we review the many developments in CCP over the last twenty years, and revisit the core idea behind this framework: the use of constraints for communication and control in concurrent programming languages. We propose C10: a pure CCP framework realized by compilation to the high performance concurrent programming language, X10, and illustrate multiple anticipated uses in the area of probabilistic programming, machine learning, and big data analytics.

10:00 - Coffee Break

10:25 - Technical Track Session 1: Constraints and SAT , Chair: Lakhdar Saïs

  • Ignasi Abío and Peter J. Stuckey. Encoding Linear Constraints into SAT.
  • André Abramé and Djamal Habet. Efficient Application of Max-SAT Resolution on Inconsistent Subsets.
  • Chavalit Likitvivatanavong, Wei Xia and Roland Yap. Higher-Order Consistencies Through GAC on Factor Variables.
  • Ruben Martins, Saurabh Joshi, Vasco Manquinho and Ines Lynce. Incremental Cardinality Constraints for MaxSAT.
  • Antonio Morgado, Carmine Dodaro and Joao Marques-Silva. Core-Guided MaxSAT with Soft Cardinality Constraints.

10:25 - Application Track Session 1 , Chair: Jimmy Lee

  • Miquel Bofill, Joan Espasa, Marc Garcia, Miquel Palahí, Josep Suy and Mateu Villaret. Scheduling B2B meetings.
  • Stefano Di Alesio, Arnaud Gotlieb, Shiva Nejati and Lionel Briand. Worst-case Scheduling of Software Tasks: A Constraint Optimization Model to Support Performance Testing.
  • Steven Gay, Pierre Schaus and Vivian De Smedt. Continuous Casting Scheduling with Constraint Programming.
  • Marie Pelleau, Louis-Martin Rousseau, Pierre L’Ecuyer, Walid Zegal and Louis Delorme. Scheduling agents using forecast call arrivals at Hydro-Québec’s call centers.
  • Mirko Stojadinovic. Air Traffic Controller Shift Scheduling by Reduction to CSP, SAT and SAT-related Problems.

12:30 - Lunch

14:00 - Technical Track Session 2: Distributed Constraints , Chair: Christian Bessiere

  • Ferdinando Fioretto, Tiep Le, William Yeoh, Son Tran and Enrico Pontelli. Improving DPOP with Branch Consistency in Distributed Constraint Optimization Problems.
  • Emma Rollon and Javier Larrosa. Decomposing Utility Functions in Bounded Max-Sum for Distributed Constraint Optimization.
  • Mohamed Wahbi and Kenneth N. Brown. Global Constraints in Distributed CSP: Concurrent GAC and Explanations in ABT.
  • Mohamed Wahbi and Kenneth N. Brown. The impact of wireless networks on distributed constraint satisfaction.

14:00 - Journal Presentation Track Session 1 , Chair: Joao Marques-Silva

  • David Bergman, Andre Cire, Willem-Jan van Hoeve and John Hooker. Optimization Bounds from Binary Decision Diagrams.
  • Miquel Bofill, Dídac Busquets and Mateu Villaret. Robust Weighted MaxSAT.
  • Elsa Carvalho, Jorge Cruz and Pedro Barahona. Probabilistic Constraints for Nonlinear Inverse Problems.
  • Andre Cire and Willem-Jan Van Hoeve. Multivalued Decision Diagrams for Sequencing Problems.

15:40 - Coffee Break

16:00 - Tutorial Session 1(a) , Chair: Alan Frisch

Automated Reformulation of Constraint Models in Savile Row Peter Nightingale, University of St Andrews. Abstract. Modelling languages such as OPL, MiniZinc and Essence’ have been and continue to be the focus of considerable research effort. These languages have several advantages compared to using a constraint solver directly: they abstract away from solver-dependent details of modelling to provide the user with a consistent language for multiple constraint solvers; they typically allow arbitrary nesting of expressions when constraint solvers do not; and they provide an opportunity for automated optimisation and reformulation of the model, before it is flattened and specialised for a particular solver. This tutorial focuses on automated optimisation and reformulation at the instance level, i.e. after problem class parameters have been substituted into the model. I also focus on finite-domain integer constraint problems, although many of the techniques can also be applied to continuous variables and set variables. I will use Essence’ and Savile Row as an example language and system.

The first part of this tutorial will be an overview of published reformulations of constraint models, such as active CSE and constraint aggregation. The second part will be a description of the internals of Savile Row, with example problems demonstrating various useful reformulations that it can perform.

Finally, the third part of the tutorial will focus on examples where a sequence of reformulations leads to a surprising result. One example of this is BIBDs, where a sequence of three reformulations lead to a model that improves on the sophisticated model published by Frisch et al (which itself is far better than the model commonly used in the constraints literature).

16:00 - Tutorial Session 1(b) , Chair: Michela Milano

The Past and Future of csplib.org: Why and How to Contribute Christopher Jefferson, University of St Andrews. Abstract. For over 15 years the www.csplib.org website has provided a central repository for problems and instances which have been studied by the CP community, leading to over 800 references of csplib in papers (according to Google Scholar). By requiring all problems are explained in natural language first and remaining agnostic to individual CP languages, csplib has remained relevant as individual CP systems and languages have gained and lost popularity.

Unfortunately, while csplib is highly cited, the work involved in submitting updates to the website meant new problems and references were not added to csplib, leaving many important problems out of date or simply missing altogether. We believe not having a central place to refer to problems and benchmarks weakens the CP community as a whole.

Recently, csplib has moved to a much more open and transparent development model. The contents and scripts which build the website are all accessible at github.com, the content is clearly licensed as creative commons, and changes can be made to any part of csplib are accepted either by e-mail or github pull request.

This tutorial will be split into two parts. Firstly, there will be a brief history of csplib to date, and an overview of the current contents. Secondly, we will interactively show how easy it is to add new problems, citations and benchmarks to csplib.org. We will also discuss the csplib mirroring service, which provides a way to ensure that websites important to the CP community remain accessible to future researchers.

The aim of this tutorial is to take the opportunity of a major redesign of csplib to encourage new contributions, both new problems and implementations in the many CP languages now in existence (cspxml, zinc, essence). We hope this will provide benefit to the whole CP community, providing a central place to find and share problems.

17:30 - Anniversary Celebration: 20 Years of CP (Plenary) , Chair: Barry O’Sullivan

In this session a panel of delegates who presented work at the first CP conference in 1995 will reflect on the work they presented at that conference, its evolution, and its legacy. An interactive Q&A session will also provide an opportunity for delegates to engage and debate with the panel.

19:00 - Wine and Cheese Welcoming Reception

Wednesday 10th, September 2014

09:00 - Invited Talk 2 (Plenary) , Chair: Guido Tack

Patrick Prosser, University of Glasgow. Teaching Constraint Programming Abstract. How do we do research? We start with a question. Then we read books, journal and conference papers, maybe even speak to people. Then we do our own work, make our own contribution, maybe coming up with an improved technique or a greater insight. We then write up our findings, maybe submit this to a conference, present our work and get feedback, and this results in further research. This is a feedback loop, open to scrutiny by our peers.

And what about teaching? You teach yourself and become competent. You decide how to teach your subject. You then teach and mark students. You analyze students’ performance and use this to modify what you teach. You continue to learn your subject and use this new knowledge to modify your teaching. Again, there is a feedback loop. But it is a closed loop, in the sense that no one really gets to critique what you do. If you are teaching Constraint Programming (CP) it is unlikely that there are many teaching colleagues who can actually evaluate what you are doing, other than looking at the final exam marks. So you can wander off topic, away from the target and this can be dangerous.

I am fortunate enough to be allowed to teach CP to final year and masters students at Glasgow University. I have been doing this for about 10 years. What I teach and how I teach has evolved over time. I now recognize some things that I did that were clearly wrong and some things that I did that were really good. I know that I do not teach in a vacuum, that my students take many other courses. So I try and identify stuff that I think a Constraint Programmer should know that is not being taught in other courses. Consequently, my CP course contains stuff that might be considered unusual. I also expect that there’s stuff that I should teach but do not.

In my talk I will describe the content of my CP course (the stuff of it), some things I have done wrong and some things that really work well. I will cover lecture material, assessed exercises and even exam questions! In essence, I will open my feedback loop allowing you to give me feedback on what I teach.

10:00 - Coffee Break

10:25 - Award Winning Papers , Chair: Barry O’Sullivan

  • Best Technical Track Paper Martin Cooper, Achref El Mouelhi, Cyril Terrioux and Bruno Zanuttini. On Broken Triangles.
  • Best Application Track Paper Morten Mossige, Arnaud Gotlieb and Hein Meling. Using CP in automatic test generation for ABB Robotics’ Paint Control System.
  • Best Student Paper Umut Oztok and Adnan Darwiche. On Compiling CNF into Decision-DNNF.
  • Runner-up Best Student Paper Thi-Van-Anh Nguyen and Arnaud Lallouet. A Complete Solver for Constraint Games.
  • ACP Doctoral Research Award 2014 David Bergman (Tepper School of Business, Carnegie Mellon University). New Techniques for Discrete Optimization.

12:30 - Lunch

14:00 - Technical Track Session 3: Optimization , Chair: Peter Stuckey

  • Alban Derrien, Thierry Petit and Stéphane Zampelli. A Declarative Paradigm for Robust Cumulative Scheduling.
  • Daniel Fontaine, Laurent Michel and Pascal Van Hentenryck. Constraint-Based Lagrangian Relaxation.
  • Wen-Yang Ku, Thiago Pinheiro and J. Christopher Beck. CIP and MIQP Models for the Load Balancing Nurse-to-Patient Assignment Problem.
  • Robert Nieuwenhuis. The IntSat method for Integer Linear Programming.

14:00 - Application Track Session 2 , Chair: Helmut Simonis

  • Andrea Bartolini, Andrea Borghesi, Thomas Bridi, Michele Lombardi and Michela Milano. Proactive Workload Dispatching on the EURORA Supercomputer.
  • Simon De Givry, Jimmy Lee, Ka Lun Leung and Yu Wai Shum. Solving a Judges Assignment Problem Using Conjunction of Global Cost Functions.
  • Shuo Li and Ahmed Hemani. Case Study: Constraint Programming in a System Level Synthesis Framework.
  • Cédric Pralet and Charles Lesire. Deployment of Mobile Wireless Sensor Networks for Crisis Management: a Constraint-Based Local Search Approach.

15:40 - Coffee Break

16:00 - Tutorial Session 2(a) , Chair: John Hooker

Social Choice Francesca Rossi, University of Padova, K. Brent Venable, Tulane University and IHMC, and Toby Walsh, NICTA and UNSW. Abstract. The goal of this tutorial is to introduce social choice theory, a framework for analysing the combination of individual preferences to reach a collective decision. It will cover both applications of constraint programming to social choice, as well as applications of social choice in constraint programming.

16:00 - Tutorial Session 2(b) , Chair: Pierre Flener

MiniZinc 2.0 Peter J. Stuckey, University of Melbourne, and Guido Tack, Monash University. Abstract. MiniZinc is a solver-independent language for modelling combinatorial problems. The NICTA MiniZinc tool chain has seen several incremental updates since its first release in 2007, and after three years of work, we are now releasing version 2.0 of the language and tool chain.

In this tutorial we will introduce the new features that make MiniZinc more expressive, more scalable, and easier to integrate into bigger software projects. We will cover functional modelling and option types as the main additions to the language, show how MiniZinc 2.0 produces better code for linear and SAT solvers, and present the API for integrating MiniZinc into existing software.

This will give beginners a good overview of what is possible in MiniZinc, and introduce experienced modellers to the technical background of the more advanced features.

17:45 - ACP General Assembly , Chair: Helmut Simonis

This session includes the ACP Distinguished Service Award and Previews of CP 2015 and CPAIOR 2015.

Distinguished Service Award.

The 2014 Distinguished Service Award of the Association for Constraint Programming is awarded to Professor Barry O’Sullivan, Insight Centre for Data Analytics, University College Cork. The citation of the award reads as follows:

“For contributions to the field of constraint programming through sustained service providing multi-faceted and tireless leadership at the national, European and broader international level, and as the longest serving ACP president.”

19:00 - Close

Thursday 11th, September 2014

09:00 - Invited Talk 3 (Plenary) , Chair: Laurent Michel

Louis-Martin Rousseau, École Polytechnique de Montréal. One Problem, Two Structures, Six Solvers, and Ten Years of Personnel Scheduling. Abstract. The shift-scheduling problem was originally introduced by Edie in 1954 in the context of scheduling highway toll booth operators. It was solved a short time later, by Georges Dantzig, using a set covering formulation. However, the Multi-Activity Shift Scheduling (MASSP) version of that problem, where one not only needs to schedule when employees are working or resting, but more precisely, what activity they are performing, still remains a challenge. During this invited lecture, we will recall theturning points of this 60-year journey, focusing particularly on the efforts of the last decade to solve MASSPs. We will cover the introduction of the Regular, and two years later, the Context-free Grammar constraint. We will discuss how the structures of these two constraints were exploited by several researchers in Constraint Programming, Integer Programming, Dynamic Programming embedded in Large Neighbourhood Search and Branch-and-Price, Hybrid CP-MIP Branch-and-Bound, as well as Lazy Clause Generation. The industrial importance of these techniques will also be discussed.

10:00 - Coffee Break

10:25 - Technical Track Session 4(a): Global Constraints , Chair: Nicolas Beldiceanu

  • Christian Bessiere, Emmanuel Hebrard, George Katsirelos, Zeynep Kiziltan, Emilie Picard-Cantin, Claude-Guy Quimper and Toby Walsh. The Balance Constraint Family.
  • Ronald De Haan, Iyad Kanj and Stefan Szeider. Subexponential Time Complexity of CSP with Global Constraints.
  • Vinasétan Ratheil Houndji, Pierre Schaus, Laurence Wolsey and Yves Deville. The StockingCost Constraint.
  • Jimmy Lee and Zichen Zhu. An Increasing-Nogoods Global Constraint for Symmetry Breaking During Search.
  • Ignacio Salas, Gilles Chabert and Alexandre Goldsztejn. The non-overlapping constraint between objects described by non-linear inequalities.

10:25 - Technical Track Session 4(b): Modelling and Solving , Chair: Andrea Rendl

  • Gilles Audemard, Christophe Lecoutre, Mouny Samy Modeliar, Daniel Porumbel and Gilles Goncalves. Scoring-based Dominance Reasoning for the Subgraph Isomorphism Problem.
  • Ian P. Gent, Bilal Syed Hussain, Christopher Jefferson, Lars Kotthoff, Ian Miguel, Glenna F. Nightingale and Peter Nightingale. Discriminating Instance Generation for Automated Constraint Model Selection
  • Ronan Le Bras, Carla Gomes and Bart Selman. On the Erdos Discrepancy Problem.
  • Ciaran McCreesh and Patrick Prosser. Reducing the Branching in a Branch and Bound Algorithm for the Maximum Clique Problem.
  • Peter Nightingale, Ozgur Akgun, Ian Gent, Christopher Jefferson and Ian Miguel. Automatically Improving Constraint Models in Savile Row through Associative-Commutative Common Subexpression Elimination.

12:30 - Lunch

14:00 - Technical Track Session 5: Parallel and Stream-based Methods , Chair: Philippe Codognet

  • Daisuke Ishii, Kazuki Yoshizoe and Toyotaro Suzumura. Scalable Parallel Numerical CSP Solver
  • Jasper Lee and Jimmy Lee. Towards Practical Infinite Stream Constraint Programming: Applications and Implementation.
  • Jean-Charles Regin, Mohamed Rezgui and Arnaud Malapert. Improvement of the Embarrassingly Parallel Search for Data Centers.
  • Ashish Sabharwal and Horst Samulowitz. Insights into Parallelism with Intensive Knowledge Sharing.

14:00 - Journal Presentation Track Session 2 , Chair: Francesca Rossi

  • Laura Climent, Richard Wallace, Miguel A. Salido and Federico Barber. Robustness and Stability in Constraint Programming under Dynamism and Uncertainty.
  • Martin Cooper, Frederic Maris and Pierre Regnier. Monotone Temporal Planning: Tractability, Extensions and Applications.
  • Lars Otten and Rina Dechter. Anytime AND/OR Depth-first Search for Combinatorial Optimization.
  • Christian Schulte and Guido Tack. View-based Propagator Derivation.

15:40 - Coffee Break

16:00 - Technical Track Session 6(a): Compilation-based Methods , Chair: Justin Pearson

  • Miquel Bofill, Miquel Palahí, Josep Suy and Mateu Villaret. Solving Intensional Weighted CSPs by incremental optimization with BDDs.
  • Guillaume Perez and Jean-Charles Regin. Improving GAC-4 for Table and MDD Constraints.

16:00 - Technical Track Session 6(b): Theory and Tractability , Chair: Peter Jeavons

  • Clément Carbonnel, Martin C. Cooper and Emmanuel Hebrard. On Backdoors To Tractable Constraint Languages.
  • Martin Cooper. Beyond Consistency and Substitutability.

18:00 - Excursion

Friday 12th, September 2014

09:00 - Invited Talk 4 (Plenary) , Chair: John Slaney

Maria Fox, King’s College London. A Modular Architecture for Hybrid Planning with Theories. Abstract. Planning technology has made huge strides, alongside other combinatorial optimisation solving technologies, over the past decade. Automated planning systems now exist for temporal and metric problems, including management of continuous time and concurrency, continuous numeric resources and action costs. There is an increasing interest in combining planners with specialised solvers, such as optimisation algorithms, to achieve a hybrid form of planning. In this context, the relationship between planning and model-checking, planning and constraint-solving and planning and control are all being clarified.

Synergies between different optimisation modelling and solving paradigms can be exploited to achieve new capabilities and improved performance of solvers. An example of this is recent work exploiting the developments in SAT solving, SAT Modulo Theories, in which atoms can be built from predicates, functions and constants whose interpretations are provided through external theory modules. In planning, extension to support external modules allows a much richer expression of preconditions and state variables. A motivation for exploring this idea is that the increased expressiveness can allow planners to work with models of application domains using specialised solvers, necessary for reasoning within those applications, alongside the generic solving cores developed in the planning community. Since this is a common requirement of planning applications, it is important to provide clean and well-understood methods for linking planners to external libraries, choosing heuristics and exchanging constraints.

In this talk we present the Planning Modulo Theories paradigm, first proposed in 2012, describing how the paradigm has been extended to incorporate the latest advances in temporal planning. We discuss how the use of constraint reasoning can provide an additional source of powerful solving capabilities within this framework.

In general, constraint solvers prune choices from the search space by inference, while most modern planners focus on heuristic guidance of the search towards good choices. Complex interactions in resource-constrained models can be obscure, making heuristic evaluation of states much more difficult, while at the same time offering more opportunity for leverage from inference. We consider, with reference to two real application domains, how constraint solving can contribute to making planners suitable for deployment in applications with demanding requirements.

One of the important challenges in extending the capabilities of planners is to continue to be able to efficiently validate plans and domain models. We will describe how the VAL system, developed incrementally over the last 10 years for validation of plans and domains in the mixed discrete-continuous expressiveness of PDDL+, is now being extended to cope with richer behaviours encountered in the PMT framework.

10:00 - Coffee Break

10:25 - Technical Track Session 7(a): Systems and Paradigms , Chair: Christian Schulte

  • Nicolas Beldiceanu, Mats Carlsson, Pierre Flener, Maria Francisco Rodriguez and Justin Pearson. Linking Prefixes and Suffixes for Constraints Encoded Using Automata with Accumulators.
  • Geoffrey Chu and Peter J. Stuckey. Nested Constraint Programs.
  • Kathryn Francis and Peter J. Stuckey. Loop Untangling.
  • Andrea Rendl, Guido Tack and Peter J. Stuckey. Stochastic MiniZinc.
  • Pascal Van Hentenryck and Laurent Michel. Domain Views for Constraint Programming.

10:25 - Technical Track Session 7(b): Reasoning , Chair: Christopher Jefferson

  • Christoph Berkholz. The Propagation Depth of Local Consistency.
  • Alban Derrien and Thierry Petit. A New Characterization of Relevant Intervals for Energetic Reasoning.
  • Florian Lonsing and Uwe Egly. Incremental QBF Solving.
  • Anthony Schneider, Robert Woodward, Berthe Y. Choueiry and Christian Bessiere. Improving Relational Consistency Algorithms Using Dynamic Relation Partitioning.
  • Robert Woodward, Anthony Schneider, Berthe Y. Choueiry and Christian Bessiere. Adaptive Parameterized Consistency for Non-Binary CSPs by Counting Supports.

12:30 - Lunch

14:00 - Technical Track Session 8(a): Portfolios and Algorithm Selection , Chair: Christine Solnon

  • Roberto Amadini and Peter J. Stuckey. Sequential Time Splitting and Bounds Communication for a Portfolio of Optimization Solvers
  • Loïc Blet, Samba Ndojh Ndiaye and Christine Solnon. Experimental comparison of BTD and intelligent backtracking: Towards an automatic per-instance algorithm selector

14:00 - Technical Track Session 8(b): Graphical Models , Chair: Thomas Schiex

  • Umberto Grandi, Hang Luo, Nicolas Maudet and Francesca Rossi. Aggregating CP-nets with unfeasible outcomes.
  • Philippe Jégou and Cyril Terrioux. Tree-Decompositions with Connected Clusters for Solving Constraint Networks.
  • Levi Lelis, Lars Otten and Rina Dechter. Memory-Efficient Tree Size Prediction for Depth-First Search in Graphical Models.

15:15 - Conference Closing Session , Chairs: Yves Deville and Christine Solnon

15:30 - Close