  Maximal lattice free bodies are maximal polytopes without interior integral
points. Scarf initiated the study of maximal lattice free bodies relative to
the facet normals in a fixed matrix. In this paper we give an efficient
algorithm for computing the maximal lattice free bodies of an integral matrix
A. An important ingredient is a test set for a certain integer program
associated with A. This test set may be computed using algebraic methods. As an
application we generalize the Scarf-Shallcross algorithm for the
three-dimensional Frobenius problem to arbitrary dimension. In this context our
method is inspired by the novel algorithm by Einstein, Lichtblau, Strzebonski
and Wagon and the Groebner basis approach by Roune.
