优化木材采购

Question

我想知道如何对以下优化问题进行分类。

木材堆场出售2x4的各种库存长度。例如，8英尺可能是3美元，10英尺可能是4美元，而14英尺可能是5.50美元。重要的是，长度与价格没有线性关系，并非所有离散长度都可以作为库存购买。可以假设现有的库存单位在这些不连续的长度上是无穷的。

length cost 
7.7ft  $2.75 
    8ft  $3.00 
10ft  $4.00 
14ft  $5.50 

我需要从上述股票的切割它们来创建一组2×4的给定长度的（说我需要2英尺，长度2.5英尺，6英尺一旦所有说，做）。此外，每个“切割”产生的材料成本为1/8英寸（即0.0104英尺），问题的解决方案是将每个所需长度分配给一块库存，同时最小化所有库存的总成本。 ，最小化成本的最佳解决方案是以5.50美元的价格购买一块14英尺的主板（亚军解决方案是购买两块8英尺的主板，分配成{6ft}和{2ft，0.0104ft，2.5ft}，成本为6美元。）

它似乎不是一个背包级问题，它似乎并不是一个切割库存问题（因为我想最小化成本而不是最小化浪费），这是什么问题？我可以去有效地解决它吗？

（作为一个后记，这是一个非虚构的问题，我hav e在Haskell中使用multiset分区和迭代以明显，低效的方式解决。运行时间对于超过23种所需长度和6种可用库存尺寸的实际使用是禁止的。）

Answer 1

我相信这是一个切削库存问题，除了它是一个多目标或多标准切削问题（其中您想最小化货币成本以及材料成本），请参阅本例this article。不幸的是，我发现这个品种的切割库存问题几乎所有的在线资源都在付费墙之后;另外，我在几年内还没有做过任何整数线性规划，但是如果我没记错的话，多目标问题比单一目标问题困难得多。

一种选择是实现双通道算法。第一遍完全忽略了切割纸板的材料成本，并且仅在单目标问题中使用货币成本（代替标准切割库存问题中的废物成本）。这可能会给您提供一个无效的解决方案，在此时您执行local search，例如用一个14英尺的电路板和一个8英尺的电路板替换两个10英尺的电路板，直到达到一个有效的解决方案。一旦找到有效的解决方案，您可以继续本地搜索多个迭代，以查看是否可以改进解决方案。与一次通过的多目标解决方案相比，该算法可能不是最优的，但它应该更容易实现。