SAT: 2D interval selection

Previous:

• SAT: optimal interval selection

"Cut rectangular slices of pizza. The pizza is divided into cells. Each slice must contain at least L tomato cells (T) and L mushroom cells (M). Each slice must contain at most H cells [1]. Maximize the total number of cells in the cuts."

In the last post, we solved a 2D slicing problem by optimizing each row independently. We should expect to do better by actually selecting 2D intervals instead. A 2D interval is represented as:

(x_start, x_end, y_start, y_end)

To generalize the code to 2D intervals, we do not have to change much. This is thanks to the fact that we only dealt with intervals in a very abstract sense before: as elements with a size (for the score) and an overlapping relation (to forbid overlapping slices). We need only to change the way we generate the intervals, and the overlapping relation. The code:

	def get_area2(c):
	ix, jx, iy, jy = c
	for x in range(ix, jx):
	for y in range(iy, jy):
	yield (x, y)
	def interval_overlap2(c0, c1):
	if any([interval_contains2(c0, p) for p in get_area2(c1)]):
	return True
	if any([interval_contains2(c1, p) for p in get_area2(c0)]):
	return True
	return False
	def interval_selection2(mat, feasible, max_width=None):
	N, M = mat.shape
	if not max_width:
	max_width = max(N, M)
	solver = SugarRush()
	coord2var = {} # coordinate to variable
	for ix in range(N):
	for jx in range(ix, min(ix + max_width, N+1)):
	for iy in range(M):
	for jy in range(iy, min(iy + max_width, M+1)):
	slize = mat[ix:jx, iy:jy]
	if feasible(slize):
	coord2var[(ix, jx, iy, jy)] = solver.var()
	mutex_clauses = [] # mutual exclusion clauses
	coord_2 = [(c0, c1) for c0 in coord2var for c1 in coord2var]
	for c0, c1 in coord_2:
	if c0 > c1: # ignore symmetries
	continue
	if c0 == c1: # can't forbid overlap with self
	continue
	if interval_overlap2(c0, c1):
	var0 = coord2var[c0]
	var1 = coord2var[c1]
	mutex_clauses.append([-var0, -var1])
	solver.add(mutex_clauses)
	p2covering = {} # point to covering
	for i in range(N):
	for j in range(M):
	p = (i, j)
	covering = []
	for c, var in coord2var.items():
	if interval_contains2(c, p):
	covering.append(var)
	if covering:
	p2covering[p] = covering
	p2covered = {}
	for p, covering in p2covering.items():
	ind, clauses = solver.indicator([covering])
	solver.add(clauses)
	p2covered[p] = ind
	opt_vars = [-ind for p, ind in p2covered.items()]
	itot_clauses, itot_vars = solver.itotalizer(opt_vars)
	solver.add(itot_clauses)
	best = solver.optimize(itot_vars)
	if best is None:
	return []
	selected_coords = [coord for coord, var in coord2var.items()
	if solver.solution_value(var)]
	return selected_coords

view raw interval_selection2.py hosted with ❤ by GitHub

Now we need a solution strategy. Tests show that the 2D interval selection gets tough (starts taking more than 10 seconds) when solving for larger than 20x20 matrices. However 12x12 matrices can be solved quickly (about 0.6 seconds). Solving with 12x12 sections often give a perfect score on the subproblem:

Optimization on 12x12 subproblem. Colored borders mark slices. 

Optimization on 12x12 subproblem. Colored borders mark slices.
In many cases, almost all slices are just rows or columns.

Now let's solve for the medium instance [1]. The max score is 50000. The row-wise maximization gave us 48977. The top result on google for "hashcode pizza" uses a greedy algorithm and gets 49567 on medium [2]. This time we get a score of 49980 missing only 20 cells. This clearly outperforms the other approaches. The runtime is about 10 minutes, without parallelization.

Conclusion
This result does not only say something about the power of model-based approaches, but also about the problem itself. It is quite an easy problem where we can get an almost perfect score by just solving independent subproblems.

[1] pizza.pdf
[2] sagishporer/hashcode-practice-pizza