The Twelfth Summer School of the Association for Constraint Programming (ACP) will be held June, 20-24th, 2016 in Cork Ireland. It is organised by the Insight Centre for Data Analytics, and will be held in the Western Gateway Building of University College Cork.
The school is intended for PhD students, masters students and industrial practitioners, who want to get a good understanding of capabilities and current research directions in the area of Constraint Programming. Prior knowledge of Constraint Programming is not required, but general problem solving skills, good programming and math skills are helpful.
The school is chaired by Helmut Simonis.
See also the pages of previous ACP Summer-schools here.
For any queries, please contact the organisers using the email firstname.lastname@example.org.
The school will run from Monday, June 20th, to Friday, June 24th, 2016, in the Western Gateway Building of University College Cork.
Registration will close May 20th, 2016.
Register early to avoid disappointment. Especially, if you require a visa to visit Ireland, please register early, so that formalities can be handled in time.
TASC, Mines de Nantes, France
G-SCOP, Grenoble Institute of Technology, Grenoble, France
Tepper School of Business, Carnegie Mellon University, Pittsburgh, USA
University of British Columbia, Vancouver, Canada
Insight Centre for Data Analytics, University College Cork, Ireland
Université de Nice-Sophia Antipolis, France
Insight Centre for Data Analytics, University College Cork, Ireland
The Summer School will consist of a mix of lectures and hands-on experiences, intended to deepen the learning experience. The topics in this year's school are:
In this tutorial we introduce the key concepts of constraint programming: variables, constraints, propagation, search, and solutions, and show how these can be used to solve interesting combinatorial problems. The concepts will be explained in the context of declarative programming, describing which properties a solution to a problem should have, without stating how this solution should be found. A constraint solver is then used to generate a solution from this declarative description. At the same time, users can control the solution process by choosing between alternative models, changing the amount of propagation that is used, and, ultimately, by providing their own search strategy. We also provide a short overview of the history of constraint programming systems, and key differentiating features of existing constraint platforms..
The first part of the tutorial will review the use of linear programming within constraint programming approaches. The main focus of this tutorial will be about the use of the linear relaxation and reduced costs as bounding and filtering mechanisms. It is intended for an audience with some basic knowledge of the simplex algorithm and will go through a series of examples to illustrate reduced cost filtering. Additionally, we will try to review the various ways these techniques have been used together in the past and some successful applications.
The second part of the tutorial will review the use of dynamic programming as an algorithmic technique for filtering global constraints and in particular weakly NP-hard constraints. We will review existing global constraints relying on this technique such as knapsack, regular, shortest path, … but also show a number of dedicated cases related to routing and scheduling.
Generalizations of Benders decomposition have found a wide range of applications, often resulting in order-of-magnitude reductions in solution time. They are ideal for combining CP with other solution methods, such as mixed integer programming and heuristics. The talk will cover logic-based Benders decomposition (the most versatile generalization of Benders) and branch-and-check methods (which combine Benders with a branching strategy). It will illustrate the methods with several real-world applications.
Binary and multivalued decision diagrams have long been used for circuit design and product configuration but have recently been adapted to CP and optimization. In CP, they provide a richer medium for constraint propagation than the traditional domain store and can propagate stronger forms of consistency than domain consistency, such as projection. In optimization, they provide a relaxation that does not require linearity or convexity, and they can be combined with Benders decomposition. The talk will show how decision diagrams can outperform state-of-the-art CP and mixed integer solvers.
Within the context of global constraints the course focusses on the following aspects of automata constraints:
For constraint problems and many other combinatorial search problems, there is often not only one, but multiple ways of solving it. Different algorithms exhibit vastly different performances on a given instance. We want to solve the problem as quickly as possible of course, but how do we find out which algorithm is the best? Even experts often struggle to make this decision. In addition, many solvers have parameters that need to be set to get the best performance. This is even harder to do for humans.
In this tutorial, we will learn how to tackle this automatically. Given some idea of how algorithms behave in practice, we can build models that make the decision which algorithm to choose for a given instance automatically. Similarly, we can explore the space of possible parameter settings and build a model of how the parameters affect performance. There will be hands-on exercises with state of the art tools.
In this course, we present different ways of using parallelism in constraint programming. First, we will recall some basic in parallelism (atomic operation, concurrency, distributed computing ...). In the second part, we will consider different possible uses of parallelism in CP: Distributed CSPs, parallelization of the propagation mechanism, portfolios methods and enumeration in parallel. Then, we will focus our attention on the latter point and consider three methods: the simple decomposition, the work stealing method and the embarassingly parallel search. We will show the advantages and drawbacks of these methods on present experimental results using different solvers on multicore machines and data centers. In the last part, we try to give some answer to the following question: "how can I solve a problem in less of one hour at the minimal". Notably, we will show how we can use cloud computing to speed up the resolution. We will give some experimental results for the Microsoft Azure cloud.
Constraint Programming is used in a number of application fields, ranging from producton planning and scheduling in aircraft manufacturing to blending wines for vineyards in the south of France. The key to its use is the simplicity of expressing the problem in a declarative form, and the ease of adding or modifying constraints of the problem as the environment changes. This talk gives an overview of the different types of problems solved with Constraint Programming, the methods that are used, and the specific advantages that Constraint Programming offers for application development.
Besides the main program, the Summer School 2016 with also run a programming competition based on a small, real-world problem. Students can try out different solutions techniques during the week, including their own favourite tools.
The Summer School will be held in room G.15 in the Western Gateway Building.
|09:00-10:30||Registration/Introduction (starts 09:30)||Automata Constraints||Benders Decomposition||Parallelism for CP||Algorithm Selection and Portfolios|
|11:00-12:30||CP: What is it?||Automata Constraints||Benders Decomposition||Parallelism for CP||Sustainability and Constraints|
|14:00-15:30||CP: What is it?||DP and LP for Constraints||Benders Decomposition||Algorithm Selection and Portfolios||CP: What is it good for?|
|16:00-17:30||Automata Constraints||DP and LP for Constraints||Parallelism for CP||Algorithm Selection and Portfolios||Conclusion (ends 16:30)|
|18:00-19:30||Introduction to Competition|
Student accommodation for the Summer School is included in the registration fee. Accommodation will be in the Brookfield Village, just a few steps away from the Western Gateway Building.
The Summer School will take place at the Western Gateway Building, University College Cork, Ireland.
Cork airport has multiple daily flights
to/from major European airports like London Heathrow, Amsterdam, and Paris CDG.
Bus Éireann provides a bus service to the city centre, costing about €5. Another option is to take a taxi for about €15 which takes 5-10 minutes.
Alternatively Dublin airport is a 3.5 hour bus journey from Cork, operated by Aircoach for about €25 return. If you spend time in Dublin, its also possible to get a 2.5 hour train from Dublin Heuston station to Cork's Kent station for between €40 - €65 return. The public bus service Bus Éireann also offers routes between Cork and Dublin but this can be less direct.
For an extended stay, the west and south-west of Ireland offers an abundance of beautiful scenery. The best option
is to rent a car and drive up along the coast, visiting
the Ring of Kerry,
the Cliffs of Moher,
and many others.
Further tourist information can be found on Discover Ireland.
Course materials can be accessed here:
CP:What is it? by Helmut Simonis
Choosing a Model by Helmut Simonis
Automata Constraints Part 1 by Nicolas Beldiceanu
Automata Constraints Part 2 by Nicolas Beldiceanu
Automata and Constraints Bibliography by Nicolas Beldiceanu
Linear and Dynamic Programming for Constraints by Hadrien Cambazard
Benders Decomposition by John Hooker
Benders Decomposition Example Data by John Hooker
Decision Diagrams for Discrete Optimization by John Hooker
Parallelism and CP by Jean-Charles Regin
Algorithm Selection and Portfolios by Lars Kotthoff
CP: What is it good for? by Helmut Simonis