0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Do you want to say that every element of one row MUST be 1 and all the other rows must be zero? Or are you trying to say that any element of only one row can be 1, but they can all be zero as well? So is it fine to have a zeros matrix? $\endgroup$
    – EhsanK
    Commented Nov 17, 2023 at 16:35
  • $\begingroup$ I am trying to say that any element of only one row can be 1, but they can all be zero as well. If row 1 has non-zero elements, then all other rows must have zeros. If I sum over rows as you mentioned I may end up with different rows having non-zero element each. $\endgroup$
    – Jika
    Commented Nov 17, 2023 at 17:10

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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