  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.
