6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark L. Stone Aug 3 '19 at 17:54
  • 2
    $\begingroup$ Maybe take a look at this question: How to linearize the product of a binary and a non-negative continuous variable? $\endgroup$ – EhsanK Aug 3 '19 at 19:14
  • $\begingroup$ 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. $\endgroup$ – anoop Aug 3 '19 at 19:28
7
$\begingroup$
  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.
| improve this answer | |
$\endgroup$
5
$\begingroup$

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]

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Could you maybe explain a bit better how this approach can be applied to the problem stated in the question? $\endgroup$ – Rolf van Lieshout Aug 4 '19 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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