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}

Answer 1

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

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.

Answer 2

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]