# Linearize sum of product in objective function

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?

• I think your $Q_n$ and $z_n$ should instead be $Q^{n,k}_{i,j}$ and $z^{n,k}_{i,j}$. Jun 19 '20 at 16:23
• @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$? Jun 19 '20 at 17:18
• 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)$. Jun 19 '20 at 17:25
• 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! Jun 19 '20 at 17:44
• 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. Jun 19 '20 at 18:12

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.