ISyE Graduate Seminar: Exploiting Decomposable Structure to Design Better Algorithms for Solving Integer Programs

3:15 p.m. - Refreshments
3:30 p.m. - Graduate Seminar

Professor Martin Savelsbergh, H. Milton Steward School of Industrial and Systems Engineering, Georgia Institute of Technology

About the seminar

Optimization problems in which some or all of the variables are constrained to take integer values are of broad applicability in a wide range of fields, ranging from medicine and healthcare to banking and finance to environmental management and conservation. Over recent decades, exact algorithms for their solution have become faster and more efficient, culminating in a variety of commercial software platforms and public domain codes that provide exceptional capability for solving practical problems to optimality. However, this seems to have only increased the appetite of practitioners to solve ever-larger problems, which challenge the state-of-the-art.

In this talk, Savelsbergh brings together two apparently disparate observations: 1) many practical problems have decomposable structure and 2) despite the enormous strides in solution algorithms, one key element common to all of them, namely, the branching rule, has remained largely untouched since it was first presented in the 1960’s. Yet the branching rule defines how the search space is divided in the "divide-and-conquer" paradigm that forms the basis of all exact algorithms; it is central to the algorithm.

Here, Savelsbergh will describe a new idea for exploiting decomposable structure in problems to derive alternative, powerful, new branching rules. These rules are demonstrated to speed up commercial solvers by orders of magnitude, on two classes of problems having different characteristics. The potential to generalize these ideas will also be discussed.

About the speaker 
Martin Savelsbergh is a logistics and optimization specialist with more than 25 years of experience in mathematical modeling, operations research, optimization methods, algorithm design, performance analysis, transport, supply chain management, and production planning. He has published more than 160 research papers in many of the top operations research and optimization journals and has supervised more than 30 Ph.D. students.

Savelsbergh has a track record of creating innovative techniques for solving large-scale optimization problems in a variety of areas, ranging from service network design, to last-mile and crowdsourced delivery, to ridesharing. He has demonstrated an ability to design and implement highly sophisticated and effective optimization algorithms as well as an ability to analyze practical decision problems and translate the insights obtained into optimal business solutions.

Savelsbergh holds the James C. Edenfield Chair in the H. Milton Stewart School of Industrial and Systems Engineering (ISyE) at Georgia Institute of Technology. He is co-director of The Supply Chain and Logistics Institute (SCL). SCL coordinates all supply chain and logistics activities on the Georgia Tech campus. Martin Savelsbergh is editor-in-chief of Transportation Science, one of the most prestigious academic journals in the area of transportation science and logistics.

 

Start date
Wednesday, April 17, 2019, 3:30 p.m.
Location

Lind Hall, Room 305

Share