Open AccessHysteresis in Combinatorial Optimization Problems
Author(s) -
Yuling Guan,
Ang Li,
Sven Koenig,
Stephan Haas,
T. K. Satish Kumar
Publication year - 2021
Publication title -
proceedings of the ... international florida artificial intelligence research society conference
Language(s) - English
Resource type - Journals
eISSN - 2334-0762
pISSN - 2334-0754
DOI - 10.32473/flairs.v34i1.128493
Subject(s) - ising model , hysteresis , statistical physics , statistical mechanics , spins , observable , ferromagnetism , monte carlo method , magnetic hysteresis , spin (aerodynamics) , relaxation (psychology) , physics , perspective (graphical) , computer science , mathematics , magnetic field , condensed matter physics , magnetization , quantum mechanics , thermodynamics , artificial intelligence , psychology , social psychology , statistics
Hysteresis is a physical phenomenon reflected in macroscopic observables of materials that are subjected to external perturbations. For example, magnetic hysteresis is observed in ferromagnetic metals such as iron, nickel and cobalt in the presence of a changing external magnetic field. In this paper, we model hysteresis using combinatorial models of microscopic spin interactions, for which we invoke the top K solution framework for Ising models and their generalizations, called Weighted Constraint Satisfaction Problems (WCSPs). We show that the WCSP model with a simple "memory effect" can be used to understand hysteresis combinatorially and from the perspective of statistical mechanics. Compared to the basic Ising model, the WCSP framework allows accurate simulations of long-range and k-body interactions between the spins; and compared to other simulation frameworks, such as Monte Carlo methods, our WCSP framework has the advantage of using a principled statistical mechanics perspective. Our WCSP framework also allows us to understand hysteresis more generally in combinatorial optimization problems, with or without a connection to physically occurring phenomena.