Title: Mathematical models for the television advertising allocation problem

Authors: Xinhui Zhang

Addresses: Department of Biomedical, Industrial and Human Factors Engineering, Wright State University, 207 Russ Engineering Center, 3640 Colonel Glenn Hwy, Dayton, OH 45435, USA

Abstract: Television networks deliver television programming to the public free of charge; their primary source of revenue is the sale of advertising slots in their programmes. A key problem faced by the TV networks is how to allocate these slots to advertisers. The problem is complicated by sophisticated show structure, limited inventory of slots, demographics, show preferences and competition avoidance. In this paper, a two step hierarchical approach is proposed to solve this problem. This approach starts with a winner determination problem to select advertisers and assign them to shows and ends with a pod assignment problem to schedule commercials of the selected advertisers in a show. The winner determination problem is solved using column generation algorithm which was able to get near optimal solutions orders of magnitudes faster than the state-of-the-art B&B algorithm. The methodology proposed offers great potential for these networks to increase revenue.

Keywords: column generation; hierarchical approach; integer programming; optimisation; television advertising; winner determination; pod assignment; advertising slots; allocation; operational research.

DOI: 10.1504/IJOR.2006.009303

International Journal of Operational Research, 2006 Vol.1 No.3, pp.302 - 322

Published online: 15 Mar 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article