Mathematical Programming Models for Mean Computation in Dynamic Time Warping Spaces

Vincent Froese, Christoph HansknechtarXiv 2019 · arXiv · OpenReview

Abstract

Computing the "average" of a set of time series is a fundamental task in data mining, yet it remains computationally daunting under the Dynamic Time Warping (DTW) distance. The DTW-Mean problem, which seeks a series minimizing the sum of squared DTW distances to a sample set, is NP-hard. Historically, researchers have relied on heuristics without performance guarantees. This paper presents the first exact mathematical programming framework for DTW-Mean. By formulating the problem as a Mixed-Integer Nonlinear Program (MINLP) and utilizing network flow techniques, the authors provide a method to find optimal solutions and provable lower bounds, marking a significant shift from heuristic-based approaches to exact optimization.

The Challenge of Averaging Warped Sequences

In time series analysis, standard Euclidean averaging often fails because sequences may represent the same underlying pattern but with local shifts or varying speeds. Dynamic Time Warping (DTW) addresses this by finding an optimal non-linear alignment between sequences.

DTW alignment between two time series $s$ and $s'$, illustrating the non-linear mapping of points.

However, finding a single "Fréchet Mean" series that minimizes the squared DTW distance to all others is a complex combinatorial problem. Until now, the field has largely depended on heuristics like DTW Barycenter Averaging (DBA). While effective in practice, these methods offer no theoretical guarantees on how close the result is to the true mathematical optimum.

Mathematical Programming Formulations

The authors propose several MINLP formulations to model the alignment and distance calculations precisely. A key contribution is the transition from vertex-based to arc-based modeling.

Vertex vs. Arc Formulations

  • DTW-V (Vertex-based): Uses binary variables to indicate if a specific point in the alignment grid is part of the optimal path.
  • DTW-A (Arc-based): Models the alignment as a network flow problem. Although it involves more variables, the authors demonstrate that this formulation is "tighter." Its mathematical relaxation is closer to the true integer solution, allowing modern solvers to prune the search space more efficiently.
An alignment path represented as a flow through a grid, a central concept in the arc-based MINLP formulation.

Optimization Techniques

To make the problem tractable, the authors introduced:

  1. Domain Bounding: A polynomial-time algorithm to calculate tight upper and lower bounds on the mean series' values, significantly reducing the search space.
  2. Distance Reformulations: They compared standard "Big-M" indicator constraints against Perspective Reformulations and Outer Approximations to handle the nonlinear squared distance terms.

Key Insights and Results

The research yielded several critical findings regarding the behavior of these optimization models:

  • The Superiority of Flow: The arc-based formulation consistently outperformed the vertex-based one. Its "tightness" allowed solvers like Gurobi to reach solutions much faster despite the increased variable count.
  • Global Constraints: Incorporating constraints like the Sakoe-Chiba band is essential. By limiting how far an alignment can stray from the diagonal, these constraints drastically reduce the number of variables and make previously intractable problems solvable.
  • Performance on Real-World Data: Testing on datasets from the UCR Time Series Classification Archive showed that for small instances (length $m=10$, $k=2$ series), the models reached a 0% optimality gap almost instantly. As complexity increased ($m=20, k=5$), the best models still maintained a respectable ~15% gap after one hour, providing a much clearer picture of solution quality than any heuristic.

Conclusion and Future Directions

While scalability remains a challenge for long sequences or large datasets, this work establishes a rigorous foundation for exact DTW-Mean computation. Future research will focus on developing new valid inequalities to further tighten lower bounds and integrating these exact models with relaxation-based heuristics to combine computational speed with provable quality.

Summary updated

Abstract

The dynamic time warping (dtw) distance is an established tool for mining time series data. The DTW-Mean problem consists of computing a series which minimizes the so-called Fr\'echet function, that is, the sum of squared dtw-distances to a given sample of time series. DTW-Mean is NP-hard and intractable in practice. So far, this challenging problem has been solved by various heuristic approaches without any performance guarantees. We give a polynomial-time algorithm yielding lower bounds on the domain of a mean time series which translate into lower bounds on the Fr\'echet function. We then formulate the problem as a discrete nonlinear optimization problem based on network flows. We introduce several mixed-integer nonlinear programming (MINLP) formulations in order to solve DTW-Mean optimally. Our formulations are based on techniques such as outer approximations and nonlinear reformulations of the well-known big M indicator constraints. Finally, we conduct several computational experiments to compare the different formulations on several instances derived from the UCR Time Series Classification Archive. While in general DTW-Mean remains quite challenging, our fomrulations yield good results in several important specialized probem settings.
BibTeX
@misc{froese2019mathematical,
  author = {Vincent Froese and Christoph Hansknecht},
  title = {{Mathematical Programming Models for Mean Computation in Dynamic Time Warping Spaces}},
  year = {2019},
  eprint = {1912.02300},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1912.02300},
}

Loading related content...

Figure