Convergence of an annealing algorithm View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1986-01

AUTHORS

M. Lundy, A. Mees

ABSTRACT

The annealing algorithm is a stochastic optimization method which has attracted attention because of its success with certain difficult problems, including NP-hard combinatorial problems such as the travelling salesman, Steiner trees and others. There is an appealing physical analogy for its operation, but a more formal model seems desirable. In this paper we present such a model and prove that the algorithm converges with probability arbitrarily close to 1. We also show that there are cases where convergence takes exponentially long—that is, it is no better than a deterministic method. We study how the convergence rate is affected by the form of the problem. Finally we describe a version of the algorithm that terminates in polynomial time and allows a good deal of ‘practical’ confidence in the solution. More... »

PAGES

111-124

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf01582166

DOI

http://dx.doi.org/10.1007/bf01582166

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1049532067


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Cambridge", 
          "id": "https://www.grid.ac/institutes/grid.5335.0", 
          "name": [
            "Department of Pure Mathematics and Mathematical Statistics, Cambridge University, 16 Mill Lane, CB2 1SB, Cambridge, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lundy", 
        "givenName": "M.", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Western Australia", 
          "id": "https://www.grid.ac/institutes/grid.1012.2", 
          "name": [
            "Department of Mathematics, University of Western Australia, 6009, Nedlands, Western, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mees", 
        "givenName": "A.", 
        "id": "sg:person.013773230777.35", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013773230777.35"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0167-6377(83)90030-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024675242"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-6377(83)90030-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024675242"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/0-387-32792-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033278098", 
          "https://doi.org/10.1007/0-387-32792-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/0-387-32792-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033278098", 
          "https://doi.org/10.1007/0-387-32792-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1111/j.1469-1809.1973.tb00595.x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038500700"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1063/1.1699114", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1057769646"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/biomet/72.1.191", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059419484"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tpami.1984.4767596", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061742090"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1986-01", 
    "datePublishedReg": "1986-01-01", 
    "description": "The annealing algorithm is a stochastic optimization method which has attracted attention because of its success with certain difficult problems, including NP-hard combinatorial problems such as the travelling salesman, Steiner trees and others. There is an appealing physical analogy for its operation, but a more formal model seems desirable. In this paper we present such a model and prove that the algorithm converges with probability arbitrarily close to 1. We also show that there are cases where convergence takes exponentially long\u2014that is, it is no better than a deterministic method. We study how the convergence rate is affected by the form of the problem. Finally we describe a version of the algorithm that terminates in polynomial time and allows a good deal of \u2018practical\u2019 confidence in the solution.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf01582166", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047630", 
        "issn": [
          "0025-5610", 
          "1436-4646"
        ], 
        "name": "Mathematical Programming", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "34"
      }
    ], 
    "name": "Convergence of an annealing algorithm", 
    "pagination": "111-124", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "ebf554401955aae53bd673cdc5db87afdfed03a62a8577db0710f4206481710e"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01582166"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1049532067"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01582166", 
      "https://app.dimensions.ai/details/publication/pub.1049532067"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T00:20", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8695_00000534.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2FBF01582166"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf01582166'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf01582166'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01582166'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01582166'


 

This table displays all metadata directly associated to this object as RDF triples.

89 TRIPLES      21 PREDICATES      33 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01582166 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N64ed7a5567df40b484fbe239f6a6a096
4 schema:citation sg:pub.10.1007/0-387-32792-4
5 https://doi.org/10.1016/0167-6377(83)90030-5
6 https://doi.org/10.1063/1.1699114
7 https://doi.org/10.1093/biomet/72.1.191
8 https://doi.org/10.1109/tpami.1984.4767596
9 https://doi.org/10.1111/j.1469-1809.1973.tb00595.x
10 schema:datePublished 1986-01
11 schema:datePublishedReg 1986-01-01
12 schema:description The annealing algorithm is a stochastic optimization method which has attracted attention because of its success with certain difficult problems, including NP-hard combinatorial problems such as the travelling salesman, Steiner trees and others. There is an appealing physical analogy for its operation, but a more formal model seems desirable. In this paper we present such a model and prove that the algorithm converges with probability arbitrarily close to 1. We also show that there are cases where convergence takes exponentially long—that is, it is no better than a deterministic method. We study how the convergence rate is affected by the form of the problem. Finally we describe a version of the algorithm that terminates in polynomial time and allows a good deal of ‘practical’ confidence in the solution.
13 schema:genre research_article
14 schema:inLanguage en
15 schema:isAccessibleForFree false
16 schema:isPartOf N55c2604ac4bc4f7ba0f29663b6b2dbe0
17 N57e1d83f94a84228b6054a7a72768653
18 sg:journal.1047630
19 schema:name Convergence of an annealing algorithm
20 schema:pagination 111-124
21 schema:productId N5cd56d14b2074cc0aec2d76c3f0957c2
22 N88c3931b4ed44e49b5e9d0c792226f6e
23 Na546176b9b7f4d43a1ece98d9c3e25fd
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049532067
25 https://doi.org/10.1007/bf01582166
26 schema:sdDatePublished 2019-04-11T00:20
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher N1b6761a5fc094546a22fbb5714c5bf51
29 schema:url http://link.springer.com/10.1007%2FBF01582166
30 sgo:license sg:explorer/license/
31 sgo:sdDataset articles
32 rdf:type schema:ScholarlyArticle
33 N1b6761a5fc094546a22fbb5714c5bf51 schema:name Springer Nature - SN SciGraph project
34 rdf:type schema:Organization
35 N44b58d744d7a44ce8744a1e31e19c938 schema:affiliation https://www.grid.ac/institutes/grid.5335.0
36 schema:familyName Lundy
37 schema:givenName M.
38 rdf:type schema:Person
39 N55c2604ac4bc4f7ba0f29663b6b2dbe0 schema:volumeNumber 34
40 rdf:type schema:PublicationVolume
41 N57e1d83f94a84228b6054a7a72768653 schema:issueNumber 1
42 rdf:type schema:PublicationIssue
43 N5cd56d14b2074cc0aec2d76c3f0957c2 schema:name readcube_id
44 schema:value ebf554401955aae53bd673cdc5db87afdfed03a62a8577db0710f4206481710e
45 rdf:type schema:PropertyValue
46 N64ed7a5567df40b484fbe239f6a6a096 rdf:first N44b58d744d7a44ce8744a1e31e19c938
47 rdf:rest Nc4fdf15ece604911834ec8b98a5d397d
48 N88c3931b4ed44e49b5e9d0c792226f6e schema:name dimensions_id
49 schema:value pub.1049532067
50 rdf:type schema:PropertyValue
51 Na546176b9b7f4d43a1ece98d9c3e25fd schema:name doi
52 schema:value 10.1007/bf01582166
53 rdf:type schema:PropertyValue
54 Nc4fdf15ece604911834ec8b98a5d397d rdf:first sg:person.013773230777.35
55 rdf:rest rdf:nil
56 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
57 schema:name Information and Computing Sciences
58 rdf:type schema:DefinedTerm
59 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
60 schema:name Computation Theory and Mathematics
61 rdf:type schema:DefinedTerm
62 sg:journal.1047630 schema:issn 0025-5610
63 1436-4646
64 schema:name Mathematical Programming
65 rdf:type schema:Periodical
66 sg:person.013773230777.35 schema:affiliation https://www.grid.ac/institutes/grid.1012.2
67 schema:familyName Mees
68 schema:givenName A.
69 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013773230777.35
70 rdf:type schema:Person
71 sg:pub.10.1007/0-387-32792-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033278098
72 https://doi.org/10.1007/0-387-32792-4
73 rdf:type schema:CreativeWork
74 https://doi.org/10.1016/0167-6377(83)90030-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024675242
75 rdf:type schema:CreativeWork
76 https://doi.org/10.1063/1.1699114 schema:sameAs https://app.dimensions.ai/details/publication/pub.1057769646
77 rdf:type schema:CreativeWork
78 https://doi.org/10.1093/biomet/72.1.191 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059419484
79 rdf:type schema:CreativeWork
80 https://doi.org/10.1109/tpami.1984.4767596 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061742090
81 rdf:type schema:CreativeWork
82 https://doi.org/10.1111/j.1469-1809.1973.tb00595.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1038500700
83 rdf:type schema:CreativeWork
84 https://www.grid.ac/institutes/grid.1012.2 schema:alternateName University of Western Australia
85 schema:name Department of Mathematics, University of Western Australia, 6009, Nedlands, Western, Australia
86 rdf:type schema:Organization
87 https://www.grid.ac/institutes/grid.5335.0 schema:alternateName University of Cambridge
88 schema:name Department of Pure Mathematics and Mathematical Statistics, Cambridge University, 16 Mill Lane, CB2 1SB, Cambridge, UK
89 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...