System of linear equations, find the solution with the maximum number of variables equal to zero

linear algebrapython

as the title says, I have a vanilla system of linear equations, say 3 equations 3 unknowns x, y, z, there are always an equal number of equations and unknowns, and always an infinity of solutions for the given system.

How do I find the resolution approach, programmatically, that maximizes the number of variables equal to zero, e.g. if resolving the above system gives something like x = y ; z + y = 3; then I know that the solution I am looking for is 0, 0, 3, not 1, 1, 2 or any other combination, I want as many variables as possible to be equal to 0.

I tried researching for such approach, or various implementations in numpy.linalg.solve or scipy.linalg.solve, but neither give me the options/methods to get the result I am looking for

EDIT:
Thanks Rob Pratt for your answer, implementation in pulp below for reference:

from pulp import *
import numpy as np

problem = LpProblem('netting', LpMinimize)

z = [LpVariable('z'+str(i), cat=LpBinary) for i in range(6)]
x = [LpVariable('x'+str(i), lowBound=-100_000, upBound=100_000, cat=LpVariable) for i in range(6)]

problem += sum(z), 'objective_function'
problem += x[0]+x[2]+x[3]-x[5] == 39
problem += x[0]-x[1] == 0
problem += x[5]-x[1] == -6
problem += -x[2] == -15
problem += -x[3]-x[4] == -27
problem += x[4] == 9

for i in range(6):
    problem += x[i].lowBound*z[i] <= x[i]
    problem += x[i] <= x[i].upBound*z[i]

print("Current Status: ", LpStatus[problem.status])

problem.solve()

for i in range(6):
    print("x",i, x[i].varValue)
    print("z",i, z[i].varValue)
print("sum(zi)", value(problem.objective))

print("Current Status: ", LpStatus[problem.status])

Best Answer

Let $x_i$ be the decision variables, and assume finite bounds $\ell_i \le x_i \le u_i$. Let binary decision variables $z_i$ indicate whether $x_i$ is nonzero. The problem is to minimize $\sum_i z_i$ subject to $$\ell_i z_i \le x_i \le u_i z_i \tag1$$ and the original linear constraints. Constraint $(1)$ enforces $z_i = 0 \implies x_i = 0$, equivalently, $x_i \not= 0 \implies z_i = 1$.

Related Question