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 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Applegate, D., Archer, A., Gopalakrishnan, V., Lee, S., Ramakrishnan, K.K.: Optimal content placement for a large-scale VoD system. In: CoNEXT, pp. 4:1–4:12 (2010)
Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta-algorithm and applications. Theor. Comput. 8, 121–164 (2012)
Batra, G., Garg, N., Gupta, G.: Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 35–46. Springer, Heidelberg (2005)
Bienstock, D.: Potential Function Methods for Approximately Solving Linear Programming Problems: Theory and Practice. Kluwer, Boston (2002)
Bienstock, D.: Personal communication (2011)
Bienstock, D., Iyengar, G.: Approximating fractional packings and coverings in O(1/ε) iterations. SIAM J. Comput. 35(4), 825–854 (2006)
Bienstock, D., Zuckerberg, M.: Solving LP Relaxations of Large-Scale Precedence Constrained Problems. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol. 6080, pp. 1–14. Springer, Heidelberg (2010)
Borger, J.M., Kang, T.S., Klein, P.N.: Approximating concurrent flow with unit demands and capacities: an implementation. In: Johnson, D.S., McGeoch, C.C. (eds.) Network Flows and Matching: First DIMACS Implementation Challenge, pp. 371–386. American Mathematical Society (1993)
Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location problems. SIAM J. Comput. 34(4), 803–824 (2005)
Duffield, N.G., Lund, C., Thorup, M.: Priority sampling for estimation of arbitrary subset sums. J. ACM 54(6) (2007)
Fleischer, L.: Approximating fractional multicommodity flow independent of the number of commodities. SIAM J. Discrete Math. 13(4), 505–520 (2000)
Fratta, L., Gerla, M., Kleinrock, L.: The flow deviation method: An approach to store-and-forward communication network design. Networks 3(2), 97–133 (1973)
Garg, N., Könemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput. 37(2), 630–652 (2007)
Goldberg, A.V., Oldham, J.D., Plotkin, S., Stein, C.: An Implementation of a Combinatorial Approximation Algorithm for Minimum-Cost Multicommodity Flow. In: Bixby, R.E., Boyd, E.A., Ríos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol. 1412, pp. 338–352. Springer, Heidelberg (1998)
Gondzio, J.: Interior point methods 25 years later. Eur. J. Oper. Res. 218, 587–601 (2012)
Grigoriadis, M.D., Khachiyan, L.G.: Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM J. Optimiz. 4(1), 86–107 (1994)
Grigoriadis, M.D., Khachiyan, L.G.: An exponential-function reduction method for block-angular convex programs. Networks 26, 59–68 (1995)
Jang, Y.: Development and implementation of heuristic algorithms for multicommodity flow problems. PhD thesis, Columbia University (1996)
Klein, P.N., Young, N.: On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms. In: Cornuéjols, G., Burkard, R.E., Woeginger, G.J. (eds.) IPCO 1999. LNCS, vol. 1610, pp. 320–327. Springer, Heidelberg (1999)
Koufogiannakis, C., Young, N.E.: Beating simplex for fractional packing and covering linear programs. In: FOCS, pp. 494–504 (2007)
Leong, T., Shor, P., Stein, C.: Implementation of a combinatorial multicommodity flow algorithm. In: Johnson, D.S., McGeoch, C.C. (eds.) Network Flows and Matching: First DIMACS Implementation Challenge, pp. 387–406. American Mathematical Society (1993)
Mądry, A.: Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In: STOC, pp. 121–130 (2010)
Müller, D., Radke, K., Vygen, J.: Faster min-max resource sharing in theory and practice. Math. Program. Comput. 3, 1–35 (2011)
Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. Ser. A 103, 127–152 (2005)
Plotkin, S.A., Shmoys, D.B., Tardos, É.: Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20, 257–301 (1995)
Radzik, T.: Fast deterministic approximation for the multicommodity flow problem. Math. Program. 77, 43–58 (1997)
Radzik, T.: Experimental study of a solution method for the multicommodity flow problem. In: ALENEX 2000, pp. 79–102 (2000)
Shahrokhi, F., Matula, D.W.: The maximum concurrent flow problem. J. ACM 37(2), 318–334 (1990)
Spring, N., Mahajan, R., Wetherall, D.: Measuring ISP topologies with Rocketfuel. In: SIGCOMM, pp. 133–145 (2002)
Szegedy, M.: The DLT priority sampling is essentially optimal. In: STOC, pp. 150–158 (2006)
Thorup, M.: Confidence intervals for priority sampling. In: SIGMETRICS, pp. 252–263 (2006)
Wunderling, R.: The kernel simplex method. Talk at ISMP (August 2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Applegate, D., Archer, A., Gopalakrishnan, V., Lee, S., Ramakrishnan, K.K. (2013). Content Placement via the Exponential Potential Function Method. In: Goemans, M., Correa, J. (eds) Integer Programming and Combinatorial Optimization. IPCO 2013. Lecture Notes in Computer Science, vol 7801. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36694-9_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-36694-9_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36693-2
Online ISBN: 978-3-642-36694-9
eBook Packages: Computer ScienceComputer Science (R0)