Mixed Integer Programming for Change-point Detection

We propose a new mixed-integer programming formulation for fitting continuous piecewise linear functions. A key family of variables in this formulation is what we call as the segment assignment variables. These are indicator variables specifying which segment each data point belongs to. We prove that the projection of the linear programming relaxation of our formulation onto the segment assignment variables is integral. We compare our formulations against the most computationally efficient benchmarks in literature, both theoretically and through computational experiments on publicly available datasets. We observe that our approach achieves a significant speedup in terms of runtime relative to these benchmark formulations on larger datasets, and comparable performance on smaller ones.