2
$\begingroup$

I have been attempting to solve a maximization problem where there is a piecewise function in the objective. Something like:

$\sum_{n}(1-prob_{n})(1+x_n)$

Where $prob_{n} = $

\begin{cases} 0.25, & x_n \geq 2 \\ 0, & 0 < x_n < 2 \\ 0.05, & x \leq 0 \\ \end{cases}

Note that this is just a toy example, I realise that this function can very easily be maximised but this is just for me to understand how one can linearise a piecewise function with several segments.

I have not been able to linearise this piecewise function using big-M constraints but I came across this (see page 9 and 10). Here they linearise a piecewise function without any big-M constraints. I have worked through the example and it makes sense to me. However, the piecewise function considered in the example does not have 'jumps' like mine does. There are kinks but at the break points the value is the same when going from one segment to another. In my piecewise function however, there are jumps. For example, at $x=2$ we are at 0.25 but at $x - \epsilon$ we are at 0.

The function considered in the example looks like:

$c(x) = $

\begin{cases} 25x, & 0 \leq x_n \leq 500 \\ 20x + 2500, & 500 \leq x_n \leq 1000 \\ 15x + 7500, & 1000 \leq x_n \leq 1500 \\ \end{cases}

This is then written as:

$z_{1}c(0) + z_{2}c(500) + z_{3}c(1000) + z_{4} c(1500)$ (1).

Then the following constraints are added:

$x = 0z_{1} + 500z_{2} + 1000z_3 + 1500z_4$

$z_1 \leq y_1$

$z_2 \leq y_1 + y_2$

$z_3 \leq y_2 + y_3$

$z_4 \leq y_3$

$y_1 + y_2 + y_3 = 1$

$z_1 + z_2 + z_3 + z_4 = 1$

Here $y_i$ are binary variables and $z_i$ are positive reals.

I tried this approach to my piecewise function but I am uncertain about how to deal with the 'jumps' when re-writing (1). Is it even possible to apply this approach to my function or do I have to figure out the big-M approach?

EDIT:

Thanks to @Ggouvine for the explanation. Here is my attempt at linearising the original problem (prob_n has been re-written for clarity).

Objective:

$\sum_{n}(1-prob_{n})(1+x_n)$

Where $prob_{n} = $

\begin{cases} 0.05, & -5 \leq x_n \leq 2 \\ 0, & 0 < x_n < 2 \\ 0.25, & 2 \leq x \leq 5 \\ \end{cases}

So now I have added -5 and +5 as lower and upper bounds. I can then re-write the objective as:

$\sum_{n}(1-0.05y_{1} - 0 y_2 - 0.25 y_3)(1+x_n)$

Where $y_i$ are binary variables. Now the problem is non-linear. However, the multiplicative terms (i,e $y_{i}x_{n}$) can be linearised given the approach outlined here: How to linearize the product of a binary and a continuous variable?

So I will simply focus on the interval and prob_n constraints.

For the interval we get:

\begin{align} -5 &\leq x_n &&\leq 0 + M(1-y_1) \\ 0 - M(1-y_2) &\leq x_n &&\leq 2 + M(1-y_2) \\ 2 - M(1-y_3) &\leq x_n &&\leq 5 \end{align}

And for prob_n we get:

\begin{align} 0.05 - (1-y_1)M &\leq prob_n &&\leq 0.05 + (1-y_1)M \\ 0 - (1-y_2)M &\leq prob_n &&\leq 0 + (1-y_2)M \\ 0.25 - (1-y_3)M &\leq prob_n &&\leq 0.25 + (1-y_3)M \\ \end{align}

I have tried different values for $y_1, y_2$ and $y_3$ and it comes out as expected. So I suppose I just need to include the constraints for linearising the multiplicative terms and I should be able to solve this using a MILP solver.

$\endgroup$
3
  • 3
    $\begingroup$ SOS2 variables were invented to do this without big-Ms. $\endgroup$ Commented Nov 20, 2023 at 6:25
  • $\begingroup$ I will look in to SOS2! Are there any advantages to using SOS2 over big-M together with binary variables? $\endgroup$
    – akkha
    Commented Nov 20, 2023 at 9:47
  • $\begingroup$ Are there any advantages to using SOS2 over big-M together with binary variables? (1) No big-Ms needed (2) Ease of use. $\endgroup$ Commented Nov 20, 2023 at 14:22

1 Answer 1

3
$\begingroup$

I don't see or remember a way around the big-M constraints. Thankfully they are not that hard to write. Or you may use indicator constraints which are even simpler.

We add new binary variables, and depending on them some constraints are equality constraints, or ignored. Typically these conditional constraints are written $a - My \leq b \leq a + My$

Here we use one binary variable per interval: $y_1 + y_2 + y_3 = 1$

To constrain the intervals: \begin{align} 0 &\leq x &&\leq 500 + M(1-y_1) \\ 500 - M(1-y_2) &\leq x &&\leq 1000 + M(1-y_2) \\ 1000 - M(1-y_3) &\leq x &&\leq 1500 \end{align}

To constrain the objective: \begin{align} 25x - M(1-y_1) &\leq prob &&\leq 25x + M(1-y_1) \\ 20x + 2500 - M(1-y_2) &\leq prob &&\leq 20x + 2500 + M(1-y_2) \\ 15x + 7500 - M(1-y_3) &\leq prob &&\leq 15x + 7500 + M(1-y_3) \\ \end{align}

Up to you to compute values for $M$ that are small but big enough to stay valid.

$\endgroup$
4
  • $\begingroup$ This was so much cleaner than I had expected, many thanks for the explanation! I have added an edit where I go through the solution attempt to my problem, does it look fine to you? $\endgroup$
    – akkha
    Commented Nov 19, 2023 at 19:12
  • 1
    $\begingroup$ You don't need a nonlinear term here. Just consider $z_{n} =$ \begin{cases} (1 - 0.25)(1 + x_n), & x_n \geq 2 \\ (1 + x_n), & 0 < x_n < 2 \\ (1 - 0.05)(1 + x_n), & x \leq 0 \\ \end{cases} $\endgroup$
    – Ggouvine
    Commented Nov 19, 2023 at 21:53
  • $\begingroup$ The rest looks fine :) But with a purely linear formulation it will be easier to find a solver $\endgroup$
    – Ggouvine
    Commented Nov 19, 2023 at 22:18
  • $\begingroup$ Great, then I will use the transformation you suggested in your post and re-write my problem as you did in the comments. This should then become a MILP which I can solve with GLPK. $\endgroup$
    – akkha
    Commented Nov 20, 2023 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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