Integrating Interval Estimates of Global Optima and Local Search Methods for Combinatorial Optimization Problems View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2000-09

AUTHORS

Irfan M. Ovacik, Srikanth Rajagopalan, Reha Uzsoy

ABSTRACT

The problem of estimating the global optimal values of intractable combinatorial optimization problems is of interest to researchers developing and evaluating heuristics for these problems. In this paper we present a method for combining statistical optimum prediction techniques with local search methods such as simulated annealing and tabu search and illustrate the approach on a single machine scheduling problem. Computational experiments show that the approach yields useful estimates of optimal values with very reasonable computational effort. More... »

PAGES

481-500

References to SciGraph publications

  • 1986-01. Convergence of an annealing algorithm in MATHEMATICAL PROGRAMMING
  • 1989-12. A controlled search simulated annealing method for the single machine weighted tardiness problem in ANNALS OF OPERATIONS RESEARCH
  • 1982-12. A stochastic method for global optimization in MATHEMATICAL PROGRAMMING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1023/a:1009669326107

    DOI

    http://dx.doi.org/10.1023/a:1009669326107

    DIMENSIONS

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


    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/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "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": {
              "name": [
                "i2 Technologies, 909 East Las Colinas Blud., 75039, Irving, TX, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ovacik", 
            "givenName": "Irfan M.", 
            "id": "sg:person.07636244107.17", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07636244107.17"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "i2 Technologies, 909 East Las Colinas Blud., 75039, Irving, TX, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Rajagopalan", 
            "givenName": "Srikanth", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Purdue University", 
              "id": "https://www.grid.ac/institutes/grid.169077.e", 
              "name": [
                "School of Industrial Engineering, Purdue University, 1287 Grissom Hall, 47907-1287, West Lafayette, IN, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Uzsoy", 
            "givenName": "Reha", 
            "id": "sg:person.01266067704.79", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01266067704.79"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1002/1520-6750(199204)39:3<369::aid-nav3220390307>3.0.co;2-f", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002793945"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02022094", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003666985", 
              "https://doi.org/10.1007/bf02022094"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02022094", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003666985", 
              "https://doi.org/10.1007/bf02022094"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/00949657908810302", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006466564"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/nav.3800260108", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044068101"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0191-2615(82)90030-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046029370"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01581033", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048958536", 
              "https://doi.org/10.1007/bf01581033"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01581033", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048958536", 
              "https://doi.org/10.1007/bf01581033"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01582166", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049532067", 
              "https://doi.org/10.1007/bf01582166"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0305004100015681", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053808967"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/ijoc.1.3.190", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064706391"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/ijoc.2.1.4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064707137"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/opre.33.5.1024", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064729651"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/opre.40.1.113", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064730378"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2000-09", 
        "datePublishedReg": "2000-09-01", 
        "description": "The problem of estimating the global optimal values of intractable combinatorial optimization problems is of interest to researchers developing and evaluating heuristics for these problems. In this paper we present a method for combining statistical optimum prediction techniques with local search methods such as simulated annealing and tabu search and illustrate the approach on a single machine scheduling problem. Computational experiments show that the approach yields useful estimates of optimal values with very reasonable computational effort.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1023/a:1009669326107", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136112", 
            "issn": [
              "1381-1231", 
              "1572-9397"
            ], 
            "name": "Journal of Heuristics", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "6"
          }
        ], 
        "name": "Integrating Interval Estimates of Global Optima and Local Search Methods for Combinatorial Optimization Problems", 
        "pagination": "481-500", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "b20730b988bcf3a1b4735e7be951ff6458702dc89b3bc6daf561ad8475cab18f"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1023/a:1009669326107"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1037372668"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1023/a:1009669326107", 
          "https://app.dimensions.ai/details/publication/pub.1037372668"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T01:57", 
        "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_8700_00000500.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1023/A:1009669326107"
      }
    ]
     

    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.1023/a:1009669326107'

    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.1023/a:1009669326107'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1009669326107'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1009669326107'


     

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

    117 TRIPLES      21 PREDICATES      39 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1023/a:1009669326107 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N59201ec2ae314f45927f6c1aba76b642
    4 schema:citation sg:pub.10.1007/bf01581033
    5 sg:pub.10.1007/bf01582166
    6 sg:pub.10.1007/bf02022094
    7 https://doi.org/10.1002/1520-6750(199204)39:3<369::aid-nav3220390307>3.0.co;2-f
    8 https://doi.org/10.1002/nav.3800260108
    9 https://doi.org/10.1016/0191-2615(82)90030-3
    10 https://doi.org/10.1017/s0305004100015681
    11 https://doi.org/10.1080/00949657908810302
    12 https://doi.org/10.1287/ijoc.1.3.190
    13 https://doi.org/10.1287/ijoc.2.1.4
    14 https://doi.org/10.1287/opre.33.5.1024
    15 https://doi.org/10.1287/opre.40.1.113
    16 schema:datePublished 2000-09
    17 schema:datePublishedReg 2000-09-01
    18 schema:description The problem of estimating the global optimal values of intractable combinatorial optimization problems is of interest to researchers developing and evaluating heuristics for these problems. In this paper we present a method for combining statistical optimum prediction techniques with local search methods such as simulated annealing and tabu search and illustrate the approach on a single machine scheduling problem. Computational experiments show that the approach yields useful estimates of optimal values with very reasonable computational effort.
    19 schema:genre research_article
    20 schema:inLanguage en
    21 schema:isAccessibleForFree false
    22 schema:isPartOf N248d5840bbe0420a91e0105971d8cb5c
    23 Nd14cf4da51664f75848bf0d12b7b1a59
    24 sg:journal.1136112
    25 schema:name Integrating Interval Estimates of Global Optima and Local Search Methods for Combinatorial Optimization Problems
    26 schema:pagination 481-500
    27 schema:productId N5c16bffb374448809943c7b4647b5735
    28 N86f27c29c002419e80bf5302052ba110
    29 N97dfa874aebd4d7d98c9ce5ed7d5608a
    30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037372668
    31 https://doi.org/10.1023/a:1009669326107
    32 schema:sdDatePublished 2019-04-11T01:57
    33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    34 schema:sdPublisher N526ef87ca2ed454aa50d2ceb1e150d6d
    35 schema:url http://link.springer.com/10.1023/A:1009669326107
    36 sgo:license sg:explorer/license/
    37 sgo:sdDataset articles
    38 rdf:type schema:ScholarlyArticle
    39 N248d5840bbe0420a91e0105971d8cb5c schema:volumeNumber 6
    40 rdf:type schema:PublicationVolume
    41 N31e4aaec895f4e18b2b49cafa73542f4 schema:name i2 Technologies, 909 East Las Colinas Blud., 75039, Irving, TX, USA
    42 rdf:type schema:Organization
    43 N526ef87ca2ed454aa50d2ceb1e150d6d schema:name Springer Nature - SN SciGraph project
    44 rdf:type schema:Organization
    45 N59201ec2ae314f45927f6c1aba76b642 rdf:first sg:person.07636244107.17
    46 rdf:rest N7288781a838d4e7fa357dcc12fa895cc
    47 N5c16bffb374448809943c7b4647b5735 schema:name doi
    48 schema:value 10.1023/a:1009669326107
    49 rdf:type schema:PropertyValue
    50 N7288781a838d4e7fa357dcc12fa895cc rdf:first N941162f7ed1641c290a94a8338e3dbdd
    51 rdf:rest N87162588bc9b4e71990c2bd2db3338eb
    52 N86f27c29c002419e80bf5302052ba110 schema:name readcube_id
    53 schema:value b20730b988bcf3a1b4735e7be951ff6458702dc89b3bc6daf561ad8475cab18f
    54 rdf:type schema:PropertyValue
    55 N87162588bc9b4e71990c2bd2db3338eb rdf:first sg:person.01266067704.79
    56 rdf:rest rdf:nil
    57 N941162f7ed1641c290a94a8338e3dbdd schema:affiliation N31e4aaec895f4e18b2b49cafa73542f4
    58 schema:familyName Rajagopalan
    59 schema:givenName Srikanth
    60 rdf:type schema:Person
    61 N97dfa874aebd4d7d98c9ce5ed7d5608a schema:name dimensions_id
    62 schema:value pub.1037372668
    63 rdf:type schema:PropertyValue
    64 Nd14cf4da51664f75848bf0d12b7b1a59 schema:issueNumber 4
    65 rdf:type schema:PublicationIssue
    66 Ne8a149edf5e546e0bc954d18c1306cd7 schema:name i2 Technologies, 909 East Las Colinas Blud., 75039, Irving, TX, USA
    67 rdf:type schema:Organization
    68 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Information and Computing Sciences
    70 rdf:type schema:DefinedTerm
    71 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Artificial Intelligence and Image Processing
    73 rdf:type schema:DefinedTerm
    74 sg:journal.1136112 schema:issn 1381-1231
    75 1572-9397
    76 schema:name Journal of Heuristics
    77 rdf:type schema:Periodical
    78 sg:person.01266067704.79 schema:affiliation https://www.grid.ac/institutes/grid.169077.e
    79 schema:familyName Uzsoy
    80 schema:givenName Reha
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01266067704.79
    82 rdf:type schema:Person
    83 sg:person.07636244107.17 schema:affiliation Ne8a149edf5e546e0bc954d18c1306cd7
    84 schema:familyName Ovacik
    85 schema:givenName Irfan M.
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07636244107.17
    87 rdf:type schema:Person
    88 sg:pub.10.1007/bf01581033 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048958536
    89 https://doi.org/10.1007/bf01581033
    90 rdf:type schema:CreativeWork
    91 sg:pub.10.1007/bf01582166 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049532067
    92 https://doi.org/10.1007/bf01582166
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/bf02022094 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003666985
    95 https://doi.org/10.1007/bf02022094
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1002/1520-6750(199204)39:3<369::aid-nav3220390307>3.0.co;2-f schema:sameAs https://app.dimensions.ai/details/publication/pub.1002793945
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1002/nav.3800260108 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044068101
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1016/0191-2615(82)90030-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046029370
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1017/s0305004100015681 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053808967
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1080/00949657908810302 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006466564
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1287/ijoc.1.3.190 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064706391
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1287/ijoc.2.1.4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064707137
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1287/opre.33.5.1024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064729651
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1287/opre.40.1.113 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064730378
    114 rdf:type schema:CreativeWork
    115 https://www.grid.ac/institutes/grid.169077.e schema:alternateName Purdue University
    116 schema:name School of Industrial Engineering, Purdue University, 1287 Grissom Hall, 47907-1287, West Lafayette, IN, USA
    117 rdf:type schema:Organization
     




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


    ...