Modeling piecewise linear functions

Math Models of OR

Piecewise linear functions can be modeled using variables that satisfy what is known as a special order set (SOS) constraint of type 2. Consider the following example of a continuous piecewise linear function:

$$z = \left\{ \begin{array}{rl} 3+4x & \mbox{for } 0 \leq x \l... ...q 3 \\ 6+x & \mbox{for } 3 \leq x \leq 7. \end{array} \right.$$

The variable x is restricted to lie between 0 and 7.

We introduce four nonnegative continuous variables x₁, x₂, x₃, and x₄. We require

x = 0x₁ + 2x₁ + 3x₂ + 7x₃, (1)

so the coefficients are the endpoints of the three intervals in the function. We also require

x₁+x₂+x₃+x₄ = 1, (2)

the same method we used for modeling a variable that takes a number of distinct values. Here, x is continuous, so we allow the x_i to be continuous. We can now define z as

z = 3x₁+11x₂+9x₃+13x₄ (3)

so the coefficients are the values of z at the breakpoints.

The calculated value of z is not accurate if, for example, x₁=0.5 and x₄=0.5. The restriction we need to impose is that at most two of the x_i can be nonzero, and the two nonzero x_i must be adjacent. This is known as a SOS-2 constraint, that is, a special order set of type 2 constraint.

The SOS-2 restriction can be modeled using binary variables y_i, $i=1,\ldots,4$:

$$\begin{array}{rcll} x_i & \leq & y_i & i = 1, \ldots ,4 \\ ... ... \\ y_1 + y_4 & \leq & 1 \\ y_2 + y_4 & \leq & 1. \end{array}$$

	John Mitchell
	mitchj@rpi.edu