本文提出了一种基于 Gabow 和 Tarjan 的图算法的新颖分析,并提供了一个简单的贪婪式迭代算法,其执行时间为 O(n^2*C/δ + nC^2/δ^2),用于求解概率分布的最优运输问题,在数值不稳定的情况下具有竞争力的执行时间。
May, 2019
本文提出了基于面积凸性的混合装箱问题LP的宽度相关算法并进一步将其应用于最密子图问题中,实现了比宽度独立算法更高的精度。
Sep, 2019
本文研究了多项式最优运输(MOT)距离的近似复杂性,提出了两个新的确定性算法:多重边缘Sinkhorn算法和加速多重边缘Sinkhorn算法。通过实验,证明了这两种算法在计算效率和准确性上的优越性。
该研究利用样本证明了学习高性能的割平面选择策略对于速度优化和优化解的寻求非常重要,同时研究了复杂的割选择策略和树搜索组件的学习方法。
Jun, 2021
探讨了第一方云中的关键资源分配问题:将容器调度到机器中。提出了一个新的目标度量标准 - 置信区间下的已用容量(UCaC),并通过概率约束对SBPP进行了重新定义,使用生成方法对容器资源使用分布进行建模,提出了三种求解算法。
Jul, 2022
我们研究了具有图论约束的背包问题,证明了该问题是NP完全问题,并提出了一个在多项式时间内运行的算法以及一个近似算法。
Jul, 2023
本文利用Q4RealBPP解决了实际问题中的装箱问题,包括异构容器、一维和二维问题实例的扩展以及物品-容器关联要求和配送优先级的特性测试。
Aug, 2023
通过改进BPP启发式算法以及提出新的CBPP启发式算法,并结合基于变量邻域搜索(VNS)和数学启发式方法的邻域搜索算法,我们的研究表明,我们的数学启发式方法优于VNS,两种方法都可以在大量实例中找到近乎最优的解,甚至对于具有许多物品的实例也是如此。
Oct, 2023
本文首次对机器学习相关的装箱问题(BPP)方法进行了系统回顾,介绍了BPP的变体和实际限制,并对多维BPP进行了全面调研。同时,我们收集了一些3D BPP的公共基准,并在Cutting Stock数据集上评估了一些在线方法。最后,我们分享了在装箱问题中存在的挑战和未来方向。
Dec, 2023
通过使用机器学习预测以改善算法的性能,该研究论文介绍了一种针对在线装箱问题的简单的学习增强算法,并展示了该框架在线性规划、背包问题、资源管理效益、吞吐量最大化和网络效用最大化等多个领域的直接应用,同时提出了理解简单黑盒解决方案何时可优化的必要与充分条件的问题。
Jun, 2024