Fall 2016

Applied Mixed Integer Programming: Beyond 'The Optimum'

Monday, Nov. 14, 2016 3:50 pm4:30 pm PST

Add to Calendar

Mixed integer programming is NP-hard, and yet it has been successfully used to solve combinatorial optimization problems in industry. In this talk, we shed some light on this puzzle from an informal, practitioner's perspective. We show the main challenges of crafting an optimization model for real-life problems. We present techniques often used to make the model "solvable in practice", and we explain what this really means and entails.  It turns out that worst-case complexity of proving the optimality is rarely an actual concern, in contrast to: input data quality, careful design of a model, rapid progression towards a feasible solution, and an overall reliability. We hope to open a discussion on plausible theoretical underpinnings of the "unreasonable effectiveness of mixed-integer programming in the industry".