# Linearize a product of binary variables

I have a function to minimize which has the following term $$\sum_{i\in I}\sum_{j\in J}\sum_{k\in K}x_{ijk}N_{ij}a_{ijk},$$ where the variables are $$x_{ijk}\in\{0,1\}$$, $$a_{ijk}$$ are given as input and $$N_{ij}=\sum_{k\in K}x_{ijk}.$$

Can we linearize this objective function assuming that we have the following constraints: $$\sum_{i\in I}x_{ijk}=1,\forall j,k.$$

Introduce bounded variable $$y_{jk}$$ to represent $$\sum_{i\in I} x_{ijk} N_{ij} a_{ijk}$$, and minimize $$\sum_{j\in J}\sum_{k\in K} y_{jk}$$. Now enforce $$x_{ijk}=1 \implies y_{jk} = N_{ij} a_{ijk}$$, by using either indicator constraints or big-M constraints. If $$a_{ijk} \ge 0$$, you need only enforce $$x_{ijk}=1 \implies y_{jk} \ge N_{ij} a_{ijk}$$ because the minimization objective will then naturally enforce equality.

If you do it, you will force a constraint that maybe is not true. Are you sure that constraint ($$\displaystyle \sum_{i \in I} x_{ijk}=1, \forall j,k$$) is always true? If you are, so it's a correct approach. If you aren't, the best way to linearize this constraint is to use a big-M approach. This approach can create problems of approximation and probably you should choose a better big-M.

So, let $$M$$ a large enough number, note that depends of your problem, but you can use $$M=\displaystyle \sum_{i \in i} \sum_{j \in J} \sum_{k \in K}a_{ijk})$$. Let $$y_{ij}$$ a variable that models the linearization. Your objective function will be:

$$\displaystyle \min \sum_{i \in i} \sum_{j \in J} \sum_{k \in K} y_{ij}a_{ijk}$$

And you will keep with the constraint:

$$\displaystyle N_{ij} = \sum_{k \in K} x_{ijk} (\mbox{put the domain})$$

$$y_{ij} \geq - M(1-x_{ijk}) + N_{ij}, \forall i \in I, j \in J, k \in K$$ $$y_{ij} \leq M(1-x_{ijk}) + N_{ij}, \forall i \in I, j \in J, k \in K$$
Note that if $$x_{ijk}=1 \rightarrow ( y_{ij} \geq N_{ij} \wedge y_{ij} \leq N_{ij}) \leftrightarrow y_{ij} = N_{ij}$$ and otherwise these constraints will be redundant.
Maybe, depending on your problem, the value of $$y_{ij}$$ will be 0 if these constraint don't activate. But, you can force $$y_{ij} =0$$ when $$x_{ijk}=0$$ with these constraints: $$y_{ij} \leq Mx_{ijk}, \forall i \in I, j \in J$$