论文标题
分支机构垃圾箱包装的价格
Branch and Price for Submodular Bin Packing
论文作者
论文摘要
子模型垃圾箱包装（SMBP）问题要求将无法填充的项目包装成最小数量的垃圾箱，其容量利用功能是子模型的。 SMBP等同于在各种条件下发生的机会约束和强大的垃圾箱包装问题。 SMBP是一个硬二进制非线性编程优化问题。在本文中，我们提出了一种分支机构和价格算法来解决此问题。由此产生的价格子问题是子模具背包问题，我们根据零件线性放松的量身定制的精确分支和切割算法来解决它们。为了加快柱子的生成，我们制定了一种混合定价策略，以快速定价启发式替代确切的定价算法。我们对文献中建议的实例进行了测试算法。计算结果表明我们的分支机构和价格算法的效率以及提出的定价技术。
The Submodular Bin Packing (SMBP) problem asks for packing unsplittable items into a minimal number of bins for which the capacity utilization function is submodular. SMBP is equivalent to chance-constrained and robust bin packing problems under various conditions. SMBP is a hard binary nonlinear programming optimization problem. In this paper, we propose a branch-and-price algorithm to solve this problem. The resulting price subproblems are submodular knapsack problems, and we propose a tailored exact branch-and-cut algorithm based on a piece-wise linear relaxation to solve them. To speed up column generation, we develop a hybrid pricing strategy to replace the exact pricing algorithm with a fast pricing heuristic. We test our algorithms on instances generated as suggested in the literature. The computational results show the efficiency of our branch-and-price algorithm and the proposed pricing techniques.
