Implementing Branch-and-Bound Algorithms on a Cluster of Workstations — A Survey, Some New Results and Open Problems View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1991

AUTHORS

Alfred Taudes , Thomas Netousek

ABSTRACT

Networks of workstations running under a multiuser, multitasking operating system like UNIX are an increasingly commonplace personal computing environment. Due to their use as personal computers these workstations are typically underutilized most of the time. Thus it is attractive to develop software to use the ample free computing resources to configure a loosely coupled multicomputer to solve computation intensive problems in a distributed fashion. In this paper we discuss the feasibility of implementing Branch-and-Bound algorithms for combinatorial optimization on a cluster of workstations. There by we use experiences made by us when solving the Vertex-Cover-Problem on a cluster of 8 HP 9000/330 workstations under HP-UX connected via Ethernet and reports from literature about combinatorial optimization on multicomputers. Besides presenting performance results we discuss programming techniques for balancing the workload, for interprocess communication and for distributed termination. Based on this evidence we conclude that given proper tuning a distributed Branch-and-Bound algorithm can yield satisfactory speed-up on a cluster of workstations. However, tools are needed that make the development and run-time control of such applications easier while preserving the favourable efficiency. More... »

PAGES

79-102

References to SciGraph publications

Book

TITLE

Parallel Computing and Mathematical Optimization

ISBN

978-3-540-54434-0
978-3-642-95665-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-95665-2_6

DOI

http://dx.doi.org/10.1007/978-3-642-95665-2_6

DIMENSIONS

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


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/0803", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computer Software", 
        "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": "Vienna University of Economics and Business", 
          "id": "https://www.grid.ac/institutes/grid.15788.33", 
          "name": [
            "Department of Applied Computer Science, Institute of Information Processing and Information Economics, Vienna University of Economics and Business Administration, Augasse 2-6, A-1090\u00a0Vienna, Austria"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Taudes", 
        "givenName": "Alfred", 
        "id": "sg:person.010346251263.14", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010346251263.14"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Vienna University of Economics and Business", 
          "id": "https://www.grid.ac/institutes/grid.15788.33", 
          "name": [
            "Department of Applied Computer Science, Institute of Information Processing and Information Economics, Vienna University of Economics and Business Administration, Augasse 2-6, A-1090\u00a0Vienna, Austria"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Netousek", 
        "givenName": "Thomas", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/3-540-51687-5_40", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000721793", 
          "https://doi.org/10.1007/3-540-51687-5_40"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/358080.358103", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017244639"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/22719.24067", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029110657"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/2.53355", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061105654"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/52.1990", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061185275"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.14.4.699", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064726998"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1991", 
    "datePublishedReg": "1991-01-01", 
    "description": "Networks of workstations running under a multiuser, multitasking operating system like UNIX are an increasingly commonplace personal computing environment. Due to their use as personal computers these workstations are typically underutilized most of the time. Thus it is attractive to develop software to use the ample free computing resources to configure a loosely coupled multicomputer to solve computation intensive problems in a distributed fashion. In this paper we discuss the feasibility of implementing Branch-and-Bound algorithms for combinatorial optimization on a cluster of workstations. There by we use experiences made by us when solving the Vertex-Cover-Problem on a cluster of 8 HP 9000/330 workstations under HP-UX connected via Ethernet and reports from literature about combinatorial optimization on multicomputers. Besides presenting performance results we discuss programming techniques for balancing the workload, for interprocess communication and for distributed termination. Based on this evidence we conclude that given proper tuning a distributed Branch-and-Bound algorithm can yield satisfactory speed-up on a cluster of workstations. However, tools are needed that make the development and run-time control of such applications easier while preserving the favourable efficiency.", 
    "editor": [
      {
        "familyName": "Grauer", 
        "givenName": "Manfred", 
        "type": "Person"
      }, 
      {
        "familyName": "Pressmar", 
        "givenName": "Dieter B.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-95665-2_6", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-54434-0", 
        "978-3-642-95665-2"
      ], 
      "name": "Parallel Computing and Mathematical Optimization", 
      "type": "Book"
    }, 
    "name": "Implementing Branch-and-Bound Algorithms on a Cluster of Workstations \u2014 A Survey, Some New Results and Open Problems", 
    "pagination": "79-102", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-95665-2_6"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "ef7a1d1e5465cff044002e8c3fdb896b62626a553e2181475ac6ac12c6c8fd4c"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1050271166"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-95665-2_6", 
      "https://app.dimensions.ai/details/publication/pub.1050271166"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T00:52", 
    "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/0000000001_0000000264/records_8700_00000274.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-642-95665-2_6"
  }
]
 

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-95665-2_6'

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-95665-2_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-95665-2_6'

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-95665-2_6'


 

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

95 TRIPLES      23 PREDICATES      33 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-95665-2_6 schema:about anzsrc-for:08
2 anzsrc-for:0803
3 schema:author N95ea47995249497e8f2b3e08838acd3e
4 schema:citation sg:pub.10.1007/3-540-51687-5_40
5 https://doi.org/10.1109/2.53355
6 https://doi.org/10.1109/52.1990
7 https://doi.org/10.1145/22719.24067
8 https://doi.org/10.1145/358080.358103
9 https://doi.org/10.1287/opre.14.4.699
10 schema:datePublished 1991
11 schema:datePublishedReg 1991-01-01
12 schema:description Networks of workstations running under a multiuser, multitasking operating system like UNIX are an increasingly commonplace personal computing environment. Due to their use as personal computers these workstations are typically underutilized most of the time. Thus it is attractive to develop software to use the ample free computing resources to configure a loosely coupled multicomputer to solve computation intensive problems in a distributed fashion. In this paper we discuss the feasibility of implementing Branch-and-Bound algorithms for combinatorial optimization on a cluster of workstations. There by we use experiences made by us when solving the Vertex-Cover-Problem on a cluster of 8 HP 9000/330 workstations under HP-UX connected via Ethernet and reports from literature about combinatorial optimization on multicomputers. Besides presenting performance results we discuss programming techniques for balancing the workload, for interprocess communication and for distributed termination. Based on this evidence we conclude that given proper tuning a distributed Branch-and-Bound algorithm can yield satisfactory speed-up on a cluster of workstations. However, tools are needed that make the development and run-time control of such applications easier while preserving the favourable efficiency.
13 schema:editor N6d6cd7d344224c1c9e7fd73e9460d2f8
14 schema:genre chapter
15 schema:inLanguage en
16 schema:isAccessibleForFree false
17 schema:isPartOf Nf89fe1ebbf2a4957a21aca012a247c05
18 schema:name Implementing Branch-and-Bound Algorithms on a Cluster of Workstations — A Survey, Some New Results and Open Problems
19 schema:pagination 79-102
20 schema:productId N833cfd138cd94cd8901513a2711b76f4
21 N8bc4bd95c40843079180387f218e684a
22 Nf677125fb48f466cbe4da36bed462992
23 schema:publisher Nbe549fa44d4649e68f248f0129db2f83
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050271166
25 https://doi.org/10.1007/978-3-642-95665-2_6
26 schema:sdDatePublished 2019-04-16T00:52
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher Nbbcb1eff1d7f4ba08234d4912e9fe4bd
29 schema:url http://link.springer.com/10.1007/978-3-642-95665-2_6
30 sgo:license sg:explorer/license/
31 sgo:sdDataset chapters
32 rdf:type schema:Chapter
33 N21071b218a29436eab420eb391d80575 rdf:first Nb76612eb95334f4182842f84dda0b7d3
34 rdf:rest rdf:nil
35 N6d6cd7d344224c1c9e7fd73e9460d2f8 rdf:first N9a20e718c7ae4c158a541fe96952b287
36 rdf:rest N76cd5db6c17b42edb8832a805c70753c
37 N76cd5db6c17b42edb8832a805c70753c rdf:first Nfe187dd860214cdda1deb1158c19eff3
38 rdf:rest rdf:nil
39 N833cfd138cd94cd8901513a2711b76f4 schema:name doi
40 schema:value 10.1007/978-3-642-95665-2_6
41 rdf:type schema:PropertyValue
42 N8bc4bd95c40843079180387f218e684a schema:name readcube_id
43 schema:value ef7a1d1e5465cff044002e8c3fdb896b62626a553e2181475ac6ac12c6c8fd4c
44 rdf:type schema:PropertyValue
45 N95ea47995249497e8f2b3e08838acd3e rdf:first sg:person.010346251263.14
46 rdf:rest N21071b218a29436eab420eb391d80575
47 N9a20e718c7ae4c158a541fe96952b287 schema:familyName Grauer
48 schema:givenName Manfred
49 rdf:type schema:Person
50 Nb76612eb95334f4182842f84dda0b7d3 schema:affiliation https://www.grid.ac/institutes/grid.15788.33
51 schema:familyName Netousek
52 schema:givenName Thomas
53 rdf:type schema:Person
54 Nbbcb1eff1d7f4ba08234d4912e9fe4bd schema:name Springer Nature - SN SciGraph project
55 rdf:type schema:Organization
56 Nbe549fa44d4649e68f248f0129db2f83 schema:location Berlin, Heidelberg
57 schema:name Springer Berlin Heidelberg
58 rdf:type schema:Organisation
59 Nf677125fb48f466cbe4da36bed462992 schema:name dimensions_id
60 schema:value pub.1050271166
61 rdf:type schema:PropertyValue
62 Nf89fe1ebbf2a4957a21aca012a247c05 schema:isbn 978-3-540-54434-0
63 978-3-642-95665-2
64 schema:name Parallel Computing and Mathematical Optimization
65 rdf:type schema:Book
66 Nfe187dd860214cdda1deb1158c19eff3 schema:familyName Pressmar
67 schema:givenName Dieter B.
68 rdf:type schema:Person
69 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
70 schema:name Information and Computing Sciences
71 rdf:type schema:DefinedTerm
72 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
73 schema:name Computer Software
74 rdf:type schema:DefinedTerm
75 sg:person.010346251263.14 schema:affiliation https://www.grid.ac/institutes/grid.15788.33
76 schema:familyName Taudes
77 schema:givenName Alfred
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010346251263.14
79 rdf:type schema:Person
80 sg:pub.10.1007/3-540-51687-5_40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000721793
81 https://doi.org/10.1007/3-540-51687-5_40
82 rdf:type schema:CreativeWork
83 https://doi.org/10.1109/2.53355 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061105654
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1109/52.1990 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061185275
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1145/22719.24067 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029110657
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1145/358080.358103 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017244639
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1287/opre.14.4.699 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064726998
92 rdf:type schema:CreativeWork
93 https://www.grid.ac/institutes/grid.15788.33 schema:alternateName Vienna University of Economics and Business
94 schema:name Department of Applied Computer Science, Institute of Information Processing and Information Economics, Vienna University of Economics and Business Administration, Augasse 2-6, A-1090 Vienna, Austria
95 rdf:type schema:Organization
 




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


...