Optimizing the Allocation of Multiple Advertisements on a Web Banner Using a Location-Based Price Model

The aim of this thesis is to optimize the allocation of multiple advertisements on a web banner, where the price of an advertisement depends on the location at the banner. This problem can be defined as a two-dimensional single orthogonal knapsack problem, with a location based price model. Two formulations are proposed in which the problem is formulated as a 0-1 integer programming problem. As this problem is NP-hard, we mainly focus on a heuristic approach to solve the problem. We propose two new heuristic algorithms: the reactive GRASP algorithm and the partitioning left justified algorithm. Next to that, we present an exact algorithm which is able to solve small problem instances in reasonable time. These newly presented algorithms are compared with respect to efficiency and effectiveness to existing algorithms which solve the problem without a location-based price model. To test the quality of the algorithms, we have executed two experiments. In the first experiment small problem instances are used, while in the second experiment more realistic, larger problem instances are used. The reactive GRASP algorithm is the only algorithm which finds the exact solution in most of the small problem instances and in most of the larger problem instances it outperforms the existing algorithms. However, as for all algorithms, there is a trade-off visible between effectiveness an efficiency.