Title

Augmented Lagrangian and Alternating Direction Methods for Convex Optimization: A Tutorial and Some Illustrative New Computational Results

Speaker

Jonathan Eckstein, Department of Management Science and Information Systems, Rutgers Business School, Rutgers University

Abstract

The alternating direction of multipliers (ADMM) is a form of augmented Lagrangian algorithm that has experienced a renaissance in recent years due to its applicability to optimization problems arising from ``big data'' and image processing applications, and the relative ease with which it may be implemented in parallel and distributed computational environments.  This talk aims to provide an accessible introduction to the analytical underpinnings of the method, which are far less well known than the method itself, and are obscured in many convergence analyses.  In particular, it is tempting to view the method as an approximate version of the classical augmented Lagrangian algorithm, using one pass of block coordinate minimization to approximately minimize the augmented Lagrangian at each iteration. This talk will show that the actual convergence mechanism of the algorithm is quite different, and then underscore this observation with some new computational results in which we compare the ADMM to algorithms that do indeed work by approximately minimizing the augmented Lagrangian.

Speaker Bio

Jonathan Eckstein is a Professor of Management Science and Information Systems (MSIS) at Rutgers University.  His research interests include augmented Lagrangian and proximal algorithms, and multiple topics on the interface between operations research and computer science, including applying parallel computing to both discrete and continuous optimization problems.  Prior to joining Rutgers in 1995, he worked for four years as a scientist in the Mathematical Science Research Group of Thinking Machines Corporation.  He holds a doctoral degree in operations research from MIT, with a minor in computer science.

Title

CP, AI, and OR or What is a Constraint?

Speaker

J. Christopher Beck, Department of Mechanical & Industrial Engineering, University of Toronto

Abstract

One of the key differences between constraint programming on one side and mixed integer programming and SAT solving on the other is the answer to the question "What is a constraint?". MIP and SAT have made strong restrictions (linear relations and clauses in propositional logic, respectively) and have achieved most of their success through the heavy exploitation of the restriction. CP takes the opposite approach, allowing pretty much anything to be expressed as a constraint. Much of CP's success, however, has come from exploiting only one aspect of this richer assumption: global constraint propagation. In this talk, I will show how work in CP, SAT, AI planning, and MIP can be understood as more seriously pursuing the implications of a rich constraint definition and how the interplay between local and global information can lead to a more flexible hybrid solver architecture.

Speaker Bio

Chris Beck is an Associate Professor and Associate Chair, Research in the Department of Mechanical & Industrial Engineering, University of Toronto. Chris' MSc and PhD degrees both come for the Department of Computer Science, University of Toronto, in the area of Artificial Intelligence. Chris then spent three years at ILOG, Paris as a Senior Scientist and Software Engineer on the team responsible for their constraint-based scheduling library (ILOG Scheduler) before spending two years at the as a Staff Scientist at the Cork Constraint Computation Centre. He returned to Toronto in 2004 to join the Department of Mechanical & Industrial Engineering. Chris' research interests include scheduling, constraint programming, AI planning, reasoning under uncertainty, queueing theory, mixed integer programming, and hybrid optimization techniques. Chris currently serves in an editorial capacity for four journals and one website in AI and OR. He is the President-Elect of the Executive Council for the International Conference on Automated Planning and Scheduling.

Title

Adventures in Scheduling in the Real World

Speaker

Michael Trick, Tepper School of Business, Carnegie Mellon University

Abstract

Improved algorithms and faster computers have greatly increased the applicability of optimization approaches to practical problems.  Drawing on my experiences in sports scheduling, supply chain design, and machine scheduling, I'll discuss some of the key trends in operations research and show how they affect problem solving in the real world.  I'll also talk about some of the key challenges for the field: scalability, uncertainty, and robustness as they relate to my own experiences.

Speaker Bio

Michael Trick is the Harry B. and James H. Higgins Professor of Operations Research and Senior Associate Dean, Education at the Tepper School of Business, Carnegie Mellon University.  Mike received a B. Math from the University of Waterloo, and his Ph.D. from the Georgia Institute of Technology in 1987.  Mike joined Carnegie Mellon in 1989 after two years of postdoctoral work at the University of Minnesota and the University of Bonn.   In 1995, he was appointed the founding Editor of INFORMS Online, the electronic information service of the Institute for Operations Research and the Management Sciences, a 14,000 member professional society.  In 2002 he was President of that society. Trick is the author of fifty professional publications and is the editor of six volumes of refereed articles.  Trick has consulted extensively with the United States Postal Service on supply chain design, with Major League Baseball and a number of college basketball conferences on scheduling issues, and with companies such as Motorola and Sony on machine scheduling.  Trick is a Fellow of INFORMS.