Maximizing Revenue Through Two-Dimensional Shelf-Space Allocation Academic Article uri icon


  • 2014 Production and Operations Management Society. 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.

published proceedings


altmetric score

  • 3

author list (cited authors)

  • Geismar, H. N., Dawande, M., Murthi, B., & Sriskandarajah, C.

citation count

  • 45

complete list of authors

  • Geismar, H Neil||Dawande, Milind||Murthi, BPS||Sriskandarajah, Chelliah

publication date

  • July 2015