Exact optimization and decomposition approaches for 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 shelf space allocation problem with additional features (e.g., integer facings, rectangular arrangement restrictions) motivated by literature and our interactions with a local bookstore. We determine optimal number of facings of all products in two aspects (width and height of a rectangular arrangement space for each product), 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 s. 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.