Siqian Shen - Ambiguous Chance-Constrained Bin Packing under Mean-Covariance Information

Speaker: Siqian Shen, Assistant Professor of Industrial and Operations Engineering, University of Michigan

4/24/2017

3:30pm - 5:00pm

Location: 3108, Etcheverry Hall

Abstract: The bin packing structure arises in a wide range of service operational applications, where a set of items are assigned to multiple bins with fixed capacities. With random item weights, a chance-constrained bin packing problem bounds, for each bin, 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 assume that only the information of the mean and covariance matrix is available, and consider distributionally robust chance-constrained bin packing (DCBP) models in this paper. 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, and utilize the submodularity as well as lifting and bin-packing structure to derive extended polymatroid inequalities to strengthen the 0-1 SOC formulations. We incorporate the valid inequalities in a branch-and-cut algorithm for efficiently solving the DCBP models. Finally, we demonstrate the computational efficacy of our approaches and performance of DCBP solutions on diverse test instances.

Bio: 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).

  • Sponsor:

    Industrial Engineering & Operations Research
View on campus calendar Add to my calendar