Piecewise linear programming via interior points

The main aim of this work is to provide some basis for the development of interior point algorithms to minimize piecewise linear objective functions. Specifically, we study a piecewise linear separable and convex objective function, subject to linear constraints. The available methods in the literature for this class of problem are of the Simplex type, except for specific cases, such as linear fitting in the sense of L1-norm. A common practice for the resolution of piecewise linear programs consists of transforming them into equivalent linear programs and exploring their structure. This strategy is suitable for simplex-type methods, but inadequate for interior point methods. We show how to extend known interior point methods devised for linear programming to piecewise linear programming without resorting to equivalent linear programs. We also show that the generated interior points for the original piecewise linear program are not interior points for the equivalent linear program. Finally, some computational experiments are presented.