# Linearize piecewise function without big-M constraints

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.

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

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.

• 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? Nov 19 at 19:12
• 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} Nov 19 at 21:53
• The rest looks fine :) But with a purely linear formulation it will be easier to find a solver Nov 19 at 22:18
• 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. Nov 20 at 9:48