Publications
A complete and up-to-date list of my publications is available on Google Scholar .
Mixed Integer Programming for Change-point Detection
February, 2026
Apoorva Narula, Santanu S. Dey, and Yao Xie.
Abstract: We present a new mixed-integer programming (MIP) approach for offline multiple change-point detection by casting the problem as a globally optimal piecewise linear (PWL) fitting problem. Our main contribution is a family of strengthened MIP formulations whose linear programming (LP) relaxations admit integral projections onto the segment assignment variables, which encode the segment membership of each data point. This property yields provably tighter relaxations than existing formulations for offline multiple change-point detection. We further extend the framework to multidimensional PWL models with shared change-points. Extensive computational experiments on benchmark real-world datasets demonstrate that the proposed formulations achieve reductions in solution times under both L-1 and L-2 loss functions in comparison to the state-of-the-art.
