Скачать или смотреть Cut-Generation Approaches for Stochastic Mixed Integer Programs - Dr. Manish Bansal (VT)

Cut-Generation Approaches for Mixed Integer Programs and Two-Stage Stochastic Programs

Dr. Manish Bansal
Assistant Professor, Department of Industrial and Systems Engineering, Virginia Tech

Synopsis. Mixed integer programming (MIP) and two-stage stochastic programming (TSSP) are powerful methods to formulate and solve optimization problems which arise in applications ranging from production planning to bio-informatics with and without data uncertainty. The existing algorithms for solving MIP and TSSP problems (such as branch-and-cut algorithm and integer L-shaped method, respectively) can be significantly improved by developing strong valid inequalities as cutting planes. In this talk, we present a consolidated cut-generating procedure by studying the polyhedral structure of multi-parameter multi-constraint mixed integer kernel set. We refer to this set as continuous multi-mixing set and present facets and extended formulation for continuous multi-mixing polyhedron. We show that this research generalizes several existing concepts in cutting plane theory and is effective in solving the multi-capacitated lot-sizing problems. Moreover, we discuss how the second stage programs of TSSP problems can be convexified by adding scenario-based cutting planes. As special cases, we present TSSP problems with generalizations of continuous mixing set and disjunctive constraints in the second stage. This research extends Balas's results for deterministic disjunctive programs to two-stage stochastic disjunctive programs. We also present our computational results.

Bio. Manish Bansal is an Assistant Professor with Department of Industrial and Systems Engineering at Virginia Tech. He did Bachelors in Electrical Engineering from National Institute of Technology in India, and M.S. (with thesis) and Ph.D. from Department of Industrial and Systems Engineering at Texas A&M University. Prior to joining Virginia Tech, he was a postdoctoral fellow in Department of Industrial Engineering and Management Sciences at Northwestern University. His research is focused on the theory of (stochastic) mixed integer programming, distributionally robust optimization, and location science, and their applications in production planning, telerobotics, and network design. His research is funded by NSF and DoD grants. Manish is also vice-president and president-elect of Junior Faculty Interest Group (JFIG) of INFORMS. He has received ICTAS Junior Faculty Award at Virginia Tech, best poster award at MIP Workshop, and second place in INFORMS Interactive Session Poster Competition.