I've encountered an unusual constraint in a LP while reading a paper. I would like to know if the problem remains linear despite the inclusion of this constraint:
$\sum_{i=1}^{g} \prod_{k=1}^{n}X_{ijk}=1 \hspace{1cm}\forall j=1\cdots m$
where the variable $X_{ijk}\in \{0,1\}$ is the decision variable which is binary in nature.
My guess is that it is non-linear as it involves multiplication of variables in the inner loop $k=1\cdots m$. Could you please clarify my doubt?
As usual when dealing with boolean (and more generally, integer) variables, this expression can be linearized, but it will introduce more variables into the problem. One way to do it is the following:
$\forall i \in [1,g], \forall j \in [1,m], Y_{i,j}$ is the binary variable equal to $\prod_{k=1}^n X_{i,j,k} $
$Y$ can be defined by the following linear equations
$\forall i \in [1,g], \forall j \in [1,m], n \cdot Y_{i,j} \leq \sum_{k=1}^n X_{i,j,k} \leq n-1+Y_{i,j} $
And your constraint becomes $\forall j \in [1,m], \sum_{i=1}^g Y_{i,j} = 1$
I am guessing the author thought this was somehow "obvious", but most papers do precise when they use such a trick.
