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

Osman Y Ozaltin (oyo1pitt.edu)
Oleg A Prokopyev (propkopyevengr.pitt.edu)
Andrew J Schaefer (schaeferie.pitt.edu)

Abstract: We consider two-stage quadratic integer programs with stochastic right-hand sides, and present an equivalent reformulation using value functions. We first derive some basic properties of value functions of quadratic integer programs. We then propose a two-phase solution approach. The first phase constructs the value functions of quadratic integer programs in both stages. The second phase solves the reformulation using a global branch-and-bound algorithm. We also consider a level-set approach to reduce the search space in the second phase. We show that our method can solve instances whose extensive forms are hundreds of orders of magnitude larger than the largest quadratic integer programming instances solved in the literature.

Keywords: Stochastic Integer Programming, Quadratic Integer Programming, Value Functions, Superadditive Duality

Category 1: Stochastic Programming

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Nonlinear Optimization (Quadratic Programming )

Citation:

Download: [PDF]

Entry Submitted: 09/22/2009
Entry Accepted: 10/02/2009
Entry Last Modified: 10/02/2009

Modify/Update this entry