A Benders Decomposition Approach for Static Data Segment Location to Servers Connected by a Tree Backbone

Goutam Sen (), Mohan Krishnamoorthy, Vishnu Narayanan and Narayan Rangaraj
Additional contact information
Goutam Sen: IIT Bombay
Mohan Krishnamoorthy: Monash University
Vishnu Narayanan: IIT Bombay
Narayan Rangaraj: IIT Bombay

A chapter in Operations Research Proceedings 2015, 2017, pp 109-116 from Springer

Abstract: Abstract We consider the problem of allocating database segments to the locations of a content distribution network (CDN). Many other decisions such as server location, query routing, user assignment and network topology are also addressed simultaneously. We consider the problem with the backbone (server network) being restricted to be a tree. Although it is an extremely hard problem to solve in its original form, prior information on the segment allocation, server location, and the tree backbone, reduces the original problem to a simple assignment problem, and therefore, indicates the suitability of a decomposition approach. We formulate the problem and develop a Benders decomposition approach. Due to the hardness of the master problem, we solve it heuristically to obtain a reasonable upper bound on the original problem in a short period of time. The success of the algorithm is particularly significant in large problems, for which CPLEX struggles to obtain even a feasible integer solution.

Date: 2017
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-42902-1_15

Ordering information: This item can be ordered from
http://www.springer.com/9783319429021

DOI: 10.1007/978-3-319-42902-1_15

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().