Oct, 2021

整数规划后门发现：一种蒙特卡罗树搜索框架

HTML
PDF
TL;DR提出了一种基于Monte Carlo Tree Search- BaMCTS算法，在Mixed Integer Linear Programming（MIP）中通过构建 backdoor（后门） 数据集来提高MIP问题的求解效率。该算法与传统MIP概念相结合，且与CPLEX求解器紧密集成，成功地优化了MIPLIB2017示例的求解效率。
发现论文，激发创造
  • 无环可满足性问题的后门

    研究使用一个特殊的集合来使得一类复杂计算问题变得简单化的方法，利用该方法可以实现CNF公式求解的多项式时间算法，同时该研究提出了一些关于求解backdoor sets大小和检测方法的结论。

    Oct, 2011

  • 有界树宽 SAT 的强背门

    本文结合分解性和后门集两种方法，研究了在与给定CNF公式相关联的图的树宽不超过t的CNF公式集合W_t中找到一个小的强后门集的算法问题。我们证明了：1.找到大小不超过2^k的强W_t后门集，或确定F没有大小不超过k的强W_t后门集；2.找到CNF公式F的满足分配数量或确定sb_t（F）> k的算法，其中sb_t（F）表示F的最小强W_t后门集的大小。

    Apr, 2012

  • 可追溯的约束语言的后门问题

    本文对基于约束满足问题的多项式算法强后门检测问题进行了系统研究，特别是当目标属性是由多项式函数族定义的特定约束语言时，我们表明在多项式函数族是幂等的假设下，当参数为r（约束元数）或k（后门大小）时，问题不可能是FPT，除非P = NP或FPT = W[2]。但是当参数为k + r时，我们能够识别出大量语言，以便找到小后门的问题是FPT。

    Apr, 2014

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

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

    Jul, 2021

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

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

    May, 2022

  • 基于启发式增强分支定界算法的MILP求解器的设计与实现

    在MIP 2022竞赛的限时10分钟内，我们的混合整数规划求解器，利用分支定界算法和多线程的原始启发式方法，表现出优异的表现，特别是在使用Diving heuristic的情况下，成功地解决了10个数据集实例，这使得我们的竞赛作品获得了“优秀学生投稿”荣誉提名。

    Jun, 2022

  • 无限域约束满足问题中的计算捷径

    研究 CSP 实例的后门问题，提出了一种泛化后门概念，即面向具有高元数约束的 CSP，并介绍了 sidedoors 作为对二元约束不利的替代方案，降低了算法复杂度和提高了计算效率。

    Nov, 2022

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

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

    Apr, 2023

  • 利用对比学习学习混合整数规划问题的后门

    利用蒙特卡洛树搜索方法收集训练数据，通过对比学习框架训练图注意力网络模型来预测 Mixed Integer Programs 中的 MIP backdoors，相比 Gurobi 和之前的模型，在四个常见的 MIP 问题领域中展现了性能的提升。

    Jan, 2024

  • Distributional MIPLIB：一种推进ML-Guided MILP方法的多领域库

    这篇论文介绍了Distributional MIPLIB，一个多领域问题分布库，用于推进基于机器学习引导的MILP方法的研究。通过从现有的工作和未使用的实际问题中策划MILP分布，并对其进行不同难度级别的分类，它为该领域的研究提供了便利，从而实现了对多样化和现实领域的全面评估。我们通过两种方式经验性地说明了使用Distributional MIPLIB作为研究工具的好处：评估了在先前未使用的分布上使用ML引导变量分支的性能，以确定改进的潜在领域；此外，我们提出了从混合分布中学习分支策略，证明了与同质分布相比，当数据有限且能很好地推广到较大实例时，混合分布能实现更好的性能。

    Jun, 2024