  The theory of $n$-fold integer programming has been recently emerging as an
important tool in parameterized complexity. The input to an $n$-fold integer
program (IP) consists of parameter $A$, dimension $n$, and numerical data of
binary encoding length $L$. It was known for some time that such programs can
be solved in polynomial time using $O(n^{g(A)}L)$ arithmetic operations where
$g$ is an exponential function of the parameter. In 2013 it was shown that it
can be solved in fixed-parameter tractable (FPT) time using $O(f(A)n^3L)$
arithmetic operations for a single-exponential function $f$. This, and a faster
algorithm for a special case of combinatorial $n$-fold IP, have led to several
very recent breakthroughs in the parameterized complexity of scheduling,
stringology, and computational social choice. In 2015 it was shown that it can
be solved in strongly polynomial time using $O(n^{g(A)})$ arithmetic
operations.
  Here we establish a result which subsumes all three of the above results by
showing that $n$-fold IP can be solved in strongly polynomial FPT time using
$O(f(A)n^3)$ arithmetic operations. In fact, our results are much more general,
briefly outlined as follows.
  - There is a strongly polynomial algorithm for ILP whenever a so-called
Graver-best oracle is realizable for it.
  - Graver-best oracles for the large classes of multi-stage stochastic and
tree-fold ILPs can be realized in FPT time. Together with the previous oracle
algorithm, this newly shows two large classes of ILP to be strongly polynomial;
in contrast, only few classes of ILP were previously known to be strongly
polynomial.
  - We show that ILP is FPT parameterized by the largest coefficient
$\|A\|_\infty$ and the primal or dual treedepth of $A$, and that this
parameterization cannot be relaxed, signifying substantial progress in
understanding the parameterized complexity of ILP.
