Mathematical models for the television advertising allocation problem

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.