3
$\begingroup$

Notation:

I have an optimisation problem with objective function: \begin{align}\max&\quad\sum_n Q_n\\\text{s.t.}&\quad Q_n=x_{ij}^{nk}(y_i^{nk}-c_n), \forall n \in N, k \in K, (i,j) \in P.\end{align} Decision variables $x$ are binary, $y$ is continuous and non-negative, and $c$ is a constant.

Problem:

I wish to linearize this objective function. A product term $xy$ of a binary and continuous variable may be replaced by $z$ and some additional constraints as is mentioned here. The example provided is about a standalone product term. Is this approach still valid in a summation?

Assuming it is, I have split the two terms within the sum: $$\sum_n Q_n = \sum_n x_{ij}^{nk}y_i^{nk} - \sum_n x_{ij}^{nk}c_n$$

Then I applied the approach cited above only to replace product in the first sum with $$z_n=x_{ij}^{nk}y_i^{nk}, \forall n \in N, k \in K, (i,j) \in P$$ and adding four inequalities of the Big-M method:

\begin{alignat}2z_n &\geq y_i^{nk}-(1-x_{ij}^{nk})M,\quad &\forall n \in N, \in K, (i,j) \in P\\z_n &\leq Mx_{ij}^{nk}, &\forall n \in N, \in K, (i,j) \in P\\z_n &\leq y_i^{nk}, &\forall n \in N, \in K, (i,j) \in P\\z_n &\geq 0\end{alignat}

Is it valid to approach the split terms separately, and substitute $z$ back into the objective function?

$$ \sum_n Q_n = \sum_n z_n - \sum_n x_{ij}^{nk}c_n = \sum_n( z_n - x_{ij}^{kn}c_n), k \in K, (i,j) \in P $$

Or do I somehow need to take the $x_{ij}^{nk}c_n$ term in $Q$ also into account when linearizing?

Improve this question
$\endgroup$
5
  • $\begingroup$ I think your $Q_n$ and $z_n$ should instead be $Q^{n,k}_{i,j}$ and $z^{n,k}_{i,j}$. $\endgroup$
    – RobPratt
    Jun 19, 2020 at 16:23
  • $\begingroup$ @RobPratt If that's the case, it's not my intention. I do have another constraint in the entire model that should ensure that the binary $x$ variable is 1 for each $n$ for a fixed combination $i,j,k$: $ \sum_{k \in K} \sum_{i \in P} \sum_{j \in P} x_{ij}^{ck} \leq 1, \forall n \in N, \forall k \in K$. The same should be the case for the $y$ variable (i.e. for each $n$ the $i,j,k$ are already fixed), but I will definitely check this. This would then hopefully make $z$ and $Q$ only dependent on $n$? $\endgroup$
    – plaene
    Jun 19, 2020 at 17:18
  • $\begingroup$ In that case, you should have either $Q_n \ge x_{ij}^{nk}(y_i^{nk}-c_n)$ or $Q_n = \sum_{i,j,k} x_{ij}^{nk}(y_i^{nk}-c_n)$. $\endgroup$
    – RobPratt
    Jun 19, 2020 at 17:25
  • $\begingroup$ Could you explain why it becomes a (greater than) inequality? In my mind, both $x_{ij}^{nk}$ and $y_{i}^{nk}$ have only one, unique, value for each $n \in N$, regardless of the associated $i,j$ or $k$ index. But it's very well possible I'm overlooking something! $\endgroup$
    – plaene
    Jun 19, 2020 at 17:44
  • $\begingroup$ Instead of $x_{i,j}^{n,k}$ being independent of $i$, $j$, and $k$, I think you meant that $x_{i,j}^{n,k}$ will take value $1$ for (at most) one $(i,j,k)$ and $0$ for all other $(i,j,k)$. If $x_{i_1,j_1}^{n,k_1}=1$ and $x_{i_2,j_2}^{n,k_2}=0$ for the same $n$, your original equality constraints would require $Q_n=y_{i_1}^{n,k_1}-c_n$ and $Q_n=0$ simultaneously. $\endgroup$
    – RobPratt
    Jun 19, 2020 at 18:12

1 Answer 1

Reset to default
3
$\begingroup$

Replace each product term by the linearized (replacement) variable, $z_n$, and add the constraints for that linearization. You can then add, subtract, and sum these $z_n$ to your heart's content. You are also still free to use the original variables, which appeared in the product terms, in any linear manner in the model; so $c_n x_{ij}^{nk}$ terms are fine.

The $z_n$ are new (additional) variables, but you still have use of the $x_{ij}^{nk}$ which remain as optimization (decision) variables in your model, and indeed they appear in the linearization constraints.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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