att_abstract={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 1000x 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, 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 real and synthetic VoD instances, we aim to give a head-start to researchers wishing to apply the EPF framework in other practical domains.
	att_authors={da1287, aa1327, vg7777, sl1858, kr2812},
	att_copyright_notice={The definitive version was published in  2012. {{, 2013-03-18}}
	att_tags={exponential potential function,  approximate linear programming,  Dantzig-Wolfe decomposition,  priority sampling,  content placement,  video-on-demand},
	author={David Applegate AND Aaron Archer AND Vijay Gopalakrishnan AND Seungjoon Lee AND K. K. Ramakrishnan},
	institution={{Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization}},
	title={{Content placement via the exponential potential function method}},