Branch and Price for Chance-Constrained Bin Packing
- 1 July 2020
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 32 (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
This publication has 33 references indexed in Scilit:
- Sample Average Approximation Method for Chance Constrained Programming: Theory and ApplicationsJournal of Optimization Theory and Applications, 2009
- Column generation approach to operating theater planning with elective and emergency patientsIIE Transactions, 2008
- A Sample Approximation Approach for Optimization with Probabilistic ConstraintsSIAM Journal on Optimization, 2008
- Solving a class of stochastic mixed-integer programs with branch and priceMathematical Programming, 2006
- On robust optimization of two-stage systemsMathematical Programming, 2004
- Estimating Times of Surgeries with Two Component ProceduresAnesthesiology, 2003
- A 1312 approximation algorithm for bin packing with extendable binsInformation Processing Letters, 1998
- An exact algorithm for IP column generationOperations Research Letters, 1996
- An Application of Bin-Packing to Multiprocessor SchedulingSIAM Journal on Computing, 1978
- Partitioning procedures for solving mixed-variables programming problemsNumerische Mathematik, 1962