Optimal Partitioning Changepoint Analysis

Detecting changepoints in time series is a fundamental task in statistical modeling and data-driven decision-making. We introduce a novel set partitioning-based model for changepoint detection that leverages combinatorial optimization to identify an optimal set of segments explaining the observed data. Unlike conventional dynamic programming approaches, which rely on restrictive structural assumptions on the cost function to ensure tractability, our formulation is based on Integer Linear Programming. While the standard additivity assumption on segment-wise costs is retained, the proposed framework departs from existing methods in its ability to incorporate both local and global structural constraints directly within the optimization model. In particular, it supports a broad class of constraints, ranging from simple segment-level restrictions to complex global conditions coupling multiple segments, without requiring modifications to the underlying solution scheme. This enhanced modeling capability constitutes the main contribution of the work, significantly increasing the expressiveness of the framework while preserving the tractability of additive cost structures. The model’s design enables high adaptability to different application domains, including finance, bioinformatics, and industrial monitoring. The efficiency of modern MILP solvers, combined with tailored dominance rules, enables the solution of instances with several hundreds of observations in practical time. Computational results indicate that the approach extends tractability beyond previously studied settings, effectively handling classes of instances whose structural constraints could not be accommodated by existing methods, while retaining robustness and interpretability.