2013 | OriginalPaper | Buchkapitel
Content Placement via the Exponential Potential Function Method
verfasst von : David Applegate, Aaron Archer, Vijay Gopalakrishnan, Seungjoon Lee, K. K. Ramakrishnan
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We empirically study the exponential potential function (EPF) approach to linear programming (LP), as applied to optimizing content placement in a video-on-demand (VoD) system. Even instances of modest size (e.g., 50 servers and 20k videos) stretch the capabilities of LP solvers such as CPLEX. These are packing LPs with block-diagonal structure, where the blocks are fractional uncapacitated facility location (UFL) problems. Our implementation of the EPF framework allows us to solve large instances to 1% accuracy 2000x faster than CPLEX, and scale to instances much larger than CPLEX can handle on our hardware.
Starting from the packing LP code described by Bienstock [4], we add many innovations. Our most interesting one uses priority sampling to shortcut lower bound computations, leveraging fast block heuristics to magnify these benefits. Other impactful changes include smoothing the duals to obtain effective Lagrangian lower bounds, shuffling the blocks after every round-robin pass, and better ways of searching for OPT and adjusting a critical scale parameter. By documenting these innovations and their practical impact on our testbed of synthetic VoD instances designed to mimic the proprietary instances that motivated this work, we aim to give a head-start to researchers wishing to apply the EPF framework in other practical domains.