Constraints 'exactly/at most one non-zero element' without binary variables

Question

In a much larger MINLP problem, I have set of variables $\{a_{ij}\}_{m,n}$, such that $0 \leq a_{ij} \leq 1 $ for all $i$, $j$, which I could think of as a matrix, for which I have two requirements:

• there is exactly one non-zero element per row;
• there is at most one non-zero element per column.

This can easily be achieved by letting $a_{ij} = x_{ij}\,b_{ij}$ and:

\begin{align*} &\min f(x_{ij}\,b_{ij},\ldots)\\ &\mbox{s.t.}\\ &\sum_j x_{ij}\,b_{ij} = 1\quad \forall i,\\ &\sum_i x_{ij}\,b_{ij} \leq 1\quad \forall j,\\ &\vdots\\ &x_{ij} \in \{0,1\}, \ 0 \leq b_{ij} \leq 1\quad \forall i,j. \end{align*} ( $f$ is some non-linear function in multiple variables, and constraints not relevant for this question are omitted)

However, for computational reason, I'd prefer to do without all those extra binary variables $x_{ij}$. That is, I am looking for a formulation of the constraints without introducing extra binary variables.

Is there a way to construct linear constraints on the $a_{ij}$, that ensure that the two requirements (as mentioned on the top of this post) are satisfied?

Any suggestions are much appreciated.

Answer 1

No, this is not possible. There is a standard way of showing this:

The feasible region of your constraints is not convex. For example, $x_{1,1}=1$, $x_{1,2}=0$ is feasible, $x_{1,1}=0$, $x_{1,2}=1$ is feasible, but the midpoint $x_{1,1}=1/2$, $x_{1,2}=1/2$ is not feasible.

The feasible set of a system of linear equality and inequality constraints is always convex.

Thus your desired constraint can’t be expressed with linear constraints.