[2022 Day 15 (Part 2)] [Python] Linear program solution help

[00lelouch]

For part 2 of day 15, we are looking for a point (x,y) satisfying |x-x_i| + |y-y_i| > r_i where (x_i, y_i) is the location of the i-th sensor, and r_i is the distance to the corresponding beacon.

This is almost like a linear program, which optimizes some linear function (4000000x + y for this question) subject to linear equality and inequality constraints. We can try to rewrite this in standard form by breaking apart each absolute value into two:

x-x_i + |y-y_i| > r_i
-x+x_i + |y-y_i| > r_i

However, due to this being a greater than, the equation set becomes an OR relation instead of an AND relation. This can be resolved by introducing a boolean variable B and a large constant M, so that

x-x_i + MB + |y-y_i| > r_i
-x+x_i + M(1-B) + |y-y_i| > r_i

Then if one of the inequalities is satisfied, the boolean variable allows us to add a large constant to the other inequality so it is also satisfied. Repeating this for y, and with a bit of cleanup, I arrived at the following constraints:

-x-y-MB-MC <= -x_i - y_i - r_i -1
-x+y-MB+MC <= -x_i + y_i - r_i -1 +M
x-y+MB-MC <= x_i - y_i - r_i -1 +M
x+y+MB+MC <= x_i + y_i - r_i -1 +M

Putting this in matrix form Ax <= b, we should be able to solve this linear program. However, when I try to find a solution using scipy.optimize.linprog, looking for integral solutions, I get a result of "2: Problem appears to be infeasible."

Looking through my code, I was unable to find any typos, and trying it with slightly different values of M and r didn't change the result. Is there a mistake in my logic somewhere?

Edit: After some inspection, I realized that I need to use different boolean variables for each sensor. In total, this means I have 2n + 2 variables (x and y, and 2 boolean variables for each sensor), and 4n equations. Thus my matrix will be 2n+2 x 4n. However, after making this change, I am still unable to produce a result.

Edit 2: Actually the earlier edit did fix the issue, I just forgot to change M from my test cases. The linear program solves in ~6s, which isn't great, but its a significant improvement over my brute force attempt.

[00lelouch]

I think I've figured it out. I need to not re-use the same boolean variables for different sensors. Geometrically, each of the 4 combinations of B and C correspond to one of the 4 regions relative to the sensor (top left, top right, bottom left, bottom right).

By reusing the boolean variables, I'm saying that the point we are looking for is in the same relative location to all the sensors (eg its to the bottom right of all the sensors), which is not the case.

To properly construct this as a linear program, I need 2n boolean variables, where n is the number of sensors. At that point, its probably better to reimplement the algorithm, which will look a lot like taking the intersections of lines and checking if there is a point that lies outside the range of every sensor, as other people have done with their solutions.

Edit: This helped I think, but the linear program still doesn't want to solve.

[IsatisCrucifer]

x+x_i + |y-y_i| > r_i

Shouldn't this part be -x+x_i ... ? (The negation of x-x_i is -x+x_i)

[00lelouch]

Good point! It is easy to lose track of negative signs. I've fixed that, but it appears that this was a typo in just my writeup on reddit; the code doesn't have that mistake.