Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Fixed dimension results in mixed integer programming: complexity, algorithms, and applications


Speaker: Robert Hildebrand, IBM Research
Related Webpage:
Location: 3106 MSB
Start time: Wed, Nov 23 2016, 11:00AM

Integer programming is a powerful tool that can model many important problems. Although linear integer programming is NP-Hard, it can be solved in polynomial time when there are few integer variables. Lenstra’s result reveals important structure for solving integer programs in practice and is applied to give polynomial time algorithms to many problems. We will show how it can be used to generalize notions of total unimodularity in a search for compact models for integer programs. We then will discuss the more general problem of polynomial integer programming and discuss algorithms and complexity.

Bio: Robert Hildebrand received his Ph.D. in Applied Mathematics from UC Davis in 2013. His thesis, Algorithms and Cutting Planes for Mixed Integer Programs, was supervised by Professor Matthias Köppe. After graduation, he spent two years in Switzerland as a postdoctoral researcher at the Institute for Operations Research in the Department for Mathematics at ETH Zürich. He is currently the Herman Goldstine Memorial Postdoctoral Fellow at IBM Research.