这个问题出现在挑战，但因为它现在已经关闭应该没问题要问一下。

This problem appeared in a challenge, but since it is now closed it should be OK to ask about it.

这个问题（不是这个问题本身，这仅仅是背景信息）可以直观地描述这样，借用自己的形象：

The problem (not this question itself, this is just background information) can be visually described like this, borrowing their own image:

我选择了最佳的解决这个问题。这可能是（决定变量）的NP完全问题（这是肯定的NP，它闻起来像一个确切的封面，虽然我还没有证明，一般的精确覆盖问题可以简化到它），但是这很好，它只有要快于实践，不一定在最坏的情况下。在这个问题的背景下，我不感兴趣的任何近似算法，除非它们提供的削减。

I chose to solve it optimally. That's probably (for the decision variant) an NP-complete problem (it's certainly in NP, and it smells like an exact cover, though I haven't proven that a general exact cover problem can be reduced to it), but that's fine, it only has to be fast in practice, not necessarily in the worst case. In the context of this question, I'm not interested in any approximation algorithms, unless they provide cuts.

有一个明显的ILP模式：生成所有可能的平方（方是可能的，如果它涵盖的是present电网只有细胞），引入二元变量 x_i 为每平方指示我们是否使用与否，那么

There is an obvious ILP model: generate all possible squares (a square is possible if it covers only cells of the grid that are present), introduce a binary variable x_i for every square indicating whether we use it or not, then

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二进制文件。最小溶液给出了一个最佳的解决方案，以原来的问题

Constraint 3 says that every cell is covered exactly once. Constraints 1 and 2 make x_i binary. The minimum solution gives an optimum solution to the original problem.

这样做的线性松弛（即不考虑约束条件1）是半体面的，但它确实像这样的事情（这是一个6x6的网格，左上角缺失）：

The linear relaxation of this (ie ignoring constraint 1) is half-decent, but it does things like this (this is a 6x6 grid with the top left corner missing):

下面被选为13平方的半壁江山（给人的6.5客观值），大小（这样你就可以找到他们更容易回）

Here 13 squares were chosen "half" (giving an objective value of 6.5), of the sizes (so you can find them back easier)

有此实例的最佳解决方案具有8客观值，象这样的：

An optimal solution for this instance has an objective value of 8, such as this one:

线性松弛是半体面的，但我并不完全满意。该间隙是有时超过10％，而有时会导致一个非常缓慢的整数相位

The linear relaxation is half-decent, but I'm not completely happy with it. The gap is sometimes over 10%, and that sometimes leads to a very slow integer phase.

这就是实际的问题来的，在那里，我可以添加（懒洋洋地）的削减，以提高分数的解决方案？额外的限制

That's where the actual question comes in, are there extra constraints that I can add (lazily) as cuts, to improve a fractional solution?

我已经试过了问题的替代配方查找削减，例如，而不是选择正方形，如果我们选择什么样的左上角和右下角，然后再进行匹配起来，形成非重叠覆盖所有小区的广场？然后对左上端和右下拐角每个反斜线状对角线，必须有一个匹配的号码。但是，这并没有帮助，因为如果我们选择平方那么该条件总是真，无论如何，也以分数的解决方案。

I've tried alternative formulations of the problem to find cuts, for example instead of choosing squares, what if we choose "left upper corners" and "right lower corners", which are then to be matched up to form non-overlapping squares that cover all cells? Then on every "backslash-like diagonal", there must be a matching number of left-upper and right-lower corners. But that doesn't help, because if we choose squares then that condition is always true anyway, also in fractional solutions.

我也试着大约重叠一些推理，例如，如果两个正方形重叠清楚它们的总和必须不大于1，且可由也加入完全包含在重叠区中的所有平方得到改善。但是，这限制比所有的细胞被完全覆盖，一旦约束不那么强大。

I've also tried some reasoning about overlaps, for example if two squares overlap clearly their sum must not be bigger than 1, and that can be improved by also adding all squares wholly contained in the overlapping region. But that constraint is less powerful than the constraint that all cells be covered exactly once.

我试图推理的总面积（如在，总覆盖面积必须等于细胞的数量），但是这已经保证由每个细胞必须覆盖一旦约束，说明它在计总面积只允许更多的自由。

I've tried reasoning about the total area (as in, the total covered area must be equal to the number of cells), but that's already guaranteed by the constraint that every cell must be covered once, stating it in terms of the total area only allows more freedom.

我也试着做一些与平方数与平方数的差异（每平方，没错，是一个正方形的面积），但没有任何东西最终有用无论是。

I've also tried to do something with square numbers (the area of every square is, well, a square) and differences of square numbers, but that didn't end in anything useful either.

推荐答案

当目标函数值不为整数 - 例如，因为你的分数液0.5重量广场奇数 - 你可以直接在目标函数来强制其在添加切下一个较高的积分值：例如，在你的榜样与13平方每个具有0.5的权重为6.5，总目标函数值的分数的​​解决方案，你可以添加约束，所有的总和x_i> = 7

Constraints on the objective function value

Whenever the objective function value is non-integral -- e.g., because you have an odd number of 0.5-weight squares in the fractional solution -- you can add a cut "directly on the objective function" to force it to the next higher integral value: e.g., in your example fractional solution with 13 squares each having a weight of 0.5 for a total objective function value of 6.5, you could add the constraint that the sum of all x_i >= 7.

这导致，将工作，只要你有一个分数的解决方案中，细胞的某些子集C的完全覆盖具有非整体的总重量W广场的某些子集S一般规律。所谓完全覆盖，我的意思是，在S中的每个方块都非零权重，共同为在C中的每一个细胞提供1总重量，而不要被任何重叠C.细胞外你可以找到细胞的这些子集轻松创建具有一个顶点为每个小区和每当它们被（部分地）受相同正方形中的小数溶液两个顶点之间的边缘的曲线图。该曲线图的每个连接的组分是（最小），例如子集

This leads to a more general rule that will work whenever you have a fractional solution in which some subset C of cells are "exactly covered" by some subset S of squares having non-integral total weight w. By "exactly covered", I mean that the squares in S each have nonzero weight and together provide a total weight of 1 for every cell in C, and do not overlap any cells outside of C. You can find these subsets of cells easily by creating a graph with a vertex for each cell and an edge between two vertices whenever they are (partially) covered by the same square in the fractional solution: each connected component of this graph is a (minimal) such subset.

由于一些完全覆盖细胞亚群℃的分数的解决方案和多子集为上述S，令T是一组重叠只是细胞在C中所有的广场（显然T是S的超集）。我们知道，任何最优解X到LP子问题组成细胞的只是一部分的C（和候选广场的相关子集T）必须具有相同的总重量为S，因为如果不这样做违背的最优分数解决了原始的LP：你可以只更换S采用X和得到较好的解决。

Given a fractional solution with some exactly covered cell subset C and square subset S as above, let T be the set of all squares that overlap only cells in C (obviously T is a superset of S). We know that any optimal solution X to the LP subproblem consisting of just the subset C of cells (and the relevant subset T of candidate squares) must have identical total weight to S, since if it didn't this would contradict the optimality of the fractional solution to the original LP: you could just replace S with X and get a better solution.

现在，有两套解决方案，以原来的问题（其中任何一个可能是空的）：那些解决方案中，没有方同时覆盖在C单元和C以外的细胞，并且这些解决方案，其中至少一些方一样。我们要禁止的解决方案的第一类的有总重量＆LT;综合报道（W）。设U是该组的重叠的至少一个细胞用C和C以外的至少一个细胞，我们可以通过添加约束实现这一切平方

Now, there are two sets of solutions to the original problem (either of which may be empty): those solutions in which no square covers both a cell in C and a cell outside C, and those solutions in which at least some square does. We want to forbid solutions in the first category that have total weight < RoundUp(w). Let U be the set of all squares that overlap at least one cell in C and at least one cell outside C. We can achieve this by adding the constraint

Sum_{square_i in T}(x_i) + RoundUp(w) * Sum_{square_j in U}(x_j) >= RoundUp(w)

通过综合报告（W）乘以在LHS的第二个任期的效果是，如果这涵盖了一个在C单元和其他一些小区甚至一个正方形包含在解决方案中，约束有效地消失。这是必要的，因为S和C告诉我们任何关于这样的解决方案，以原来的问题，因此我们不能排除他们。注意，含有正方形S中的子集的原始溶液将由此约束被禁止，因为以U每平方必须已在此溶液具有重量0

The effect of multiplying the second term on the LHS by RoundUp(w) is that if even a single square that covers both a cell in C and some other cell is included into the solution, the constraint effectively "goes away". This is needed because S and C tell us nothing about such solutions to the original problem, and therefore we can't afford to rule them out. Note that the original solution containing the subset of squares S will be forbidden by this constraint, since every square in U must have had weight 0 in this solution.

第二种方法比第一个功能更强大的，因为它可能发生的是，例如，该图包含两个组件，每一个都具有方格数为奇数，所有这些都重0.5：这将意味着，有整体偶数平方，意思是总的目标函数值是积分，preventing目标函数增加一个切口的可能性。但是，即使将这些切口连连并不保证一个可行的解决方案最终将发现：作为一个具体的例子，任何时间网格本身是水平和/或垂直地对称，但可以覆盖一个不对称集的平方，然后更烦人和，由这两个方集（即任何仿射组合，以任何组合与重量总和为1 - 它也可以很容易地包含在该组方块的水平方向和/或垂直翻转版本）。一般来说，可能有许多同样优秀可行的解决方案，而我在这里所描述的削减给没有办法从返回包含它们的所有K的叠加的解决方案停止LP求解器，所有的方块分配的权重为1 / ķ。

The second approach is more powerful than the first, since it may happen that, e.g., the graph contains two components, each of which has an odd number of squares, all of which have weight 0.5: this would mean that there are overall an even number of squares, meaning the overall objective function value is integral, preventing the possibility of adding a cut on the objective function. But even applying these cuts again and again doesn't guarantee that a feasible solution will eventually be found: as a concrete example, any time the grid itself is horizontally and/or vertically symmetrical but can be covered by an asymmetrical set of squares, then it can just as easily be covered by the horizontally and/or vertically flipped version of that set of squares -- and, more annoyingly, by any "affine combination" of these two square sets (i.e., by any combination with weights summing to 1). In general there could be many equally good feasible solutions, and the cuts I've described here give no way to stop the LP solver from returning a solution that contains a "superposition" of all k of them, with all squares assigned weight 1/k.

虽然，正如我上面提到的，有没有办法得到LP求解器从几个对称最佳盖分数叠加到隔离一个特定的可行的封面，有一个好消息：在你做得到事件这样的叠加，它实际上很容易从它恢复单个最佳的，可行的封面。所有你需要做的就是贪婪地挑广场有非零权重，每一次跨越了重叠，你只是选择了方形任何正方形。这是保证工作，如果该解决方案是为我所描述的叠加，并且，同样重要的是：如果这个程序适用于分数的解决方案的（也就是说，如果重复这个贪婪的一步，最终覆盖所有细胞），那么你得到的解决方案必须是最优的！ （假如它不是：设X是由LP求解器返回的最佳分数的解决方案，令F是你刚刚从它贪婪地提取了可行的解决方案，并令y是任何方形的最小重量F.注意，每平方在F中有助于至少y以每小区的覆盖值;这样，因为F是次优的根据假设，从F中每平方的重量减去y和结垢的In x所有其他的权重由1 /（1-y）的会再举一个（可能再次分数）解决方案更低的重量，矛盾X的最优性。）

Although, as I mentioned above, there's no way of getting the LP solver to "isolate" one particular feasible cover from a fractional "superposition" of several symmetric optimal covers, there is good news: In the event that you do get such a superposition, it's actually very easy to recover a single optimal, feasible cover from it. All you need to do is greedily pick squares with nonzero weight, each time crossing out any squares that overlap the square you just picked. This is guaranteed to work if the solution is a superposition as I've described, and, just as importantly: if this procedure works on a fractional solution (that is, if repeating this greedy step eventually covers all the cells) then the solution you get must be optimal! (Suppose it wasn't: Let X be the optimal fractional solution returned by the LP solver, let F be the feasible solution you just extracted from it greedily, and let y be the smallest weight of any square in F. Notice that every square in F contributes at least y to the coverage value of every cell; so, since F is suboptimal by assumption, subtracting y from the weight of every square in F and scaling all other weights in X up by 1/(1-y) will give another (possibly again fractional) solution of lower weight, contradicting the optimality of X.)

这将是非常有用的，以证明任何小数溶液或者（i）具有在覆盖图与非积分总重量，或某些组分（ii）包括这样的叠加的：这将意味着你可以去申请我的将军的削减，直到你得到的叠加，然后你可以解决贪婪。但因为它的立场，有可能是这两类之外的分数的解决方案。

It would be very useful to prove that any fractional solution either (i) has some component in the "covering graph" with non-integral total weight, or (ii) consists of such a superposition: this would mean that you could go on applying my "general" cuts until you get a superposition, which you could then solve greedily. But as it stands, there might be fractional solutions outside these two categories.