ICMLMay, 2021

CombOptNet：通过学习整数规划约束来解决正确的 NP-hard 问题

PDF
TL;DR在这项工作中，我们旨在将整数规划求解器整合到神经网络架构中作为能够学习成本项和约束项的层，以便从原始数据中提取特征并使用最先进的整数规划求解器解决适当的（经过学习的）组合问题。该结果的端到端可训练架构以综合性能分析在合成数据上演示，且在竞争性计算机视觉关键点匹配基准上有展示其潜力。
machine learninginteger programmingneural networkcombinatorial problemcomputer vision
发现论文，激发创造
  • 物理启发图神经网络的组合优化

    本文介绍了如何使用图神经网络来解决组合优化问题，包括最大割、最小顶点覆盖和最大独立集等一些组合优化问题。通过在问题哈密顿量上应用松弛策略，我们生成了一个可区分的损失函数，并在无监督训练过程结束后对整数变量进行简单的投影。实验表明，我们的方法在解决包含数百万个变量的问题时能够胜任。

    Jul, 2021

  • 使用图卷积神经网络进行精确组合优化

    本文提出了一种基于图卷积神经网络的分支定界变量选择新模型，通过模仿学习和强分支专家规则训练，成功解决了组合优化问题。实验结果表明，该方法不仅在分支机制上优于现有的机器学习方法，而且在大问题上也优于现有的专家设计分支规则。

    Jun, 2019

  • 带逻辑约束的混合整数优化问题的统一方法

    本文研究了一种统一的框架方法用于解决一类混合整数优化问题，通过对其逻辑约束进行非线性方式的表达，结合规则化条件及基于混合精度算法，形成了凸二进制优化问题，并利用一种综合的数字策略方法解决问题。

    Jul, 2019

  • 可扩展的深度学习与逻辑推理的耦合

    本文介绍了一种可扩展的神经网络结构和损失函数，专门用于学习离散图形模型所表达的 NP-hard 解决问题的约束和标准，并在实践中证明其能够高效地从自然输入中学习如何解决 NP-hard 推理问题，具有数据效率，可解释性和后验控制。

    May, 2023

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

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

    Aug, 2023

  • 结合强化学习和约束编程用于组合优化

    本文介绍了一种基于深度强化学习和约束编程的混合算法，应用于复杂的组合优化问题，并在实验中成功运用于旅行商问题和投资组合优化问题，表现优于单独的深度强化学习和约束编程算法，同时也达到了与工业级求解器相竞争的水平。

    Jun, 2020

  • 从数据中挖掘约束条件的整数线性规划框架

    本文提出了一种用于从数据中挖掘约束条件的一般框架，该框架以整数线性规划问题的形式考虑结构化输出预测中的推断，然后通过估计可行集的外部和内部多面体来挖掘底层约束条件，并在各种合成和现实应用中验证了所提出的约束挖掘算法。

    Jun, 2020

  • 最大约束满足的图神经网络

    提出了一种解决组合优化问题的图神经网络体系结构，可运用于所有二元约束满足问题的训练，无监督训练，性能非常优秀。尽管是通用的，但其性能可超过大多数贪心和半定编程算法，有时甚至优于特定问题的最优启发式算法。

    Sep, 2019

  • 基于整数规划的贝叶斯网络学习的进展

    本研究通过整数规划方案和贪心算法等方法，从离散数据中学习 Bayesian 网络，在实验结果中取得了和之前相比有着巨大的改进。

    Sep, 2013

  • 图卷积网络与引导树搜索的组合优化

    文章提出一种基于深度学习和启发式算法的图卷积网络方法，用于解决某些 NP 困难问题，并在四个 NP 困难问题和五个数据集上进行了评估，结果表明该方法在某些 NP 困难问题上已经达到了高度优化的最新启发式算法的水平，并具有较强的泛化性和扩展性。

    Oct, 2018