Agent算法工程：优化共享内存精确最小割

无向边加权图的最小割问题要求我们将其节点集分为两个块，同时最小化割边的加权和。在过去的几年里，我们针对这个问题设计了一系列快速算法。我们最快的精确算法使用不精确算法来获得问题的更好界限、依赖于该界限的减少、改进的数据结构和并行收缩例程。它可在开源包 VieCut 中使用，在实际实例中，顺序运行时的性能比以前最快的求解器高出 2.5 倍，并行运行时高出 12.9 倍。我们使用智能体算法工程（AAE）来改进这个算法，这是我们在这里介绍的一种方法，其中自治大语言模型智能体在现有代码库上运行算法工程周期：它们形成关于运行时间损失的假设，实现它们，在固定实例集上对结果进行基准，并保留或放弃更改。尽管我们已经手动广泛调整了算法，但智能体发现了显着的优化，特别是在 DIMACS 核心实例上：实际 k 核心上的因子为 1.28（顺序）和 1.63（32 个线程），DIMACS 核心实例上的因子为 6.26 和 127。