Apr, 2024

机器学习增强的蚁群算法在列生成中的应用

PDF
TL;DR机器学习增强蚁群算法（MLACO）是一种用于列生成（CG）的有效方法，通过训练机器学习模型来预测子问题的最优解，并将该预测融入蚁群算法的概率模型中，以生成多个高质量的列。在解决冲突的装箱问题上，实验证明 MLACO 方法显著改善了 CG 的性能，并且当将该方法与分支定价法相结合时，能大幅缩短求解时间。
column generationoptimization problemsmachine learning enhanced ant colony optimizationmlacobranch-and-price method
发现论文，激发创造
  • 基于机器学习的定价启发式算法增强列生成法在图着色中的应用

    本文提出使用基于机器学习的定价启发式方法（MLPH）解决大规模优化问题中的瓶颈，经过在图着色问题中的实验表明 MLPH 相比于六种最先进的方法可以显着提高 Column Generation 方法的效率，使其与分支定界法得到更好的表现。

    Dec, 2021

  • 一种基于强化学习的多列选择策略对于列生成

    利用基于强化学习的多列选择策略，通过选择最有前途的列以提高目标值和加快收敛速度，比较传统单列和多列选择策略，在切割库存问题和图着色问题中取得了显著的收敛速度和迭代次数的减少。

    Dec, 2023

  • 基于机器学习的自适应列生成稳定化

    本论文介绍了一种新方法，通过机器学习准确预测最优对偶解，并结合自适应稳定化技术，缩小对偶值获得更准确结果的间隙，实现了在图着色问题中相对于传统方法更大幅度的收敛速率提升。

    May, 2024

  • 基于深度强化学习的列生成算法框架

    本文提出了 RLCG—— 一种用于解决大规模整数线性规划的迭代算法，它是第一个采用强化学习方法的列生成算法，并使用图神经网络表示感兴趣的 LP 的变量约束结构，成功应用于切割库存问题和带时间窗口的车辆路由问题中，相对于常用的贪心策略，该算法平均缩短 22.4％CSP 和 40.9％VRPTW 的 CG 迭代次数。

    Jun, 2022

  • 制造业中基于数据驱动的列生成算法解决装箱问题

    本文提出了一种利用历史数据解决运输中的装箱问题的方法，通过将问题转化为集合覆盖问题，并应用约束处理和流程加速策略来解决该问题，最终得出可以提高装箱成功率并同时减少计算时间的最优解决方案。

    Feb, 2022

  • 基于强化学习的超启发式方法增强列生成在车辆路径规划与调度问题中的应用

    基于强化学习的超启发式框架，在列生成中提供更好的整数解和加速收敛，通过减少含潜在最优解边的网络规模，在解决车辆路径和巴士司机调度问题中比传统方法降低至多 27.9% 和 15.4% 的总成本。

    Oct, 2023

  • DeepACO：神经增强的蚁群优化系统用于组合优化

    DeepACO 是一个利用深度强化学习来自动化启发式设计的通用框架，用于加强现有 ACO 算法的启发式措施并在未来 ACO 应用中省去繁琐的手动设计。作为一个神经增强元启发式方法，DeepACO 在八个组合优化问题上使用单个神经模型和一组超参数始终优于其 ACO 对应物。作为一种神经元组合优化方法，DeepACO 在经典路由问题上表现优于或与特定问题方法相当。

    Sep, 2023

  • 重访基于列生成的数学启发式方法学习分类树

    决策树是一种高度可解释的模型，用于解决机器学习中的分类问题。本文提出了一种基于列生成的启发式方法来学习决策树，在多类别分类实例中减少子问题数量，并改进了数据依赖约束和线性规划松弛解的分离模型，以提高可扩展性。

    Aug, 2023

  • 利用图神经网络增强列生成算法，实现乘客行程规划和机组班次安排的联合优化

    通过使用 AGGNNI-CG 方法（基于注意力机制和门控循环神经网络的混合方法）解决服务调度的基本问题，本研究在复杂的动态移动服务中联合优化乘客行程规划和人员排班，取得了接近最优解决方案，对现有系统进行了显著改进。

    Jan, 2024

  • 列生成的二进制码结构化学习

    本文提出了基于列生成的二进制哈希函数学习框架，通过拥有编码成对相似性比较信息的三元组集合，学习哈希函数来在大边缘学习框架内保留相对比较关系，此方法可以直接优化 AUC 和 NDCG 等多变量性能度量。作者使用列生成和割平面技术来解决优化问题，并提出了一种简化的 NDCG 损失用于有效推理。通过应用于排名预测和图像检索，实验表明，该方法优于一些最先进的哈希方法。

    Feb, 2016