Solving Piecewise-Linear Programs: Experiments with a Simplex Approach

We report tests of CPLP, a piecewise-linear simplex implementation based on the XMP subroutine library. Using test problems of various shapes and origins, we judge CPLP against a comparable linear bounded-variable simplex code that is applied to equivalent linear programs. Our evidence indicates that CPLP is typically 2 to 3 times faster in solving the test problems that are most significantly piecewise-linear; previously predicted advantages of the piecewise-linear simplex approach are observed to occur, though with different combinations of advantages being relevant in different cases. The savings achieved by CPLP appear likely to extend, moreover, to the costs involved in formulating, generating and analyzing piecewise-linear programs.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.