Exact Optimization and Decomposition Approaches for 2D Shelf Space Allocation

Shelf space is one of the scarcest resources, and its effective management to maximize profits has become essential to gain a competitive advantage for retailers. We consider the two-dimensional shelf space allocation problem (2DSSAP) with additional features motivated by literature and our interactions with a local bookstore. Two dimensions represent the width and height of rectangular arrangement space of a product. We determine optimal number of facings of all products in both dimensions and allocate them as contiguous rectangles to maximize profit. We first develop a mixed-integer linear mathematical programming model (MIP) for our problem and propose a solution method based on logic-based Benders decomposition (LBBD). Next, we construct an exact 2-stage algorithm (IP1/IP2), inspired by LBBD, which can handle larger and real-world size instances. To compare performances of our methods, we generate 100 test instances inspired by real-world applications and benchmarks from the literature. We observe that IP1/IP2 finds optimal solutions for real-world instances efficiently and can increase the local bookstore's profit up to 16.56\%. IP1/IP2 can provide optimal solutions for instances with 100 products in minutes and optimally solve up to 250 products (assigned to 8 rows x 160 columns) within a time limit of 1800 seconds. This exact 2-stage IP1/IP2 solution approach can be effective in solving similar problems such as display problem of webpage design, allocation of product families in grocery stores, and flyer advertising