## Monday, August 27, 2012

### 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:

1. Professor Rubin,
Nice article indeed. Thanks a lot.

1. You're very welcome.

2. Dear Paul,

If a convex continues curve instead of step function is in two adjacent endpoints, then is it possible to apply your proposed techniques to model it?

Regards,

Dewan

1. That depends what you mean by "curve". The technique above works for any piecewise-linear function (any mix of steps and linear segments). If your "curve" is nonlinear, you can do the same things, but you are now dealing with an MINLP (mixed integer nonlinear program), and you need a solver that can solve MINLPs. I don't work with MINLPs, so I don't know which solvers are commonly used and how (or if) they handle SOS constraints.