Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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})$$
You can add these constraints:
$$ 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$$
