Tutte seminar - Osman Ozaltin

Friday, January 13, 2012 3:30 pm - 4:30 pm EST (GMT -05:00)

Two-Stage Quadratic Integer Programs with Stochastic Right-Hand Sides

Speaker: Osman Ozaltin
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

We consider two-stage quadratic integer programs with stochastic right-hand sides, and present an equivalent reformulation using value functions. A two-phase solution approach is proposed. The first phase constructs value functions of quadratic integer programs in both stages. The second phase solves the reformulation using a global branch-and-bound algorithm or a level-set approach. We derive some basic properties of value functions of quadratic integer programs and utilize them in our algorithms. We show that our approach can solve instances whose extensive forms are hundreds of orders of magnitude larger than the largest quadratic integer programming instances solved in the literature.