Optimization Online


Branch and Price for Chance Constrained Bin Packing

Z. Zhang(zhang***at***sjtu.edu.cn)
B.T. Denton(btdenton***at***umich.edu)
Xiaolan X.(xie***at***sjtu.edu.cn)

Abstract: This article considers two versions of the stochastic bin packing problem with chance constraints. In the first version, we formulate the problem as a two-stage stochastic integer program that considers item-to-bin allocation decisions in the context of chance constraints on total item size within the bins. Next, we describe a distributionally robust formulation of the problem that assumes the item sizes are ambiguous. We present a branch-and-price approach based on a column generation reformulation that is tailored to these two model formulations. We further enhance this approach using antisymmetry branching and subproblem reformulations of the stochastic integer programming model based on conditional value at risk (CVaR) and probabilistic covers. For the distributionally robust formulation we derive a closed form expression for the chance constraints; furthermore, we show that under mild assumptions the robust model can be reformulated as a mixed integer program with significantly fewer integer variables compared to the stochastic integer program. We implement a series of numerical experiments based on real data in the context of an application to surgery scheduling in hospitals to demonstrate the performance of the methods for practical applications.

Keywords: bin packing; chance constraints; branch-and-price; surgery scheduling

Category 1: Stochastic Programming

Category 2: Applications -- OR and Management Sciences

Citation: University of Michigan and Shanghai Jiao Tong University, December, 2015.

Download: [PDF]

Entry Submitted: 11/25/2015
Entry Accepted: 11/25/2015
Entry Last Modified: 11/25/2015

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