The location-dispatching problem: Polyhedral results and content delivery network design

Let G=(V,A) be a directed graph and F be a set of items. The Location-Dispatching Problem consists of determining subsets L_i⊆ F, i ∈ V, minimizing the sum of two costs: an installation cost associated with nodes i of V such that L_i ≠ θ and an access cost to each item of F. We formulate this problem as an integer linear program and propose a facial study of the associated polytope. We describe valid inequalities and give sufficient conditions for these inequalities to be facet defining. Using this, we devise a Branch-and-Cut algorithm and report some preliminary experimental results. This algorithm has been used to solve Content Delivery Network instances in order to optimize a Video On Demand (VoD) system.