2
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.