We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Ambiguous Chance-Constrained Bin Packing under Mean-Covariance Information

Formale Metadaten

Titel
Ambiguous Chance-Constrained Bin Packing under Mean-Covariance Information
Serientitel
Anzahl der Teile
39
Autor
Mitwirkende
Lizenz
CC-Namensnennung - keine kommerzielle Nutzung - keine Bearbeitung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nicht-kommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
Genre
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.