多变量基数分支的预训练混合整数优化
本文提出了基于三分图的方法表示 MIP 问题,该问题可以通过图卷积网络结合机器学习方法来预测二进制变量的解,以生成一种局部分支类型切割,从而提高求解 MIP 问题的性能。
Jun, 2019
本文介绍了一种将机器学习与混合整数规划相结合的方法,通过构建两个神经网络组件 Neural Diving 和 Neural Branching 来生成高质量的联合变量分配和绑定目标值差异,在实验中,该方法比传统方法得到了更好的结果。
Dec, 2020
本文提出了一种新的基于支持向量机和 1 - 范数分多元决策树(ODT)训练的混合整数规划(MIP)公式,利用线性规划(LP)数据选择方法选择数据样本,实现了对大数据集的有效训练,并在包含 245,000 个样本的数据集上验证了该方法优于现有的启发式方法和其他基于 MIP 的技术的效果。
Nov, 2020
通过深度学习来解决混合整数规划(MIP)模型中固有的计算复杂性,并比较前馈神经网络(ANN)和卷积神经网络(CNN)在逼近 MIP 问题中的活动维度的效果,利用多标签分类来纳入多个活动维度,通过贝叶斯优化进行超参数调优以提升模型性能,并应用于基于流量的设施位置分配混合整数线性规划(MILP)问题,描述个性化医疗供应链中的长期投资规划和中期战略规划。
Jan, 2024
本文提出了一种基于理论模型的枝界算法,其用于选择分支变量的方法是对 MIP 问题进行简化后,对选择不同变量可以得到对偶理论的提升(LP gains)的解析式进行计算,并提出了该方法在实验中的有效性。
Nov, 2015
提出了一种称作 MIP-GNN 的混合整数规划改进方法,利用图神经网络模型预测混合整数线性规划的变量偏差,并将其集成到一个先进的 MIP 求解器中,针对二进制 MILP 的节点选择和启发式方面展示了与默认设置相比的显著改进。
May, 2022
混合整数线性规划 (MILP) 是数学优化领域的重要组成部分,其提供了一个强大的建模语言,适用于各种应用领域。本文总结了近年来在 MILP 求解中使用机器学习算法优化分支定界等主要任务的发展,探索了机器学习和数学优化的整合以及其对 MILP 求解效果的提升。
Feb, 2024
本文提出了一种基于混合整数规划的方法来解决最佳子集选择问题,旨在通过离散优化方法扩展现有的一阶连续优化算法,为线性回归提供更高质量的可行解,并延伸到最小绝对偏差损失函数,最终实验证明本文的方法在求解 $n$ 为 1000s 和 $p$ 为 100s 及 $n$ 为 100s 和 $p$ 为 1000s 的问题时可以在几分钟内得到可靠的最优解,并且相比于其他流行的稀疏学习过程,具有更好的预测能力和更少的稀疏性。
Jul, 2015
我们提出了一个集成的预测 - 优化(PredOpt)框架,通过预测二进制决策变量在最优解中的值,高效地解决顺序决策问题。我们通过循环神经网络和滑动注意机制捕捉组合优化问题的顺序特性,并将基于注意力的编码器 - 解码器神经网络架构与消除不可行性和泛化框架相结合,以学习高质量的适用于时间相关优化问题的可行解。我们的结果表明,可以成功地使用在较短和较小维度实例上训练的模型来预测更长更大维度的问题。优化解决时间可缩短三个数量级,平均最优性差距小于 0.1%。我们将 PredOpt 与各种专门设计的启发式方法进行比较,并证明我们的框架表现优于它们。PredOpt 对于需要立即且重复求解的动态 MIP 问题具有优势。
Nov, 2023
利用蒙特卡洛树搜索方法收集训练数据,通过对比学习框架训练图注意力网络模型来预测 Mixed Integer Programs 中的 MIP backdoors,相比 Gurobi 和之前的模型,在四个常见的 MIP 问题领域中展现了性能的提升。
Jan, 2024