Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 2020 | Published + Submitted
Journal Article Open

Wishart planted ensemble: A tunably rugged pairwise Ising model with a first-order phase transition

Abstract

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.

Additional Information

© 2020 American Physical Society. Received 1 June 2019; revised manuscript received 26 February 2020; accepted 31 March 2020; published 4 May 2020. We acknowledge useful discussions with Bill Macready, Federico Ricci-Tersenghi, Hidetoshi Nishimori, Jon Machta, Cris Moore, Koji Hukushima, Brad Lackey, Lenka Zdeborová, Salvatore Mandrà, Mohammad Amin, Andrew King, Cathy McGeogh, and Aidan Roy. H.G.K. thanks the Department of Poultry Science at Texas A&M University for providing support. H.G.K. and C.P. are supported in part by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA), via MIT Lincoln Laboratory Air Force Contract No. FA8721-05-C-0002. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of ODNI, IARPA, or the US Government. The US Government is authorized to reproduce and distribute reprints for Governmental purpose notwithstanding any copyright annotation thereon.

Attached Files

Published - PhysRevE.101.052102.pdf

Submitted - 1906.00275.pdf

Files

1906.00275.pdf
Files (4.9 MB)
Name Size Download all
md5:076e76d89d91d1ef041f4e0a3b3e2091
2.5 MB Preview Download
md5:1c279a94478c95f69223656ead6b0a8a
2.4 MB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 20, 2023