# Linearization of objective function

### Notation

• $$\text{src}_{h,s},\text{dst}_{h,s},\text{ch}_{h,s}$$ are constants.

• $$a_{h,s},x_{i,j,s}$$ are binary variables.

• $$\text{wt}_{h,s}$$ are continuous variables.

### Problem

\begin{align}\min.&\qquad\sum_{h \in H}\sum_{s\in S}(\text{src}_{h,s}+\text{ch}_{h,s}+\text{dst}_{h,s}+\text{wt}_{h,s})\times a_{h,s}\\\text{s.t.}&\qquad{\forall h,i,j\in H\\\forall s\in S}:\begin{cases}\text{wt}_{j,s}\geq((\text{src}_{i,s}+\text{ch}_{i,s}+\text{wt}_{i,s})-\text{src}_{j,s})\times x_{i,j,s}\\x_{ij} + x_{ji}\leq1\\x_{ij}+x_{ji}\geq a_{i,s}+a_{j,s}+1\\\sum\limits_{s\in S}b_{h,s}\leq 1\end{cases}\end{align}

I want to use a LP solver on this problem but there are continuous variable $$\text{wt}_{h,s}$$ and Boolean variable $$a_{h,s}$$ together in objective function, how to separate them.

I have found a link for linearization in constraints1, but how to linearize in objective function?

Also in first constraint there are two continuous variable $$\text{wt}_{j,s}$$ and $$\text{wt}_{i,s}$$, is it possible to linearize it?

[1] https://www.leandro-coelho.com/linearization-product-variables

• Linearize the objective function the same way you would a constraint. Having two continuous variables in the first constraint doesn't add any complications because one of these variable appears "by itself", i.e., not multiplied by another variable, and therefore that variable already appears linearly. – Mark L. Stone Aug 3 '19 at 17:54
• Maybe take a look at this question: How to linearize the product of a binary and a non-negative continuous variable? – EhsanK Aug 3 '19 at 19:14
• Is this $$\sum_{h \in H} \sum_{s \in S} (src_{h,s} + ch_{h,s} + dst_{h,s} ) \times a_{h,s} + ( wt_{h,s} - (1 - a_{h,s}) \times \infty )$$ correct linearization of objective function, but what about the bounds. – ooo Aug 3 '19 at 19:28

1. Add some additional continuous variables $$s_{h,s}$$ to your model and use those variables in the objective, instead of the products.

2. Add the following constraints for each $$s_{h,s}$$:

• This constraint ensures that $$s_{h,s}$$ is at most equal to the sum:

$$s_{h,s} \leq \text{src}_{h,s}+\text{ch}_{h,s}+\text{dst}_{h,s}+\text{wt}_{h,s}$$

• This constraint ensures that $$s_{h,s}$$ will be at least the sum when $$a_{h,s}=1$$:

$$s_{h,s} \geq \text{src}_{h,s}+\text{ch}_{h,s}+\text{dst}_{h,s}+\text{wt}_{h,s} - M \times (1 - a_{h,s})$$

• This constraints ensures that $$s_{h,s}=0$$ when $$a_{h,s}=0$$:

$$s_{h,s} \leq M \times a_{h,s}$$

• You should pick small values for the constant $$M$$ to make it all work (e.g. $$\text{src}_{h,s}+\text{ch}_{h,s}+\text{dst}_{h,s}+\text{UB}(\text{wt}_{h,s})$$). Picking much larger values leads to lower performance and might even introduce numerical problems.