Linearize piecewise function without big-M constraints

Question

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.

Answer 1

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.