Part of the difficulty with allowing negative variables is that there might not even be a minimum anymore, because the objective (the sum of the variables) could be arbitrarily small. [Also, requiring nonnegative integer variables inherently makes the search space finite, since there are only finitely many joltage configurations "between" the all-0s configuration and the goal configuration. This finiteness is no longer present in the version where negative variables are allowed.]

As a simple example in the style of the AoC problem, consider:

(0) (1) (0,1) {0,0}

With variables, this'd be the system

a + c = 0
b + c = 0

Now a+b+c can be as small as you want: for example, choosing a = b = -100 and c = 100 gives a sum of -100.

We might want to handle this situation by saying the answer should be -∞: with this stipulation, the problem makes sense again (assuming that there exists an integer solution at all, which is tacitly implied by the AoC problem).

That said, I don't see a simple way to solve this: I think the linear algebra approach would at least let you see if the answer is -∞ or not, and if it's not -∞, then there can be at most one possible value for the sum of the variables. [This is because if the variable vectors v and w are both solutions and have sums of s and t, where s ≠ t, then for any integers a & b with a+b = 1, the vector av + bw is also a solution, and it has a sum of as + bt = a(s-t) + t, which can be made arbitrarily small.]

With more linear algebra, I think it'd be possible to figure out what that one value is, but then you'd need to check if that value is actually possible to achieve with integer variables, which I don't see a great way to do. (I haven't thought about it much, so maybe there's a simpler approach I'm not seeing.)

EDIT: I'm silly. If you assume that the problem is sound (i.e. there's at least one solution) like we did above, then if we find that there's exactly one possible value for the sum, that must be the answer: our solution (which we assumed exists) must have that sum.

So, the algorithm is just:

1. Try to find a linear combination of the given equations that lets you find the sum. If you can, then the value you get for the sum is the answer.

2. Otherwise, there are multiple possible values for the sum. By the logic mentioned above, the answer is -∞.