One of the questions I get asked quite often from members of the Decide Operational Research Unit is: How is a Piecewise Linear Function (PWL) formulated so that it can be resolved with an Integer Linear Programming engine?
The easy answer is: it doesn’t need to be formulated. Many of the products that solve Integer Linear Programming products have by default a PWL formula that allows them to be used without knowing how they are actually represented internally. Yet, as my colleague Miguel Ángel Bógalo always says, and something I completely agree with, before using a framework, utility or anything else, it is important to work it out manually in order to understand in depth what is being done.
So, I will use this post to explain a PWL formula and the implications of incorporating this type of function to models that solve problems using Integer Linear Programming.
What is a Piecewise Linear Function?
Since a picture is worth a thousand words, PWL can be defined as follows:
More specifically, a PWL is a sequence of contiguous segments. It could be represented as a formula in this way:
How can you linearise a PWL?
Although the PWL itself is not linear, each of the intervals of x corresponding to each of the segments is.
So, thinking about it a little more, we can reach another formula which becomes almost linear: If we represent x as:
and we ensure that at most two λs are unequal to 0, and in that case they are consecutive, then f(x) can be represented as follows:
Ultimately, representing x as a convex linear combination of the values a, and ensuring that a maximum of two λs are unequal to 0, and if this is the case, they are consecutive, we can place x in one of the segments, leaving f(x) as:
It is very important to note the importance of the property: and if this is the case, they are consecutive. With this property, when calculating f(x) for an arbitrary x, the calculation is correct:
If this property is not fulfilled, an ‘inadequate’ convex linear combination could lead to this situation:
This property, owing to its importance, has a name: a type 2 Special Ordered Set. All Integer Linear Programming engines have an internal representation of this type, and they are treated efficiently. Even so, in the spirit of this post, we will now create this type of formula using intermediate binary variables, so that we have a completely linear representation of the PWLs. The formula is as follows:
Notice that, in this formula, each binary variable appears in two equations, corresponding to the λs which may be positive if the binary variable is 1. Thus, we have succeeded in creating the PWL formula a completely linear way, with the help of a number of binary variables for formulating the type 2 Special Ordered Set.
Further Considerations
he first thing to keep in mind when using this type of Piecewise Linear Function is that the problem becomes generally more complex. In our case, if our model works only with continuous variables, it will automatically change from being a Linear Problem to a much more complex Integer Linear Problem.
Still, there are instances in which introducing this type of function does not affect the complexity of the problem. These are the cases in which the relaxed solution to the problem automatically coincides with the integer solution. Supposing that our PWL lies in the objective function, and analysing the case in which the selection of λs was incorrect:
Why would the Linear Programming engine make this incorrect selection of λs? Really this could only happen if our objective function were to minimise the cost function. In this case, it is more profitable to select these λs, as this obtains a smaller target function. If the target function, on the other hand, were to maximise the cost function, these λs would never have been selected, since the correct choice:
provides a greater profit (a higher value of the cost function).
Therefore, if the purpose of the PWL is to be in the target function (which, incidentally, is quite common), we simply analyse its concavity or convexity, as well as the direction (minimise or maximise) of the target function to determine the need to incorporate binary variables that force the SOS2 property over the λs, ensuring our problem does not increase in complexity.
Update: My recommendation is almost always to use the native PWL formulas that the Linear Programming engine has by default, and, where these do not exist, always use the SOS2 formulas.