  We propose the Wishart planted ensemble, a class of zero-field Ising models
with tunable algorithmic hardness and specifiable (or planted) ground state.
The problem class arises from a simple procedure for generating a family of
random integer programming problems with specific statistical symmetry
properties, but turns out to have intimate connections to a sign-inverted
variant of the Hopfield model. The Hamiltonian contains only 2-spin
interactions, with the coupler matrix following a type of Wishart distribution.
The class exhibits a classical first-order phase transition in temperature. For
some parameter settings the model has a locally-stable paramagnetic state, a
feature which correlates strongly with difficulty in finding the ground state
and suggests an extremely rugged energy landscape. We analytically probe the
ensemble thermodynamic properties by deriving the Thouless-Anderson-Palmer
equations and free energy and corroborate the results with a replica and
annealed approximation analysis; extensive Monte Carlo simulations confirm our
predictions of the first-order transition temperature. The class exhibits a
wide variation in algorithmic hardness as a generation parameter is varied,
with a pronounced easy-hard-easy profile and peak in solution time towering
many orders of magnitude over that of the easy regimes. By deriving the
ensemble-averaged energy distribution and taking into account finite-precision
representation, we propose an analytical expression for the location of the
hardness peak and show that at fixed precision, the number of constraints in
the integer program must increase with system size to yield truly hard
problems. The Wishart planted ensemble is interesting for its peculiar physical
properties and provides a useful and analytically-transparent set of problems
for benchmarking optimization algorithms.
