Step Functions and Mixed Functions

Someone asked me (elsewhere) about modeling, in a mathematical program, a piece-wise linear function that was a mixture of steps and linear segments. Since it contains step functions, it is neither continuous nor convex, but nonetheless it can be modeled within a mixed-integer linear program (MILP). Here is a sketch of a sample function.

I drew this with one diagonal linear segment, at the right end, but what follows will work for any mixture of steps and linear segments. If you are wondering why the heights are listed at $y_2,y_4,y_6$, it will become clear in a minute. The labeling is a bit fuzzy (sorry about that). The annotation of the diagonal segment is $y=mx+b$.

The key to modeling this is recognizing that every point on the graph is a linear combination of two adjacent endpoints. (The endpoints are the ones represented by dots on the graph.) There are nine endpoints on the graph, which we will designate as $(x_1,y_1),\dots,(x_9,y_9)$, as shown in the second sketch. For the modeling trick to work, it is necessary that the domain of the function be bounded (in this case $0\le x\le x_9$).

Hopefully the reason for the subscripts of the ordinates of the horizontal segments is now apparent

Let $y$ be the value of the function. We introduce continuous variables $\mu_1,\dots,\mu_9\in [0,1]$, which will be the weights of a convex combination of the graph points. Both $x$ and $y$ are expressed using these weights:\begin{gather*}x=\mu_1 x_1 + \dots + \mu_9 x_9\\y=\mu_1 y_1 + \dots + \mu_9 y_9\\\mu_1+\dots+\mu_9=1.\end{gather*}
What makes this work is that we also make the weights $\{\mu_1,\dots,\mu_9\}$ a type 2 special ordered set (SOS2), specified in index order. This tells the browser that at most two of the weights can be nonzero and, if there are two nonzero weights, they must be consecutive in the stated order (e.g., $\mu_3=0.4,\mu_4=0.6$ is fine but $\mu_2=0.4,\mu_7=0.6$ is invalid). The SOS2 restriction essentially forces the solver to select one segment of the graph, whether horizontal, diagonal or even vertical; the weights then select one point on the segment. If $y$ is part of the objective, and the chosen segment happens to be vertical, it's a safe bet that one of the weights will be 1 and the rest 0 (picking whichever endpoint of the segment better suits the objective direction).

Although the weight variables are continuous, introducing the SOS2 constraint will effectively turn the problem into a MILP even if it otherwise would have been a linear program (LP).

There are other ways to model this type of function. In particular, anything done with SOS1 or SOS2 constraints can be done with binary variables and linear constraints involving those binaries.

Related posts:

• Piecewise-linear Functions in Math Programs
• Modeling the All Units Discount
• Piecewise-linear Functions Redux
• Modeling Absolute Values
• Piecewise Linear Functions in CPLEX