ICMLMay, 2024

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

PDF
TL;DR本论文介绍了一种新方法，通过机器学习准确预测最优对偶解，并结合自适应稳定化技术，缩小对偶值获得更准确结果的间隙，实现了在图着色问题中相对于传统方法更大幅度的收敛速率提升。
column generationlinear programsdual valuesstabilization techniquesconvergence rate
发现论文，激发创造
  • 机器学习增强的蚁群算法在列生成中的应用

    机器学习增强蚁群算法（MLACO）是一种用于列生成（CG）的有效方法，通过训练机器学习模型来预测子问题的最优解，并将该预测融入蚁群算法的概率模型中，以生成多个高质量的列。在解决冲突的装箱问题上，实验证明 MLACO 方法显著改善了 CG 的性能，并且当将该方法与分支定价法相结合时，能大幅缩短求解时间。

    Apr, 2024

  • 基于机器学习的定价启发式算法增强列生成法在图着色中的应用

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

    Dec, 2021

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

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

    Dec, 2023

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

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

    Jun, 2022

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

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

    Oct, 2023

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

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

    Feb, 2016

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

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

    Aug, 2023

  • CGXplain: 基于规则的深度神经网络解释，使用双线性程序

    介绍了 CGX（Column Generation eXplainer），一种基于线性规划的分解方法，可以从深度神经网络的隐藏表示中提取规则，优化任意数量的目标，并满足准确复现、稳定性和复杂度降低等特点，提高了可解释性。

    Apr, 2023

  • 通过机器学习解决一类切割生成线性规划问题

    提出了一种基于机器学习的新框架来近似求解割平面问题，并通过分类方法获得近似的割平面，从而提高分支定界树中添加割平面的候选节点的识别效率。

    Oct, 2023

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

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

    Jan, 2024