A comparison of multiobjective depth-first algorithms View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2013-08

AUTHORS

J. Coego, L. Mandow, J. L. Pérez de la Cruz

ABSTRACT

Many real world problems involve several, usually conflicting, objectives. Multiobjective analysis deals with these problems locating trade-offs between different optimal solutions. Regarding graph search problems, several algorithms based on best-first and depth-first approaches have been proposed to return the set of all Pareto optimal solutions. This article presents a detailed comparison between two representatives of multiobjective depth-first algorithms, PIDMOA* and MO-DF-BnB. Both of them extend previous single-objective search algorithms with linear-space requirements to the multiobjective case. Experimental analyses on their time performance over tree-shaped search spaces are presented. The results clarify the fitness of both algorithms to parameters like the number or depth of goal nodes. More... »

PAGES

821-829

References to SciGraph publications

  • 2010-02. Path recovery in frontier search for multiobjective shortest path problems in JOURNAL OF INTELLIGENT MANUFACTURING
  • 2009. A New Approach to Iterative Deepening Multiobjective A* in AI*IA 2009: EMERGENT PERSPECTIVES IN ARTIFICIAL INTELLIGENCE
  • 1999. State-Space Search, Algorithms, Complexity, Extensions, and Applications in NONE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10845-012-0632-y

    DOI

    http://dx.doi.org/10.1007/s10845-012-0632-y

    DIMENSIONS

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


    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": {
              "alternateName": "University of Malaga", 
              "id": "https://www.grid.ac/institutes/grid.10215.37", 
              "name": [
                "Dpto. Lenguajes y Ciencias de la Computaci\u00f3n, Universidad de M\u00e1laga, Bulevar Louis Pasteur, 35, 29071, Malaga, Spain"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Coego", 
            "givenName": "J.", 
            "id": "sg:person.011651000035.25", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011651000035.25"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Malaga", 
              "id": "https://www.grid.ac/institutes/grid.10215.37", 
              "name": [
                "Dpto. Lenguajes y Ciencias de la Computaci\u00f3n, Universidad de M\u00e1laga, Bulevar Louis Pasteur, 35, 29071, Malaga, Spain"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Mandow", 
            "givenName": "L.", 
            "id": "sg:person.012065311235.60", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012065311235.60"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Malaga", 
              "id": "https://www.grid.ac/institutes/grid.10215.37", 
              "name": [
                "Dpto. Lenguajes y Ciencias de la Computaci\u00f3n, Universidad de M\u00e1laga, Bulevar Louis Pasteur, 35, 29071, Malaga, Spain"
              ], 
              "type": "Organization"
            }, 
            "familyName": "P\u00e9rez de la Cruz", 
            "givenName": "J. L.", 
            "id": "sg:person.011222621661.19", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011222621661.19"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/j.cor.2008.02.002", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006277134"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-10291-2_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009850090", 
              "https://doi.org/10.1007/978-3-642-10291-2_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-10291-2_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009850090", 
              "https://doi.org/10.1007/978-3-642-10291-2_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-1538-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018081143", 
              "https://doi.org/10.1007/978-1-4612-1538-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-1538-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018081143", 
              "https://doi.org/10.1007/978-1-4612-1538-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1754399.1754400", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029423234"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0004-3702(85)90084-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030400469"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0004-3702(85)90084-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030400469"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(96)00009-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038700679"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0004-3702(94)00047-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039071211"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1089023.1089024", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040031928"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ejor.2009.10.015", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046770222"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10845-008-0169-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048419306", 
              "https://doi.org/10.1007/s10845-008-0169-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/34.297950", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061156013"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/ijoc.1070.0260", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064706675"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2307/1910129", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1069639071"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2013-08", 
        "datePublishedReg": "2013-08-01", 
        "description": "Many real world problems involve several, usually conflicting, objectives. Multiobjective analysis deals with these problems locating trade-offs between different optimal solutions. Regarding graph search problems, several algorithms based on best-first and depth-first approaches have been proposed to return the set of all Pareto optimal solutions. This article presents a detailed comparison between two representatives of multiobjective depth-first algorithms, PIDMOA* and MO-DF-BnB. Both of them extend previous single-objective search algorithms with linear-space requirements to the multiobjective case. Experimental analyses on their time performance over tree-shaped search spaces are presented. The results clarify the fitness of both algorithms to parameters like the number or depth of goal nodes.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s10845-012-0632-y", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1043477", 
            "issn": [
              "0956-5515", 
              "1572-8145"
            ], 
            "name": "Journal of Intelligent Manufacturing", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "24"
          }
        ], 
        "name": "A comparison of multiobjective depth-first algorithms", 
        "pagination": "821-829", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "1f0fde302e6d6571343fe0b86c60d298f31fab87cd16aaba9a2dc559c4f4aa34"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10845-012-0632-y"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1006521246"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10845-012-0632-y", 
          "https://app.dimensions.ai/details/publication/pub.1006521246"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T23:18", 
        "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_8693_00000486.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/s10845-012-0632-y"
      }
    ]
     

    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/s10845-012-0632-y'

    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/s10845-012-0632-y'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10845-012-0632-y'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10845-012-0632-y'


     

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

    117 TRIPLES      21 PREDICATES      40 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10845-012-0632-y schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author Nef91dd5164944686848b65612b3cf632
    4 schema:citation sg:pub.10.1007/978-1-4612-1538-7
    5 sg:pub.10.1007/978-3-642-10291-2_27
    6 sg:pub.10.1007/s10845-008-0169-2
    7 https://doi.org/10.1016/0004-3702(85)90084-0
    8 https://doi.org/10.1016/0004-3702(94)00047-6
    9 https://doi.org/10.1016/0020-0190(96)00009-9
    10 https://doi.org/10.1016/j.cor.2008.02.002
    11 https://doi.org/10.1016/j.ejor.2009.10.015
    12 https://doi.org/10.1109/34.297950
    13 https://doi.org/10.1145/1089023.1089024
    14 https://doi.org/10.1145/1754399.1754400
    15 https://doi.org/10.1287/ijoc.1070.0260
    16 https://doi.org/10.2307/1910129
    17 schema:datePublished 2013-08
    18 schema:datePublishedReg 2013-08-01
    19 schema:description Many real world problems involve several, usually conflicting, objectives. Multiobjective analysis deals with these problems locating trade-offs between different optimal solutions. Regarding graph search problems, several algorithms based on best-first and depth-first approaches have been proposed to return the set of all Pareto optimal solutions. This article presents a detailed comparison between two representatives of multiobjective depth-first algorithms, PIDMOA* and MO-DF-BnB. Both of them extend previous single-objective search algorithms with linear-space requirements to the multiobjective case. Experimental analyses on their time performance over tree-shaped search spaces are presented. The results clarify the fitness of both algorithms to parameters like the number or depth of goal nodes.
    20 schema:genre research_article
    21 schema:inLanguage en
    22 schema:isAccessibleForFree false
    23 schema:isPartOf N0350be0c37d142bbba757adc1cedafbc
    24 N6493261ef83b437abad88b7b161482ab
    25 sg:journal.1043477
    26 schema:name A comparison of multiobjective depth-first algorithms
    27 schema:pagination 821-829
    28 schema:productId N009571219fae4a54a330c3878ec94438
    29 N195b2b6bfa374747823879baaadac6ff
    30 N6ae4b06281c24fdc97f532eef7b240cd
    31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006521246
    32 https://doi.org/10.1007/s10845-012-0632-y
    33 schema:sdDatePublished 2019-04-10T23:18
    34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    35 schema:sdPublisher N9d3ce61b9ea34dab8f97d389f517cb3f
    36 schema:url http://link.springer.com/10.1007/s10845-012-0632-y
    37 sgo:license sg:explorer/license/
    38 sgo:sdDataset articles
    39 rdf:type schema:ScholarlyArticle
    40 N009571219fae4a54a330c3878ec94438 schema:name doi
    41 schema:value 10.1007/s10845-012-0632-y
    42 rdf:type schema:PropertyValue
    43 N0350be0c37d142bbba757adc1cedafbc schema:issueNumber 4
    44 rdf:type schema:PublicationIssue
    45 N195b2b6bfa374747823879baaadac6ff schema:name dimensions_id
    46 schema:value pub.1006521246
    47 rdf:type schema:PropertyValue
    48 N4305c02b370e41ca96041f824dee7561 rdf:first sg:person.012065311235.60
    49 rdf:rest N736674b0b23945a9bd6425119463b510
    50 N6493261ef83b437abad88b7b161482ab schema:volumeNumber 24
    51 rdf:type schema:PublicationVolume
    52 N6ae4b06281c24fdc97f532eef7b240cd schema:name readcube_id
    53 schema:value 1f0fde302e6d6571343fe0b86c60d298f31fab87cd16aaba9a2dc559c4f4aa34
    54 rdf:type schema:PropertyValue
    55 N736674b0b23945a9bd6425119463b510 rdf:first sg:person.011222621661.19
    56 rdf:rest rdf:nil
    57 N9d3ce61b9ea34dab8f97d389f517cb3f schema:name Springer Nature - SN SciGraph project
    58 rdf:type schema:Organization
    59 Nef91dd5164944686848b65612b3cf632 rdf:first sg:person.011651000035.25
    60 rdf:rest N4305c02b370e41ca96041f824dee7561
    61 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    62 schema:name Information and Computing Sciences
    63 rdf:type schema:DefinedTerm
    64 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    65 schema:name Artificial Intelligence and Image Processing
    66 rdf:type schema:DefinedTerm
    67 sg:journal.1043477 schema:issn 0956-5515
    68 1572-8145
    69 schema:name Journal of Intelligent Manufacturing
    70 rdf:type schema:Periodical
    71 sg:person.011222621661.19 schema:affiliation https://www.grid.ac/institutes/grid.10215.37
    72 schema:familyName Pérez de la Cruz
    73 schema:givenName J. L.
    74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011222621661.19
    75 rdf:type schema:Person
    76 sg:person.011651000035.25 schema:affiliation https://www.grid.ac/institutes/grid.10215.37
    77 schema:familyName Coego
    78 schema:givenName J.
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011651000035.25
    80 rdf:type schema:Person
    81 sg:person.012065311235.60 schema:affiliation https://www.grid.ac/institutes/grid.10215.37
    82 schema:familyName Mandow
    83 schema:givenName L.
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012065311235.60
    85 rdf:type schema:Person
    86 sg:pub.10.1007/978-1-4612-1538-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018081143
    87 https://doi.org/10.1007/978-1-4612-1538-7
    88 rdf:type schema:CreativeWork
    89 sg:pub.10.1007/978-3-642-10291-2_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009850090
    90 https://doi.org/10.1007/978-3-642-10291-2_27
    91 rdf:type schema:CreativeWork
    92 sg:pub.10.1007/s10845-008-0169-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048419306
    93 https://doi.org/10.1007/s10845-008-0169-2
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1016/0004-3702(85)90084-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030400469
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1016/0004-3702(94)00047-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039071211
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1016/0020-0190(96)00009-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038700679
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1016/j.cor.2008.02.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006277134
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1016/j.ejor.2009.10.015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046770222
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1109/34.297950 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061156013
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1145/1089023.1089024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040031928
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1145/1754399.1754400 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029423234
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1287/ijoc.1070.0260 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064706675
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.2307/1910129 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069639071
    114 rdf:type schema:CreativeWork
    115 https://www.grid.ac/institutes/grid.10215.37 schema:alternateName University of Malaga
    116 schema:name Dpto. Lenguajes y Ciencias de la Computación, Universidad de Málaga, Bulevar Louis Pasteur, 35, 29071, Malaga, Spain
    117 rdf:type schema:Organization
     




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


    ...