3
$\begingroup$

Suppose I have a system of $n$ inhomogeneous linear equations in $m$ variables, where $n$ and $m$ are of the order of a few hundred, and $m$ is significantly larger than $n$. All the coefficients are integers. I want to find an integer solution in which the number of nonzero variables is minimised (or perhaps the sum of the absolute values of the variables is minimised; I suspect that the outcome will be similar). Is there a standard method for this? Of course it is straightforward to obtain the general solution, which has many parameters. However, it is not obvious to me how to choose these parameters so as to minimise the solution in the specified way.

$\endgroup$
4
  • 1
    $\begingroup$ For minimizing the sum of absolute values, the standard trick would be to introduce for each variable $x_i$ an auxiliary variable $y_i$ and constraints $x_i \le y_i$, $-x_i \le y_i$. Then minimize the sum of $y_i$. $\endgroup$ May 9 at 16:42
  • $\begingroup$ @JukkaKohonen Thanks, that worked well; it seems that the standard integer programming algorithms are more effective than I thought. $\endgroup$ May 9 at 17:15
  • $\begingroup$ You can certainly get the number of non-zero variables to be $\leq n$ but if the $nm$ coefficients are random real numbers from some range then I’d suspect that, with probability $1$, $n$ is the best you can get. $\endgroup$ May 11 at 7:13
  • $\begingroup$ @AaronMeyerowitz in the case of interest the coefficients are highly structured and there are solutions where the number of nonzero variables is much smaller than $\min(n,m)$. Among these I am looking for solutions with various auxiliary properties. Eventually I hope to give small, explicit and comprehensible solutions, but for the moment I am just searching by computer. $\endgroup$ May 11 at 7:39

1 Answer 1

5
$\begingroup$

Minimizing the sum of absolute values was covered in the comments. To instead minimize the number of nonzero variables, let $[\ell_j,u_j]$ be finite constant bounds on $x_j$, introduce binary variables $z_j$, and minimize $\sum_j z_j$ subject to linear constraints: \begin{align} Ax &\ge b \tag1 \\ x_j &\ge \ell_j z_j &&\text{for all $j$} \tag2 \\ x_j &\le u_j z_j &&\text{for all $j$} \tag3 \end{align} Constraint $(1)$ is the original system. Constraints $(2)$ and $(3)$ together enforce the logical implication $z_j = 0 \implies x_j = 0$.

By the way, traditionally $n$ is the number of variables and $m$ is the number of constraints.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.