研究人员找到了一种更快的整数线性规划方法

原文 ↗ Hacker News 讨论 ↗

研究人员提出了一种用于整数线性规划（ILP）的新算法，在理论上的最坏情况运行时间上有了显著改进，收紧了这一核心 NP-hard 优化问题已知的界限。评论者将这一突破与当今求解器（如 Gurobi、CPLEX、SCIP）中大量工程化的 branch-and-bound 和基于单纯形的方法进行对比，指出实际性能更多取决于启发式、数值计算和问题结构，而不是渐近保证。讨论也扩展到线性规划和整数规划如何支撑现实中的调度、物流和组合优化，何时近似或启发式方法已经足够，以及为什么理论进展仍可能需要多年才能转化为工业工具。

学习和使用线性 / 整数规划

  • 许多评论者认为软件工程师应该学习 LP/ILP；很多现实世界问题都可以这样建模（调度、类似背包的任务、套利、路由、近似算法）。
  • 推荐的实际入门路径：Python 库（PuLP、Google OR-Tools）、标准运筹学教材、研究生级近似算法讲义。
  • 概述了 LP 基础：可行域、有界性、极点、单纯形法，以及连续 LP 与 ILP 之间的区别。

术语与历史（“Programming”）

  • 一些人认为“linear programming”和“integer linear programming”这个名字不够贴切。
  • 历史说明：“programming”来自军事计划/排程，而不是编程；“dynamic programming”的命名部分是为了避免对“mathematical research”的政治反弹。
  • 有人建议把“programming”理解为“排程”，这样这些术语会更容易理解。

复杂性、理论与实践

  • ILP/0-1 ILP 是 NP-hard/NP-complete；最坏情况算法是超指数级的（此前约为 nⁿ·2^O(n)，现在改进为 (log n)^O(n)）。
  • 评论者强调：最坏情况的困难性并不妨碍实际可解性；在现代求解器和启发式方法下，许多真实实例是可处理的。
  • 连续 LP 在理论上是多项式时间（椭球法、内点法等），但单纯形法尽管最坏情况是指数级，仍因结构复用和工程优化而在实践中占主导地位。

对现有求解器的影响

  • 新结果普遍被看作主要是理论性的：它改进了基于格的 ILP 算法的复杂度界，而不是工业界使用的 branch-and-bound MILP 求解器。
  • 实际求解器是深度工程化的启发式、割平面和单纯形/LP 引擎的集合；要整合一种基于格的方法，需要大量研究和重新工程化。
  • 当前格方法在大问题上仍然吃力，因为它们需要任意精度算术、稠密运算和较大的内存；它们主要在小众的密码学/数论场景中表现出色。

启发式、元启发式与自然类比

  • 讨论了蚂蚁、群智能和蚁群优化：受自然启发的方法通常能找到不错的局部最优，但不能保证全局最优。
  • 经典近似方案（例如用于欧几里得 TSP 的 Christofides–Serdyukov）提供可证明的界；元启发式通常缺乏这类保证。
  • 对“bio-inspired metaheuristics”文献的批评很强烈：许多方法只是换了名字的变体，基准测试薄弱，严谨性不足。

职业与应用

  • OR/LP/ILP 被视为强大但小众；有人描述其在工业中的影响很大（电网市场、物流、类似 FedEx 的车队调度），但职业路径也有限。
  • 讨论了将工业工程、OR 和 CS 结合；运筹学被描述为 IE + 数学优化 + 编程。