Siqian Shen - Distributionally Robust Chance-Constrained Bin Packing
Monday, April 24

3108 Etcheverry Hall, 3:30 p.m. - 5:00 p.m.


The stochastic bin packing structure arises in wide service operations applications including healthcare, cloud computing, and transportation. Chance-constrained bin packing problem optimizes the allocation of a set of items into bins and for each bin it bounds the probability that the total weight of packed items exceeds the bin's capacity. Different from the stochastic programming approaches relying on full distributional information of the random item weights, we study distributionally robust chance-constrained bin packing (DCBP) models when only the first two moments (i.e., mean and covariance) are available. Using two types of ambiguity sets, we equivalently reformulate the DCBP models as 0-1 second-order cone (SOC) programs. We further exploit the submodularity of the 0-1 SOC constraints under special and general covariance matrices, to derive extended polymatroid inequalities to strengthen the 0-1 SOC formulations and procedures for generating valid bounds. We incorporate these valid inequalities and bounds in a branch-and- cut algorithm, which significantly improves thecomputational efficacy for solving the DCBP models.


Siqian Shen is an Assistant Professor of Industrial and Operations Engineering at the University of Michigan. She obtained a B.S. degree from Tsinghua University in 2007 and Ph.D. from the University of Florida in 2011. Her research interests are in mathematical optimization, particularly in stochastic programming, network optimization, and integer programming. She was named a runner up of the 2010 INFORMS Computing Society Best Student Paper award, was awarded the 1st Place of the 2012 IIE Pritsker Doctoral Dissertation Award, and was a recipient of 2012 IBM Smarter Planet Innovation Faculty Award. She currently serves as an Associate Director in the Michigan Institute for Computational Discovery & Engineering (MICDE).