  We prove that primal-dual log-barrier interior point methods are not strongly
polynomial, by constructing a family of linear programs with $3r+1$
inequalities in dimension $2r$ for which the number of iterations performed is
in $\Omega(2^r)$. The total curvature of the central path of these linear
programs is also exponential in $r$, disproving a continuous analogue of the
Hirsch conjecture proposed by Deza, Terlaky and Zinchenko. Our method is to
tropicalize the central path in linear programming. The tropical central path
is the piecewise-linear limit of the central paths of parameterized families of
classical linear programs viewed through logarithmic glasses. This allows us to
provide combinatorial lower bounds for the number of iterations and the total
curvature, in a general setting.

Optimization and Control;Combinatorics