algorithm - Minimum exact cover of grid with squares; extra cuts

Question

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:

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.

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

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.

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):

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

• 1 of 4x4
• 3 of 3x3
• 6 of 2x2
• 3 of 1x1

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

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.

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.

Answer 1

I used the branch and price method to good effect on a similar problem (ITA's Strawberry Fields; scroll down). Here is my code, which (lacking comments) is probably only good as a zero-knowledge proof that I know what I'm talking about. It was orders of magnitude faster than a commercial solver (which I won't name).

The key was the branching strategy. Rather than branch directly on the x_i variables, which is likely what your solver is doing, branch on a higher-level decision. The one that I used for Strawberry Fields was to decide whether two cells would be covered by the same square. If you target the pairs that the fractional solution is most on the fence about, then the structure of the solution seems to be set fairly quickly.

Unfortunately, I can't offer you advice on how to program this into an existing integer program solver. For Strawberry Fields, I went with custom everything, mostly because I wanted to but in part because I was generating columns on the fly, using cumulative grid row and grid column sums to evaluate rectangles quickly.