View in EDS

Mixed Integer Programming Formulations for Steiner Tree and Quality of Service Multicast Tree Problems.

Saved in:
Bibliographic Details
Title: Mixed Integer Programming Formulations for Steiner Tree and Quality of Service Multicast Tree Problems.
Authors: Risso, C.1 (AUTHOR) crisso@fing.edu.uy, Robledo, F.1 (AUTHOR) frobledo@fing.edu.uy, Nesmachnow, S.1 (AUTHOR) sergion@fing.edu.uy
Source: Programming & Computer Software. Dec2020, Vol. 46 Issue 8, p661-678. 18p.
Subjects: Multicasting (Computer networks), Integer programming, Quality of service, Content delivery networks, Telecommunication systems
Abstract: This article presents flow-based mixed integer programming formulations for the Steiner Tree Problem and its variant applied to model and solve the Quality of Service Multicast Tree problem. This is a relevant problem related to nowadays telecommunication networks, particularly Content Delivery Networks, to distribute multimedia over cloud-based Internet systems. To the best of our knowledge, no previous mixed integer programming formulation was proposed for the Quality of Service Multicast Tree problem variant. Experimental evaluation is performed over a set of realistic problem instances from SteinLib, a reference test-set repository, modified accordingly to prove that standard exact solvers are capable of finding solutions to real-world size instances. Exact methods are applied for benchmarking the proposed formulations, finding optimal solutions and low feasible-to-optimal gaps in reasonable execution times. [ABSTRACT FROM AUTHOR]
Copyright of Programming & Computer Software is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 147734526
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Mixed Integer Programming Formulations for Steiner Tree and Quality of Service Multicast Tree Problems.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Risso%2C+C%2E%22">Risso, C.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> crisso@fing.edu.uy</i><br /><searchLink fieldCode="AR" term="%22Robledo%2C+F%2E%22">Robledo, F.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> frobledo@fing.edu.uy</i><br /><searchLink fieldCode="AR" term="%22Nesmachnow%2C+S%2E%22">Nesmachnow, S.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> sergion@fing.edu.uy</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Programming+%26+Computer+Software%22">Programming & Computer Software</searchLink>. Dec2020, Vol. 46 Issue 8, p661-678. 18p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Multicasting+%28Computer+networks%29%22">Multicasting (Computer networks)</searchLink><br /><searchLink fieldCode="DE" term="%22Integer+programming%22">Integer programming</searchLink><br /><searchLink fieldCode="DE" term="%22Quality+of+service%22">Quality of service</searchLink><br /><searchLink fieldCode="DE" term="%22Content+delivery+networks%22">Content delivery networks</searchLink><br /><searchLink fieldCode="DE" term="%22Telecommunication+systems%22">Telecommunication systems</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: This article presents flow-based mixed integer programming formulations for the Steiner Tree Problem and its variant applied to model and solve the Quality of Service Multicast Tree problem. This is a relevant problem related to nowadays telecommunication networks, particularly Content Delivery Networks, to distribute multimedia over cloud-based Internet systems. To the best of our knowledge, no previous mixed integer programming formulation was proposed for the Quality of Service Multicast Tree problem variant. Experimental evaluation is performed over a set of realistic problem instances from SteinLib, a reference test-set repository, modified accordingly to prove that standard exact solvers are capable of finding solutions to real-world size instances. Exact methods are applied for benchmarking the proposed formulations, finding optimal solutions and low feasible-to-optimal gaps in reasonable execution times. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Programming & Computer Software is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=147734526
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1134/S0361768820080174
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 18
        StartPage: 661
    Subjects:
      – SubjectFull: Multicasting (Computer networks)
        Type: general
      – SubjectFull: Integer programming
        Type: general
      – SubjectFull: Quality of service
        Type: general
      – SubjectFull: Content delivery networks
        Type: general
      – SubjectFull: Telecommunication systems
        Type: general
    Titles:
      – TitleFull: Mixed Integer Programming Formulations for Steiner Tree and Quality of Service Multicast Tree Problems.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Risso, C.
      – PersonEntity:
          Name:
            NameFull: Robledo, F.
      – PersonEntity:
          Name:
            NameFull: Nesmachnow, S.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 15
              M: 12
              Text: Dec2020
              Type: published
              Y: 2020
          Identifiers:
            – Type: issn-print
              Value: 03617688
          Numbering:
            – Type: volume
              Value: 46
            – Type: issue
              Value: 8
          Titles:
            – TitleFull: Programming & Computer Software
              Type: main
ResultId 1