KDDJun, 2024

整数规划的有效可行解生成方法：引导扩散

PDF
TL;DR我们提出了一种新颖的框架，通过对整数规划实例和解决方案之间的关系进行对比学习，以生成完整的可行解，其质量可与 Gurobi 的最佳启发式解相媲美，且在整个数据集上表现优于最先进方法，提高了与最优值之间的差距，并且在所有数据集上保持超过 99.7% 的可行比率。
integer programmingdeep learningfeasible solutionscontrastive learningheuristic solutions
发现论文，激发创造
  • 利用神经网络解决混合整数规划问题

    本文介绍了一种将机器学习与混合整数规划相结合的方法，通过构建两个神经网络组件 Neural Diving 和 Neural Branching 来生成高质量的联合变量分配和绑定目标值差异，在实验中，该方法比传统方法得到了更好的结果。

    Dec, 2020

  • 阈值感知学习生成混合整数规划可行解

    研究通过优化变量分配的覆盖率，建立深度神经网络模型以实现高质量的可行解，在组合优化问题中实现了最先进的性能表现。

    Aug, 2023

  • 基于数据驱动的框架用于指导组合优化求解器 (MIP-GNN)

    提出了一种称作 MIP-GNN 的混合整数规划改进方法，利用图神经网络模型预测混合整数线性规划的变量偏差，并将其集成到一个先进的 MIP 求解器中，针对二进制 MILP 的节点选择和启发式方面展示了与默认设置相比的显著改进。

    May, 2022

  • 深度学习增强的整数混合优化：学习降低模型维度

    通过深度学习来解决混合整数规划（MIP）模型中固有的计算复杂性，并比较前馈神经网络（ANN）和卷积神经网络（CNN）在逼近 MIP 问题中的活动维度的效果，利用多标签分类来纳入多个活动维度，通过贝叶斯优化进行超参数调优以提升模型性能，并应用于基于流量的设施位置分配混合整数线性规划（MILP）问题，描述个性化医疗供应链中的长期投资规划和中期战略规划。

    Jan, 2024

  • 用基于学习的算法快速计算随机整数规划的优秀原始解

    本研究提出了一种使用监督学习的新方法来解决约束在第一阶段和第二阶段的两阶段随机整数规划（2SIP）问题，该算法预测问题的 “代表性情景”（RS），以确保解的第一阶段的可行性，并保证第二阶段的可行性。用于计算测试的应用是在两阶段整数规划的情景下，寻找代表性情景，为直线约束下的两阶段随机设施位置问题提供近乎最优解，并且具有很好的计算性能。

    Dec, 2019

  • 基于解预测加速混合整数规划原始解求解

    本文提出了基于三分图的方法表示 MIP 问题，该问题可以通过图卷积网络结合机器学习方法来预测二进制变量的解，以生成一种局部分支类型切割，从而提高求解 MIP 问题的性能。

    Jun, 2019

  • 物理相关扩散模型

    通过在模型训练过程中加入约束条件使其生成的样本更符合所施加的约束，从而提高生成样本与约束的一致性，且相较于现有方法有更好的性能且不影响推断速度；该方法还可以自然地防止过拟合。

    Mar, 2024

  • 无监督神经组合优化的扩散模型框架

    通过引入一种可以上界反向 Kullback-Leibler 散度且避免要求确切样本似然的损失函数，本研究提出了一种能够解决在不依赖相应训练数据的情况下从难以处理的离散集合中进行采样的问题的方法，并展示了该方法在无数据组合优化中实现了最先进的性能。

    Jun, 2024

  • 数据驱动的黑箱优化扩散模型

    基于扩散模型的条件采样方法，在黑盒优化中生成接近最佳解且保留设计的潜在结构，通过建立理论模型和进行实验验证，证明了奖励导向扩散模型在黑盒优化中的效率和准确性。

    Mar, 2024

  • 有限数据可用情况下深度实例生成框架在 MILP 求解器中的应用

    提出了 G2MILP 方法，它作为第一个深度生成 MILP 实例的框架，通过将 MILP 实例表示为二分图，并应用掩码变分自编码器来生成新的实例，既不依赖于专家设计的公式，同时又能保持真实世界数据集的结构和计算难度，从而为增强 MILP 求解器提供有限数据的下游任务提供帮助。

    Oct, 2023