A Piecewise Linearization Framework for Retail Shelf Space Management Models

Managing shelf space is critical for retailers to attract customers and to optimize profit. This paper develops a shelf space allocation optimization model that explicitly incorporates essential in-store costs and considers space- and cross-elasticities. The resultant model maximizes a signomial objective function over linear and bilinear constraints in mixed-integer variables. We propose a piecewise linearization technique that transforms the nonconvex optimization problem into an approximating linear Mixed Integer Program (MIP). This MIP not only generates near-optimal solutions, but also provides an {\em a posteriori} error bound to evaluate the quality of the solution. Consequently, our approach can solve single category shelf space management problems with as many products as are typically encountered in practice and with more complicated cost and profit structures than currently possible by existing methods. Numerical experiments on small test cases show the accuracy of the proposed method when comparing the optimal solutions of our approximating linear MIP to the known global solutions of the exact nonlinear model. Several extensions of the main model are investigated to illustrate the flexibility of the proposed methodology.


Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205 July 2004



View A Piecewise Linearization Framework for Retail Shelf Space Management Models