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.