Tailoring Instances of the 1D Bin Packing Problem for Assessing Strengths and Weaknesses of Its Solvers View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-08-21

AUTHORS

Ivan Amaya , José Carlos Ortiz-Bayliss , Santiago Enrique Conant-Pablos , Hugo Terashima-Marín , Carlos A. Coello Coello

ABSTRACT

Solvers for different combinatorial optimization problems have evolved throughout the years. These can range from simple strategies such as basic heuristics, to advanced models such as metaheuristics and hyper-heuristics. Even so, the set of benchmark instances has remained almost unaltered. Thus, any analysis of solvers has been limited to assessing their performance under those scenarios. Even if this has been fruitful, we deem necessary to provide a tool that allows for a better study of each available solver. Because of that, in this paper we present a tool for assessing the strengths and weaknesses of different solvers, by tailoring a set of instances for each of them. We propose an evolutionary-based model and test our idea on four different basic heuristics for the 1D bin packing problem. This, however, does not limit the scope of our proposal, since it can be used in other domains and for other solvers with few changes. By pursuing an in-depth study of such tailored instances, more relevant knowledge about each solver can be derived. More... »

PAGES

373-384

Book

TITLE

Parallel Problem Solving from Nature – PPSN XV

ISBN

978-3-319-99258-7
978-3-319-99259-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-99259-4_30

DOI

http://dx.doi.org/10.1007/978-3-319-99259-4_30

DIMENSIONS

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


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/17", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology and Cognitive Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1701", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "School of Engineering and Sciences, Tecnologico de Monterrey, Monterrey, Mexico", 
          "id": "http://www.grid.ac/institutes/grid.419886.a", 
          "name": [
            "School of Engineering and Sciences, Tecnologico de Monterrey, Monterrey, Mexico"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Amaya", 
        "givenName": "Ivan", 
        "id": "sg:person.011101442012.32", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011101442012.32"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "School of Engineering and Sciences, Tecnologico de Monterrey, Monterrey, Mexico", 
          "id": "http://www.grid.ac/institutes/grid.419886.a", 
          "name": [
            "School of Engineering and Sciences, Tecnologico de Monterrey, Monterrey, Mexico"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ortiz-Bayliss", 
        "givenName": "Jos\u00e9 Carlos", 
        "id": "sg:person.013420763115.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013420763115.19"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "School of Engineering and Sciences, Tecnologico de Monterrey, Monterrey, Mexico", 
          "id": "http://www.grid.ac/institutes/grid.419886.a", 
          "name": [
            "School of Engineering and Sciences, Tecnologico de Monterrey, Monterrey, Mexico"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Conant-Pablos", 
        "givenName": "Santiago Enrique", 
        "id": "sg:person.01361510467.59", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01361510467.59"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "School of Engineering and Sciences, Tecnologico de Monterrey, Monterrey, Mexico", 
          "id": "http://www.grid.ac/institutes/grid.419886.a", 
          "name": [
            "School of Engineering and Sciences, Tecnologico de Monterrey, Monterrey, Mexico"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Terashima-Mar\u00edn", 
        "givenName": "Hugo", 
        "id": "sg:person.015346177635.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015346177635.19"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "CINVESTAV-IPN (Evolutionary Computation Group), Mexico City, Mexico", 
          "id": "http://www.grid.ac/institutes/grid.418275.d", 
          "name": [
            "CINVESTAV-IPN (Evolutionary Computation Group), Mexico City, Mexico"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Coello Coello", 
        "givenName": "Carlos A.", 
        "id": "sg:person.01345625161.61", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01345625161.61"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2018-08-21", 
    "datePublishedReg": "2018-08-21", 
    "description": "Solvers for different combinatorial optimization problems have evolved throughout the years. These can range from simple strategies such as basic heuristics, to advanced models such as metaheuristics and hyper-heuristics. Even so, the set of benchmark instances has remained almost unaltered. Thus, any analysis of solvers has been limited to assessing their performance under those scenarios. Even if this has been fruitful, we deem necessary to provide a tool that allows for a better study of each available solver. Because of that, in this paper we present a tool for assessing the strengths and weaknesses of different solvers, by tailoring a set of instances for each of them. We propose an evolutionary-based model and test our idea on four different basic heuristics for the 1D bin packing problem. This, however, does not limit the scope of our proposal, since it can be used in other domains and for other solvers with few changes. By pursuing an in-depth study of such tailored instances, more relevant knowledge about each solver can be derived.", 
    "editor": [
      {
        "familyName": "Auger", 
        "givenName": "Anne", 
        "type": "Person"
      }, 
      {
        "familyName": "Fonseca", 
        "givenName": "Carlos M.", 
        "type": "Person"
      }, 
      {
        "familyName": "Louren\u00e7o", 
        "givenName": "Nuno", 
        "type": "Person"
      }, 
      {
        "familyName": "Machado", 
        "givenName": "Penousal", 
        "type": "Person"
      }, 
      {
        "familyName": "Paquete", 
        "givenName": "Lu\u00eds", 
        "type": "Person"
      }, 
      {
        "familyName": "Whitley", 
        "givenName": "Darrell", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-99259-4_30", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-99258-7", 
        "978-3-319-99259-4"
      ], 
      "name": "Parallel Problem Solving from Nature \u2013 PPSN XV", 
      "type": "Book"
    }, 
    "keywords": [
      "evolutionary-based model", 
      "domain", 
      "depth study", 
      "tool", 
      "study", 
      "simple strategy", 
      "analysis", 
      "changes", 
      "set", 
      "strategies", 
      "knowledge", 
      "instances", 
      "model", 
      "years", 
      "scenarios", 
      "better studies", 
      "advanced models", 
      "relevant knowledge", 
      "scope", 
      "idea", 
      "proposal", 
      "strength", 
      "weakness", 
      "problem", 
      "performance", 
      "paper", 
      "different combinatorial optimization problems", 
      "basic heuristics", 
      "combinatorial optimization problems", 
      "optimization problem", 
      "available solvers", 
      "set of instances", 
      "bin packing problem", 
      "packing problem", 
      "solver", 
      "heuristics", 
      "benchmark instances", 
      "different solvers", 
      "metaheuristics", 
      "analysis of solvers", 
      "different basic heuristics", 
      "Assessing Strengths"
    ], 
    "name": "Tailoring Instances of the 1D Bin Packing Problem for Assessing Strengths and Weaknesses of Its Solvers", 
    "pagination": "373-384", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1106254458"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-99259-4_30"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-99259-4_30", 
      "https://app.dimensions.ai/details/publication/pub.1106254458"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:05", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_323.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-99259-4_30"
  }
]
 

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/978-3-319-99259-4_30'

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/978-3-319-99259-4_30'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-99259-4_30'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-99259-4_30'


 

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

158 TRIPLES      23 PREDICATES      67 URIs      60 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-99259-4_30 schema:about anzsrc-for:17
2 anzsrc-for:1701
3 schema:author Nc7f02dd69dd7411a9a64387471c4d91e
4 schema:datePublished 2018-08-21
5 schema:datePublishedReg 2018-08-21
6 schema:description Solvers for different combinatorial optimization problems have evolved throughout the years. These can range from simple strategies such as basic heuristics, to advanced models such as metaheuristics and hyper-heuristics. Even so, the set of benchmark instances has remained almost unaltered. Thus, any analysis of solvers has been limited to assessing their performance under those scenarios. Even if this has been fruitful, we deem necessary to provide a tool that allows for a better study of each available solver. Because of that, in this paper we present a tool for assessing the strengths and weaknesses of different solvers, by tailoring a set of instances for each of them. We propose an evolutionary-based model and test our idea on four different basic heuristics for the 1D bin packing problem. This, however, does not limit the scope of our proposal, since it can be used in other domains and for other solvers with few changes. By pursuing an in-depth study of such tailored instances, more relevant knowledge about each solver can be derived.
7 schema:editor N40788996536b4a5a992bc1afc3b57458
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N025896428a3f42f699a367916cf405f5
12 schema:keywords Assessing Strengths
13 advanced models
14 analysis
15 analysis of solvers
16 available solvers
17 basic heuristics
18 benchmark instances
19 better studies
20 bin packing problem
21 changes
22 combinatorial optimization problems
23 depth study
24 different basic heuristics
25 different combinatorial optimization problems
26 different solvers
27 domain
28 evolutionary-based model
29 heuristics
30 idea
31 instances
32 knowledge
33 metaheuristics
34 model
35 optimization problem
36 packing problem
37 paper
38 performance
39 problem
40 proposal
41 relevant knowledge
42 scenarios
43 scope
44 set
45 set of instances
46 simple strategy
47 solver
48 strategies
49 strength
50 study
51 tool
52 weakness
53 years
54 schema:name Tailoring Instances of the 1D Bin Packing Problem for Assessing Strengths and Weaknesses of Its Solvers
55 schema:pagination 373-384
56 schema:productId N178f4a43e8584fcfab0ac60ab33ed07c
57 N96e85adf0b5142649ce07a764d518d42
58 schema:publisher N4fe8c58ed7444f2089f8f3eb6a9887ab
59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1106254458
60 https://doi.org/10.1007/978-3-319-99259-4_30
61 schema:sdDatePublished 2021-12-01T20:05
62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
63 schema:sdPublisher Nb42240a906494d439575f770648b8694
64 schema:url https://doi.org/10.1007/978-3-319-99259-4_30
65 sgo:license sg:explorer/license/
66 sgo:sdDataset chapters
67 rdf:type schema:Chapter
68 N025896428a3f42f699a367916cf405f5 schema:isbn 978-3-319-99258-7
69 978-3-319-99259-4
70 schema:name Parallel Problem Solving from Nature – PPSN XV
71 rdf:type schema:Book
72 N0b9d2610ceeb499a8b99c76b02b255a7 schema:familyName Auger
73 schema:givenName Anne
74 rdf:type schema:Person
75 N0f30e195b6084d9a83a8637ceb34fd97 rdf:first sg:person.013420763115.19
76 rdf:rest N99f49bd09189402eb74c4ce5ec7ad293
77 N178f4a43e8584fcfab0ac60ab33ed07c schema:name doi
78 schema:value 10.1007/978-3-319-99259-4_30
79 rdf:type schema:PropertyValue
80 N1940e9ca7af84e2d8c4f2598fc775c68 schema:familyName Fonseca
81 schema:givenName Carlos M.
82 rdf:type schema:Person
83 N271b575247b04960aca6b1949e373b26 rdf:first N76e18ecc0b1145599bb37243edb1e1d0
84 rdf:rest rdf:nil
85 N40788996536b4a5a992bc1afc3b57458 rdf:first N0b9d2610ceeb499a8b99c76b02b255a7
86 rdf:rest Ndbec3285b0df4ab380b7a756b427b590
87 N4fe8c58ed7444f2089f8f3eb6a9887ab schema:name Springer Nature
88 rdf:type schema:Organisation
89 N76e18ecc0b1145599bb37243edb1e1d0 schema:familyName Whitley
90 schema:givenName Darrell
91 rdf:type schema:Person
92 N96e85adf0b5142649ce07a764d518d42 schema:name dimensions_id
93 schema:value pub.1106254458
94 rdf:type schema:PropertyValue
95 N9785902ffaef41fb8262bb9f88769370 rdf:first sg:person.01345625161.61
96 rdf:rest rdf:nil
97 N99f49bd09189402eb74c4ce5ec7ad293 rdf:first sg:person.01361510467.59
98 rdf:rest Nb5d4c30fd3ac478e882d04cc0796d579
99 Nacd17e43edbd4824bae56c4927b4e0cf rdf:first Ncaab116dd0f34c30a1172257eff0ae15
100 rdf:rest Nee703b2fb87941b1b06118933a2b5e28
101 Nade56db8ade648879ddcf4f870f645bc schema:familyName Paquete
102 schema:givenName Luís
103 rdf:type schema:Person
104 Nb42240a906494d439575f770648b8694 schema:name Springer Nature - SN SciGraph project
105 rdf:type schema:Organization
106 Nb5d4c30fd3ac478e882d04cc0796d579 rdf:first sg:person.015346177635.19
107 rdf:rest N9785902ffaef41fb8262bb9f88769370
108 Nc7f02dd69dd7411a9a64387471c4d91e rdf:first sg:person.011101442012.32
109 rdf:rest N0f30e195b6084d9a83a8637ceb34fd97
110 Nc89e297684854f559d051e9cbb52fbf2 schema:familyName Machado
111 schema:givenName Penousal
112 rdf:type schema:Person
113 Ncaab116dd0f34c30a1172257eff0ae15 schema:familyName Lourenço
114 schema:givenName Nuno
115 rdf:type schema:Person
116 Ncedfd66a5a0b427ba69332a0aae4ee5c rdf:first Nade56db8ade648879ddcf4f870f645bc
117 rdf:rest N271b575247b04960aca6b1949e373b26
118 Ndbec3285b0df4ab380b7a756b427b590 rdf:first N1940e9ca7af84e2d8c4f2598fc775c68
119 rdf:rest Nacd17e43edbd4824bae56c4927b4e0cf
120 Nee703b2fb87941b1b06118933a2b5e28 rdf:first Nc89e297684854f559d051e9cbb52fbf2
121 rdf:rest Ncedfd66a5a0b427ba69332a0aae4ee5c
122 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
123 schema:name Psychology and Cognitive Sciences
124 rdf:type schema:DefinedTerm
125 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
126 schema:name Psychology
127 rdf:type schema:DefinedTerm
128 sg:person.011101442012.32 schema:affiliation grid-institutes:grid.419886.a
129 schema:familyName Amaya
130 schema:givenName Ivan
131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011101442012.32
132 rdf:type schema:Person
133 sg:person.013420763115.19 schema:affiliation grid-institutes:grid.419886.a
134 schema:familyName Ortiz-Bayliss
135 schema:givenName José Carlos
136 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013420763115.19
137 rdf:type schema:Person
138 sg:person.01345625161.61 schema:affiliation grid-institutes:grid.418275.d
139 schema:familyName Coello Coello
140 schema:givenName Carlos A.
141 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01345625161.61
142 rdf:type schema:Person
143 sg:person.01361510467.59 schema:affiliation grid-institutes:grid.419886.a
144 schema:familyName Conant-Pablos
145 schema:givenName Santiago Enrique
146 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01361510467.59
147 rdf:type schema:Person
148 sg:person.015346177635.19 schema:affiliation grid-institutes:grid.419886.a
149 schema:familyName Terashima-Marín
150 schema:givenName Hugo
151 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015346177635.19
152 rdf:type schema:Person
153 grid-institutes:grid.418275.d schema:alternateName CINVESTAV-IPN (Evolutionary Computation Group), Mexico City, Mexico
154 schema:name CINVESTAV-IPN (Evolutionary Computation Group), Mexico City, Mexico
155 rdf:type schema:Organization
156 grid-institutes:grid.419886.a schema:alternateName School of Engineering and Sciences, Tecnologico de Monterrey, Monterrey, Mexico
157 schema:name School of Engineering and Sciences, Tecnologico de Monterrey, Monterrey, Mexico
158 rdf:type schema:Organization
 




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


...