# Find the optimal dividing line

Consider the following grid of numbers:

[[-3  2  2  2 -1  2  0  1  2 -1]
[ 0  1 -2 -1 -1  1  3  3  1  3]
[ 1 -3  0 -1  1  2  2 -2  0  3]
[-1  0  1 -2  0  2  2 -2 -3  2]
[-3  0 -3  1 -2  1 -3  3  0 -3]
[-2 -1  0  2  1  3  1  2  2 -1]
[ 0  3  1  0  1 -1 -1  2  2  2]
[-2 -3  1  2 -1  3  3 -1 -1  2]
[ 2  1  3  2  0  2 -1  1  2 -1]
[-1  3 -2 -1  1  1 -2  1  2 -1]]


If you draw a straight line from one side to another of the grid, your score is the sum of all the numbers in squares where the middle (shown with blue dots) is on the side of the line including the top left corner of the grid. You are not allowed to start or end the line exactly in the top left corner.

What is the optimal line? You are aiming to maximize the score.

• would. be nice to provide text/sheet version.
– Oray
Dec 17, 2023 at 14:10
– Simd
Dec 17, 2023 at 14:21

The sum of all the numbers in the grid is 38.

Color-coding the grid allows us to easily see favorable/unfavorable portions of the grid:

Our goal is then to remove the least favorable portion with a single straight cut.

I believe this may be optimal:

Removing a sum of -7 leaves us with a sum of 45.

• A very nice answer. How did you draw the color coded grid?
– Simd
Dec 17, 2023 at 20:00
• @Simd I just used the bucket tool (flood fill) in Paint Dec 17, 2023 at 20:01
• I confirmed optimality via integer linear programming. Dec 21, 2023 at 2:53
• @RobPratt Could you add the ilp you used? I would be interested
– Simd
Dec 30, 2023 at 10:01

The maximum is

45,

achieved, for example, by

I solved the problem via mixed integer linear programming as follows. Let $$a_{ij}$$ be the given value in cell $$(i,j)$$. Let $$\epsilon>0$$ be a small constant tolerance. Let decision variables $$\alpha$$ and $$\beta$$ define the line $$\alpha i + \beta j = 1$$. Let binary decision variable $$x_{ij}$$ indicate whether cell $$(i,j)$$ is selected. The problem is to maximize $$\sum_{i,j} a_{ij} x_{ij}$$ subject to linear constraints \begin{align} x_{0,0} &= 1 \tag1\label1 \\ \alpha i + \beta j - 1 + \epsilon &\le M(1-x_{ij}) &&\text{for all (i,j)} \tag2\label2 \\ -\alpha i - \beta j + 1 + \epsilon &\le M x_{ij} &&\text{for all (i,j)} \tag3\label3 \end{align}

Constraint \eqref{1} selects the top left corner. Big-M constraint \eqref{2} enforces $$x_{ij}=1 \implies \alpha i + \beta j \le 1 - \epsilon$$ so that cell $$(i,j)$$ is on the same side of the line as $$(0,0)$$. Big-M constraint \eqref{3} enforces $$x_{ij}=0 \implies \alpha i + \beta j \ge 1 + \epsilon$$ so that cell $$(i,j)$$ is on the opposite side of the line.

For the $$100 \times 100$$ instance (with total sum $$\sum_{i,j} a_{ij}=316$$), I get a maximum of $$449$$ by excluding the following cells with sum $$-133$$:

If I fix $$x_{74,10}=x_{85,29}=x_{96,48}=1$$ and $$x_{74+1,10}=x_{85+1,29}=x_{96+1,48}=0$$, I get a maximum of $$440$$ by excluding the following cells with sum $$-124$$:

If I fix $$x_{74,10}=x_{85,29}=x_{96,48}=0$$ and $$x_{74-1,10}=x_{85-1,29}=x_{96-1,48}=1$$, I get a maximum of $$441$$ by excluding the following cells with sum $$-125$$:

• This is a very nice example of MILP.
– Simd
Dec 30, 2023 at 22:24
• If you scale the problem to 100 by 100 does your code still finish quickly?
– Simd
Dec 31, 2023 at 5:22
• @Simd That is 100x bigger, so probably not. Do you have example data for that? Dec 31, 2023 at 14:50
• I will next be by a real computer in two days but I would make the data with numpy.random.randint(-3, 4, size=(100, 100)).
– Simd
Dec 31, 2023 at 15:55
• @Simd For your 100 by 100 instance, I got an optimal objective value of 449 in 36 minutes. Jan 5 at 18:18

I have found two solutions.

Both solutions sum to 45. The sum of all the cells is 38.

I permuted a line connecting every pair of blobs.
I then consider a parallel dividing line moved slightly to one side.

First, blobs passed through are excluded from the black blob's region.
Excluded cells are (-3) + (-2) + (0) + (-2 -3) + (+2 +1) + (-1 +3 -2) = -7.
This is the same as other answers.

Then, blobs passed through are included with the black blob's region.
Excluded cells are (-1) + (-3) + (-2) + (0) + (-2) + (2) + (-1) = -7.
This is a new solution.

• Very nice Indeed.
– Simd
Jan 6 at 12:11
• I confirmed that these are the only two optimal solutions. Jan 9 at 23:03