管道连接的优化算法（与切割库存算法相反）

Question

我遇到了一个问题，我必须使用管道连接两点。我有不同长度的管道库存，我需要优化管道的选择，以尽量减少浪费的管道（超过目标）并尽量减少管道之间的接头。

我搜索了这个问题的算法，发现了与我需要做的基本上相反的下料算法。是否有处理此类问题的算法？任何建议表示赞赏。

Answer 1

下料问题的“对立面”是装箱问题 (BPP) - 尽管在数学上它们本质上是相同的。此外，在您的情况下，您可以超出垃圾箱的容量。 BPP 可以表示为混合整数线性规划 (MILP)，并通过 CBC、CPLEX、Gurobi 等 MILP 求解器求解。还有各种可用的启发式方法，至少会找到一个好的解决方案。

请注意，将长度超过 0.5 的边料视为不浪费可能会导致短件堆积。这将增加连接的数量，从而增加以后的成本。即短期的最优解从长远来看可能不是最优的。