2

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.$$

zdm
  • 381
  • 1
  • 5

2 Answers2

5

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.

RobPratt
  • 32,006
  • 1
  • 44
  • 84
2

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$$

EhsanK
  • 5,864
  • 3
  • 17
  • 54
Judecir
  • 21
  • 2