کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419086 | 681741 | 2014 | 18 صفحه PDF | دانلود رایگان |
Let G=(V,A)G=(V,A) be a directed graph and FF be a set of items. The Location-Dispatching Problem consists of determining subsets Li⊆FLi⊆F located at nodes i∈Vi∈V, minimizing the sum of two costs: a piecewise linear installation cost associated with LiLi and an access cost for each node of VV to reach a copy of each item of FF. We formulate this problem as a linear program with binary variables xx and integer variables zz. We propose a facial study of the associated polytope and we introduce the so-called integrity hop cost inequalities that force zz to be an integer as soon as xx is binary. Using this, we devise a branch-and-cut algorithm and report some experimental results. This algorithm has been used to solve Content Delivery Network instances in order to optimize a Video On Demand (VoD) system.
Journal: Discrete Applied Mathematics - Volume 164, Part 1, 19 February 2014, Pages 68–85