DOI: 10.1126/science.220.4598.671. Optimization by Simulated Annealing

10.1126/science.220.4598.671

Crossref journal-article

American Association for the Advancement of Science (AAAS)

Science (221)

Abstract

There is a deep and useful connection between statistical mechanics (the behavior of systems with many degrees of freedom in thermal equilibrium at a finite temperature) and multivariate or combinatorial optimization (finding the minimum of a given function depending on many parameters). A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems. This connection to statistical mechanics exposes new information and provides an unfamiliar perspective on traditional optimization problems and methods.

Bibliography

Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671â680.

Authors 3

S. Kirkpatrick (first)
C. D. Gelatt (additional)
M. P. Vecchi (additional)

References 32 Referenced 32,276

Aho A. V. The Design and Analysis of Computer Algorithms (1974).
BEARDWOOD, J, MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY 55: 299 (1959). (10.1017/S0305004100034095) / MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY (1959)
BLODGETT, A.J., THERMAL CONDUCTION MODULE - A HIGH-PERFORMANCE MULTILAYER CERAMIC PACKAGE, IBM JOURNAL OF RESEARCH AND DEVELOPMENT 26: 30 (1982). (10.1147/rd.261.0030) / IBM JOURNAL OF RESEARCH AND DEVELOPMENT (1982)
Blodgett, A., Proceedings of the Electronics and Computers Conference: 283 (1980). / Proceedings of the Electronics and Computers Conference (1980)
BREUER, M. A., JOURNAL OF DESIGN AUTOMATION & FAULT-TOLERANT COMPUTING 1: 343 (1977). / JOURNAL OF DESIGN AUTOMATION & FAULT-TOLERANT COMPUTING (1977)
Breuer M. A. Design Automation of Digital Systems (1972).
CASE, P.W., DESIGN AUTOMATION IN IBM, IBM JOURNAL OF RESEARCH AND DEVELOPMENT 25: 631 (1981). (10.1147/rd.255.0631) / IBM JOURNAL OF RESEARCH AND DEVELOPMENT (1981)
Castellani C. Disordered .Systems and Localization (1981). (10.1007/BFb0012537)
CERNY V unpublished data.
Chen, K. A., Proceedings of the 14th IEEE Design Automation Conference: 298 (1977). / Proceedings of the 14th IEEE Design Automation Conference (1977)
CROWDER, H, SOLVING LARGE-SCALE SYMMETRIC TRAVELING SALESMAN PROBLEMS TO OPTIMALITY, MANAGEMENT SCIENCE 26: 495 (1980). (10.1287/mnsc.26.5.495) / MANAGEMENT SCIENCE (1980)
Davis, C., Proceedings of the IEEE International Conference on Circuits and Computers: 669 (1980). / Proceedings of the IEEE International Conference on Circuits and Computers (1980)
DUNHAM, B, SYNTHESE 15: 254 (1963). (10.1007/BF00484855) / SYNTHESE (1963)
Garey M. R. Computers and Intractability: A Guide to the Theory of NP-Completeness (1979).
HANAN, M, JOURNAL OF DESIGN AUTOMATION & FAULT-TOLERANT COMPUTING 2: 145 (1978). / JOURNAL OF DESIGN AUTOMATION & FAULT-TOLERANT COMPUTING (1978)
Hightower, D., Proceedings of the 6th IEEE Design Automation Workshop: 1 (1969). / Proceedings of the 6th IEEE Design Automation Workshop (1969)
KARP, R.M., MATH OPER RES 2: 209 (1977). (10.1287/moor.2.3.209) / MATH OPER RES (1977)
KIRKPATRICK, S, FRUSTRATION AND GROUND-STATE DEGENERACY IN SPIN-GLASSES, PHYSICAL REVIEW B 16: 4630 (1977). (10.1103/PhysRevB.16.4630) / PHYSICAL REVIEW B (1977)
KIRKPATRICK, S, INFINITE-RANGED MODELS OF SPIN-GLASSES, PHYSICAL REVIEW B 17: 4384 (1978). (10.1103/PhysRevB.17.4384) / PHYSICAL REVIEW B (1978)
Lallier K. W. paper presented at the European Conference on Design Automation September (1981).
Lawlor E. L. Combinatorial Optimization (1976).
LIN, S, COMPUTER SOLUTIONS OF TRAVELING SALESMAN PROBLEM, BELL SYSTEM TECHNICAL JOURNAL 44: 2245 (1965). (10.1002/j.1538-7305.1965.tb04146.x) / BELL SYSTEM TECHNICAL JOURNAL (1965)
LIN, S, NETWORKS 5: 33 (1975). (10.1002/net.1975.5.1.33) / NETWORKS (1975)
LIN, S, EFFECTIVE HEURISTIC ALGORITHM FOR TRAVELING-SALESMAN PROBLEM, OPERATIONS RESEARCH 21: 498 (1973). (10.1287/opre.21.2.498) / OPERATIONS RESEARCH (1973)
Mandelbrot, B., Fractals: Form, Chance, and Dimension: 237 (1979). / Fractals: Form, Chance, and Dimension (1979)
METROPOLIS, N, EQUATION OF STATE CALCULATIONS BY FAST COMPUTING MACHINES, JOURNAL OF CHEMICAL PHYSICS 21: 1087 (1953). (10.1063/1.1699114) / JOURNAL OF CHEMICAL PHYSICS (1953)
RESENKRANTZ, D.J., SIAM JOURNAL ON COMPUTING 6: 563 (1977). (10.1137/0206041) / SIAM JOURNAL ON COMPUTING (1977)
SHERRINGTON, D, SOLVABLE MODEL OF A SPIN-GLASS, PHYSICAL REVIEW LETTERS 35: 1792 (1975). (10.1103/PhysRevLett.35.1792) / PHYSICAL REVIEW LETTERS (1975)
Shrodinger E. Statistical Thermodynamics (1946).
SOUKUP, J, CIRCUIT LAYOUT, PROCEEDINGS OF THE IEEE 69: 1281 (1981). (10.1109/PROC.1981.12167) / PROCEEDINGS OF THE IEEE (1981)
TOULOUSE, G, THEORY OF FRUSTRATION EFFECT IN SPIN-GLASSES .1., COMMUNICATIONS ON PHYSICS 2: 115 (1977). / COMMUNICATIONS ON PHYSICS (1977)
YOUNG, A.P., LOW-TEMPERATURE BEHAVIOR OF THE INFINITE-RANGE ISING SPIN-GLASS - EXACT STATISTICAL-MECHANICS FOR SMALL SAMPLES, PHYSICAL REVIEW B 25: 440 (1982). (10.1103/PhysRevB.25.440) / PHYSICAL REVIEW B (1982)

Dates

Type	When
Created	18 years, 10 months ago (Oct. 5, 2006, 2:37 p.m.)
Deposited	1 year, 7 months ago (Jan. 12, 2024, 3:45 a.m.)
Indexed	3 minutes ago (Aug. 30, 2025, 11:03 p.m.)
Issued	42 years, 3 months ago (May 13, 1983)
Published	42 years, 3 months ago (May 13, 1983)
Published Print	42 years, 3 months ago (May 13, 1983)

Funders 0

None

BibTeX

@article{Kirkpatrick_1983, title={Optimization by Simulated Annealing}, volume={220}, ISSN={1095-9203}, url={http://dx.doi.org/10.1126/science.220.4598.671}, DOI={10.1126/science.220.4598.671}, number={4598}, journal={Science}, publisher={American Association for the Advancement of Science (AAAS)}, author={Kirkpatrick, S. and Gelatt, C. D. and Vecchi, M. P.}, year={1983}, month=may, pages={671–680} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        8,
        31
      ]
    ],
    "date-time": "2025-08-31T03:03:53Z",
    "timestamp": 1756609433884
  },
  "reference-count": 32,
  "publisher": "American Association for the Advancement of Science (AAAS)",
  "issue": "4598",
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        1983,
        5,
        13
      ]
    ]
  },
  "abstract": "<jats:p>There is a deep and useful connection between statistical mechanics (the behavior of systems with many degrees of freedom in thermal equilibrium at a finite temperature) and multivariate or combinatorial optimization (finding the minimum of a given function depending on many parameters). A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems. This connection to statistical mechanics exposes new information and provides an unfamiliar perspective on traditional optimization problems and methods.</jats:p>",
  "DOI": "10.1126/science.220.4598.671",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2006,
        10,
        5
      ]
    ],
    "date-time": "2006-10-05T18:37:18Z",
    "timestamp": 1160073438000
  },
  "page": "671-680",
  "source": "Crossref",
  "is-referenced-by-count": 32276,
  "title": "Optimization by Simulated Annealing",
  "prefix": "10.1126",
  "volume": "220",
  "author": [
    {
      "given": "S.",
      "family": "Kirkpatrick",
      "sequence": "first",
      "affiliation": [
        {
          "name": "Research staff members at IBM Thomas J. Watson Research Center, Yorktown Heights, New York 10598"
        }
      ]
    },
    {
      "suffix": "Jr.",
      "given": "C. D.",
      "family": "Gelatt",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Research staff members at IBM Thomas J. Watson Research Center, Yorktown Heights, New York 10598"
        }
      ]
    },
    {
      "given": "M. P.",
      "family": "Vecchi",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Instituto Venezolano de Investigaciones Cientificas, Caracas 1010A, Venezuela"
        }
      ]
    }
  ],
  "member": "221",
  "reference": [
    {
      "key": "e_1_2_1_1_1",
      "unstructured": "Aho A. V. The Design and Analysis of Computer Algorithms (1974)."
    },
    {
      "key": "e_1_2_1_2_1",
      "doi-asserted-by": "crossref",
      "first-page": "299",
      "DOI": "10.1017/S0305004100034095",
      "volume": "55",
      "year": "1959",
      "unstructured": "BEARDWOOD, J, MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY 55: 299 (1959).",
      "journal-title": "MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY"
    },
    {
      "key": "e_1_2_1_3_1",
      "doi-asserted-by": "crossref",
      "first-page": "30",
      "DOI": "10.1147/rd.261.0030",
      "volume": "26",
      "year": "1982",
      "unstructured": "BLODGETT, A.J., THERMAL CONDUCTION MODULE - A HIGH-PERFORMANCE MULTILAYER CERAMIC PACKAGE, IBM JOURNAL OF RESEARCH AND DEVELOPMENT 26: 30 (1982).",
      "journal-title": "IBM JOURNAL OF RESEARCH AND DEVELOPMENT"
    },
    {
      "key": "e_1_2_1_4_1",
      "first-page": "283",
      "year": "1980",
      "unstructured": "Blodgett, A., Proceedings of the Electronics and Computers Conference: 283 (1980).",
      "journal-title": "Proceedings of the Electronics and Computers Conference"
    },
    {
      "key": "e_1_2_1_5_1",
      "first-page": "343",
      "volume": "1",
      "year": "1977",
      "unstructured": "BREUER, M. A., JOURNAL OF DESIGN AUTOMATION & FAULT-TOLERANT COMPUTING 1: 343 (1977).",
      "journal-title": "JOURNAL OF DESIGN AUTOMATION & FAULT-TOLERANT COMPUTING"
    },
    {
      "key": "e_1_2_1_6_1",
      "unstructured": "Breuer M. A. Design Automation of Digital Systems (1972)."
    },
    {
      "key": "e_1_2_1_7_1",
      "doi-asserted-by": "crossref",
      "first-page": "631",
      "DOI": "10.1147/rd.255.0631",
      "volume": "25",
      "year": "1981",
      "unstructured": "CASE, P.W., DESIGN AUTOMATION IN IBM, IBM JOURNAL OF RESEARCH AND DEVELOPMENT 25: 631 (1981).",
      "journal-title": "IBM JOURNAL OF RESEARCH AND DEVELOPMENT"
    },
    {
      "key": "e_1_2_1_8_1",
      "doi-asserted-by": "crossref",
      "unstructured": "Castellani C. Disordered .Systems and Localization (1981).",
      "DOI": "10.1007/BFb0012537"
    },
    {
      "key": "e_1_2_1_9_1",
      "unstructured": "CERNY V unpublished data."
    },
    {
      "key": "e_1_2_1_10_1",
      "first-page": "298",
      "year": "1977",
      "unstructured": "Chen, K. A., Proceedings of the 14th IEEE Design Automation Conference: 298 (1977).",
      "journal-title": "Proceedings of the 14th IEEE Design Automation Conference"
    },
    {
      "key": "e_1_2_1_11_1",
      "doi-asserted-by": "crossref",
      "first-page": "495",
      "DOI": "10.1287/mnsc.26.5.495",
      "volume": "26",
      "year": "1980",
      "unstructured": "CROWDER, H, SOLVING LARGE-SCALE SYMMETRIC TRAVELING SALESMAN PROBLEMS TO OPTIMALITY, MANAGEMENT SCIENCE 26: 495 (1980).",
      "journal-title": "MANAGEMENT SCIENCE"
    },
    {
      "key": "e_1_2_1_12_1",
      "first-page": "669",
      "year": "1980",
      "unstructured": "Davis, C., Proceedings of the IEEE International Conference on Circuits and Computers: 669 (1980).",
      "journal-title": "Proceedings of the IEEE International Conference on Circuits and Computers"
    },
    {
      "key": "e_1_2_1_13_1",
      "doi-asserted-by": "crossref",
      "first-page": "254",
      "DOI": "10.1007/BF00484855",
      "volume": "15",
      "year": "1963",
      "unstructured": "DUNHAM, B, SYNTHESE 15: 254 (1963).",
      "journal-title": "SYNTHESE"
    },
    {
      "key": "e_1_2_1_14_1",
      "unstructured": "Garey M. R. Computers and Intractability: A Guide to the Theory of NP-Completeness (1979)."
    },
    {
      "key": "e_1_2_1_15_1",
      "first-page": "145",
      "volume": "2",
      "year": "1978",
      "unstructured": "HANAN, M, JOURNAL OF DESIGN AUTOMATION & FAULT-TOLERANT COMPUTING 2: 145 (1978).",
      "journal-title": "JOURNAL OF DESIGN AUTOMATION & FAULT-TOLERANT COMPUTING"
    },
    {
      "key": "e_1_2_1_16_1",
      "first-page": "1",
      "year": "1969",
      "unstructured": "Hightower, D., Proceedings of the 6th IEEE Design Automation Workshop: 1 (1969).",
      "journal-title": "Proceedings of the 6th IEEE Design Automation Workshop"
    },
    {
      "key": "e_1_2_1_17_1",
      "doi-asserted-by": "crossref",
      "first-page": "209",
      "DOI": "10.1287/moor.2.3.209",
      "volume": "2",
      "year": "1977",
      "unstructured": "KARP, R.M., MATH OPER RES 2: 209 (1977).",
      "journal-title": "MATH OPER RES"
    },
    {
      "key": "e_1_2_1_18_1",
      "doi-asserted-by": "crossref",
      "first-page": "4630",
      "DOI": "10.1103/PhysRevB.16.4630",
      "volume": "16",
      "year": "1977",
      "unstructured": "KIRKPATRICK, S, FRUSTRATION AND GROUND-STATE DEGENERACY IN SPIN-GLASSES, PHYSICAL REVIEW B 16: 4630 (1977).",
      "journal-title": "PHYSICAL REVIEW B"
    },
    {
      "key": "e_1_2_1_19_1",
      "doi-asserted-by": "crossref",
      "first-page": "4384",
      "DOI": "10.1103/PhysRevB.17.4384",
      "volume": "17",
      "year": "1978",
      "unstructured": "KIRKPATRICK, S, INFINITE-RANGED MODELS OF SPIN-GLASSES, PHYSICAL REVIEW B 17: 4384 (1978).",
      "journal-title": "PHYSICAL REVIEW B"
    },
    {
      "key": "e_1_2_1_20_1",
      "unstructured": "Lallier K. W. paper presented at the European Conference on Design Automation September (1981)."
    },
    {
      "key": "e_1_2_1_21_1",
      "unstructured": "Lawlor E. L. Combinatorial Optimization (1976)."
    },
    {
      "key": "e_1_2_1_22_1",
      "doi-asserted-by": "crossref",
      "first-page": "2245",
      "DOI": "10.1002/j.1538-7305.1965.tb04146.x",
      "volume": "44",
      "year": "1965",
      "unstructured": "LIN, S, COMPUTER SOLUTIONS OF TRAVELING SALESMAN PROBLEM, BELL SYSTEM TECHNICAL JOURNAL 44: 2245 (1965).",
      "journal-title": "BELL SYSTEM TECHNICAL JOURNAL"
    },
    {
      "key": "e_1_2_1_23_1",
      "doi-asserted-by": "crossref",
      "first-page": "33",
      "DOI": "10.1002/net.1975.5.1.33",
      "volume": "5",
      "year": "1975",
      "unstructured": "LIN, S, NETWORKS 5: 33 (1975).",
      "journal-title": "NETWORKS"
    },
    {
      "key": "e_1_2_1_24_1",
      "doi-asserted-by": "crossref",
      "first-page": "498",
      "DOI": "10.1287/opre.21.2.498",
      "volume": "21",
      "year": "1973",
      "unstructured": "LIN, S, EFFECTIVE HEURISTIC ALGORITHM FOR TRAVELING-SALESMAN PROBLEM, OPERATIONS RESEARCH 21: 498 (1973).",
      "journal-title": "OPERATIONS RESEARCH"
    },
    {
      "key": "e_1_2_1_25_1",
      "first-page": "237",
      "year": "1979",
      "unstructured": "Mandelbrot, B., Fractals: Form, Chance, and Dimension: 237 (1979).",
      "journal-title": "Fractals: Form, Chance, and Dimension"
    },
    {
      "key": "e_1_2_1_26_1",
      "doi-asserted-by": "crossref",
      "first-page": "1087",
      "DOI": "10.1063/1.1699114",
      "volume": "21",
      "year": "1953",
      "unstructured": "METROPOLIS, N, EQUATION OF STATE CALCULATIONS BY FAST COMPUTING MACHINES, JOURNAL OF CHEMICAL PHYSICS 21: 1087 (1953).",
      "journal-title": "JOURNAL OF CHEMICAL PHYSICS"
    },
    {
      "key": "e_1_2_1_27_1",
      "doi-asserted-by": "crossref",
      "first-page": "563",
      "DOI": "10.1137/0206041",
      "volume": "6",
      "year": "1977",
      "unstructured": "RESENKRANTZ, D.J., SIAM JOURNAL ON COMPUTING 6: 563 (1977).",
      "journal-title": "SIAM JOURNAL ON COMPUTING"
    },
    {
      "key": "e_1_2_1_28_1",
      "doi-asserted-by": "crossref",
      "first-page": "1792",
      "DOI": "10.1103/PhysRevLett.35.1792",
      "volume": "35",
      "year": "1975",
      "unstructured": "SHERRINGTON, D, SOLVABLE MODEL OF A SPIN-GLASS, PHYSICAL REVIEW LETTERS 35: 1792 (1975).",
      "journal-title": "PHYSICAL REVIEW LETTERS"
    },
    {
      "key": "e_1_2_1_29_1",
      "unstructured": "Shrodinger E. Statistical Thermodynamics (1946)."
    },
    {
      "key": "e_1_2_1_30_1",
      "doi-asserted-by": "crossref",
      "first-page": "1281",
      "DOI": "10.1109/PROC.1981.12167",
      "volume": "69",
      "year": "1981",
      "unstructured": "SOUKUP, J, CIRCUIT LAYOUT, PROCEEDINGS OF THE IEEE 69: 1281 (1981).",
      "journal-title": "PROCEEDINGS OF THE IEEE"
    },
    {
      "key": "e_1_2_1_31_1",
      "first-page": "115",
      "volume": "2",
      "year": "1977",
      "unstructured": "TOULOUSE, G, THEORY OF FRUSTRATION EFFECT IN SPIN-GLASSES .1., COMMUNICATIONS ON PHYSICS 2: 115 (1977).",
      "journal-title": "COMMUNICATIONS ON PHYSICS"
    },
    {
      "key": "e_1_2_1_32_1",
      "doi-asserted-by": "crossref",
      "first-page": "440",
      "DOI": "10.1103/PhysRevB.25.440",
      "volume": "25",
      "year": "1982",
      "unstructured": "YOUNG, A.P., LOW-TEMPERATURE BEHAVIOR OF THE INFINITE-RANGE ISING SPIN-GLASS - EXACT STATISTICAL-MECHANICS FOR SMALL SAMPLES, PHYSICAL REVIEW B 25: 440 (1982).",
      "journal-title": "PHYSICAL REVIEW B"
    }
  ],
  "container-title": "Science",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://www.science.org/doi/pdf/10.1126/science.220.4598.671",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2024,
        1,
        12
      ]
    ],
    "date-time": "2024-01-12T08:45:43Z",
    "timestamp": 1705049143000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://www.science.org/doi/10.1126/science.220.4598.671"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1983,
        5,
        13
      ]
    ]
  },
  "references-count": 32,
  "journal-issue": {
    "issue": "4598",
    "published-print": {
      "date-parts": [
        [
          1983,
          5,
          13
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1126/science.220.4598.671"
  ],
  "URL": "http://dx.doi.org/10.1126/science.220.4598.671",
  "relation": {},
  "ISSN": [
    "0036-8075",
    "1095-9203"
  ],
  "subject": [],
  "container-title-short": "Science",
  "published": {
    "date-parts": [
      [
        1983,
        5,
        13
      ]
    ]
  }
}