报告题目： Introduction to Chance-constrained Bin Packing Problems

报 告 人：张政

报告时间：2019年12月27日（周五）9:00-10:30

报告地点：劝学楼223

主办单位：现代供应链管理研究院

【报告人简介】

张政，浙江大学管理学院“百人计划研究员”、博士生导师。他博士毕业于上海交通大学，并曾在密西根大学从事博士后研究。他的研究重点是将运筹学应用到医疗与健康管理，利用建模和优化方法提高医疗资源运作效率、改善疾病诊疗决策，最终帮助改善我国整体的医疗服务水平；具体研究兴趣包括数据驱动决策优化、随机优化及其在医疗资源运作管理、慢性病管理、健康管理中的应用。其研究成果发表在Informs Journal on Computing和IISE Transactions等期刊，并获得2016年Informs服务科学板块最佳论文提名奖。

【摘要】

In this talk, I will introduce 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. 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 (B&C) algorithm, and it significantly improves upon the performance of a well-known bin packing heuristic.