AAAINov, 2022

基于自适应约束分区的大规模整数线性规划优化框架（学生摘要）

PDF
TL;DR本文提出了一个基于自适应约束分区的优化框架，旨在解决解决大规模整数规划问题时可能会陷入局部最优解的问题。与现有的大邻域搜索算法相比，该框架可以更高效地利用任何现有优化求解器作为子例程来优化决策变量。实验结果表明，该框架在规定的墙钟时间内显示出比 SCIP 和 Gurobi 更好的性能。
integer programming problemslarge neighborhood searchadaptive constraint partition-based optimization frameworklocal optimasubroutine solver
发现论文，激发创造
  • 使用对比学习技术在大邻域内搜索整数线性规划问题

    本文介绍了一种新的算法 CL-LNS，通过使用正负样本集合学习一个次优解算法并使用图注意力网络和更丰富的特征进一步提高解决 LP 问题的性能。

    Feb, 2023

  • 整数线性规划的局部分支松弛启发式算法

    本文探讨了在整数线性规划（ILP）的大邻域搜索（LNS）中设计有效和高效的启发式。 创新性地提出了 LB-RELAX 及其变体，利用线性规划松弛代替 Local Branching 来选择邻居。实验证明相对于 LB，LB-RELAX 及其变体计算出的邻域相同，但是速度更快。在多个 ILP 基准测试中取得了最新的任意时间性能。

    Dec, 2022

  • 大领域优先搜索策略在组合优化与答案集编程中的应用

    我们提出了大邻域优先搜索（LNPS）用于解决回答集程序设计中的组合优化问题。LNPS 是一种元启发式方法，通过交替破坏和优先搜索当前解来寻找更好的解决方案。我们基于 ASP 实现了 LNPS，并通过 heulingo 求解器的实验证明了 LNPS 可以显著提高 ASP 在优化方面的求解性能。此外，我们通过与（自适应）大邻域搜索的对比来证明我们 LNPS 方法的竞争力。

    May, 2024

  • 混合整数规划的大邻域搜索算法学习

    该论文提出了一种基于学习的大邻域搜索 (LNS) 方法来解决混合整数规划 (MIP)，该方法使用神经潜水模型来表示变量分配的可能性分布，并使用非自用 MIP 求解器生成初始分配，并使用诱导学习来训练神经网络选择在每个步骤中寻找下一个分配的邻域。

    Jul, 2021

  • 整数线性规划的局部搜索

    该论文开发了第一个独立的本地搜索模型，使用紧密移动和提升移动两种算子，解决了复杂的整数线性规划问题，并在 MIPLIB 数据集上实现了比市场上同类解决方案更好的结果。

    Apr, 2023

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

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

    Jul, 2019

  • IntSat: 基于冲突驱动约束学习的整数线性规划

    通过扩展冲突驱动子句学习技术，本文使用基于整数线性规划方法处理复杂的实际问题，并讨论该方法在优化方面的潜在改进。

    Feb, 2024

  • 基于线性优化预言机的大规模凸优化问题的复杂性

    本文探讨了一类名为线性优化型凸规划算法的迭代优化算法，证明了它们解决一系列滑顺、非滑顺和某些鞍点问题的低复杂度下界； 验证了在大规模情况下，条件梯度法及其变种求解不同类别的凸规划问题的理论最优性或接近最优性； 推出了几种新的最优 LCP 方法，并通过修改 Nesterov 的加速梯度方法，证明了它们在解决一些大规模凸规划问题的特定类别时的优势。

    Sep, 2013

  • 自适应划分的多元凸回归

    提出了 Convex Adaptive Partitioning (CAP) 这一新的非参数方法，它可以在响应函数上受到凸性或凹性限制的情况下进行多元回归。CAP 是计算有效的，适用于定价具有大量基础资产的美式篮式期权的价值函数近似，并表明 CAP 的计算复杂度为 O (nlog (n) log (log (n)))。

    May, 2011

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

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

    Dec, 2019