利用机器学习的分支限界算法,通过比较三个神经网络 —— 图卷积神经网络(GCNN)、GraphSAGE 和图注意力网络(GAT)的结果,在解决有容量限制的车辆路径问题方面展现了潜力。通过训练这些神经网络,以模拟计算代价高昂的 Strong Branching 策略的决策过程。经过严格的实验证明,这种方法可以在较短的计算时间内达到或超过分支限界算法与 Strong Branching 策略的性能,并且所对应的研究结果和方法的源代码在以下网址中可以轻松获得并进行参考。
Oct, 2023
本文提出了一种基于深度神经网络和注意力机制的学习启发式算法的大邻域搜索框架,用于解决车辆路径问题,该方法在性能方面优于现有的机器学习方法,也接近于现有优化方法的性能。
Nov, 2019
通过将 Capacitated Vehicle Routing Problem(CVRP)转化为 Constrained Centroid-Based Clustering(CCBC),本文提出了一个基于 CCBC 的近似解决方法,该方法利用常见的聚类算法(如 K-means)将一个指数复杂度的问题转化为多项式复杂度的问题,并在实验中展示了该方法在解决车辆路径问题(VRP)方面的优越性。
Mar, 2024
本文将界定传播程序推广到允许添加任意切割平面约束,包括涉及松弛整数变量的约束,并将其命名为广义界定传播程序 (GCP-CROWN),提高了神经网络验证的效率和 GPU 加速,实现了全面解决 Oval 20 基准和优于当今众多基准的状态表现验证工具在 Oval 21 基准上的效果。
Aug, 2022
本研究通过机器学习,在混合整数线性规划问题中选择切平面,以加速求解过程并提高求解时间。
Nov, 2023
通过聚类的数据驱动方法,将车辆路径问题分解成子问题以降低复杂性,并应用剪枝和局部搜索来优化解决方案。结果表明,该方法在解决大规模车辆路径问题时优于传统基于空间信息的方法,并能够适应不同情景的路由问题。
Jan, 2024
研究基于竞争市场背景下的设施选址问题,采用随机实用选择模型预测客户需求。引入了路由约束,确保所选择的位置存在一个符合指定上界的旅行访问所有选定位置的路径。通过外估计近似法、子模割平面法和子回路消除法解决非线性目标函数和复杂路由约束问题,并开发了两种精确解法。同时,基于局部搜索的元启发式方法用于解决大规模实例,并与精确方法进行比较,实验证明了我们方法在解决方案质量和计算时间方面的优越性。
我们提出了一种定制的分支限界算法来解决 $k$-densest-disjoint biclique 问题,通过同时聚类数据矩阵的行和列,找到给定加权完全二分图的 $k$ 个不相交的完全二分子图(称为 bicliques),使它们的密度之和最大化。
本文提出了一种数据驱动的、可推广的割平面方法 Cut Ranking,用于选择多实例学习中的切割。通过训练一个由特征决定的评分函数,该方法被证明比传统的启发式算法更为有效,可适用于具有不同特性的多种问题,且在实验和在线 A / B 测试中效果显著。
May, 2021
提出了一种基于机器学习的新框架来近似求解割平面问题,并通过分类方法获得近似的割平面,从而提高分支定界树中添加割平面的候选节点的识别效率。