Master Class

Monday, May 23, will feature a Master Class on Search Strategies in CP, SAT, AI and MIP with lectures by four invited speakers:
  1. Prof. John Chinneck, Carleton University, Canada
    "Search in Mixed-Integer Linear Programming" (details)

  2. Prof. Gilles Pesant, Polytechnique Montreal, Canada
    "(Backtrack) Search in Constraint Programming" (details)

  3. Dr. Marijn Heule, TU Delft, The Netherlands
    "Search in SAT" (details)

  4. Prof. Nathan Sturtevant, University of Denver, USA
    "The Deployment of Fast A* Search" (details)

The lectures are scheduled full-day and followed by a reception:

8:15 - 9:00 Registration and Opening
9:00 - 10:15
John Chinneck
10:15 - 10:45 Coffee Break
10:45 - 12:00
Gilles Pesant
12:00 - 13:30 Lunch Break
13:30 - 14:45
Marijn Heule
14:45 - 15:15 Coffee Break
15:15 - 16:30
Nathan Sturtevant
16:30 - 16:45 Stretch Break
16:45 - 18:00
John Chinneck, Gilles Pesant, Marijn Heule, Nathan Sturtevant
Panel Session: Ideas for Crossfertilization and Hybrids
18:00 - later Master Class

Please find details on the speakers and talks below.

Prof. John Chinneck

Lecture: Search in Mixed-Integer Linear Programming (slides for download)

Research on methods for solving Mixed-Integer Linear Programs (MIPs) dates to 1956. This long history means that MIP researchers proposed many of the seminal ideas in search that are echoed in other disciplines. At the same time, the Linear Programming (LP) structure inherent in MIP means that some search techniques are peculiar to MIP. The presentation is a tutorial overview of the main ideas relating to search in MIP, along with a summary of more recent ideas and techniques. The two most important topics are node selection and branching variable selection, and the principles motivating the choice of heuristics for each of these.

John W. Chinneck is a professor in the Department of Systems and Computer Engineering at Carleton University in Ottawa, Canada. His research is in applied optimization, with a focus on issues of feasibility and infeasibility. Recent topics include (i) algorithms that speed the identification of feasible solutions in mixed-integer linear programs and large-scale nonlinear programs, and (ii) algorithms and computer tools that assist in the formulation and analysis of very large and complex optimization models. His algorithms for the analysis of infeasible linear programs are used in most commercial linear programming solvers. He is the Editor-in-Chief of the INFORMS Journal on Computing, which covers the interface between Operations Research and Computer Science, and is the past Chair of the INFORMS Computing Society, the INFORMS group that covers the same area.

Prof. Gilles Pesant

Lecture: (Backtrack) Search in Constraint Programming (slides for download)

Constraint Programming originated for the most part from the field of Artificial Intelligence and is thus similarly structured around Representation and Search. The former led to declarative models and powerful inference algorithms encapsulated in each of their constraints. The latter offers programmable search that can be tailored to a specific problem, most often based on backtrack search. Much of the originality and success of Constraint Programming so far has come from the side of inference but there has been growing interest lately in robust generic search heuristics as key to the widespread use of this technology. The presentation is a tutorial overview of the main ideas relating to search in CP (search tree traversal, variable and value selection heuristics) along with a summary of more recent ideas and techniques (e.g. learning during search, impact-based search, counting-based search).

Gilles Pesant is currently Professor of Computer and Software Engineering at the École Polytechnique de Montréal, Canada, after postgraduate studies at McGill, U. Montréal, and the Centre for Research on Transportation. For the last twenty years, his research interests have focused on Constraint Programming and its application to workforce scheduling, transportation logistics and telecommunications. Until recently he had worked mostly on inference algorithms for constraints but his focus has now turned to search, specifically generic search heuristics built from the number of solutions to individual constraints. He is regularly involved in the scientific programming of international conferences in the area of Constraint Programming. He serves as an Associate Editor for Constraint Programming Letters, Journal of Heuristics, INFOR, and is the Editor-in-Chief of Constraints.

Dr. Marijn Heule

Lecture: Search in SAT (slides for download)

Satisfiability (SAT) solvers have become powerful search engines to solve a wide range of applications in fields such as formal verification, planning and bio-informatics. Due to the elementary representation of SAT problems, many low-level optimizations can be implemented. At the same time, there exist clause-based techniques that can simulate several high-level reasoning methods. The tutorial focuses on the search procedures in successful conflict-driven clause learning SAT solvers. It shows how to learn from conflicts and provides an overview of effective heuristics for variable and value selection. Additionally, the presentation covers recent developments, in particular a technique used in today's strongest solvers: the alternation between "classic" depth-first search with learning, and breadth-first search for simplification.

Marijn J.H. Heule is a postdoc at the Institute for Formal Models and Verification at the Johannes Kepler University in Linz, Austria. His research focuses on construction SAT solvers for general purposes. In contrast to most researchers in the field, he aims to achieve this merely by adding extensive reasoning to his solver March. This successful solver won a dozen awards in several SAT competitions. Apart form developing solvers, he applied the power of SAT solving to outperform alternative techniques for problems such as identifying deterministic finite state automata and improving lower bounds for numbers in the Ramsey Theory. He is one of the editors of the Handbook of Satisfiability and editor of the Journal on Satisfiability, Boolean Modeling and Computation (JSAT). He received his PhD and MSc from TU Delft, The Netherlands.

Prof. Nathan Sturtevant

Lecture: The Deployment of Fast A* Search (slides for download)

Research in heuristic search over the last 25 years has often tended towards domains that grow exponentially, often typified by puzzles such as the sliding tile puzzle or Rubik's cube. But, in the last five years there have been a great number of advancements for search in domains that fit in memory where very fast search is required. This tutorial will begin with the basics of A* search with consistent and inconsistent heuristics, and then cover recent algorithms used for search in road networks and in games, with detailed examples from the game Dragon Age: Origins.

Nathan is an Assistant Professor in Computing Science at the University of Denver in Denver, CO where he teaches and performs research in artificial intelligence and games with a specific interest in applications for the game industry; he designed and implemented the pathfinding system in BioWare's recent game Dragon Age: Origins. Other interests include single- and mult-agent search and planning as well as general game playing. Nathan has published over 40 papers in his field, collaborating with over 30 different researchers. In 2009 he won the University of Alberta Teaching Unit Award, which recognizes teaching excellence that occurs as a result of the collaboration of instructors. Nathan was formerly an Assistant Adjunct Professor at the University of Alberta; he received his PhD and M.S. from UCLA and his B.S. from UC Berkeley.