What is the best way to constrain a binary matrix so that at most one row has positive values?

Question

I have a binary variable $x_{i,j}$ for $i\in\{1,\ldots,m\}$ and $j\in\{1,\ldots,n\}$ and the constraint is to have at most one row that has ones. I wrote this as: $$x_{i,j}+x_{i',j'}\leqslant1,\forall i'\ne i,\forall i,j,j'$$ which creates $O(m^2n^2)$ constraints. Can I have a different and better formulation?

Answer 1

Introduce a binary variable $y_{i}$ and then define these constraints:

$x_{i,j} \le y_{i} \quad \forall i, j \tag{1}$

$\sum_{i} y_i \le 1 \tag{2}$

So, at most one of the $y_i$ can be 1 and in that case, any of the elements in that row can be either 0 or 1.

Answer 2

Adding to the solution provided by @EhsanK. By introducing a binary variable $z$, which is 1 only if all $x_{i,j}$ are equal to 0, and adding a constraint, potential symmetries in the branch-and-bound tree can be avoided. $x_{i,j} \le y_{i} \quad \forall i, j \tag{1}$

$\sum_{i} y_i + z = 1 \tag{2}$

$\sum_i \sum_j x_{i,j} \geq 1-z \tag{3}$

If for example $y_1 =0.5$ in the LP-solution, and one branches on $y_1$, then one wants to partition the solution space in two. However, if one does not have the variable $z$ and the additional constraint, then the solution where all $x_{i,j}$ equals 0 is contained in both partitions after branching on $y_1$.

To be clear, I am not saying including $z$ and the additional constraint is going to perform better, but in some cases it might.