Hysteresis in Combinatorial Optimization Problems


  • Yuling Guan University of Southern California
  • Ang Li University of Southern California
  • Sven Koenig University of Southern California
  • Stephan Haas University of Southern California
  • T. K. Satish Kumar University of Southern California




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.




How to Cite

Guan, Y., Li, A., Koenig, S., Haas, S., & Kumar, T. K. S. (2021). Hysteresis in Combinatorial Optimization Problems. The International FLAIRS Conference Proceedings, 34. https://doi.org/10.32473/flairs.v34i1.128493



Main Track Proceedings