Cocktail Optimization, an Integer Programming Problem 深度解读

背景

整数规划（Integer Programming）是运筹学和计算机科学中一类极具挑战性但也极具魅力的优化问题。作者长期关注这一领域，特别是在数据去重（dedupe）任务中，整数规划往往扮演着核心角色。

在过去，面对这类问题时，作者倾向于采用“手工打造”的方式，即编写自定义的分支定界（branch-and-bound）算法来求解。然而，随着项目需求的演变，作者近期开始使用 Google 的 OR-Tools 库来处理涉及大量车辆路径规划（Vehicle Routing Problem, VRP）的项目。这一实践经历促使作者产生了一个疑问：这些经过工业界千锤百炼的混合整数线性规划（MILP）求解器，究竟能否在性能上超越作者精心编写的定制算法？

核心内容

文章通过一个具体的“鸡尾酒优化”案例，直观地展示了现代通用求解器相对于传统手写算法的巨大优势。

1. 求解器的技术奇迹

作者坦言，现代混合整数线性规划求解器在性能上彻底碾压了作者过去“精心呵护”的定制算法。这些求解器并非简单的代码堆砌，而是凝聚了数千小时的研究成果和工程智慧，堪称技术奇迹。作者承认，个人的手写代码在如此强大的工业级工具面前，根本无法构成竞争。

2. 鸡尾酒优化问题定义

几年前，作者曾为了解决“在给定鸡尾酒托盘的原料数量限制下，最大化能制作的鸡尾酒种类数量”这一问题，编写了一个分支定界求解器。当时作者对此颇为自豪。

然而，该自定义算法存在明显的性能瓶颈：

• 计算耗时：当原料预算（ingredient budget）设定为 30 时，找到最优解需要花费数分钟。
• 收敛困难：算法在找到初步解后，几乎不会停止搜索更优解的过程，导致计算资源浪费且结果不确定。

3. 现代求解器的表现对比

为了验证现代求解器的能力，作者使用 glpk.js（GLPK 的 JavaScript 端口）重新运行了相同的优化问题。结果令人震惊：

• 速度提升：求解时间从“数分钟”缩短至“毫秒级”。
• 结果确定：算法迅速找到了最终的最优解，并给出了明确的购物清单。

4. 具体案例结果

在原料预算为 30 的情况下，模型计算出最多可以制作 29 种 鸡尾酒。系统随即生成了对应的购物清单（Shopping List），列出了所需的具体原料。

关键要点

• 通用求解器的压倒性优势：Google OR-Tools 等现代混合整数线性规划（MILP）求解器，在性能和效率上远超个人编写的定制分支定界算法。
• 工业级算法的积累：这些求解器背后是成千上万小时的科研与工程投入，代表了该领域的最高技术水平。
• 自定义算法的局限性：即使是作者自认为“写得不错”的分支定界算法，在处理中等规模问题（如 30 个原料预算）时，也存在耗时长（分钟级）和难以收敛的问题。
• 毫秒级求解能力：使用 glpk.js 等现代工具，同样的问题可以在毫秒级别内得出精确的最优解。
• 从理论到实践的验证：通过“鸡尾酒优化”这一具体案例，验证了将问题建模为整数规划并使用标准求解器求解的高效性。

意义与影响

这篇文章虽然篇幅简短，但揭示了一个在数据科学和工程实践中常被忽视的重要真理：不要重复造轮子，尤其是对于复杂的组合优化问题。

1. 工程实践建议：对于数据去重、资源分配、路径规划等涉及整数规划的场景，开发者应优先选择成熟的求解器（如 Gurobi, CPLEX, OR-Tools, GLPK 等），而不是尝试从头实现分支定界或割平面算法。除非有极特殊的约束条件或性能需求，否则手写算法往往在鲁棒性和速度上都无法与工业级求解器抗衡。
2. 技术民主化：glpk.js 等工具的出现，使得即使在浏览器端或轻量级环境中，也能调用强大的优化求解能力，降低了使用高级优化技术的门槛。
3. 认知转变：它提醒技术人员，现代求解器不仅仅是数学公式的代码实现，而是集成了启发式搜索、线性规划松弛、割平面生成等大量高级技术的复杂系统。理解并利用好这些工具，比掌握底层算法细节更能解决实际问题。