An Efficient Algorithm for Dynamic Pricing Using a Graphical Representation

We study a multi-period, multi-item dynamic pricing problem faced by a retailer. The objective is to maximize the total profit by choosing prices, while satisfying several business rules. The strength of our work lies in our graphical model reformulation, which allows us to use ideas from combinatorial optimization. We do not make any assumptions on the structure of the demand function. The complexity of our method depends linearly on the number of time periods but is exponential in the memory of the model (number of past prices that affect current demand) and in the number of items. We prove that the profit maximization problem is NP-hard by showing an approximation preserving reduction from the weighted Max-3-SAT problem. We next introduce the discrete reference price model which is a discretized version of the reference price model, accounting for an exponentially smoothed contribution of all past prices. We show that our problem can be solved efficiently under this model. We then approximate common demand functions using the discrete reference price model. To handle cross-item effects among multiple items, we propose to use a virtual reference price that assigns a reference price for each category of items (as opposed to a reference price for each item). To enhance the tractability of our approach, we cluster items into blocks and show how to adapt our method to include business constraints across blocks. Finally, we apply our solution approach using demand models calibrated with supermarket data and validate its practical performance