Linearization of objective function

Question

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 constraints¹, 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 03 '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 03 '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 03 '19 at 19:28

score 8 · Accepted Answer · edited Aug 04 '19 at 08:25

Add some additional continuous variables $s_{h,s}$ to your model and use those variables in the objective, instead of the products.
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} $

Some notes about this:

I assumed that your constants and variables are all nonnegative.
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.
If your solver of choice supports indicator constraints, you could also formulate it using those.

score 6 · Answer 2 · answered Aug 03 '19 at 18:27

Piecewise linearization methods have been widely applied to convert a nonlinear programming problem into a linear programming problem or a mixed-integer convex programming problem for obtaining an approximated global optimal solution. In the transformation process, extra binary variables, continuous variables, and constraints are introduced to reformulate the original problem. These extra variables and constraints mainly determine the solution efficiency of the converted problem.[source]

Could you maybe explain a bit better how this approach can be applied to the problem stated in the question? — Rolf van Lieshout, Aug 04 '19 at 09:24

Linearization of objective function

Notation

Problem

2 Answers2