MASSACHUSETTS INSTITUTE OF TECHNOLOGY
OPERATIONS RESEARCH CENTER
FALL 2004 SEMINAR SERIES

DATE

Thursday, November 18, 2004

LOCATION: Room E40-298           TIME: 4:15pm

Reception immediately following in the
Philip M. Morse Reading Room, E40-106

SPEAKER

Professor George L. Nemhauser
Institute Professor and Chandler Chair
Georgia Institute of Technology

TITLE

Polyhedral Stochastic Integer Programming

ABSTRACT

     We give a procedure for obtaining new valid inequalities for a 0-1 mixed-integer program (MIP) by combining known valid inequalities. Although the procedure can be applied to any 0-1 MIP, it is particularly useful for multi-stage stochastic 0-1 MIPs. Here we show how to combine valid inequalities from individual scenarios (deterministic instances) to obtain new inequalities that are valid for the scenario tree.

     We then illustrate the procedure by developing inequalities for the stochastic uncapacitated lot-sizing problem and a stochastic knapsack problem.
Joint work with: Yongpei Gu and Shabbir Ahmed