Abstract: We consider chance-constrained binary programs, where each row of the inequalities that involve uncertainty needs to be satisfied probabilistically. Only the information of the mean and covariance matrix is available, and we solve distributionally robust chance-constrained binary programs (DCBPs). Using two different ambiguity sets, we equivalently reformulate the DCBPs as 0-1 second-order cone (SOC) programs. We further exploit the submodularity of 0-1 SOC constraints under special and general covariance matrices and use the submodularity as well as lifting 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 DCBPs. We demonstrate the computational efficacy and solution performance using diverse instances of a chance-constrained bin packing problem.

Bio: Siqian Shen is an associate professor of industrial and operations engineering at the University of Michigan and also serves as an associate director of the Michigan Institute for Computational Discovery and Engineering (MICDE). She obtained a B.S. degree from Tsinghua University in 2007 and a Ph.D. from the University of Florida in 2011. Her theoretical research interests are in integer programming, stochastic/robust optimization, and network optimization.