Probing the Pareto front of a large-scale multiobjective problem with a MIP solver View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2022-06-06

AUTHORS

I. Kaliszewski, J. Miroforidis

ABSTRACT

The rapid growth of computing power and the development of highly effective optimization solvers build the appetite for solving increasingly extensive problems. However, despite all these efforts, resource constraints (time, memory) often strike back. The ”curse of dimensionality” haunts primarily combinatorial problems, but not only. The issue is even more acute in multiobjective optimization, where several Pareto optimal solutions have to be derived. In our earlier works, we developed a general methodology for multiobjective optimization that allows representing the outcome of a Pareto optimal solution by a hyperrectangle. The sides of the hyperrectangle are defined by lower and upper bounds on the outcome components, i.e., intervals of possible objective function values. Such a representation makes sense if the Pareto optimal solution cannot be derived with the available computation resources. Beyond the research interest, to be of practical value, methodologies of that kind have to be computationally effective and scalable. In this work, we show that our methodology can be effectively coupled with any MIP optimization solver. With that, as long as an analyst is willing to accept a (sufficiently tight) interval representation of the Pareto optimal solution outcome instead of its exact outcome, our methodology scales multiobjective-based analyses well beyond the reach of the MIP solver itself. We operationalize our methodology in the form of a workflow (we nicknamed it Crescent Workflow). We illustrate the workflow working on several large-scale instances of the multiobjective multidimensional 0–1 knapsack problem with three objectives. More... »

PAGES

5617-5673

References to SciGraph publications

  • 1986-06-01. On the completeness and constructiveness of parametric characterizations to vector optimization problems in OR SPECTRUM
  • 2005-09. Approximation Methods in Multiobjective Programming in JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • 2021-04-23. Bounds on efficient outcomes for large-scale cardinality-constrained Markowitz problems in JOURNAL OF GLOBAL OPTIMIZATION
  • 1998-06. A Genetic Algorithm for the Multidimensional Knapsack Problem in JOURNAL OF HEURISTICS
  • 2013-10-16. Multi-objective Approaches for Design of Assembly Lines in APPLICATIONS OF MULTI-CRITERIA AND GAME THEORY APPROACHES
  • 2002. Evolutionary Algorithms for Solving Multi-Objective Problems in NONE
  • 2016. Multiple Criteria Decision Making by Multiobjective Optimization, A Toolbox in NONE
  • 2020-09-19. Cooperative multiobjective optimization with bounds on objective functions in JOURNAL OF GLOBAL OPTIMIZATION
  • 2018-03-13. On upper approximations of Pareto fronts in JOURNAL OF GLOBAL OPTIMIZATION
  • 2013-12-17. Two-Sided Pareto Front Approximations in JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s12351-022-00708-y

    DOI

    http://dx.doi.org/10.1007/s12351-022-00708-y

    DIMENSIONS

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


    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/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Warsaw School of Information Technology, ul. Newelska 6, 01-447, Warsaw, Poland", 
              "id": "http://www.grid.ac/institutes/grid.445568.e", 
              "name": [
                "Systems Research Institute, Polish Academy of Sciences, ul. Newelska 6, 01-447, Warsaw, Poland", 
                "Warsaw School of Information Technology, ul. Newelska 6, 01-447, Warsaw, Poland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kaliszewski", 
            "givenName": "I.", 
            "id": "sg:person.012603160252.47", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012603160252.47"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Systems Research Institute, Polish Academy of Sciences, ul. Newelska 6, 01-447, Warsaw, Poland", 
              "id": "http://www.grid.ac/institutes/grid.465202.7", 
              "name": [
                "Systems Research Institute, Polish Academy of Sciences, ul. Newelska 6, 01-447, Warsaw, Poland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Miroforidis", 
            "givenName": "J.", 
            "id": "sg:person.012343036301.29", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012343036301.29"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s10957-013-0498-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010309214", 
              "https://doi.org/10.1007/s10957-013-0498-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-32756-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035014119", 
              "https://doi.org/10.1007/978-3-319-32756-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10957-005-5494-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008721920", 
              "https://doi.org/10.1007/s10957-005-5494-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10898-021-01022-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1137430609", 
              "https://doi.org/10.1007/s10898-021-01022-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1009642405419", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053131829", 
              "https://doi.org/10.1023/a:1009642405419"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4757-5184-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044422346", 
              "https://doi.org/10.1007/978-1-4757-5184-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01719738", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037736752", 
              "https://doi.org/10.1007/bf01719738"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10898-020-00946-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1130995001", 
              "https://doi.org/10.1007/s10898-020-00946-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4471-5295-8_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003668952", 
              "https://doi.org/10.1007/978-1-4471-5295-8_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10898-018-0642-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1101517830", 
              "https://doi.org/10.1007/s10898-018-0642-1"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2022-06-06", 
        "datePublishedReg": "2022-06-06", 
        "description": "The rapid growth of computing power and the development of highly effective optimization solvers build the appetite for solving increasingly extensive problems. However, despite all these efforts, resource constraints (time, memory) often strike back. The \u201dcurse of dimensionality\u201d haunts primarily combinatorial problems, but not only. The issue is even more acute in multiobjective optimization, where several Pareto optimal solutions have to be derived. In our earlier works, we developed a general methodology for multiobjective optimization that allows representing the outcome of a Pareto optimal solution by a hyperrectangle. The sides of the hyperrectangle are defined by lower and upper bounds on the outcome components, i.e., intervals of possible objective function values. Such a representation makes sense if the Pareto optimal solution cannot be derived with the available computation resources. Beyond the research interest, to be of practical value, methodologies of that kind have to be computationally effective and scalable. In this work, we show that our methodology can be effectively coupled with any MIP optimization solver. With that, as long as an analyst is willing to accept a (sufficiently tight) interval representation of the Pareto optimal solution outcome instead of its exact outcome, our methodology scales multiobjective-based analyses well beyond the reach of the MIP solver itself. We operationalize our methodology in the form of a workflow (we nicknamed it Crescent Workflow). We illustrate the workflow working on several large-scale instances of the multiobjective multidimensional 0\u20131 knapsack problem with three objectives.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s12351-022-00708-y", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1271390", 
            "issn": [
              "1109-2858", 
              "1866-1505"
            ], 
            "name": "Operational Research", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "5", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "22"
          }
        ], 
        "keywords": [
          "Pareto optimal solutions", 
          "optimal solution", 
          "optimization solver", 
          "MIP solver", 
          "available computation resources", 
          "multiobjective optimization", 
          "large-scale instances", 
          "objective function value", 
          "curse of dimensionality", 
          "computation resources", 
          "combinatorial problems", 
          "knapsack problem", 
          "upper bounds", 
          "resource constraints", 
          "Pareto front", 
          "multiobjective problem", 
          "solver", 
          "function values", 
          "interval representation", 
          "general methodology", 
          "workflow", 
          "hyperrectangles", 
          "exact outcome", 
          "rapid growth", 
          "practical value", 
          "solution outcome", 
          "optimization", 
          "problem", 
          "representation", 
          "solution", 
          "research interest", 
          "methodology", 
          "earlier work", 
          "bounds", 
          "extensive problem", 
          "dimensionality", 
          "curse", 
          "analysts", 
          "constraints", 
          "work", 
          "instances", 
          "resources", 
          "issues", 
          "kind", 
          "front", 
          "sense", 
          "efforts", 
          "values", 
          "power", 
          "interest", 
          "form", 
          "objective", 
          "components", 
          "development", 
          "interval", 
          "analysis", 
          "reach", 
          "side", 
          "growth", 
          "outcomes", 
          "outcome components", 
          "appetite"
        ], 
        "name": "Probing the Pareto front of a large-scale multiobjective problem with a MIP solver", 
        "pagination": "5617-5673", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1148453755"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s12351-022-00708-y"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s12351-022-00708-y", 
          "https://app.dimensions.ai/details/publication/pub.1148453755"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-11-24T21:08", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/article/article_919.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s12351-022-00708-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/s12351-022-00708-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/s12351-022-00708-y'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s12351-022-00708-y'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s12351-022-00708-y'


     

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

    170 TRIPLES      21 PREDICATES      96 URIs      78 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s12351-022-00708-y schema:about anzsrc-for:01
    2 anzsrc-for:0103
    3 schema:author Nf03ca9d894fa490d8c7e25ce686313af
    4 schema:citation sg:pub.10.1007/978-1-4471-5295-8_2
    5 sg:pub.10.1007/978-1-4757-5184-0
    6 sg:pub.10.1007/978-3-319-32756-3
    7 sg:pub.10.1007/bf01719738
    8 sg:pub.10.1007/s10898-018-0642-1
    9 sg:pub.10.1007/s10898-020-00946-4
    10 sg:pub.10.1007/s10898-021-01022-1
    11 sg:pub.10.1007/s10957-005-5494-4
    12 sg:pub.10.1007/s10957-013-0498-y
    13 sg:pub.10.1023/a:1009642405419
    14 schema:datePublished 2022-06-06
    15 schema:datePublishedReg 2022-06-06
    16 schema:description The rapid growth of computing power and the development of highly effective optimization solvers build the appetite for solving increasingly extensive problems. However, despite all these efforts, resource constraints (time, memory) often strike back. The ”curse of dimensionality” haunts primarily combinatorial problems, but not only. The issue is even more acute in multiobjective optimization, where several Pareto optimal solutions have to be derived. In our earlier works, we developed a general methodology for multiobjective optimization that allows representing the outcome of a Pareto optimal solution by a hyperrectangle. The sides of the hyperrectangle are defined by lower and upper bounds on the outcome components, i.e., intervals of possible objective function values. Such a representation makes sense if the Pareto optimal solution cannot be derived with the available computation resources. Beyond the research interest, to be of practical value, methodologies of that kind have to be computationally effective and scalable. In this work, we show that our methodology can be effectively coupled with any MIP optimization solver. With that, as long as an analyst is willing to accept a (sufficiently tight) interval representation of the Pareto optimal solution outcome instead of its exact outcome, our methodology scales multiobjective-based analyses well beyond the reach of the MIP solver itself. We operationalize our methodology in the form of a workflow (we nicknamed it Crescent Workflow). We illustrate the workflow working on several large-scale instances of the multiobjective multidimensional 0–1 knapsack problem with three objectives.
    17 schema:genre article
    18 schema:isAccessibleForFree false
    19 schema:isPartOf N546e4a557c7d4f5cbe28bbe921c3125e
    20 N5f0b76e78d31410f86d1d0509ca9fb2f
    21 sg:journal.1271390
    22 schema:keywords MIP solver
    23 Pareto front
    24 Pareto optimal solutions
    25 analysis
    26 analysts
    27 appetite
    28 available computation resources
    29 bounds
    30 combinatorial problems
    31 components
    32 computation resources
    33 constraints
    34 curse
    35 curse of dimensionality
    36 development
    37 dimensionality
    38 earlier work
    39 efforts
    40 exact outcome
    41 extensive problem
    42 form
    43 front
    44 function values
    45 general methodology
    46 growth
    47 hyperrectangles
    48 instances
    49 interest
    50 interval
    51 interval representation
    52 issues
    53 kind
    54 knapsack problem
    55 large-scale instances
    56 methodology
    57 multiobjective optimization
    58 multiobjective problem
    59 objective
    60 objective function value
    61 optimal solution
    62 optimization
    63 optimization solver
    64 outcome components
    65 outcomes
    66 power
    67 practical value
    68 problem
    69 rapid growth
    70 reach
    71 representation
    72 research interest
    73 resource constraints
    74 resources
    75 sense
    76 side
    77 solution
    78 solution outcome
    79 solver
    80 upper bounds
    81 values
    82 work
    83 workflow
    84 schema:name Probing the Pareto front of a large-scale multiobjective problem with a MIP solver
    85 schema:pagination 5617-5673
    86 schema:productId N62cd3348266e41dda3b9772fe201b7ee
    87 Nfc63e8c7d42c498e872d31be28f8cd5c
    88 schema:sameAs https://app.dimensions.ai/details/publication/pub.1148453755
    89 https://doi.org/10.1007/s12351-022-00708-y
    90 schema:sdDatePublished 2022-11-24T21:08
    91 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    92 schema:sdPublisher N54e60dfe31c54a89a5062256f48160c4
    93 schema:url https://doi.org/10.1007/s12351-022-00708-y
    94 sgo:license sg:explorer/license/
    95 sgo:sdDataset articles
    96 rdf:type schema:ScholarlyArticle
    97 N44d1220f57a5408087aaf9e447061b66 rdf:first sg:person.012343036301.29
    98 rdf:rest rdf:nil
    99 N546e4a557c7d4f5cbe28bbe921c3125e schema:issueNumber 5
    100 rdf:type schema:PublicationIssue
    101 N54e60dfe31c54a89a5062256f48160c4 schema:name Springer Nature - SN SciGraph project
    102 rdf:type schema:Organization
    103 N5f0b76e78d31410f86d1d0509ca9fb2f schema:volumeNumber 22
    104 rdf:type schema:PublicationVolume
    105 N62cd3348266e41dda3b9772fe201b7ee schema:name doi
    106 schema:value 10.1007/s12351-022-00708-y
    107 rdf:type schema:PropertyValue
    108 Nf03ca9d894fa490d8c7e25ce686313af rdf:first sg:person.012603160252.47
    109 rdf:rest N44d1220f57a5408087aaf9e447061b66
    110 Nfc63e8c7d42c498e872d31be28f8cd5c schema:name dimensions_id
    111 schema:value pub.1148453755
    112 rdf:type schema:PropertyValue
    113 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    114 schema:name Mathematical Sciences
    115 rdf:type schema:DefinedTerm
    116 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    117 schema:name Numerical and Computational Mathematics
    118 rdf:type schema:DefinedTerm
    119 sg:journal.1271390 schema:issn 1109-2858
    120 1866-1505
    121 schema:name Operational Research
    122 schema:publisher Springer Nature
    123 rdf:type schema:Periodical
    124 sg:person.012343036301.29 schema:affiliation grid-institutes:grid.465202.7
    125 schema:familyName Miroforidis
    126 schema:givenName J.
    127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012343036301.29
    128 rdf:type schema:Person
    129 sg:person.012603160252.47 schema:affiliation grid-institutes:grid.445568.e
    130 schema:familyName Kaliszewski
    131 schema:givenName I.
    132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012603160252.47
    133 rdf:type schema:Person
    134 sg:pub.10.1007/978-1-4471-5295-8_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003668952
    135 https://doi.org/10.1007/978-1-4471-5295-8_2
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/978-1-4757-5184-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044422346
    138 https://doi.org/10.1007/978-1-4757-5184-0
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/978-3-319-32756-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035014119
    141 https://doi.org/10.1007/978-3-319-32756-3
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1007/bf01719738 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037736752
    144 https://doi.org/10.1007/bf01719738
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1007/s10898-018-0642-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1101517830
    147 https://doi.org/10.1007/s10898-018-0642-1
    148 rdf:type schema:CreativeWork
    149 sg:pub.10.1007/s10898-020-00946-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1130995001
    150 https://doi.org/10.1007/s10898-020-00946-4
    151 rdf:type schema:CreativeWork
    152 sg:pub.10.1007/s10898-021-01022-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1137430609
    153 https://doi.org/10.1007/s10898-021-01022-1
    154 rdf:type schema:CreativeWork
    155 sg:pub.10.1007/s10957-005-5494-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008721920
    156 https://doi.org/10.1007/s10957-005-5494-4
    157 rdf:type schema:CreativeWork
    158 sg:pub.10.1007/s10957-013-0498-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1010309214
    159 https://doi.org/10.1007/s10957-013-0498-y
    160 rdf:type schema:CreativeWork
    161 sg:pub.10.1023/a:1009642405419 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053131829
    162 https://doi.org/10.1023/a:1009642405419
    163 rdf:type schema:CreativeWork
    164 grid-institutes:grid.445568.e schema:alternateName Warsaw School of Information Technology, ul. Newelska 6, 01-447, Warsaw, Poland
    165 schema:name Systems Research Institute, Polish Academy of Sciences, ul. Newelska 6, 01-447, Warsaw, Poland
    166 Warsaw School of Information Technology, ul. Newelska 6, 01-447, Warsaw, Poland
    167 rdf:type schema:Organization
    168 grid-institutes:grid.465202.7 schema:alternateName Systems Research Institute, Polish Academy of Sciences, ul. Newelska 6, 01-447, Warsaw, Poland
    169 schema:name Systems Research Institute, Polish Academy of Sciences, ul. Newelska 6, 01-447, Warsaw, Poland
    170 rdf:type schema:Organization
     




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


    ...