How to check if just one element of a vector is nonzero by a linear operator

620 Views Asked by At

I want to check by a linear operator if none or just one element of a non-negative matrix is positive. Consider a matrix $A$ as a $1\times N$ non-negative matrix and for each element $a_i \in A$ we have $0\leq a_i \leq A_{max}$. $A$ is valid if it is all zero or it just has one none zero element like $A=(0, 2, 0, 0)$ or $A=(0, 0, 0, 5)$. $A$ is not valid if it is like $A=(1, 0, 1, 0)$ as more than one element of A are non-zero.

I think normally it can be checked if $\sum_{i = 1}^{N} a_i = ||A||$ but this is not linear.

Is there any way to maybe multiply A into another matrix and check the result to see if $A$ is valid. I am using $A$ in a integer linear optimization problem and having less than one non-zero element in $A$ is one of my constraints.

Thanks

1

There are 1 best solutions below

1
On

Counting nonzero elements in a MIP (Mixed Integer Program) is usually done by adding binary variables. Using your definition of $0\le a_i \le Amax$ we can write,

$$\begin{align} & a_i \le \delta_i \cdot Amax \\ & \sum_i \delta_i \le 1 \\ & \delta_i \in \{0,1\} \end{align}$$

The condition "maximum one nonzero" can also be achieved by using a SOS1 set. This will not require any additional binary variables. Many MIP solvers (but not all) have built-in support for Special Ordered Sets.