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

this problem appeared in challenge, since closed should ok ask it.

the problem (not question itself, background information) can visually described this, borrowing own image:

i chose solve optimally. that's (for decision variant) np-complete problem (it's in np, , smells exact cover, though haven't proven general exact cover problem can reduced it), that's fine, has fast in practice, not in worst case. in context of question, i'm not interested in approximation algorithms, unless provide cuts.

there obvious ilp model: generate possible squares (a square possible if covers cells of grid present), introduce binary variable x_i every square indicating whether use or not, then

minimize sum x_i  subject to: 1) x_i integer 2) 0 ≤ x_i ≤ 1 3) every cell c        (sum[j | c ϵ square_j] x_j) = 1 

constraint 3 says every cell covered once. constraints 1 , 2 make x_i binary. minimum solution gives optimum solution original problem.

the linear relaxation of (ie ignoring constraint 1) half-decent, things (this 6x6 grid top left corner missing):

here 13 squares chosen "half" (giving objective value of 6.5), of sizes (so can find them easier)

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

an optimal solution instance has objective value of 8, such one:

the linear relaxation half-decent, i'm not happy it. gap on 10%, , leads slow integer phase.

that's actual question comes in, there constraints can add (lazily) cuts, improve fractional solution?

i've tried alternative formulations of problem find cuts, example instead of choosing squares, if choose "left upper corners" , "right lower corners", matched form non-overlapping squares cover cells? on every "backslash-like diagonal", there must matching number of left-upper , right-lower corners. doesn't help, because if choose squares condition true anyway, in fractional solutions.

i've tried reasoning overlaps, example if 2 squares overlap sum must not bigger 1, , can improved adding squares wholly contained in overlapping region. constraint less powerful constraint cells covered once.

i've tried reasoning total area (as in, total covered area must equal number of cells), that's guaranteed constraint every cell must covered once, stating in terms of total area allows more freedom.

i've tried square numbers (the area of every square is, well, square) , differences of square numbers, didn't end in useful either.

constraints on objective function value

whenever objective function value non-integral -- e.g., because have odd number of 0.5-weight squares in fractional solution -- can add cut "directly on objective function" force next higher integral value: e.g., in example fractional solution 13 squares each having weight of 0.5 total objective function value of 6.5, add constraint sum of x_i >= 7.

more general cuts

this leads more general rule work whenever have fractional solution in subset c of cells "exactly covered" subset s of squares having non-integral total weight w. "exactly covered", mean squares in s each have nonzero weight , provide total weight of 1 every cell in c, , not overlap cells outside of c. can find these subsets of cells creating graph vertex each cell , edge between 2 vertices whenever (partially) covered same square in fractional solution: each connected component of graph (minimal) such subset.

given fractional solution covered cell subset c , square subset s above, let t set of squares overlap cells in c (obviously t superset of s). know optimal solution x lp subproblem consisting of subset c of cells (and relevant subset t of candidate squares) must have identical total weight s, since if didn't contradict optimality of fractional solution original lp: replace s x , better solution.

now, there 2 sets of solutions original problem (either of may empty): solutions in no square covers both cell in c , cell outside c, , solutions in @ least square does. want forbid solutions in first category have total weight < roundup(w). let u set of squares overlap @ least 1 cell in c , @ least 1 cell outside c. can achieve adding constraint

sum_{square_i in t}(x_i) + roundup(w) * sum_{square_j in u}(x_j) >= roundup(w) 

the effect of multiplying second term on lhs roundup(w) if single square covers both cell in c , other cell included solution, constraint "goes away". needed because s , c tell nothing such solutions original problem, , therefore can't afford rule them out. note original solution containing subset of squares s forbidden constraint, since every square in u must have had weight 0 in solution.

no panacea

the second approach more powerful first, since may happen that, e.g., graph contains 2 components, each of has odd number of squares, of have weight 0.5: mean there overall number of squares, meaning overall objective function value integral, preventing possibility of adding cut on objective function. applying these cuts again , again doesn't guarantee feasible solution found: concrete example, time grid horizontally and/or vertically symmetrical can covered asymmetrical set of squares, can covered horizontally and/or vertically flipped version of set of squares -- and, more annoyingly, "affine combination" of these 2 square sets (i.e., combination weights summing 1). in general there many equally feasible solutions, , cuts i've described here give no way stop lp solver returning solution contains "superposition" of k of them, squares assigned weight 1/k.

[edit 1/7/2015]

a bright side!

although, mentioned above, there's no way of getting lp solver "isolate" 1 particular feasible cover fractional "superposition" of several symmetric optimal covers, there news: in event such superposition, it's easy recover single optimal, feasible cover it. need greedily pick squares nonzero weight, each time crossing out squares overlap square picked. guaranteed work if solution superposition i've described, and, importantly: if procedure works on fractional solution (that is, if repeating greedy step covers cells) solution must optimal! (suppose wasn't: let x optimal fractional solution returned lp solver, let f feasible solution extracted greedily, , let y smallest weight of square in f. notice every square in f contributes @ least y coverage value of every cell; so, since f suboptimal assumption, subtracting y weight of every square in f , scaling other weights in x 1/(1-y) give (possibly again fractional) solution of lower weight, contradicting optimality of x.)

it useful prove fractional solution either (i) has component in "covering graph" non-integral total weight, or (ii) consists of such superposition: mean go on applying "general" cuts until superposition, solve greedily. stands, there might fractional solutions outside these 2 categories.