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 N23103476ceaa4a45973a851400a035df
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 Naf3fbaf198db47f59f28b524ab8a1ef1
17 Ne6bc2ca1ba534b708e8b22281a694f0d
18 sg:journal.1047630
19 schema:name Convergence of an annealing algorithm
20 schema:pagination 111-124
21 schema:productId N191e0734f8bb46ddb84b418f8434a5db
22 N3173574f919543d593c6426aec6af951
23 N8f752bc00b91489dbe8d730c42fd74a2
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 N7f0df069adcc456cb9756bdfe8ac13c4
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 N191e0734f8bb46ddb84b418f8434a5db schema:name doi
34 schema:value 10.1007/bf01582166
35 rdf:type schema:PropertyValue
36 N23103476ceaa4a45973a851400a035df rdf:first Ncbd49ead8b5a4c4095967faa5450b965
37 rdf:rest N99e37bedac9842d2a9e6aac54d237ee8
38 N3173574f919543d593c6426aec6af951 schema:name dimensions_id
39 schema:value pub.1049532067
40 rdf:type schema:PropertyValue
41 N7f0df069adcc456cb9756bdfe8ac13c4 schema:name Springer Nature - SN SciGraph project
42 rdf:type schema:Organization
43 N8f752bc00b91489dbe8d730c42fd74a2 schema:name readcube_id
44 schema:value ebf554401955aae53bd673cdc5db87afdfed03a62a8577db0710f4206481710e
45 rdf:type schema:PropertyValue
46 N99e37bedac9842d2a9e6aac54d237ee8 rdf:first sg:person.013773230777.35
47 rdf:rest rdf:nil
48 Naf3fbaf198db47f59f28b524ab8a1ef1 schema:volumeNumber 34
49 rdf:type schema:PublicationVolume
50 Ncbd49ead8b5a4c4095967faa5450b965 schema:affiliation https://www.grid.ac/institutes/grid.5335.0
51 schema:familyName Lundy
52 schema:givenName M.
53 rdf:type schema:Person
54 Ne6bc2ca1ba534b708e8b22281a694f0d schema:issueNumber 1
55 rdf:type schema:PublicationIssue
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)


...