linearization of constraints

Question

I am dealing with an optimization model where my binary variables xi have to follow this type of constraint (in the attached link):

[https://i.stack.imgur.com/j39eh.jpg]

where j is different from i and aij are predetermined coefficient equal to 0 or 1.

I was wondering if there is an alternative formulation that would allow me to make it an ILP.

Answer 1

I'm not clear on exactly what the constraint is, but if your variables are all binary then yes, you should be able to linearise it.

Define additional binary variables xprod[i,j] subject to constraints:

• for all i, j, xprod[i,j] <= x[i]
• for all i, j, xprod[i,j] <= x[j]
• for all i, j, xprod[i,j] >= -1 + x[i] +x[j]

With all variables binary, this implies that xprod[i,j] = x[i]*x[j]. You can then define other constraints on xprod as necessary.