Let \(x_i\) be binary variables and \(a_i\) given positive integers. I have an equality constraint like the following \[x_i\left(\sum_{j=1}^nx_{j}\right)=a_ix_i,\] for all \(i\). This means that if \(x_i=1\), then there must exists a set \(S\) with cardinality \(|S|=a_i-1\) such that \(x_j=1\) for all \(j\in S\). How can I linearize these constraints? If the constraints were of type inequality I could use a large (or small) number and write it as: \[\left(\sum_{j=1}^nx_{j}\right)\leq a_ix_i+M(1-x_i),\] for all \(i\).
asked
zbir |

Hint: Think of your equality as two inequalities and apply your big-M approach twice. Also, for numerical reasons be sure to choose \(M\) as small as possible.
answered
Rob Pratt |