Under some conditions, a piecewise linear problem may be equivalent to a linear program (rather than a MIP). In such a case, no branching is necessary. Whether a problem represented by a piecewise linear function made up of segments can be modeled as a linear program (and thus it can be solved straightforwardly without branching) depends on the slope of these segments.

A piecewise linear function is convex if the succession of the slopes of its segments is increasing. In contrast, a piecewise linear function is concave if the succession of slopes is decreasing.

Consider a minimization problem having linear constraints of the form

a1x1+...+anxn <= a0 and

a1x1+...+anxn = a0 where xi is a variable or a piecewise linear function.

Sufficient conditions for this problem to be a linear program are these:

With this background about piecewise linear functions and their representation in Concert Technology, consider a transportation example exploiting piecewise linearity.