带正方形的网格的最小精确覆盖; 额外的削减

Question

这个问题出现在一个挑战中,但由于它现在已经关闭,因此可以询问它.

问题(不是这个问题本身,这只是背景信息)可以像这样直观地描述,借用他们自己的图像:

我选择以最佳方式解决它.这可能(对于决策变量)是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个方块被选为"一半"(给出一个6.5的目标值),大小(所以你可以更容易找到它们)

• 1x of 4x4
• 3x3中的3
• 6x2x2
• 1x1中的3个

此实例的最佳解决方案的目标值为8,例如:

线性放松是一半体面,但我并不完全满意.差距有时超过10%,有时会导致非常缓慢的整数阶段.

那是实际问题的来源,是否有额外的限制,我可以添加(懒惰)作为削减,以改善分数解决方案？

我已经尝试了问题的替代配方来寻找切割,例如,而不是选择正方形,如果我们选择"左上角"和"右下角",然后匹配形成非重叠方块覆盖所有细胞？然后在每个"反斜杠状对角线"上,必须有匹配数量的左上角和右下角.但这没有用,因为如果我们选择正方形,那么无论如何,这种情况总是正确的,也是在分数解决方案中.

我还尝试了一些关于重叠的推理,例如,如果两个正方形明显重叠,它们的总和不得大于1,并且可以通过添加完全包含在重叠区域中的所有正方形来改善.但是这种约束不如所有细胞只被覆盖一次的约束力强.

我已经尝试过关于总面积的推理(例如,总覆盖面积必须等于单元格的数量),但是已经通过约束来保证,每个单元必须覆盖一次,并根据总面积来说明只允许更多的自由.

我也尝试用方形数字(每个方格的面积,正好,正方形)和方形数字的差异做一些事情,但这并没有以任何有用的方式结束.

Answer 1

我使用分支和价格方法对类似的问题产生了很好的效果(ITA的Strawberry Fields ;向下滚动).这是我的代码,(缺少评论)可能只是一个零知识证据,我知道我在说什么.它比商业解算器快了几个数量级(我不会说出来).

关键是分支策略.而不是直接分支x_i变量,这可能是你的解算器正在做的事情,而是分支更高层次的决策.我用于Strawberry Fields的那个是决定两个细胞是否会被同一个方块覆盖.如果您针对分数解决方案最关注的对,那么解决方案的结构似乎设置得相当快.

不幸的是,我无法就如何将其编程到现有的整数程序求解器中提供建议.对于Strawberry Fields,我选择了自定义所有内容,主要是因为我想,但部分是因为我在运行中生成列,使用累积网格行和网格列总和来快速评估矩形.

Answer 2

目标函数值的约束

每当目标函数值是非整数时——例如，因为分数解中有奇数个 0.5 权重方块——您可以“直接在目标函数上”添加一个剪切，以强制其达到下一个更高的积分值：例如，在您的示例分数解中，有 13 个方格，每个方格的权重为 0.5，总目标函数值为 6.5，您可以添加所有 x_i 之和 >= 7 的约束。

更一般的削减

这导致了一个更通用的规则，只要您有一个分数解，其中某些单元子集 C 被具有非整数总权重 w 的正方形子集 S“完全覆盖”，该规则就会起作用。我所说的“完全覆盖”是指 S 中的每个方块都具有非零权重，并且为 C 中的每个单元格提供的总权重为 1，并且不与 C 外部的任何单元格重叠。您可以通过以下方式轻松找到这些单元格子集创建一个图，每个单元都有一个顶点，两个顶点之间有一条边，只要它们（部分）被分数解中的同一个正方形覆盖：该图的每个连通分量都是一个（最小）这样的子集。

如上所述，给定一个带有一些完全覆盖的单元子集 C 和正方形子集 S 的分数解，令 T 为仅与 C 中的单元重叠的所有正方形的集合（显然 T 是 S 的超集）。我们知道，仅由单元格子集 C（以及候选方格的相关子集 T）组成的 LP 子问题的任何最优解 X 必须具有与 S 相同的总权重，因为如果不是这样，这将与原始 LP 的分数解：您只需用 X 替换 S 即可获得更好的解。

现在，原始问题有两组解决方案（其中任何一个都可能为空）：其中没有正方形覆盖 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 中的单元格和其他单元格的单个正方形，约束也会有效地“消失”。这是必要的，因为 S 和 C 没有告诉我们任何关于原始问题的解决方案，因此我们不能排除它们。请注意，包含方格子集 S 的原始解决方案将受到此约束的禁止，因为 U 中的每个方格在此解决方案中的权重必须为 0。

没有灵丹妙药

第二种方法比第一种方法更强大，因为可能会发生这样的情况，例如，图包含两个分量，每个分量都有奇数个方格，所有方格的权重均为 0.5：这意味着总体上有偶数个方格。平方数，意味着总体目标函数值是整数，防止在目标函数上添加切割的可能性。但即使一次又一次地应用这些切割也不能保证最终会找到一个可行的解决方案：作为一个具体的例子，任何时候网格本身是水平和/或垂直对称的，但可以被一组不对称的正方形覆盖，那么它可以很容易地被该组正方形的水平和/或垂直翻转版本覆盖——而且，更烦人的是，被这两个正方形组的任何“仿射组合”覆盖（即，通过权重总和为 1 的任何组合） ）。一般来说，可能有许多同样好的可行解决方案，并且我在这里描述的切割无法阻止 LP 求解器返回包含所有 k 个“叠加”的解决方案，所有方格都分配了权重 1/ k.

[编辑 2015 年 1 月 7 日]

光明的一面！

尽管正如我上面提到的，没有办法让 LP 求解器从几个对称最优覆盖的分数“叠加”中“分离”出一个特定的可行覆盖，但有个好消息：如果您确实得到了这样的叠加，实际上很容易从中恢复出一个最佳的、可行的覆盖层。您需要做的就是贪婪地选择权重非零的方块，每次都划掉与您刚刚选择的方块重叠的任何方块。如果解决方案是我所描述的叠加，那么这保证有效，并且同样重要的是：如果此过程适用于分数解决方案（即，如果重复此贪婪步骤最终覆盖所有单元格），则您的解决方案得到的一定是最优的！（假设不是：设 X 为 LP 求解器返回的最优分数解，设 F 为您刚刚从中贪婪提取的可行解，设 y 为 F 中任何方格的最小权重。请注意，每个方格F 中的值至少对每个像元的覆盖值有 y 贡献；因此，由于假设 F 不是最优的，因此从 F 中每个方块的权重中减去 y 并将 X 中的所有其他权重按 1/(1-y) 缩放将给出另一个（可能又是分数）较低权重的解决方案，与 X 的最优性相矛盾。）

证明任何分数解要么（i）在“覆盖图”中具有非整数总重量的某些组件，要么（ii）由这样的叠加组成：这意味着您可以继续应用我的“将军”会不断削减，直到你得到一个叠加，然后你就可以贪婪地解决它。但就目前情况而言，在这两个类别之外可能还存在部分解决方案。