ACP Summer School 2016

Cork, Ireland June 20-24, 2016

Welcome to the website for the ACP Summer School 2016!


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 acpsummerschool2016@gmail.com.

Important Dates


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.

Registration


Registration is now open at UCC Conferencing. The registration cost of the Summer School will be 400 Euro, including accommodation, and 300 Euro without accommodation. The registration cost includes teaching materials, lunches and coffee breaks, and organized social events. Registration will close May 20th, 2016.

Speakers


Nicolas Beldiceanu

TASC, Mines de Nantes,
France

Hadrien Cambazard

G-SCOP, Grenoble Institute of Technology, Grenoble, France

John Hooker

Tepper School of Business, Carnegie Mellon University, Pittsburgh, USA

Lars Kotthoff

University of British Columbia, Vancouver, Canada


Barry O'Sullivan

Insight Centre for Data Analytics, University College Cork, Ireland

Jean-Charles Régin

Université de Nice-Sophia Antipolis, France

Helmut Simonis

Insight Centre for Data Analytics, University College Cork, Ireland

Program


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:

  • types of automata
  • reformulation of automata
  • guideline for creating automata
  • synthesising automata from transducers
  • implied constraints related to automata constraints (e.g. abstracting the execution of several automata in the context of matrix models, glue matrices for reversible automata)
  • using automata for describing specific sets of optimal solutions

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.

Competition

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.

Schedule


The Summer School will be held in room G.15 in the Western Gateway Building.

Monday Tuesday Wednesday Thursday Friday
09:00-10:30 Registration/Introduction (starts 09:30) Automata Constraints Benders Decomposition Parallelism for CP Algorithm Selection and Portfolios
10:30-11:00BreakBreakBreakBreakBreak
11:00-12:30 CP: What is it? Automata Constraints Benders Decomposition Parallelism for CP Sustainability and Constraints
12:30-14:00LunchLunchLunchLunchLunch
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?
15:30-16:00BreakBreakBreakBreakBreak
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
19:30 Reception

Accommodation and local info


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.

Local Information

The Summer School will take place at the Western Gateway Building, University College Cork, Ireland.

Getting to Cork

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.

Shannon airport is another option with a 2 hour bus to Parnell Place, Cork.

For ferries, see AFerry, Irish Ferries, or Brittany Ferries.

Tourism

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 West Cork, the Ring of Kerry, the Cliffs of Moher, and many others.
Further tourist information can be found on Discover Ireland.

Links

Materials


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

Sponsors


The support of the following sponsors is gratefully acknowledged.

Association for Constraint Programming

Insight Centre for Data Analytics

If you are interested in sponsoring this event, please contact acpsummerschool2016@gmail.com