The location-dispatching problem: Polyhedral results and content delivery network design
Let G=(V,A) G = ( V , A ) be a directed graph and F F be a set of items. The Location-Dispatching Problem consists of determining subsets Li?F L i ? F located at nodes i?V i ? V , minimizing the sum of two costs: a piecewise linear installation cost associated with Li L i and an access cost for each node of V V to reach a copy of each item of F F . We formulate this problem as a linear program with binary variables x x and integer variables z z . We propose a facial study of the associated polytope and we introduce the so-called integrity hop cost inequalities that force z z to be an integer as soon as x x 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.
location polytope branch-and-cut algorithm integer program cdn design