Mixed Integer Optimization : A Solution Methodology

Amitabh Basu

Abstract - Mixed Integer Programming has emerged as an indispensable tool for the Operations Research community. In spite of its enormous success as a key solution technique for numerous application domains, there are areas which require significant improvements in this technology, like facility location and combinatorial auctions to name a few. I will present my work on techniques that make progress towards achieving the next methodological breakthrough in solving general mixed integer programming models. The talk will focus on my work in cutting plane theory for solving such problems. I will present a framework which unifies previous methods in cutting planes and provides new, and potentially much stronger, cutting plane ideas. This line of work combines the insights behind Gomory's Corner Polyhedron and Balas' Intersection Cuts, using tools from convex analysis, polyhedral geometry and the geometry of numbers. This has initiated intense research activity in the integer programming community in the past 5 years. The ultimate hope is to achieve the next leap in solving large scale optimization problems in practice.