Spin Glass and Pseudo-Boolean Optimization

  • I. G. Rosenberg
Conference paper
Part of the NATO ASI Series book series (volume 20)


The minimization of pseudo-boolean functions started in the early sixties and since then has been studied as a discrete optimization problem in operations research, mathematical programming and combinatorics. The author was quite surprised to learn that more recently the problem emerged as the spin glass problem in statistical mechanics. The probabilistic approach developed there has been applied to various combinatorial problems and even to biology or cellular automata.


Cellular Automaton Steep Descent Discrete Optimization Problem Early Sixty Quadratic Case 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. [1]
    Garey, M.R., Johnson, D.S., Computers and intractability, A guide to the theory of NP-completeness, W.H. Freeman and Co. 1979.zbMATHGoogle Scholar
  2. [2]
    Hammer, P.L., Rudeanu S., Boolean Methods in Operations Research and Related Areas, Springer Verlag 1968, French translation, Dunod 1969.Google Scholar
  3. [3]
    Hammer, P.L., Rosenberg, I.G., Equivalent forms of zero-one programs. In Applications of number theory to numerical analysis, Academic Press 1972 pp. 453–463.Google Scholar
  4. [4]
    Rosenberg, I.G., Reduction of bivalent maximisation to the quadratic case, Cahiers Centre Etudes Rech. Oper. 17 (1975) 71–74.zbMATHGoogle Scholar
  5. [5]
    Rosenberg, I.G., 0–1 optimization and non-linear programming, R.A.I.R.O. 6 V-2 (1972) 95–97.Google Scholar
  6. [6]
    Rosenberg, I.G., 0–1 optimization and non-linear programming. Talk presented at TIMS/ORSA Meeting Miami.Fla,Nov.3–5 1976, # FP 21.1 p 266Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1986

Authors and Affiliations

  • I. G. Rosenberg
    • 1
  1. 1.Mathematics and StatisticsUniversite de MontrealMontrealCanada

Personalised recommendations