Name
Title | ||
|---|---|---|
Chance-Constrained Multiple Bin Packing Problem with an Application to Operating Room Planning |
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 sizes 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 bilinear 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 lowerbound 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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1287/ijoc.2020.1010 | INFORMS JOURNAL ON COMPUTING |
Keywords | DocType | Volume |
chance-constrained stochastic programming, bin packing, bilinear integer program, branch-and-cut, valid inequalities, operating room planning | Journal | 33 |
Issue | ISSN | Citations |
4 | 1091-9856 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shanshan Wang | 1 | 0 | 0.68 |
| Li Jin-Lin | 2 | 30 | 4.80 |
| Sanjay Mehrotra | 3 | 521 | 77.18 |