ORIE Colloquium

Oktay GunlukIBM
Cutting planes for mixed-integer programming: theory and practice

Tuesday, October 2, 2018 - 4:15pm
Rhodes 253

During the last decade, the progress in the computational performance of commercial mixed-integer programming solvers have been significant. Part of this success is due to faster computers and better software engineering but a more significant part of it is due to the power of the cutting planes used in these solvers.

In the first part of this talk, we will discuss main components of a MIP solver and describe some classical families of valid inequalities (Gomory mixed integer cuts, mixed integer rounding cuts, split cuts, etc.) that are routinely used in these solvers. In the second part, we will discuss recent progress in cutting plane theory that has not yet made its way to commercial solvers. In particular, we will discuss cuts from lattice-free convex sets and answer a long standing question in the affirmative by deriving a finite cutting plane algorithm for mixed-integer programming.

Bio: Oktay Gunluk is a research staff member at IBM Research. He has received his B.S. and M.S. degrees from Bogazici University and his Ph.D. in operations research from Columbia University. His research interests are mainly mixed-integer programming and discrete optimization. His applied work spans various industrial problems including production planning, fleet scheduling, port optimization, vehicle routing, oil pipeline scheduling and site selection in agriculture. He has served on the editorial boards of Networks, Mathematical Programming Computation, and MOS/SIAM Book Series on Optimization. He is currently an associate editor for Operations Research and Optimization and Engineering journals. He has served on the program committees for MIP, IPCO, and ISCO and currently serves in the IPCO steering committee.