  Lattice models, also known as generalized Ising models or cluster expansions,
are widely used in many areas of science and are routinely applied to alloy
thermodynamics, solid-solid phase transitions, magnetic and thermal properties
of solids, and fluid mechanics, among others. However, the problem of finding
the true global ground state of a lattice model, which is essential for all of
the aforementioned applications, has remained unresolved, with only a limited
number of results for highly simplified systems known. In this article, we
present the first general algorithm to find the exact ground states of complex
lattice models and to prove their global optimality, resolving this fundamental
problem in condensed matter and materials theory. We transform the
infinite-discrete-optimization problem into a pair of combinatorial
optimization (MAX-SAT) and non-smooth convex optimization (MAX-MIN) problems,
which provide upper and lower bounds on the ground state energy respectively.
By systematically converging these bounds to each other, we find and prove the
exact ground state of realistic Hamiltonians whose solutions are completely
intractable via traditional methods. Considering that currently such
Hamiltonians are solved using simulated annealing and genetic algorithms that
are often unable to find the true global energy minimum, and never able to
prove the optimality of their result, our work opens the door to resolving
long-standing uncertainties in lattice models of physical phenomena.
