Nonconvex, lower semicontinuous piecewise linear optimization

A branch-and-cut algorithm for solving linear problems with continuous separable piecewise linear cost functions was developed in 2005 by Keha et al. This algorithm is based on valid inequalities for an SOS2 based formulation of the problem. In this paper we study the extension of the algorithm to the case where the cost function is only lower semicontinuous. We extend the SOS2 based formulation to the lower semicontinuous case and show how the inequalities introduced by Keha et al. can also be used for this new formulation. We also introduce a simple generalization of one of the inequalities introduced by Keha et al.