Hysteresis in Combinatorial Optimization Problems

Resumo

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.