B&B method for discrete partial order optimization View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-02-20

AUTHORS

Vladimir I. Norkin

ABSTRACT

The paper extends the branch and bound (B&B) method, primarily developed for the solution of global, discrete, and vector programming problems, to finding nondominated points in a partially ordered space/set. The framework of the generalized B&B method is standard, it includes partition, estimation, and pruning steps, but bounds are different, they are set-valued, and, as a particular case, the bounds may be singletons. For bounding, the method uses a set ordering in the following sense. One set is “less or equal” than the other if for any element of the first set there is a “greater or equal” element in the second one. The defined set ordering is a partial order in the space of sets consisting of mutually nondominated elements. In the B&B method, partitioning is applied to the parts of the original space with nondominated upper bounds. Parts with small upper bounds (less than some lower bound) are pruned. Convergence of the method to the set of all nondominated points is established. The acceleration with respect to the enumerative search is achieved through group evaluation of elements of the original space. Further, the developed B&B method is extended to vector partial order optimization. In the latter case, several partial orders are defined in the decision space. Finally, we develop a B&B method for a so-called constrained partial order optimization problem, where the feasible set is defined by a family of partial orders. More... »

PAGES

1-16

References to SciGraph publications

  • 2011-07-05. Vector Optimization Problems and Their Solution Concepts in RECENT DEVELOPMENTS IN VECTOR OPTIMIZATION
  • 1998-03. Two-phases Method and Branch and Bound Procedures to Solve the Bi–objective Knapsack Problem in JOURNAL OF GLOBAL OPTIMIZATION
  • 2009. Isotonic Regression Problems in ENCYCLOPEDIA OF OPTIMIZATION
  • 2009. Decomposition in Global Optimization in ENCYCLOPEDIA OF OPTIMIZATION
  • 2011-07. Boolean lexicographic optimization: algorithms & applications in ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE
  • 2017-12-07. B&B Solution Technique for Multicriteria Stochastic Optimization Problems in OPTIMIZATION METHODS AND APPLICATIONS
  • 2000. A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimization: NSGA-II in PARALLEL PROBLEM SOLVING FROM NATURE PPSN VI
  • 2002. Multicriteria Analysis in Engineering, Using the PSI Method with MOVI 1.0 in NONE
  • 2001. Bounds and Bound Sets for Biobjective Combinatorial Optimization Problems in MULTIPLE CRITERIA DECISION MAKING IN THE NEW MILLENNIUM
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10287-019-00346-4

    DOI

    http://dx.doi.org/10.1007/s10287-019-00346-4

    DIMENSIONS

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


    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/0103", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Numerical and Computational Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "National Technical University of Ukraine Kiev Polytechnic Institute", 
              "id": "https://www.grid.ac/institutes/grid.440544.5", 
              "name": [
                "V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine", 
                "Faculty of Applied Mathematics, National Technical University of Ukraine \u201cI. Sikorsky Kyiv Polytechnic Institute\u201d, Kyiv, Ukraine"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Norkin", 
            "givenName": "Vladimir I.", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-642-21114-0_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002806548", 
              "https://doi.org/10.1007/978-3-642-21114-0_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-21114-0_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002806548", 
              "https://doi.org/10.1007/978-3-642-21114-0_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/02331939208843803", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007249127"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10472-011-9233-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016768956", 
              "https://doi.org/10.1007/s10472-011-9233-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-0-387-74759-0_112", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019548372", 
              "https://doi.org/10.1007/978-0-387-74759-0_112"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45356-3_83", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019904657", 
              "https://doi.org/10.1007/3-540-45356-3_83"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45356-3_83", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019904657", 
              "https://doi.org/10.1007/3-540-45356-3_83"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-56680-6_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021154327", 
              "https://doi.org/10.1007/978-3-642-56680-6_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-56680-6_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021154327", 
              "https://doi.org/10.1007/978-3-642-56680-6_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-0-387-74759-0_311", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040635571", 
              "https://doi.org/10.1007/978-0-387-74759-0_311"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1008258310679", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045901761", 
              "https://doi.org/10.1023/a:1008258310679"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.cor.2005.10.003", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046991658"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1048686541", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-94-015-9968-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048686541", 
              "https://doi.org/10.1007/978-94-015-9968-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-94-015-9968-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048686541", 
              "https://doi.org/10.1007/978-94-015-9968-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s1052623402420528", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062883339"
            ], 
            "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.1016/j.ejor.2017.01.032", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1074210064"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-68640-0_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1099813811", 
              "https://doi.org/10.1007/978-3-319-68640-0_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-68640-0_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1099813811", 
              "https://doi.org/10.1007/978-3-319-68640-0_17"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2019-02-20", 
        "datePublishedReg": "2019-02-20", 
        "description": "The paper extends the branch and bound (B&B) method, primarily developed for the solution of global, discrete, and vector programming problems, to finding nondominated points in a partially ordered space/set. The framework of the generalized B&B method is standard, it includes partition, estimation, and pruning steps, but bounds are different, they are set-valued, and, as a particular case, the bounds may be singletons. For bounding, the method uses a set ordering in the following sense. One set is \u201cless or equal\u201d than the other if for any element of the first set there is a \u201cgreater or equal\u201d element in the second one. The defined set ordering is a partial order in the space of sets consisting of mutually nondominated elements. In the B&B method, partitioning is applied to the parts of the original space with nondominated upper bounds. Parts with small upper bounds (less than some lower bound) are pruned. Convergence of the method to the set of all nondominated points is established. The acceleration with respect to the enumerative search is achieved through group evaluation of elements of the original space. Further, the developed B&B method is extended to vector partial order optimization. In the latter case, several partial orders are defined in the decision space. Finally, we develop a B&B method for a so-called constrained partial order optimization problem, where the feasible set is defined by a family of partial orders.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s10287-019-00346-4", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136802", 
            "issn": [
              "1619-697X", 
              "1619-6988"
            ], 
            "name": "Computational Management Science", 
            "type": "Periodical"
          }
        ], 
        "name": "B&B method for discrete partial order optimization", 
        "pagination": "1-16", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "d379c30a7cee9657cc765829ff98b04aafdf24cca93c7f5040da4fb5923d442f"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10287-019-00346-4"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1112261901"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10287-019-00346-4", 
          "https://app.dimensions.ai/details/publication/pub.1112261901"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T09:36", 
        "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/0000000346_0000000346/records_99821_00000004.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs10287-019-00346-4"
      }
    ]
     

    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/s10287-019-00346-4'

    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/s10287-019-00346-4'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10287-019-00346-4'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10287-019-00346-4'


     

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

    108 TRIPLES      21 PREDICATES      39 URIs      16 LITERALS      5 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10287-019-00346-4 schema:about anzsrc-for:01
    2 anzsrc-for:0103
    3 schema:author N41cce8ac0bb64a6e81cea647ae388baf
    4 schema:citation sg:pub.10.1007/3-540-45356-3_83
    5 sg:pub.10.1007/978-0-387-74759-0_112
    6 sg:pub.10.1007/978-0-387-74759-0_311
    7 sg:pub.10.1007/978-3-319-68640-0_17
    8 sg:pub.10.1007/978-3-642-21114-0_1
    9 sg:pub.10.1007/978-3-642-56680-6_22
    10 sg:pub.10.1007/978-94-015-9968-9
    11 sg:pub.10.1007/s10472-011-9233-2
    12 sg:pub.10.1023/a:1008258310679
    13 https://app.dimensions.ai/details/publication/pub.1048686541
    14 https://doi.org/10.1016/j.cor.2005.10.003
    15 https://doi.org/10.1016/j.ejor.2017.01.032
    16 https://doi.org/10.1080/02331939208843803
    17 https://doi.org/10.1137/s1052623402420528
    18 https://doi.org/10.1287/ijoc.1070.0260
    19 schema:datePublished 2019-02-20
    20 schema:datePublishedReg 2019-02-20
    21 schema:description The paper extends the branch and bound (B&B) method, primarily developed for the solution of global, discrete, and vector programming problems, to finding nondominated points in a partially ordered space/set. The framework of the generalized B&B method is standard, it includes partition, estimation, and pruning steps, but bounds are different, they are set-valued, and, as a particular case, the bounds may be singletons. For bounding, the method uses a set ordering in the following sense. One set is “less or equal” than the other if for any element of the first set there is a “greater or equal” element in the second one. The defined set ordering is a partial order in the space of sets consisting of mutually nondominated elements. In the B&B method, partitioning is applied to the parts of the original space with nondominated upper bounds. Parts with small upper bounds (less than some lower bound) are pruned. Convergence of the method to the set of all nondominated points is established. The acceleration with respect to the enumerative search is achieved through group evaluation of elements of the original space. Further, the developed B&B method is extended to vector partial order optimization. In the latter case, several partial orders are defined in the decision space. Finally, we develop a B&B method for a so-called constrained partial order optimization problem, where the feasible set is defined by a family of partial orders.
    22 schema:genre research_article
    23 schema:inLanguage en
    24 schema:isAccessibleForFree false
    25 schema:isPartOf sg:journal.1136802
    26 schema:name B&B method for discrete partial order optimization
    27 schema:pagination 1-16
    28 schema:productId N51668a2518ce4f9aab1bcd15889c6396
    29 Nbc9f6d720d43470ab01f8706ef8c1eea
    30 Nc5fcb23c136e4d2bb1cd330a78335543
    31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112261901
    32 https://doi.org/10.1007/s10287-019-00346-4
    33 schema:sdDatePublished 2019-04-11T09:36
    34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    35 schema:sdPublisher Nb544996778ef4912a795e7454a6295fa
    36 schema:url https://link.springer.com/10.1007%2Fs10287-019-00346-4
    37 sgo:license sg:explorer/license/
    38 sgo:sdDataset articles
    39 rdf:type schema:ScholarlyArticle
    40 N41cce8ac0bb64a6e81cea647ae388baf rdf:first N58c01244fcc14af5840bf22bc543f73b
    41 rdf:rest rdf:nil
    42 N51668a2518ce4f9aab1bcd15889c6396 schema:name readcube_id
    43 schema:value d379c30a7cee9657cc765829ff98b04aafdf24cca93c7f5040da4fb5923d442f
    44 rdf:type schema:PropertyValue
    45 N58c01244fcc14af5840bf22bc543f73b schema:affiliation https://www.grid.ac/institutes/grid.440544.5
    46 schema:familyName Norkin
    47 schema:givenName Vladimir I.
    48 rdf:type schema:Person
    49 Nb544996778ef4912a795e7454a6295fa schema:name Springer Nature - SN SciGraph project
    50 rdf:type schema:Organization
    51 Nbc9f6d720d43470ab01f8706ef8c1eea schema:name doi
    52 schema:value 10.1007/s10287-019-00346-4
    53 rdf:type schema:PropertyValue
    54 Nc5fcb23c136e4d2bb1cd330a78335543 schema:name dimensions_id
    55 schema:value pub.1112261901
    56 rdf:type schema:PropertyValue
    57 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    58 schema:name Mathematical Sciences
    59 rdf:type schema:DefinedTerm
    60 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    61 schema:name Numerical and Computational Mathematics
    62 rdf:type schema:DefinedTerm
    63 sg:journal.1136802 schema:issn 1619-697X
    64 1619-6988
    65 schema:name Computational Management Science
    66 rdf:type schema:Periodical
    67 sg:pub.10.1007/3-540-45356-3_83 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019904657
    68 https://doi.org/10.1007/3-540-45356-3_83
    69 rdf:type schema:CreativeWork
    70 sg:pub.10.1007/978-0-387-74759-0_112 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019548372
    71 https://doi.org/10.1007/978-0-387-74759-0_112
    72 rdf:type schema:CreativeWork
    73 sg:pub.10.1007/978-0-387-74759-0_311 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040635571
    74 https://doi.org/10.1007/978-0-387-74759-0_311
    75 rdf:type schema:CreativeWork
    76 sg:pub.10.1007/978-3-319-68640-0_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1099813811
    77 https://doi.org/10.1007/978-3-319-68640-0_17
    78 rdf:type schema:CreativeWork
    79 sg:pub.10.1007/978-3-642-21114-0_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002806548
    80 https://doi.org/10.1007/978-3-642-21114-0_1
    81 rdf:type schema:CreativeWork
    82 sg:pub.10.1007/978-3-642-56680-6_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021154327
    83 https://doi.org/10.1007/978-3-642-56680-6_22
    84 rdf:type schema:CreativeWork
    85 sg:pub.10.1007/978-94-015-9968-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048686541
    86 https://doi.org/10.1007/978-94-015-9968-9
    87 rdf:type schema:CreativeWork
    88 sg:pub.10.1007/s10472-011-9233-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016768956
    89 https://doi.org/10.1007/s10472-011-9233-2
    90 rdf:type schema:CreativeWork
    91 sg:pub.10.1023/a:1008258310679 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045901761
    92 https://doi.org/10.1023/a:1008258310679
    93 rdf:type schema:CreativeWork
    94 https://app.dimensions.ai/details/publication/pub.1048686541 schema:CreativeWork
    95 https://doi.org/10.1016/j.cor.2005.10.003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046991658
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1016/j.ejor.2017.01.032 schema:sameAs https://app.dimensions.ai/details/publication/pub.1074210064
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1080/02331939208843803 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007249127
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1137/s1052623402420528 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062883339
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1287/ijoc.1070.0260 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064706675
    104 rdf:type schema:CreativeWork
    105 https://www.grid.ac/institutes/grid.440544.5 schema:alternateName National Technical University of Ukraine Kiev Polytechnic Institute
    106 schema:name Faculty of Applied Mathematics, National Technical University of Ukraine “I. Sikorsky Kyiv Polytechnic Institute”, Kyiv, Ukraine
    107 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
    108 rdf:type schema:Organization
     




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


    ...