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

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的网格，左上角缺失）：

• 4x4中的1个
• 3x3
• 第6个2x2
• 第3个，共1x1

此实例的最优解的目标值为8，例如：

线性放松是半体面的，但我并不完全满意它。间隙有时超过10%，这有时会导致非常慢的整数相位。

我试过对总面积的推理（例如，总覆盖面积必须等于单元格的数量），但这已经通过每个单元格必须覆盖一次的约束来保证了，以总面积来说明它只允许更多的自由。

我也试着用平方数（每个平方的面积都是一个平方）和平方数的差值做一些事情，但也没有任何有用的结果。

Answer 1

每当目标函数值是非整数的--例如，因为在分数解中有一个奇数个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外的一个单元格的解，以及那些至少有一些正方形覆盖的解。我们希望禁止总重量 集合，我们可以通过添加约束来实现这一点<>

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)由这样一个叠加组成，这将是非常有用的：这将意味着你可以继续应用我的“一般”割，直到你得到一个叠加，然后你可以贪婪地求解它。但就目前情况而言，在这两个类别之外可能还有部分解决方案。