带正方形的网格的最小精确覆盖；额外削减
Minimum exact cover of grid with squares; extra cuts
这个问题出现在challenge，但是现在已经关闭了，问一下应该没问题。
这个问题（不是这个问题本身，这只是背景资料）可以这样形象地描述，借用自己的形象：
我选择最优解。这可能（对于决策变体）是一个 NP 完全问题（它肯定在 NP 中，而且它闻起来像一个精确的覆盖，虽然我还没有证明可以将一般的精确覆盖问题简化为它），但没关系，它只需要在实践中很快，不一定在最坏的情况下。在这个问题的上下文中，我对任何近似算法都不感兴趣，除非它们提供削减。
有一个明显的ILP模型：生成所有可能的正方形（如果正方形只覆盖存在的网格单元格，则可能是正方形），为每个正方形引入一个二进制变量x_i，指示我们是否使用不管它与否，然后
minimize sum x_i
subject to:
1) x_i is an integer
2) 0 ≤ x_i ≤ 1
3) for every cell c
(sum[j | c ϵ square_j] x_j) = 1
约束 3 表示每个单元格恰好被覆盖一次。约束 1 和 2 使 x_i 二进制。最小解给出了原问题的最优解。
这个（即忽略约束 1）的线性松弛是半体面的，但它做的事情是这样的（这是一个 6x6 网格，左上角缺失）：
这里选择了 13 个正方形 "half"（给出 objective 值 6.5），尺寸（这样您可以更容易地找到它们）
- 1 个 4x4
- 3 个 3x3
- 6 个 2x2
- 3 个 1x1
此实例的最佳解决方案的 objective 值为 8，例如：
线性松弛效果一般，但我不是很满意。差距有时超过 10%，这有时会导致整数阶段非常慢。
这就是真正的问题所在，是否有额外的约束可以添加（懒惰地）作为削减，以改进分数解决方案？
我已经尝试了问题的替代公式来找到切割，例如，如果我们选择 "left upper corners" 和 "right lower corners"，而不是选择正方形，那么它们将被匹配到形式覆盖所有单元格的非重叠正方形？然后在每个 "backslash-like diagonal" 上，必须有匹配数量的左上角和右下角。但这无济于事，因为如果我们选择正方形，那么无论如何该条件始终为真，在分数解中也是如此。
我也尝试过一些关于重叠的推理，例如，如果两个正方形明显重叠，它们的总和不能大于 1，并且可以通过添加完全包含在重叠区域中的所有正方形来改进。但是该约束不如所有单元格只被覆盖一次的约束强大。
我已经尝试对总面积进行推理（例如，总覆盖面积必须等于单元格的数量），但是每个单元格必须被覆盖一次的约束已经保证了这一点，在总面积只允许更多的自由。
我也尝试用平方数（每个正方形的面积是一个正方形）和平方数的差来做一些事情，但也没有任何有用的结果。
我使用了 branch and price method to good effect on a similar problem (ITA's Strawberry Fields; scroll down). Here is my code，它（缺少注释）可能只适合作为我知道我在说什么的零知识证明。它比商业求解器（我不会命名）快几个数量级。
关键是分支策略。不要直接在 x_i 变量上分支，这可能是您的求解器正在做的事情，而是在更高级别的决策上分支。我在 Strawberry Fields 中使用的方法是决定两个单元格是否会被同一个正方形覆盖。如果您针对分数解最犹豫的对，那么解的结构似乎设置得相当快。
很遗憾，我无法就如何将其编程到现有的整数规划求解器中向您提供建议。对于 Strawberry Fields，我选择了自定义所有内容，主要是因为我想这样做，但部分原因是我正在动态生成列，使用累积网格行和网格列总和来快速评估矩形。
除了不重叠的约束之外，如何使用正方形的总面积等于要覆盖的总面积的约束？这应该比检查双覆盖约束要快。
动态规划：选择一个单元格（任何单元格都可以），计算覆盖它的所有有效方块（即只覆盖当前单元格和网格中其他单元格）。对于每个这样的正方形，递归地获取剩余区域的最小覆盖值（网格减去正方形），然后从中选择最小值（结果是该值 + 1）。
为了使事情更快，尝试选择一个单元格，该单元格在每个递归级别中具有最少的有效覆盖方块（从而减少每个级别中的递归调用次数）。
真的很简单。
objective 函数值的约束
每当 objective 函数值是非整数时——例如，因为在分数解中有奇数个 0.5 权重的方块——你可以添加一个切割 "directly on the objective function" 到将其强制为下一个更高的积分值：例如，在您的示例分数解中，有 13 个正方形，每个正方形的权重为 0.5，总 objective 函数值为 6.5，您可以添加约束条件，即所有 x_i >= 7.
更普遍的削减
这导致了一个更通用的规则，只要你有一个分数解决方案，其中一些单元格子集 C "exactly covered" 乘以一些具有非整数总权重 w 的正方形子集 S。 "exactly covered"，我的意思是 S 中的每个方块都具有非零权重，并且一起为 C 中的每个单元格提供总权重 1，并且不与 C 之外的任何单元格重叠。您可以轻松找到这些单元格子集通过创建一个图，每个单元格都有一个顶点，两个顶点之间有一条边，只要它们（部分）在分数解中被同一个正方形覆盖：该图的每个连通分量都是一个（最小）这样的子集。
给定一个部分解，其中包含一些完全覆盖的单元子集 C 和正方形子集 S，令 T 为仅与 C 中的单元重叠的所有正方形的集合（显然 T 是 S 的超集）。我们知道，LP 子问题的任何最优解 X 仅由细胞的子集 C（以及候选方块的相关子集 T）组成，其总权重必须与 S 相同，因为如果不是这样，这将与最优性相矛盾原始 LP 的分数解：您可以将 S 替换为 X 并获得更好的解。
现在，原始问题有两组解决方案（其中任何一个都可能为空）：没有正方形同时覆盖 C 中的单元格和 C 外的单元格的解决方案，以及满足至少有一些广场。我们要禁止在第一类 中总重量 < RoundUp(w) 的解决方案 。设 U 是与 C 中至少一个单元格重叠且 C 外至少一个单元格重叠的所有正方形的集合。我们可以通过添加约束
来实现这一点
Sum_{square_i in T}(x_i) + RoundUp(w) * Sum_{square_j in U}(x_j) >= RoundUp(w)
将 LHS 上的第二项乘以 RoundUp(w) 的效果是，如果即使是覆盖 C 中的一个单元格和其他一些单元格的单个正方形也被包含在解决方案中，约束有效地 "goes away".这是必需的，因为 S 和 C 没有告诉我们关于原始问题的此类解决方案，因此我们不能排除它们。请注意，包含正方形子集 S 的原始解决方案将被此约束禁止，因为 U 中的每个正方形在此解决方案中必须具有权重 0。
无药可救
第二种方法比第一种方法更强大，因为可能会发生这种情况，例如，图形包含两个组件，每个组件都有奇数个方块，所有这些方块的权重均为 0.5：这意味着总的来说有偶数个方块，这意味着整个 objective 函数值是整数，防止在 objective 函数上添加切割的可能性。但即使一次又一次地应用这些切割并不能保证最终会找到可行的解决方案：举一个具体的例子，任何时候网格本身水平 and/or 垂直对称但可以被一组不对称的正方形覆盖, 然后它可以很容易地被该组正方形的水平 and/or 垂直翻转版本覆盖——更烦人的是，这两个正方形组中的任何 "affine combination" （即，通过任何组合权重总和为 1)。一般来说，可能有许多同样好的可行解决方案，我在这里描述的削减无法阻止 LP 求解器返回包含所有 k 个 "superposition" 的解决方案，所有方块都分配了权重1/k.
[编辑 2015 年 1 月 7 日]
好的一面！
虽然，正如我上面提到的，没有办法让 LP 求解器从几个对称最优覆盖的分数 "superposition" 中得到 "isolate" 一个特定的可行覆盖，但有个好消息：在如果你确实得到了这样的叠加，实际上很容易从中恢复一个最优的、可行的覆盖。您需要做的就是贪婪地选择权重非零的方块，每次划掉与您刚刚选择的方块重叠的任何方块。如果解决方案是我所描述的叠加，那么这保证有效，并且同样重要的是：如果此过程适用于分数解决方案（即，如果重复此贪婪步骤最终覆盖所有细胞）那么你得到的解决方案一定是最优的！ （假设不是：令 X 为 LP 求解器返回的最优分数解，令 F 为您刚刚从中贪婪地提取的可行解，并令 y 为 F 中任何方块的最小权重。注意每个方块在 F 中至少为每个单元格的覆盖值贡献 y；因此，由于假设 F 是次优的，因此从 F 中每个方块的权重中减去 y 并将 X 中的所有其他权重按 1/(1-y) 缩放给出另一个（可能又是分数的）较低权重的解决方案，与 X 的最优性相矛盾。）
证明任何分数解 (i) 在 "covering graph" 中具有非整数总权重的某些分量，或 (ii) 由这样的叠加组成将非常有用：这意味着你可以继续应用我的 "general" 削减直到你得到一个叠加，然后你可以贪婪地解决它。但就目前而言，可能存在这两个类别之外的部分解决方案。
我会使用 A* 之类的搜索来找到解决方案。重要的是要注意 A* 就像 Greedy Best-First-Search 因为它可以使用启发式 来引导自己。假设您有正确的启发式方法，它将在合理的时间内找到接近最优 (~0.95) 的解决方案。
示例解决方案使用 18 个块而不是示例中所示的 19 个。除了 heuristic 之外，您还可以使用一些 precomputation 来提高算法效率。例如，我为每个位置计算了所谓的自由梯度。例如你的初始地图变成了一个舞台：
您可以拥有自己的启发式方法，它可以同样好，甚至更好。我使用它只是因为我发现它很简单。阶段编号具有以下含义：数字越大 - 它越有可能放在一个大盒子里（您可以得出更多限制，但这只是一个开始）。
阶段值是4个地窖自动化规则的总和。
例如左上角
cell(x,y) := min(cell(x,y-1) ?? 0, cell(x-1,y) ?? 0, cell(x-1,y-1) ?? 0) + 1
The ?? operator is called the null-coalescing operator. It returns the left-hand operand if the operand is not null; otherwise it returns the right hand operand.
此外，您可以通过删除从预计算和每个阶段获得的已知解决方案来减少所需的计算工作。在这种情况下状态 0:
算法本身会重复：
- 订购单元格并取最高
- 订购自动化规则结果并取最高
- 找到平凡的截止点
如果您想为更大的网格获得更快的结果，那么一种相当直接的方法是将预计算扩展到编译模板。之后就可以做模板缩减了。
例如你可以有一个模板（左上部分）
--+++
+-+++
+++++
您可以生成它的散列并将其添加到 hashmap/dictionary 中，值为 4（这意味着至少需要 4 个矩形来覆盖 +）。然后你有 5x3 范围和相同的散列你知道它是一个微不足道的切断成本 4.
之所以更快，是因为与计算接近恒定速度的哈希相比，比较需要花费大量时间。
或者，有一种方法可以催眠我们是否正在寻找或寻找什么样的解决方案。使用 Wolfram Mathematica 函数 FindMinimum 它看起来像：
FindMinimum[{
a + b + c + d + e + f + g,
(a 1^2 + b 2^2 + c 3^2 + d 4^2 + e 5^2 + f 6^2 + g 7^2) == 119 &&
a >= 0 && b >= 0 && c >= 0 && d >= 0 && e >= 0 && f >= 0 && g >= 0 &&
a \[Element] Integers &&
b \[Element] Integers &&
c \[Element] Integers &&
d \[Element] Integers &&
e \[Element] Integers &&
f \[Element] Integers &&
g \[Element] Integers
}, {a,b,c,d,e,f,g}]
这是基于我们有 12x12 网格和 119 个单元的假设，它会为我们提供一个使用网格大小计数的最佳解决方案。
遗憾的是wolfram alpha搜索引擎不解释这个，也许在将来。
这个问题出现在challenge，但是现在已经关闭了，问一下应该没问题。
这个问题（不是这个问题本身，这只是背景资料）可以这样形象地描述，借用自己的形象：
我选择最优解。这可能（对于决策变体）是一个 NP 完全问题（它肯定在 NP 中，而且它闻起来像一个精确的覆盖，虽然我还没有证明可以将一般的精确覆盖问题简化为它），但没关系，它只需要在实践中很快，不一定在最坏的情况下。在这个问题的上下文中，我对任何近似算法都不感兴趣，除非它们提供削减。
有一个明显的ILP模型：生成所有可能的正方形（如果正方形只覆盖存在的网格单元格，则可能是正方形），为每个正方形引入一个二进制变量x_i，指示我们是否使用不管它与否，然后
minimize sum x_i
subject to:
1) x_i is an integer
2) 0 ≤ x_i ≤ 1
3) for every cell c
(sum[j | c ϵ square_j] x_j) = 1
约束 3 表示每个单元格恰好被覆盖一次。约束 1 和 2 使 x_i 二进制。最小解给出了原问题的最优解。
这个（即忽略约束 1）的线性松弛是半体面的，但它做的事情是这样的（这是一个 6x6 网格，左上角缺失）：
这里选择了 13 个正方形 "half"（给出 objective 值 6.5），尺寸（这样您可以更容易地找到它们）
- 1 个 4x4
- 3 个 3x3
- 6 个 2x2
- 3 个 1x1
此实例的最佳解决方案的 objective 值为 8，例如：
线性松弛效果一般，但我不是很满意。差距有时超过 10%，这有时会导致整数阶段非常慢。
这就是真正的问题所在，是否有额外的约束可以添加（懒惰地）作为削减，以改进分数解决方案？
我已经尝试了问题的替代公式来找到切割，例如，如果我们选择 "left upper corners" 和 "right lower corners"，而不是选择正方形，那么它们将被匹配到形式覆盖所有单元格的非重叠正方形？然后在每个 "backslash-like diagonal" 上，必须有匹配数量的左上角和右下角。但这无济于事，因为如果我们选择正方形，那么无论如何该条件始终为真，在分数解中也是如此。
我也尝试过一些关于重叠的推理，例如，如果两个正方形明显重叠，它们的总和不能大于 1，并且可以通过添加完全包含在重叠区域中的所有正方形来改进。但是该约束不如所有单元格只被覆盖一次的约束强大。
我已经尝试对总面积进行推理（例如，总覆盖面积必须等于单元格的数量），但是每个单元格必须被覆盖一次的约束已经保证了这一点，在总面积只允许更多的自由。
我也尝试用平方数（每个正方形的面积是一个正方形）和平方数的差来做一些事情，但也没有任何有用的结果。
我使用了 branch and price method to good effect on a similar problem (ITA's Strawberry Fields; scroll down). Here is my code，它（缺少注释）可能只适合作为我知道我在说什么的零知识证明。它比商业求解器（我不会命名）快几个数量级。
关键是分支策略。不要直接在 x_i 变量上分支，这可能是您的求解器正在做的事情，而是在更高级别的决策上分支。我在 Strawberry Fields 中使用的方法是决定两个单元格是否会被同一个正方形覆盖。如果您针对分数解最犹豫的对，那么解的结构似乎设置得相当快。
很遗憾，我无法就如何将其编程到现有的整数规划求解器中向您提供建议。对于 Strawberry Fields，我选择了自定义所有内容，主要是因为我想这样做，但部分原因是我正在动态生成列，使用累积网格行和网格列总和来快速评估矩形。
除了不重叠的约束之外，如何使用正方形的总面积等于要覆盖的总面积的约束？这应该比检查双覆盖约束要快。
动态规划：选择一个单元格（任何单元格都可以），计算覆盖它的所有有效方块（即只覆盖当前单元格和网格中其他单元格）。对于每个这样的正方形，递归地获取剩余区域的最小覆盖值（网格减去正方形），然后从中选择最小值（结果是该值 + 1）。 为了使事情更快，尝试选择一个单元格，该单元格在每个递归级别中具有最少的有效覆盖方块（从而减少每个级别中的递归调用次数）。
真的很简单。
objective 函数值的约束
每当 objective 函数值是非整数时——例如，因为在分数解中有奇数个 0.5 权重的方块——你可以添加一个切割 "directly on the objective function" 到将其强制为下一个更高的积分值：例如，在您的示例分数解中，有 13 个正方形，每个正方形的权重为 0.5，总 objective 函数值为 6.5，您可以添加约束条件，即所有 x_i >= 7.
更普遍的削减
这导致了一个更通用的规则，只要你有一个分数解决方案，其中一些单元格子集 C "exactly covered" 乘以一些具有非整数总权重 w 的正方形子集 S。 "exactly covered"，我的意思是 S 中的每个方块都具有非零权重，并且一起为 C 中的每个单元格提供总权重 1，并且不与 C 之外的任何单元格重叠。您可以轻松找到这些单元格子集通过创建一个图，每个单元格都有一个顶点，两个顶点之间有一条边，只要它们（部分）在分数解中被同一个正方形覆盖：该图的每个连通分量都是一个（最小）这样的子集。
给定一个部分解，其中包含一些完全覆盖的单元子集 C 和正方形子集 S，令 T 为仅与 C 中的单元重叠的所有正方形的集合（显然 T 是 S 的超集）。我们知道，LP 子问题的任何最优解 X 仅由细胞的子集 C（以及候选方块的相关子集 T）组成，其总权重必须与 S 相同，因为如果不是这样，这将与最优性相矛盾原始 LP 的分数解：您可以将 S 替换为 X 并获得更好的解。
现在，原始问题有两组解决方案（其中任何一个都可能为空）：没有正方形同时覆盖 C 中的单元格和 C 外的单元格的解决方案，以及满足至少有一些广场。我们要禁止在第一类 中总重量 < RoundUp(w) 的解决方案 。设 U 是与 C 中至少一个单元格重叠且 C 外至少一个单元格重叠的所有正方形的集合。我们可以通过添加约束
来实现这一点Sum_{square_i in T}(x_i) + RoundUp(w) * Sum_{square_j in U}(x_j) >= RoundUp(w)
将 LHS 上的第二项乘以 RoundUp(w) 的效果是，如果即使是覆盖 C 中的一个单元格和其他一些单元格的单个正方形也被包含在解决方案中，约束有效地 "goes away".这是必需的，因为 S 和 C 没有告诉我们关于原始问题的此类解决方案，因此我们不能排除它们。请注意，包含正方形子集 S 的原始解决方案将被此约束禁止，因为 U 中的每个正方形在此解决方案中必须具有权重 0。
无药可救
第二种方法比第一种方法更强大，因为可能会发生这种情况，例如，图形包含两个组件，每个组件都有奇数个方块，所有这些方块的权重均为 0.5：这意味着总的来说有偶数个方块，这意味着整个 objective 函数值是整数，防止在 objective 函数上添加切割的可能性。但即使一次又一次地应用这些切割并不能保证最终会找到可行的解决方案：举一个具体的例子，任何时候网格本身水平 and/or 垂直对称但可以被一组不对称的正方形覆盖, 然后它可以很容易地被该组正方形的水平 and/or 垂直翻转版本覆盖——更烦人的是，这两个正方形组中的任何 "affine combination" （即，通过任何组合权重总和为 1)。一般来说，可能有许多同样好的可行解决方案，我在这里描述的削减无法阻止 LP 求解器返回包含所有 k 个 "superposition" 的解决方案，所有方块都分配了权重1/k.
[编辑 2015 年 1 月 7 日]
好的一面！
虽然，正如我上面提到的，没有办法让 LP 求解器从几个对称最优覆盖的分数 "superposition" 中得到 "isolate" 一个特定的可行覆盖，但有个好消息：在如果你确实得到了这样的叠加，实际上很容易从中恢复一个最优的、可行的覆盖。您需要做的就是贪婪地选择权重非零的方块，每次划掉与您刚刚选择的方块重叠的任何方块。如果解决方案是我所描述的叠加，那么这保证有效，并且同样重要的是：如果此过程适用于分数解决方案（即，如果重复此贪婪步骤最终覆盖所有细胞）那么你得到的解决方案一定是最优的！ （假设不是：令 X 为 LP 求解器返回的最优分数解，令 F 为您刚刚从中贪婪地提取的可行解，并令 y 为 F 中任何方块的最小权重。注意每个方块在 F 中至少为每个单元格的覆盖值贡献 y；因此，由于假设 F 是次优的，因此从 F 中每个方块的权重中减去 y 并将 X 中的所有其他权重按 1/(1-y) 缩放给出另一个（可能又是分数的）较低权重的解决方案，与 X 的最优性相矛盾。）
证明任何分数解 (i) 在 "covering graph" 中具有非整数总权重的某些分量，或 (ii) 由这样的叠加组成将非常有用：这意味着你可以继续应用我的 "general" 削减直到你得到一个叠加，然后你可以贪婪地解决它。但就目前而言，可能存在这两个类别之外的部分解决方案。
我会使用 A* 之类的搜索来找到解决方案。重要的是要注意 A* 就像 Greedy Best-First-Search 因为它可以使用启发式 来引导自己。假设您有正确的启发式方法，它将在合理的时间内找到接近最优 (~0.95) 的解决方案。
示例解决方案使用 18 个块而不是示例中所示的 19 个。除了 heuristic 之外，您还可以使用一些 precomputation 来提高算法效率。例如，我为每个位置计算了所谓的自由梯度。例如你的初始地图变成了一个舞台：
您可以拥有自己的启发式方法，它可以同样好，甚至更好。我使用它只是因为我发现它很简单。阶段编号具有以下含义：数字越大 - 它越有可能放在一个大盒子里（您可以得出更多限制，但这只是一个开始）。
阶段值是4个地窖自动化规则的总和。
例如左上角
cell(x,y) := min(cell(x,y-1) ?? 0, cell(x-1,y) ?? 0, cell(x-1,y-1) ?? 0) + 1
The ?? operator is called the null-coalescing operator. It returns the left-hand operand if the operand is not null; otherwise it returns the right hand operand.
此外，您可以通过删除从预计算和每个阶段获得的已知解决方案来减少所需的计算工作。在这种情况下状态 0:
算法本身会重复：
- 订购单元格并取最高
- 订购自动化规则结果并取最高
- 找到平凡的截止点
如果您想为更大的网格获得更快的结果，那么一种相当直接的方法是将预计算扩展到编译模板。之后就可以做模板缩减了。
例如你可以有一个模板（左上部分）
--+++
+-+++
+++++
您可以生成它的散列并将其添加到 hashmap/dictionary 中，值为 4（这意味着至少需要 4 个矩形来覆盖 +）。然后你有 5x3 范围和相同的散列你知道它是一个微不足道的切断成本 4.
之所以更快，是因为与计算接近恒定速度的哈希相比，比较需要花费大量时间。
或者，有一种方法可以催眠我们是否正在寻找或寻找什么样的解决方案。使用 Wolfram Mathematica 函数 FindMinimum 它看起来像：
FindMinimum[{
a + b + c + d + e + f + g,
(a 1^2 + b 2^2 + c 3^2 + d 4^2 + e 5^2 + f 6^2 + g 7^2) == 119 &&
a >= 0 && b >= 0 && c >= 0 && d >= 0 && e >= 0 && f >= 0 && g >= 0 &&
a \[Element] Integers &&
b \[Element] Integers &&
c \[Element] Integers &&
d \[Element] Integers &&
e \[Element] Integers &&
f \[Element] Integers &&
g \[Element] Integers
}, {a,b,c,d,e,f,g}]
这是基于我们有 12x12 网格和 119 个单元的假设，它会为我们提供一个使用网格大小计数的最佳解决方案。
遗憾的是wolfram alpha搜索引擎不解释这个，也许在将来。