Branch and Price for Chance-Constrained Bin Packing

Zheng Zhang (), Brian T. Denton () and Xiaolan Xie ()
Additional contact information
Zheng Zhang: Department of Service Science and Operations Management, School of Management, Zhejiang University, 310058 Hangzhou, China; Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109
Brian T. Denton: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109
Xiaolan Xie: Mines Saint-Etienne, Université Clermont Auvergne, CNRS, UMR 6158 LIMOS, Centre CIS, F-42023 Saint-Etienne, France; Antai College of Economics and Management, Shanghai Jiao Tong University, 200030 Shanghai, China

INFORMS Journal on Computing, 2020, vol. 32, issue 3, 547-564

Abstract: This article describes two versions of the chance-constrained stochastic bin-packing (CCSBP) problem that consider item-to-bin allocation decisions in the context of chance constraints on the total item size within the bins. The first version is a stochastic CCSBP (SP-CCSBP) problem, which assumes that the distributions of item sizes are known. We present a two-stage stochastic mixed-integer program (SMIP) for this problem and a Dantzig–Wolfe formulation suited to a branch-and-price (B&P) algorithm. We further enhance the formulation using coefficient strengthening and reformulations based on probabilistic packs and covers. The second version is a distributionally robust CCSBP (DR-CCSBP) problem, which assumes that the distributions of item sizes are ambiguous. Based on a closed-form expression for the DR chance constraints, we approximate the DR-CCSBP problem as a mixed-integer program that has significantly fewer integer variables than the SMIP of the SP-CCSBP problem, and our proposed B&P algorithm can directly solve its Dantzig–Wolfe formulation. We also show that the approach for the DR-CCSBP problem, in addition to providing robust solutions, can obtain near-optimal solutions to the SP-CCSBP problem. We implement a series of numerical experiments based on real data in the context of surgery scheduling, and the results demonstrate that our proposed B&P algorithm is computationally more efficient than a standard branch-and-cut algorithm, and it significantly improves upon the performance of a well-known bin-packing heuristic.

Keywords: bin packing; chance constraints; branch and price; surgery scheduling (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2019.0894 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:32:y:3:i:2020:p:547-564

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().