Optimization Online


Chance-Constrained Bin Packing Problem with an Application to Operating Room Planning

Shanshan Wang(shshwang_bit***at***163.com)
Jinlin Li(jinlinli***at***bit.edu.cn)
Sanjay Mehrotra(mehrotra***at***iems.northwestern.edu)

Abstract: We study the chance-constrained bin packing problem, with an application to hospital operating room planning. The bin packing problem allocates items of random size that follow a discrete distribution to a set of bins with limited capacity, while minimizing the total cost. The bin capacity constraints are satisfied with a given probability. We investigate a big-M and a 0-1 bilinear formulation of this problem. We analyze the bilinear structure of the formulation and use the lifting techniques to identify cover, clique and projection inequalities to strengthen the formulation. We show that in certain cases these inequalities are facet defining for a bi-linear knapsack constraint that arises in the reformulation. An extensive computational study is conducted for the operating room planning problem that minimizes the number of open operating rooms. The computational tests are performed using problems generated based on real data from a hospital. A lower bound improvement heuristic is combined with the cuts proposed in this paper in a branch-and-cut framework. The computations illustrate that the techniques developed in this paper can significantly improve the performance of the branch-and-cut method. Problems with up to 1,000 scenarios are solved to optimality in less than an hour. A safe-approximation based on conditional value at risk (CVaR) is also solved. The computations show that the CVaR approximation typically leaves a gap of one operating room (e.g., six instead of five) to satisfy the chance constraint.

Keywords: chance-constrained stochastic programming, bin packing, bilinear integer program, branch-and-cut, valid inequalities, operating room planning

Category 1: Applications -- OR and Management Sciences

Citation: Wang, Shanshan, Jinlin Li, and Sanjay Mehrotra. "Chance-Constrained Bin Packing Problem with an Application to Operating Room Planning." (2019)

Download: [PDF]

Entry Submitted: 02/01/2019
Entry Accepted: 02/01/2019
Entry Last Modified: 02/01/2019

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