Real-Time Solution of Quadratic Optimization Problems with Banded Matrices and Indicator Variables

We consider mixed-integer quadratic optimization problems with banded matrices and indicator variables. These problems arise pervasively in statistical inference problems with time-series data, where the banded matrix captures the temporal relationship of the underlying process. In particular, the problem studied arises in monitoring problems, where the decision-maker wants to detect changes or anomalies. We propose to solve these problems using decision diagrams. In particular we show how to exploit the temporal dependencies to construct exact and approximate decision diagrams. For problems over matrices with bandwidth equal to one, the proposed method runs in polynomial time. Moreover, if the bandwidth and condition number of the matrix is fixed, then we show that the proposed method can be modified to run into an additive approximation scheme. We also describe how to construct the convex hull of the set under study from the decision diagrams, and how to deploy the method online to solve the problems via a shortest path algorithm. Computational experiments show that, for problems with bandwidths less or equal than three, our proposed algorithm compares favorably to a state-of-the-art off-the-shelf solver in the offline setting, and that we are able to solve problems in milliseconds for the online setting.