Optimization Online


Ambiguous Chance-Constrained Bin Packing under Mean-Covariance Information

Yiling Zhang (zyiling***at***umich.edu)
Ruiwei Jiang (ruiwei***at***umich.edu)
Siqian Shen (siqian***at***umich.edu)

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.

Keywords: chance-constrained binary program; distributionally robust optimization; conic integer program; submodularity; extended polymatroid

Category 1: Stochastic Programming

Category 2: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Category 3: Integer Programming (0-1 Programming )

Citation: Technical Report, University of Michigan at Ann Arbor

Download: [PDF]

Entry Submitted: 09/30/2016
Entry Accepted: 09/30/2016
Entry Last Modified: 03/26/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society