Piecewise-linear functions

Piecewise-linear functions are important in many applications. They are often specified by giving a set of slopes, a set of breakpoints at which the slopes change, and the value of the functions at a given point. Consider, for instance, a transportation problem in which the transportation cost between two locations o and d depends on the size of the shipment ship[o][d]. The piecewise-linear expression

piecewise{10 -> 100;20 -> 200;40}(0,0) ship[o][d]; 

describes the piecewise-linear function of ship[o,d] depicted in Figure 1 The function has slopes 10, 20, and 40, breakpoints 100 and 200, and evaluates to 0 at point 0.

In other words, the piecewise-linear expression is equivalent to the expression:

10 * ship[o][d] 

when

ship[o,d] <= 100

equivalent to

(10 * 100) + 20 * (ship[o][d] - 100) 

when

100 <= ship[o][d] <= 200 

and equivalent to

(10 * 100) + (20 * 200) + 40 * (ship[o][d] - 200) 

otherwise.

By default, OPL assumes that a piecewise-linear function evaluates to zero at the origin, so that the last piecewise-linear function could actually be written as

piecewise{10 -> 100;20 -> 200;40} ship[o][d]; 

The last piecewise-linear function has a fixed number of pieces, but OPL also allows generic pieces. The number of pieces may then depend on the input data, as in

piecewise(i in 1..n) { 
   slope[i] -> breakpoint[i]; 
   slope[n+1]; 
} ship[o][d]; 

If breakpoint[1] ≥ 0 this piecewise-linear function is equivalent to

slope[1] * ship[o][d]

when

ship[o][d] <= breakpoint[1]

It is equivalent to

when

breakpoint[k-1] < ship[o][d] <= breakpoint [k] (1 < k <= n)

and equivalent to

otherwise.

Note that there may be several generic pieces in piecewise-linear functions. It is important to stress that breakpoints and slopes in piecewise-linear functions must always be grounded by a point on the piecewise-linear function. Such a point (called an anchor point) uniquely defines the function. Also, the breakpoints must be strictly increasing.

To sort your model data for this purpose, use sorted sets, as explained in Sorted and ordered sets.

Section Piecewise linear programming in the Language User’s Manual discusses piecewise-linear functions applied to an inventory problem.