Optimal Partitioning Changepoint Analysis

Introduction. Detecting changepoints in time series is a fundamental task in statistical modeling and data-driven decision making. Classical dynamic programming (DP) approaches, such as Optimal Partitioning and PELT, guarantee global optimality under additive cost structures, but their effectiveness fundamentally relies on the separability of segment-wise costs. This constraint limits their ability to enforce global structural properties of coupling multiple segments, such as bounds on the number of changepoints within specific windows, monotonicity of segment parameters or direction-change constraints. We introduce SP-CPD (Set-Partitioning Changepoint Detection), a novel Mixed-Integer Linear Programming (MILP) framework that overcomes these limitations.

Methods. The changepoint detection problem was reformulated as a Time Series Set Partitioning Problem (TSSP), in which all feasible segments were pre-enumerated as binary decision variables and the optimal segmentation was obtained by selecting a minimum-cost subset that exactly covers the time index set. A relaxed Set Covering variant (TSSC) was also considered for improved scalability, with postprocessing to resolve overlapping segments. The framework supports any additive segment cost function, including AIC and the proposed Quartic-root RMSE (QRMSE), and incorporates global structural constraints via linear inequalities and a cutting-plane strategy.

Results. Computational experiments on time series from the M3, M4 and M6 forecasting competitions demonstrate that SP-CPD produces globally optimal segmentations on instances with up to several hundred observations within practical runtimes. The TSSC heuristic achieves an average optimality gap below 1% relative to TSSP while reducing solution time by approximately 40%. Compared to DP baselines (PELT, Dynp) and Wild Binary Segmentation, SP-CPD is competitive in runtime for moderate-length series and strictly superior in its ability to handle global constraints.

Conclusions. SP-CPD offers a flexible and extensible optimization framework for changepoint detection, enabling the direct incorporation of global structural constraints that are beyond the practical reach of DP-based methods, with no modifications to the underlying solution scheme.