Open Collections

Ambiguous Chance-Constrained Bin Packing under Mean-Covariance Information

Banff International Research Station for Mathematical Innovation and Discovery

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. This is joint work with Yiling Zhang and Ruiwei Jiang .

Mathematics; Operations research, mathematical programming; Probability theory and stochastic processes; Operation research

video/mp4

Author affiliation: University of Michigan

2018-09-05

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/67105

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/