University of Minnesota
University of Minnesota
http://www.umn.edu/

Industrial and Systems Engineering

Home > Events

 

ISyE Seminar Series


Exploiting Decomposable Structure to Design Better Algorithms for Solving Integer Programs

Wednesday, April 17
3:15pm - Refreshments
3:30pm - Graduate Seminar, Lind Hall 305

 



Martin Savelsbergh

H. Milton Stewart School of Industrial and Systems Engineering

Georgia Institute of Technology

 

 

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 challenges the state-of the art. In this talk, we bring together two apparently disparate observations. (i) Many practical problems have decomposable structure and (ii) 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, we will describe the 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.

BIO:
Martin Savelsbergh is a logistics and optimization specialist with over 25 years’ experience in mathematical modeling, operations research, optimization methods, algorithm design, performance analysis, transport, supply chain management, and production planning. He has published over 160 research papers in many of the top operations research and optimization journals and has supervised more than 30 Ph.D. students. Martin 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 survey, 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. Martin holds the James C. Edenfield Chair in the Milton Stewart School of ISyE at Georgia Institute of Technology. He is co-director of The Supply Chain and Logistics Institute. 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.

 

Upcoming and Past Seminars


 

Faculty Search

Upcoming Seminar

News

Check out this feature story on the CSE website about our undergraduate student group University of Minnesota Robotics!
Learn More...

UMN Robotics is up for three Tony Diggs awards this year!
Learn More...

ISyE Professor Lisa Miller received the Horace T. Morse - University of Minnesota Alumni Award for...
Learn More...

ISyE Professor Guangwen Kong received the 2018 M&SOM Meritorious Service Award.
Learn More...

ISyE Professor Bill Cooper received the Russell J. Penrose Excellence in Teaching Award.
Learn More...

University of Minnesota Robotics has had a very successful start to the year!
Learn More...

ISyE undergraduate students receive scholarships and grant from UROP...
Learn More...

Professor Qie He awarded grant...
Learn More...

We are pleased to welcome Professor Jean-Philippe "JP" Richard...
Learn More...

Prof. Benjaafar and collaborators awarded a $1.75M grant from NSF...
Learn More...

Prof. Benjaafar is next Editor-in-Chief for INFORMS...
Learn More...

Asst. Professor Mani has been awarded the DTC DTI Seed Grant...
Learn More...

Prof. Benjaafar served on the panel at the INFORMS Summit...
Learn More...

Behrooz Pourghannad selected as POM-CBOM 2018 Jr. Scholar Finalist.
Learn More...

ISyE Sr. Shoubhik Sinha helped develop a caffeine alternative...
Learn More...

Associate Professor Leder selected as Fulbright Scholar.
Learn More...

Dr. Diana Negoescu has received the Melinda and Bill Gates Foundation Award through Grand Challenges in Global Health program.
Learn More...

Former ISyE PhD student, Mehdi Behroozi has received two dissertation awards. Read More...

ISyE is pleased to announce the launch of a new Analytics Track. More information...

Zizhuo Wang wins the Adobe Digital Marketing Research Award 2017... Read More...

Fan Jia received honorable mention, 2016 SOLA Dissertation Award... Read More...

Professor Benjaafar - named Director of the Initiative on the Sharing Economy... Read More...

Symposium on the Sharing Economy held last May... Read More...

Sherwin Doroudi - joined the Department as an Assistant Professor... Read More...

Mehdi Behroozi, a recent ISyE PhD grad, offered position as Asst. Professor at Northeastern... Read More...

ISyE Undergrad student Christopher Kuehn - co-founder of AdrenaCard, an epi-pen alternative. Read More...

Dr. Leder awarded the NSF CAREER Award: Rare Events in Cancer Evolution with a grant in the amount of $500,000. Read More...

More ISyE News...