ACP Summer School 2018

June 4–8th 2018, Jackson, Wyoming, USA

The 14th Summer School of the Association for Constraint Programming (ACP) will be held June, 4–8th, 2018, in Jackson, Wyoming, USA, at the Snow King Resort. It is organised by the University of Wyoming with generous sponsorship from the College of Engineering and Applied Science and from Artificial Intelligence Journal.

The school is intended for PhD students, masters students, and industrial practitioners who want to get a good understanding of capabilities of Constraint Programming and how to apply it to practical problems. Prior knowledge of Constraint Programming is not required, but general problem solving skills, good programming, and math skills will be helpful.

We highly recommend that students complete the Coursera MOOC on Basic Modeling for Discrete Optimization prior to attending the summer school. You will get a lot more out of it with some background knowledge.

The school is chaired by Lars Kotthoff. Please contact him with any questions. Download the poster!

Speakers


Helmut Simonis
Insight Centre for Data Analytics, University College Cork, Ireland

Constraint Programming Methodology ⌄


Christian Schulte
KTH Royal Institute of Technology, Sweden

The Solver Side of Constraint Programming ⌄

Lars Kotthoff
University of Wyoming, USA

Algorithm Selection and Portfolios ⌄

In this talk we provide an introduction to Constraint Programming and provide a methodology for developing constraint-based applications. We recall the basic principles of Constraint Programming, variables, constraints, and search, and discuss the impact of the constraint bias used on modelling and problem solving. Examples of different problems explain the common elements and differences between constraint models for various constraint systems.

The goal of this tutorial is simple: you will learn that the solver side of CP is in fact not the dark side, but just a natural complement to the modelling side of CP. The tutorial is concerned with two topics: stuff that's (almost) for free and stuff that you might be forced to do.

The for-free stuff will be concerned with how to use standard search heuristics, restarts, portfolios, and large neighbourhood search in practice. It is almost for free as these techniques are orthogonal to your model and often offer a substantial improvement in robustness and scalability with very limited effort.

The stuff that you might be forced to do will be concerned with what to do when your solver does not offer what you need! More specifically, we will explore how to design and implement constraints and branching heuristics.

The idea is that you will get your hands dirty and you will have to come modestly prepared, more details will be made available later.

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 that will enable you to apply these powerful techniques to problems you want to solve.


Christopher Beck
Toronto Intelligent Decision Engineering Laboratory, University of Toronto, Canada

Constrain Your Robots! The Application of CP and MIP to Robot Planning and Scheduling ⌄


Laurent Michel
University of Connecticut, USA

Constraint Programming for Security Applications ⌄


Serdar Kadıoğlu
Fidelity Investments, USA

Constraint Programming Solutions for Resource Management ⌄

As robots start to be able to autonomously operate in the world, we (or they) face the question of what to do, when, where, and how. While there is clearly a strong AI planning aspect of this problem, there is also the need to reason about time, resources, and numerical values: traditionally the purview of scheduling and optimization approaches such as constraint programming and mixed integer programming. In this tutorial, I will present an existing framework the reflects how the robotics literature has conceptualized the problem of robot planning and scheduling. I will then concentrate on three problems: (1) the allocation of stochastically arriving, independent activities to a team of robots; (2) the creation of a schedule for a team of socially assistive robots in a long-term care home; and (3) the determination of a robot fleet size for a variant of the pursuit-evasion problem. In each case, I will present optimization-based approaches and contrast them to alternatives from AI planning and heuristic algorithms.

The purpose of this session is to introduce applications from security domains and explore how Constraint Programming can be leveraged for modeling and solving such applications. You will get to discover the modeling challenges, the search aspects and the needed underlying extensions to a solver. After the necessary introduction to background material from cryptography, we will explore two main avenues: How to construct intelligent CP-driven attacks against cryptographic algorithms (e.g., AES) and how to leverage combinatorial optimization to design more secure systems.

Resource allocation poses unique challenges ranging from load balancing in heterogeneous environments to privacy concerns and various service-level agreements. High-impact applications within the industry include Cloud Resource Allocation and Customer Relationship Management.

In this tutorial, we showcase two distinct problem domains that span both extremes of the analytics landscape; operational decision making in real-time and resource provisioning for future considerations. Starting with real-world business requirements, we will walk through how Constraint Programming delivers effective solutions in both cases.

While solving large-scale problems is of great practical importance, we emphasize the need for solutions that are not only efficient, but also flexible, easy to update and maintain. We show how Constraint Programming neatly suits the needs of such dynamic environments with continually changing requirements.

Schedule

The summer school will run from Monday morning until Friday mid-day (arrival on Sunday and departure Friday afternoon). There will be a social event on Wednesday afternoon.

MondayTuesdayWednesdayThursdayFriday
Morning (9:00—12:30) SimonisSchulteSchulteBeckreview (9:00—10:00)
Kadıoğlu (10:00—13:00)
Afternoon (14:00—17:30) SimonisKotthoffSocial EventMichel

Registration

We provide shared accommodation at the Snow King Resort (check-in Sunday June 3rd, check-out Friday June 8th), coffee and snacks during breaks, and transportation from and to Jackson airport. Meals and transportation to Jackson are not included.

The summer school is free for students, but registration is required. The registration fee for non-students is $250.

Applications are now closed. See you all in Jackson!

Local Information

Jackson is located in one of the most scenic parts of the US in northwestern Wyoming, very close to Grand Teton and Yellowstone National Parks.

Jackson airport has direct connections to Denver, Salt Lake City, Dallas/Ft. Worth, Minneapolis, Chicago, Atlanta, San Francisco, Houston, Newark, JFK-New York, Seattle, Phoenix, and Los Angeles. The Snow King Resort provides transportation from and to the airport.

It takes about 4.5 hours from Salt Lake City and Bozeman to Jackson by car, 5.5 hours from Boise, and about 8 hours from Denver.

ACP Policy for Duty of Respect and Equal Opportunity