鸡尾酒优化：一个整数规划问题
鸡尾酒优化：一个整数规划问题
2026年6月18日
我对整数规划问题一直很感兴趣（它们是dedupe中最有趣的问题）。过去，我通过编写自定义的分支定界算法来处理它们。最近，我在一个涉及大量车辆路径规划的项目中使用了Google的OR-Tools，并开始好奇这些混合整数线性规划求解器与我精心编写的算法相比表现如何。它们完全超越了我。这些求解器是技术奇迹，凝聚了数千小时研究和工程的结晶。当然，我的代码根本无法与之竞争。
几年前，我编写了一个分支定界求解器，用于解决在给定鸡尾酒托盘上有限原料下最大化可调制鸡尾酒数量的问题。我曾为此感到自豪，但如果你将原料预算设置为30，找到最优解需要很长时间，而且它几乎永远不会停止寻找更好的解。如下所示，使用glpk.js，只需几毫秒就能找到最终的最优解。
使用30种原料，你可以制作29款鸡尾酒。
| 鸡尾酒 | 原料 |
|---|---|
以下是购物清单：
| 原料 | 可制作的鸡尾酒数量 |
|---|---|