An Approximate Algorithm for Lexicographic Search in Multiple Orders for the Solution of the Multidimensional Boolean Knapsack Problem View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-07

AUTHORS

S. V. Chupov

ABSTRACT

A new scheme of approximate lexicographic search is proposed for the solution of the multidimensional Boolean knapsack problem. The main idea of the algorithm is to gradually define the lexicographic order (ordering of variables) in which “qualitative” solutions of the problem belong to a direct two-sided lexicographic constraint whose upper bound is the lexicographic maximum of the set of feasible solutions of the problem in this order. Since the search for “qualitative” solutions in each order is carried out on a bounded lexicographic interval, the proposed algorithm is called a bounded lexicographic search. The quality of the approximate method of bounded lexicographic search is investigated by solving test tasks from the well-known Beasley and Glover–Kochenberger sets. More... »

PAGES

563-575

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10559-018-0057-5

DOI

http://dx.doi.org/10.1007/s10559-018-0057-5

DIMENSIONS

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


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": "Uzhhorod National University", 
          "id": "https://www.grid.ac/institutes/grid.77512.36", 
          "name": [
            "Uzhhorod National University, Uzhhorod, Ukraine"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chupov", 
        "givenName": "S. V.", 
        "id": "sg:person.013767235045.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013767235045.43"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1057/jors.1990.166", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008396729", 
          "https://doi.org/10.1057/jors.1990.166"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.ejor.2004.01.024", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014433273"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.ejor.2007.06.068", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033943588"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10559-016-9855-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034255202", 
          "https://doi.org/10.1007/s10559-016-9855-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10559-016-9855-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034255202", 
          "https://doi.org/10.1007/s10559-016-9855-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4613-1361-8_25", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034396442", 
          "https://doi.org/10.1007/978-1-4613-1361-8_25"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0377-2217(03)00274-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035335840"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0377-2217(03)00274-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035335840"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4236/apm.2016.610055", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052452785"
        ], 
        "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"
      }
    ], 
    "datePublished": "2018-07", 
    "datePublishedReg": "2018-07-01", 
    "description": "A new scheme of approximate lexicographic search is proposed for the solution of the multidimensional Boolean knapsack problem. The main idea of the algorithm is to gradually define the lexicographic order (ordering of variables) in which \u201cqualitative\u201d solutions of the problem belong to a direct two-sided lexicographic constraint whose upper bound is the lexicographic maximum of the set of feasible solutions of the problem in this order. Since the search for \u201cqualitative\u201d solutions in each order is carried out on a bounded lexicographic interval, the proposed algorithm is called a bounded lexicographic search. The quality of the approximate method of bounded lexicographic search is investigated by solving test tasks from the well-known Beasley and Glover\u2013Kochenberger sets.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s10559-018-0057-5", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1130475", 
        "issn": [
          "1060-0396", 
          "1573-8337"
        ], 
        "name": "Cybernetics and Systems Analysis", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "54"
      }
    ], 
    "name": "An Approximate Algorithm for Lexicographic Search in Multiple Orders for the Solution of the Multidimensional Boolean Knapsack Problem", 
    "pagination": "563-575", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "e37288733cc9bb018edc1ecd2ce282427d274c3b96ad788b0cbe231b4d2b75d3"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10559-018-0057-5"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1105856410"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10559-018-0057-5", 
      "https://app.dimensions.ai/details/publication/pub.1105856410"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T10:16", 
    "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/0000000348_0000000348/records_54302_00000001.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs10559-018-0057-5"
  }
]
 

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/s10559-018-0057-5'

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/s10559-018-0057-5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10559-018-0057-5'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10559-018-0057-5'


 

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

89 TRIPLES      21 PREDICATES      35 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10559-018-0057-5 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N426598a5e09b4558ade21bc0b4029a3b
4 schema:citation sg:pub.10.1007/978-1-4613-1361-8_25
5 sg:pub.10.1007/s10559-016-9855-9
6 sg:pub.10.1023/a:1009642405419
7 sg:pub.10.1057/jors.1990.166
8 https://doi.org/10.1016/j.ejor.2004.01.024
9 https://doi.org/10.1016/j.ejor.2007.06.068
10 https://doi.org/10.1016/s0377-2217(03)00274-1
11 https://doi.org/10.4236/apm.2016.610055
12 schema:datePublished 2018-07
13 schema:datePublishedReg 2018-07-01
14 schema:description A new scheme of approximate lexicographic search is proposed for the solution of the multidimensional Boolean knapsack problem. The main idea of the algorithm is to gradually define the lexicographic order (ordering of variables) in which “qualitative” solutions of the problem belong to a direct two-sided lexicographic constraint whose upper bound is the lexicographic maximum of the set of feasible solutions of the problem in this order. Since the search for “qualitative” solutions in each order is carried out on a bounded lexicographic interval, the proposed algorithm is called a bounded lexicographic search. The quality of the approximate method of bounded lexicographic search is investigated by solving test tasks from the well-known Beasley and Glover–Kochenberger sets.
15 schema:genre research_article
16 schema:inLanguage en
17 schema:isAccessibleForFree false
18 schema:isPartOf N5e4411ea37984979b2d7fc383ae0cf5b
19 Na0922a91e1624f3ba335b8a11681266d
20 sg:journal.1130475
21 schema:name An Approximate Algorithm for Lexicographic Search in Multiple Orders for the Solution of the Multidimensional Boolean Knapsack Problem
22 schema:pagination 563-575
23 schema:productId N6239d67bf264450a86373696d94b5d67
24 N7282c3e276d54fba8273da093f839548
25 Ne0b9e5e75f1f4cc7b26eb5515da204f1
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105856410
27 https://doi.org/10.1007/s10559-018-0057-5
28 schema:sdDatePublished 2019-04-11T10:16
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher Ncb2f0fd890034c7b8915f9f40c66f3b2
31 schema:url https://link.springer.com/10.1007%2Fs10559-018-0057-5
32 sgo:license sg:explorer/license/
33 sgo:sdDataset articles
34 rdf:type schema:ScholarlyArticle
35 N426598a5e09b4558ade21bc0b4029a3b rdf:first sg:person.013767235045.43
36 rdf:rest rdf:nil
37 N5e4411ea37984979b2d7fc383ae0cf5b schema:volumeNumber 54
38 rdf:type schema:PublicationVolume
39 N6239d67bf264450a86373696d94b5d67 schema:name dimensions_id
40 schema:value pub.1105856410
41 rdf:type schema:PropertyValue
42 N7282c3e276d54fba8273da093f839548 schema:name doi
43 schema:value 10.1007/s10559-018-0057-5
44 rdf:type schema:PropertyValue
45 Na0922a91e1624f3ba335b8a11681266d schema:issueNumber 4
46 rdf:type schema:PublicationIssue
47 Ncb2f0fd890034c7b8915f9f40c66f3b2 schema:name Springer Nature - SN SciGraph project
48 rdf:type schema:Organization
49 Ne0b9e5e75f1f4cc7b26eb5515da204f1 schema:name readcube_id
50 schema:value e37288733cc9bb018edc1ecd2ce282427d274c3b96ad788b0cbe231b4d2b75d3
51 rdf:type schema:PropertyValue
52 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
53 schema:name Information and Computing Sciences
54 rdf:type schema:DefinedTerm
55 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
56 schema:name Artificial Intelligence and Image Processing
57 rdf:type schema:DefinedTerm
58 sg:journal.1130475 schema:issn 1060-0396
59 1573-8337
60 schema:name Cybernetics and Systems Analysis
61 rdf:type schema:Periodical
62 sg:person.013767235045.43 schema:affiliation https://www.grid.ac/institutes/grid.77512.36
63 schema:familyName Chupov
64 schema:givenName S. V.
65 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013767235045.43
66 rdf:type schema:Person
67 sg:pub.10.1007/978-1-4613-1361-8_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034396442
68 https://doi.org/10.1007/978-1-4613-1361-8_25
69 rdf:type schema:CreativeWork
70 sg:pub.10.1007/s10559-016-9855-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034255202
71 https://doi.org/10.1007/s10559-016-9855-9
72 rdf:type schema:CreativeWork
73 sg:pub.10.1023/a:1009642405419 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053131829
74 https://doi.org/10.1023/a:1009642405419
75 rdf:type schema:CreativeWork
76 sg:pub.10.1057/jors.1990.166 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008396729
77 https://doi.org/10.1057/jors.1990.166
78 rdf:type schema:CreativeWork
79 https://doi.org/10.1016/j.ejor.2004.01.024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014433273
80 rdf:type schema:CreativeWork
81 https://doi.org/10.1016/j.ejor.2007.06.068 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033943588
82 rdf:type schema:CreativeWork
83 https://doi.org/10.1016/s0377-2217(03)00274-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035335840
84 rdf:type schema:CreativeWork
85 https://doi.org/10.4236/apm.2016.610055 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052452785
86 rdf:type schema:CreativeWork
87 https://www.grid.ac/institutes/grid.77512.36 schema:alternateName Uzhhorod National University
88 schema:name Uzhhorod National University, Uzhhorod, Ukraine
89 rdf:type schema:Organization
 




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


...