Shelf space allocation to products greatly impacts the profitability in a retail store. This paper makes two contributions to existing retail shelf space allocation problem. First, a nonlinear shelf space allocation model (NLSSAMINV) is developed incorporating inventory replenishment into an existing nonlinear shelf space allocation model (NLSSAM). Second, existing solution methods [dynamic programming algorithm (DPA) and local search heuristic (LSH)] developed to solve NLSSAM are suitably adapted for solving NLSSAMINV. A pre-processing routine is also developed to reduce the search space in DPA and LSH. It is found from experimental studies that due to pre-processing routine, DPA and LSH took less CPU time to solve NLSSAMINV than that required for solving NLSSAM.