打印多张贴纸时最小化印版数量的算法

Question

我正在研究一种算法，通过解决印刷公司面临的问题来优化其成本。该问题与背包问题类似，但有一点不同，我们需要优化需要使用的独特容器的数量，而不是最小化容器的数量来容纳内容。问题是印刷公司首先需要设计和开发印刷版，然后用于印刷纸张。印刷纸张很便宜，但印刷印版很昂贵，因此公司必须最大限度地减少所需制造的印版数量，以实现所需的结果。 简单来说，有 X 种不同类型的贴纸需要打印一定数量。每个印版可容纳N张贴纸。我们需要一种算法来计算打印给定贴纸所需的最小印版数量（印版可以无限次使用来打印一张纸）。一个简单的未优化方法是创建 X 个印刷版并在每个版中容纳 N 个贴纸，即如果版尺寸为 10 并且有 2 种不同类型的贴纸，我们需要打印 A(200) 和 B(300)，我们可以简单地创建 2 个印版，第一个印版有 10 个 A 贴纸，第二个印版有 10 个 B 贴纸，然后我们可以根据所需数量进行打印（印版 1 为 20 张，印版 2 为 30 张）。然而，更好的方法是使用 1 个印版，贴有 4 个 A 贴纸和 6 个 B 贴纸，然后打印 50 张以达到所需数量。

When plate size = 10 and required quantities = {A: 200, B: 300}

Unoptimized Approach:

 _________               _________
|A|A|A|A|A| x 20        |B|B|B|B|B| x 30
|A|A|A|A|A|             |B|B|B|B|B|
 ---------               ---------

Optimized Approach:
 _________
|A|A|A|A|B| x 50
|B|B|B|B|B|
 ---------

任何帮助将不胜感激！

我解决这个问题的第一个暴力方法是按所需数量对贴纸进行排序，然后计算它们的比例并根据它们的比例将它们分配到印刷版，然后打印它们，直到最小数量变为0或负数（打印额外的纸张可以是浪费，但少量的话也没什么大不了的）。然而，这并没有给出最佳答案，因此，现在我陷入了困境。试图搜索类似的问题，但没有找到。尝试询问法学硕士，但它总是用通用背包问题方法回答。

Answer 1

它可以表示为一个整数规划问题，可以通过 OR-Tools 等工具来解决，尽管 LP 的约束如下：

• 固定数量的变量 (F)
• 没有变量相乘 (M)

意味着两件事： 1. 由于 (F) 和 2. 您必须假定最大印版数量 2. 您无法明确建模“从印版打印的张数”以乘以“具有贴纸类型的印版上的槽数

t 

”因为（M）。

围绕此进行建模的技巧是为

{plate, slot, kind of sticker}

的每个三元组设置一个单独的变量，其值

v

表示“我需要从此插槽打印的特定类型的

v

贴纸。例如，您问题中的优化方法将是：

Slot:   0  1  2  3  4  5  6  7  8  9
A      50 50 50 50  0  0  0  0  0  0
B       0  0  0  0 50 50 50 50 50 50

并且印版必须打印 50 张，因为这是单个插槽的最大数量。

显然，这需要一些限制，以避免尝试从单个插槽打印多种不同类型的贴纸。幸运的是，这可以用整数规划来表达。

实际上，您从每个插槽打印相同数量的贴纸。幸运的是，这仅意味着对于特定的板，您需要从中打印

m

表，其中

m

是所有插槽中变量的最大值 - 但成本函数必须考虑到这一点。

现在介绍防止同一插槽用于不同类型贴纸的技巧。第一部分是引入一组影子整数变量，每个

v

一个，每个变量的值在 [0..1] 范围内。

现在，如果我们添加一组像

v[p,s,k] < b[p,s,k] * 1000000

这样的约束，我们表示当且仅当相应的

v

为 1 时，特定的

b

才可以为非零。现在我们只需添加一个每时隙约束，即

b

的总和至多为 1，这又使得每个板中的每个槽只有一个

v

不为零。

显然还需要一些约束来表示每种贴纸的所有板和槽上的

v

的总和产生所需数量的贴纸，但这很简单。

对于目标函数，我们需要使用的板的数量，这同样可以通过每个板的“布尔”类型变量 1 来解决。

我已经使用 OR 工具为此编写了一个 PoC，它似乎有效，尽管三个板和

[20000, 500, 500]

贴纸需要 8 秒才能生成第一个板，其中 A10 打印 1600 次，第二个板打印 A8、B ,C 打印500次。在较大的情况下，它似乎很快就会收敛到最佳或接近最佳的解决方案，但需要永远“证明”它是最佳的。