2000元阿里云代金券免费领取，2核4G云服务器仅664元/3年，新老用户都有优惠，立即抢购>>>
阿里云采购季（云主机223元/3年）活动入口：请点击进入>>>，
阿里云学生服务器（9.5元/月）购买入口：请点击进入>>>，
ICLR、NIPS和ICML是人工智能领域的三个顶级学术会议，以下是它们的介绍：
ICLR (International Conference on Learning Representations) 是一个聚焦于深度学习和表示学习领域的国际性学术会议，由深度学习三巨头之中的Yoshua Bengio和Yann LeCun牵头创办，2013年开始每年举办一次，已经得到学术研究者们的广泛认可，被认为是深度学习领域的顶级会议。
NeurIPS (Conference on Neural Information Processing Systems) 是一个主要关注神经网络和机器学习领域的大型学术会议，固定在每年的12月举行。它提供了一个交流和展示最新研究成果的平台，吸引了世界各地的研究人员和从业者。NIPS会议涵盖的主题广泛，包括深度学习、强化学习、神经网络、模式识别等，是该领域的顶会。
ICML（International Conference on Machine Learning）是一个专注于机器学习领域的国际性学术会议，创办于1980年，每年6月中下旬举行。会议包括主题演讲、技术报告、海报展示等环节，旨在促进学术界和工业界之间的交流与合作。ICML覆盖了机器学习的多个方向，包括监督学习、无监督学习、强化学习、集成学习等，是机器学习领域的顶会。
本文梳理了ICLR 2023、ICML 2023、NeurIPS 2023有关机器学习+混合整数规划问题求解加速求解加速的研究成果，总共包含8篇文章。
A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming ICLR, 2023
论文地址：arxiv.org/abs/2302.05…
论文源码：github.com/sribdcn/Pre…
论文摘要：混合整数线性规划（MILP）被广泛用于建模组合优化问题。在实践中，部分业务场景所产生的MILP实例通常仅在优化目标或约束项的系数上有所差异，并且机器学习算法具备识别相似MILP实例之间共同模式的能力。在这项工作中，我们将机器学习跟优化算法结合起来，提出了一种新颖的预测和搜索框架，以有效地识别高质量的可行解。具体而言，我们首先利用图神经网络预测每个变量的边际概率，然后在围绕初始预测解所定义的合适球体内搜索最佳可行解。我们在公开的标准数据集上进行了大量实验，结果表明我们提出的框架在primal gaps这个指标上相比开源求解器SCIP以及商业求解器Gurobi分别提升了51.1%和9.9%。
On Representing Mixed-Integer Linear Programs by Graph Neural Networks ICLR, 2023
论文地址：arxiv.org/abs/2210.10…
论文源码：github.com/liujl11git/…
论文摘要：虽然混合整数线性规划（MILP）的求解通常是NP-hard的，但在过去的二十年里，实际应用中的MILP的求解效率大致获得了100倍的提升。然而，随着问题规模的增加，很多类型的MILP很快变得无法解决，这促使研究人员寻找新的加速技术来处理这些MILP。借助深度学习算法，研究人员取得了显著的进展，其中不少研究成果是通过将图神经网络（GNN）应用于求解MILP的各个阶段（例如初始解构建、分支定界变量/节点选择等）而获得的。然而，我们的工作揭示了1个根本的局限性：过往工作提出的图神经网络模型会同等对待存在可行解以及不存在可行解的MILP，这说明它们刻画通用MILP的能力还存在缺陷。接着，通过将MILPs限制为不可展开的问题或添加随机特征，我们发现特定的GNNs能够可靠地预测MILP的可行性、最优目标值和最优解，且能达到预期的精度。最后，我们进行了小规模的实验来验证前面的理论发现。
Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model ICLR, 2023
论文地址：arxiv.org/abs/2302.00…
论文源码：github.com/MIRALab-UST…
论文摘要：割平面法是解决混合整数线性规划问题（MILPs）的核心算法之一。然而，割平面法的求解效率严重依赖两个关键问题: P1-优先选择哪些切割、P2-选择多少个切割。虽然很多MILP求解器通过手动设计的启发式方法解决了P1和P2，但机器学习提供了1个有望从特定业务场景所收集的MILPs中学习更有效的启发式方法的途径。然而，大部分现有的机器学习方案侧重于学习优先选择哪些切割，而忽视了切割数量的重要性。此外，我们从实验结果中观察到，切割的选择顺序-P3 对解决MILPs的效率也有着显著影响。为了应对以上的挑战，我们提出了一种新颖的层次序列模型（HEM），其核心思想是通过强化学习学习切割选择策略。具体而言，HEM包含两个层次的模型：高层次模型，负责学习合适的切割数量；低层次模型，将切割选择任务转化为1个序列到序列的学习问题，在高层次模型确定切割数量的前提下学习有序子集的选择。据我们所知，HEM是第1个从数据驱动的角度同时解决切割选择中3个核心问题的方案。实验证明，与人工设计以及基于机器学习的基线相比，HEM在合成以及来自真实业务的大规模MILPs（包括MIPLIB 2017）上显著提高了MILPs的求解效率。此外，实验结果同时表明了HEM能有效地求解比训练阶段见过的规模更大的MILPs.
Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning ICML, 2023
论文地址：arxiv.org/abs/2302.01…
论文源码：github.com/facebookres…
论文摘要：整数线性规划（ILPs）是用于建模和解决大量组合优化问题的强大工具。最近的研究表明，经典的启发式算法大邻域搜索（LNS）能够比分支定界（Branch and Bound）更快地找到ILPs的高质量可行解。然而，如何找到合适的启发式方法来最大化LNS的求解性能仍然没有很好地解决。在本文中，我们提出了一种基于对比学习（Constrastive Learning）的新颖方案CL-LNS。在好几个标准ILP benchmarks上，该方案能在primal gap、primal intergal等核心指标上取得sota。具体而言，CL-LNS会先从1个求解效率较慢但能获取较优解的专家（经典的启发式算法）中收集正负样本，然后通过对比学习这种范式学习出1个更有效的启发式算法。此外，我们还使用图注意力网络以及更丰富的特征来进一步提高CL-LNS的性能。
GNN&GBDT-Guided Fast Optimizing Framework for Large-scale Integer Programming ICML, 2023
论文地址：openreview.net/forum?id=tX…
论文源码：github.com/thuiar/GNN-…
论文摘要：最新的基于图神经网络（GNN）和大邻域搜索（LNS）的两阶段优化框架在大规模整数规划问题（IPs）求解中非常流行。然而，该框架不能有效地利用GNN所产出的包含空间信息的embedding，而是仍然严重依赖LNS中的大规模求解器，导致能求解的IP的规模受到当前求解器性能瓶颈的限制。为了解决这些问题，本文提出了一种基于GNN和GBDT引导的快速优化框架，该框架可以配合小规模优化器高效解决大规模IPs。具体而言，本文提出的框架可以分为三个阶段：使用多任务学习范式训练GNN，目标是生成包含空间信息的低纬稠密embedding；引入基于GBDT的预测模块，从而有效利用上阶段构建的embedding；在邻域搜索中使用小规模优化器。通过大量实验证明，本文提出的框架能解决百万规模的IP，且在指定的求解时间内仅使用问题规模的30%的小规模优化器就能获得比SCIP和Gurobi更优的解。此外，相关实验还表明本文提出的框架能在节省99%运行时间的情况下打平SCIP的求解效果，这也验证了所提框架在解决大规模IPs方面的有效性和效率。
Learning to Configure Separators in Branch-and-Cut NeurIPS, 2023
论文地址：arxiv.org/abs/2311.05…
论文源码：github.com/mit-wu-lab/…
论文摘要：割平面算法在解决混合整数线性规划问题（MILP）中至关重要，因为它们有助于改进最优解的边界。现有的MILP求解器依赖于各种separators，且在解决过程中频繁调用separators以生成多样化的切割平面集。本研究发现，选择合适的separators能显著提高MILP求解器的求解效率。考虑到不同separators之间能够形成的组合非常多（2的n次方），因此我们提出了一种新颖的数据驱动方案来限制选择空间，并在受限空间上使用learning-guided的算法。本文提出的方法会根据每个MILP实例的特性构建出合适的且在求解过程中可以动态调整的separators，从而有效地提升了开源求解器SCIP的求解效率。在多个MILP benchmark上的实验可知，本文提出的方案能在获取相同质量可行解的前提下大幅度降低求解时间（合成数据/真实数据，分别降低了72%/27%）。
Learning to Dive in Branch and Bound NeurIPS, 2023
论文地址：arxiv.org/pdf/2301.09…
论文源码：暂未找到；
论文摘要：针对初始解的启发式算法（Primal heuristics）对于混合整数线性规划问题（MILP）的求解至关重要，因为它们能够找到有助于分支定界搜索的可行解。diving heuristics是经典算法之一，它们能从分支定界搜索树的任意节点出发，通过迭代式地调整和解决线性规划来进行深度优先搜索。现有的diving heuristics依赖于通用的决策规则，而没有充分利用相似问题在结构上的共性。因此我们提出一种新方案L2Dive，它能基于图神经网络学习特定的diving heuristics：先训练1个用于预测变量取值的生成模型，然后借助线性规划的对偶性以及模型的预测值产出diving决策。L2Dive具有较好的适配性，我们能将其集成到开源求解器 SCIP 中。通过大量的实验，我们发现L2Dive 在很多组合优化问题上的表现要优于标准的diving heuristics（即能找到更好的可行解）。
A Deep Instance Generative Framework for MILP Solvers Under Limited Data Availability NeurIPS, 2023
论文地址：arxiv.org/abs/2310.02…
论文源码：github.com/MIRALab-UST…
论文摘要：在过去的几年中，使用机器学习（ML）技术解决组合优化问题（CO）的工作经历了爆炸性增长（尤其是针对混合整数线性规划的求解加速）。尽管取得了显著的成就，但实际问题中规模有限的MILP数据集可能会导致次优决策和有偏向的求解器评估，这促使人们提出了一系列针对MILP实例的合成技术。然而，现有的方法要么过于依赖专家的设计，要么难以捕捉真实MILP实例的丰富特征。为了解决这个问题，我们提出了G2MILP，这是第1个用于MILP实例的深度生成框架。具体而言，G2MILP先将MILP实例表示为二分图，然后使用掩码变分自编码器（masked variational autoencoder）迭代性地破坏和替换原始二部图的部分信息，从而生成新的二部图。G2MILP的优点在于它能在不引入专家知识的前提下生成新颖且逼真的MILP实例，同时保留真实数据集的结构和求解难度。因此，生成的实例可以在数据集规模比较有限的情况下提升MILP求解器处理下游任务的能力。我们设计了一套基准测试来评估合成MILP实例的质量，实验证明G2MILP能够生成在结构和求解难度方面与实际数据集非常相似的实例。
原文链接，欢迎关注公众号【决策AI探索者】，获取更多有关决策AI的前沿工作～
https://mp.weixin.qq.com/s?__biz=MzUxMjQzOTc1Nw==&mid=2247483778&idx=1&sn=91b4890704278e4d8ca70a1b15520f9b&chksm=f9652520ce12ac36571d8d728b8f383b1e08768fc8be04d9ba9e2527c37fc80f09c60ab40910&token=542039009&lang=zh_CN#rd
![[译][AI OpenAI-doc] 延迟优化](https://ucc.alicdn.com/tbo73ymmu5nmu_20240513_802c2d330d8f44d1bed5bdb43be55cba.png?x-oss-process=image/resize,h_160,m_lfit)