Computing and Selecting ε-Efficient Solutions of {0, 1}-Knapsack Problems View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2009-10-21

AUTHORS

Emilia Tantar , Oliver Schütze , José Rui Figueira , Carlos A. Coello Coello , El-Ghazali Talbi

ABSTRACT

This work deals with the computation and the selection of approximate – or ε-efficient – solutions of {0, 1}-knapsack problems. By allowing approximate solutions in general a much larger variety of possibilities for the underlying problem is offered to the decision maker. We enlighten the gap that can occur when passing ε-approximate solutions from the objective space into the parameter space (in terms of neighborhood). In this paper, we propose a novel adaptive ε-approximation based stochastic algorithm for the computation of the entire set of ε-efficient solutions, state a convergence result, and address the related decision making problem. For the latter we propose an interactive selection process which is intended to help the decision maker to understand the landscape of the obtained solutions. More... »

PAGES

379-389

Book

TITLE

Multiple Criteria Decision Making for Sustainable Energy and Transportation Systems

ISBN

978-3-642-04044-3
978-3-642-04045-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-04045-0_32

DOI

http://dx.doi.org/10.1007/978-3-642-04045-0_32

DIMENSIONS

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


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/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "INRIA Lille-Nord Europe, LIFL (UMR USTL/CNRS 8022), Parc Scientifique de la Haute Borne 40, avenue Halley B\u00e2t.A, Park Plaza, 59650, Villeneuve d\u2019Ascq C\u00e9dex, France", 
          "id": "http://www.grid.ac/institutes/grid.457352.2", 
          "name": [
            "INRIA Lille-Nord Europe, LIFL (UMR USTL/CNRS 8022), Parc Scientifique de la Haute Borne 40, avenue Halley B\u00e2t.A, Park Plaza, 59650, Villeneuve d\u2019Ascq C\u00e9dex, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tantar", 
        "givenName": "Emilia", 
        "id": "sg:person.014120034333.51", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014120034333.51"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "Sch\u00fctze", 
        "givenName": "Oliver", 
        "id": "sg:person.016044046023.99", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016044046023.99"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "Figueira", 
        "givenName": "Jos\u00e9 Rui", 
        "id": "sg:person.01241703202.23", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01241703202.23"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "Coello", 
        "givenName": "Carlos A. Coello", 
        "id": "sg:person.012160505340.13", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012160505340.13"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "Talbi", 
        "givenName": "El-Ghazali", 
        "id": "sg:person.010541644207.95", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010541644207.95"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009-10-21", 
    "datePublishedReg": "2009-10-21", 
    "description": "This work deals with the computation and the selection of approximate \u2013 or \u03b5-efficient \u2013 solutions of {0, 1}-knapsack problems. By allowing approximate solutions in general a much larger variety of possibilities for the underlying problem is offered to the decision maker. We enlighten the gap that can occur when passing \u03b5-approximate solutions from the objective space into the parameter space (in terms of neighborhood). In this paper, we propose a novel adaptive \u03b5-approximation based stochastic algorithm for the computation of the entire set of \u03b5-efficient solutions, state a convergence result, and address the related decision making problem. For the latter we propose an interactive selection process which is intended to help the decision maker to understand the landscape of the obtained solutions.", 
    "editor": [
      {
        "familyName": "Ehrgott", 
        "givenName": "Matthias", 
        "type": "Person"
      }, 
      {
        "familyName": "Naujoks", 
        "givenName": "Boris", 
        "type": "Person"
      }, 
      {
        "familyName": "Stewart", 
        "givenName": "Theodor J.", 
        "type": "Person"
      }, 
      {
        "familyName": "Wallenius", 
        "givenName": "Jyrki", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-04045-0_32", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-04044-3", 
        "978-3-642-04045-0"
      ], 
      "name": "Multiple Criteria Decision Making for Sustainable Energy and Transportation Systems", 
      "type": "Book"
    }, 
    "keywords": [
      "approximate solution", 
      "knapsack problem", 
      "efficient solution", 
      "stochastic algorithm", 
      "objective space", 
      "convergence results", 
      "interactive selection process", 
      "parameter space", 
      "computation", 
      "problem", 
      "solution", 
      "space", 
      "approximation", 
      "decision makers", 
      "entire set", 
      "large variety", 
      "algorithm", 
      "set", 
      "related decisions", 
      "selection process", 
      "gap", 
      "work", 
      "results", 
      "selection", 
      "possibility", 
      "variety", 
      "process", 
      "makers", 
      "decisions", 
      "landscape", 
      "paper", 
      "Selecting \u03b5"
    ], 
    "name": "Computing and Selecting \u03b5-Efficient Solutions of {0, 1}-Knapsack Problems", 
    "pagination": "379-389", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1018148320"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-04045-0_32"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-04045-0_32", 
      "https://app.dimensions.ai/details/publication/pub.1018148320"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:12", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_221.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-04045-0_32"
  }
]
 

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-642-04045-0_32'

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-642-04045-0_32'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-04045-0_32'

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-642-04045-0_32'


 

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

131 TRIPLES      23 PREDICATES      57 URIs      50 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-04045-0_32 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author N2d0495fd699c4fe1837a4a80133bb4eb
4 schema:datePublished 2009-10-21
5 schema:datePublishedReg 2009-10-21
6 schema:description This work deals with the computation and the selection of approximate – or ε-efficient – solutions of {0, 1}-knapsack problems. By allowing approximate solutions in general a much larger variety of possibilities for the underlying problem is offered to the decision maker. We enlighten the gap that can occur when passing ε-approximate solutions from the objective space into the parameter space (in terms of neighborhood). In this paper, we propose a novel adaptive ε-approximation based stochastic algorithm for the computation of the entire set of ε-efficient solutions, state a convergence result, and address the related decision making problem. For the latter we propose an interactive selection process which is intended to help the decision maker to understand the landscape of the obtained solutions.
7 schema:editor N2a48429d442c44698725abdb1a82cc8a
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N558482b2e4664383a0b9a5303740176d
12 schema:keywords Selecting ε
13 algorithm
14 approximate solution
15 approximation
16 computation
17 convergence results
18 decision makers
19 decisions
20 efficient solution
21 entire set
22 gap
23 interactive selection process
24 knapsack problem
25 landscape
26 large variety
27 makers
28 objective space
29 paper
30 parameter space
31 possibility
32 problem
33 process
34 related decisions
35 results
36 selection
37 selection process
38 set
39 solution
40 space
41 stochastic algorithm
42 variety
43 work
44 schema:name Computing and Selecting ε-Efficient Solutions of {0, 1}-Knapsack Problems
45 schema:pagination 379-389
46 schema:productId N54d4f2b485e84f8aace05ccf7f21944f
47 Nc34ee145908c41e480fdd34ee134044b
48 schema:publisher N1c58f66773934f3dabe21565f0415945
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018148320
50 https://doi.org/10.1007/978-3-642-04045-0_32
51 schema:sdDatePublished 2022-01-01T19:12
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N9a6318c83c0b4857a0564db941d042bd
54 schema:url https://doi.org/10.1007/978-3-642-04045-0_32
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N1c58f66773934f3dabe21565f0415945 schema:name Springer Nature
59 rdf:type schema:Organisation
60 N2a48429d442c44698725abdb1a82cc8a rdf:first N8b5fcd970ba641de846b45bb42c070c5
61 rdf:rest Nfcd0aa2910ba4575b2dc2ae8043ccf12
62 N2d0495fd699c4fe1837a4a80133bb4eb rdf:first sg:person.014120034333.51
63 rdf:rest N5114cb828364464b9ed4155458d5bda6
64 N5114cb828364464b9ed4155458d5bda6 rdf:first sg:person.016044046023.99
65 rdf:rest Nb4eb501a32a4434bb7f41c92dd9057ea
66 N54d4f2b485e84f8aace05ccf7f21944f schema:name doi
67 schema:value 10.1007/978-3-642-04045-0_32
68 rdf:type schema:PropertyValue
69 N558482b2e4664383a0b9a5303740176d schema:isbn 978-3-642-04044-3
70 978-3-642-04045-0
71 schema:name Multiple Criteria Decision Making for Sustainable Energy and Transportation Systems
72 rdf:type schema:Book
73 N631af49264214006ae6201d31cd3023a rdf:first sg:person.012160505340.13
74 rdf:rest Nfe66819cc2104a4f9aee4874a8153202
75 N66d31736b85d4f10a247274956c254f6 rdf:first Nef92771cd5654173b1cc3bc4d55c5ab7
76 rdf:rest Na7e5e460385840b3aa5736c66202b3bd
77 N6d85dbbc5c074c76acdf02aff0c793e7 schema:familyName Naujoks
78 schema:givenName Boris
79 rdf:type schema:Person
80 N7a41cddedc284faf803634f96867c808 schema:familyName Wallenius
81 schema:givenName Jyrki
82 rdf:type schema:Person
83 N8b5fcd970ba641de846b45bb42c070c5 schema:familyName Ehrgott
84 schema:givenName Matthias
85 rdf:type schema:Person
86 N9a6318c83c0b4857a0564db941d042bd schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 Na7e5e460385840b3aa5736c66202b3bd rdf:first N7a41cddedc284faf803634f96867c808
89 rdf:rest rdf:nil
90 Nb4eb501a32a4434bb7f41c92dd9057ea rdf:first sg:person.01241703202.23
91 rdf:rest N631af49264214006ae6201d31cd3023a
92 Nc34ee145908c41e480fdd34ee134044b schema:name dimensions_id
93 schema:value pub.1018148320
94 rdf:type schema:PropertyValue
95 Nef92771cd5654173b1cc3bc4d55c5ab7 schema:familyName Stewart
96 schema:givenName Theodor J.
97 rdf:type schema:Person
98 Nfcd0aa2910ba4575b2dc2ae8043ccf12 rdf:first N6d85dbbc5c074c76acdf02aff0c793e7
99 rdf:rest N66d31736b85d4f10a247274956c254f6
100 Nfe66819cc2104a4f9aee4874a8153202 rdf:first sg:person.010541644207.95
101 rdf:rest rdf:nil
102 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
103 schema:name Mathematical Sciences
104 rdf:type schema:DefinedTerm
105 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
106 schema:name Applied Mathematics
107 rdf:type schema:DefinedTerm
108 sg:person.010541644207.95 schema:familyName Talbi
109 schema:givenName El-Ghazali
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010541644207.95
111 rdf:type schema:Person
112 sg:person.012160505340.13 schema:familyName Coello
113 schema:givenName Carlos A. Coello
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012160505340.13
115 rdf:type schema:Person
116 sg:person.01241703202.23 schema:familyName Figueira
117 schema:givenName José Rui
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01241703202.23
119 rdf:type schema:Person
120 sg:person.014120034333.51 schema:affiliation grid-institutes:grid.457352.2
121 schema:familyName Tantar
122 schema:givenName Emilia
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014120034333.51
124 rdf:type schema:Person
125 sg:person.016044046023.99 schema:familyName Schütze
126 schema:givenName Oliver
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016044046023.99
128 rdf:type schema:Person
129 grid-institutes:grid.457352.2 schema:alternateName INRIA Lille-Nord Europe, LIFL (UMR USTL/CNRS 8022), Parc Scientifique de la Haute Borne 40, avenue Halley Bât.A, Park Plaza, 59650, Villeneuve d’Ascq Cédex, France
130 schema:name INRIA Lille-Nord Europe, LIFL (UMR USTL/CNRS 8022), Parc Scientifique de la Haute Borne 40, avenue Halley Bât.A, Park Plaza, 59650, Villeneuve d’Ascq Cédex, France
131 rdf:type schema:Organization
 




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


...