Maximizing Revenue Through Two-Dimensional Shelf-Space Allocation

We consider the problem of optimally allocating contiguous rectangular presentation spaces in order to maximize revenues. Such problems are encountered in the arrangement of products in retail shelf-space and in the design of feature advertising displays or webpages. Specifically, we allow (i) the shape of a product's presentation to have a vertical as well as a horizontal component and (ii) displays to extend across multiple shelves for in-store presentations. Since the vertical location of the shelf on which a product is displayed affects its sales, each vertical location is assigned its own effectiveness with regard to revenue generation. The problem of maximizing the total weighted revenue of a display is strongly NP-hard. Therefore, we decompose it into two subproblems. The first consists of allocating products to different cabinets. In the second, within each cabinet, each product's units are arranged in a contiguous rectangle and assigned a location. These subproblems are solved using an innovative approach that uses a combination of integer programming and an algorithm for the maximum-weight independent set problem. Based on computational studies on both real-world and simulated data, we demonstrate the efficiency and effectiveness of our approach. Specifically, the revenue generated by this scheme is within 1% of the optimum for actual data and within 5% for simulated data