Valid inequalities for concave piecewise linear regression

We consider the problem of fitting a concave piecewise linear function to multivariate data using the Least Absolute Deviation objective. We propose new valid inequalities for the problem using the properties of concave functions. Results with univariate data show that the proposed valid inequalities improve the root relaxation lower bound, permitting significant improvements in solution time.