Scheduling Banner Advertisements on the Web

Despite the slowdown in the economy, advertisement revenue remains a significant source of income for many Internet-based organizations. Banner advertisements form a critical component of this income, accounting for 40 to 50% of the total revenue. There are considerable gains to be realized through the efficient scheduling of banner advertisements. This problem has received only limited attention in the literature. This paper introduces formulations for an important version of the banner advertisement scheduling problem. Two solution approaches, one based on Lagrangean decomposition and the other based on column generation, are presented, along with extensive results based on 1,500 randomly generated data sets. These results suggest that, while both approaches do very well in general, column generation consistently performs better than Lagrangean decomposition, giving gaps of 0.0004% or better in 4.4 seconds or less, even on relatively large problem instances.