A polyhedral study of stochastic integer programming

Qie He, ISYE, (mentors: Shabbir Ahmed; George Nemhauser, ISYE) - We are interested in the stochastic integer programming (SIP) model that captures the uncertainty in real-world problems. In the SIP model, parameters evolve over time and are typically modeled as discrete time stochastic processes within a probability space with finite support. The uncertainty information structure of the SIP model can be further interpreted as a scenario tree with T levels, where each node at level t gives the information of the system available up to stage t. Cutting planes derived from relaxations based on a single scenario may not be sufficient to describe the convex hull of feasible sets of the original problem. We are particularly interested in two possible research directions. One is to design general cutting plane schemes which involve decision variables from different scenarios. Recent advances in the theory of multi-row cuts and disjunctive programming can come to help. The other is to investigate particular SIP problems with special structures, such as dynamic portfolio problems and stochastic dynamic knapsack problems, and obtain the convex hull description of the feasible sets for these problems.