The Promotion Optimization Problem (POP) is a challenging problem for supermarkets. The retailer needs to decide which items to promote, what is the price discount and finally, when to schedule the promotions. Using data from a large supermarket, we introduce an optimization formulation that captures important business requirements. We identify and study two major modeling challenges: time dynamics and cross item effects. First, we consider a single item model and propose a general class of demand functions that captures the stockpiling behavior of consumers and can be easily estimated from data. Since the exact formulation is NP-hard, we propose a linear approximation that allows us to solve the problem efficiently as a linear program by showing the integrality of the formulation. We present analytical results on the accuracy of the approximation relative to the optimal solution by showing guarantees on profits. Our methodology further generalizes for dynamic submodular maximization. Second, we consider the multi-item problem and examine the tradeoff between cross item and stockpiling effects. For significant cross item effects, the optimization problem becomes harder and extending the linear approximation in a naïve way may depict poor performance. We then propose an efficient solution approach that can be applied to general demand models and yields good performance. Together with our industry collaborators from Oracle Retail, our framework allows us to develop a tool that can help supermarket managers. We show that our formulation solves fast in practice and that the accuracy is high. Part of this work was awarded the first place in the 2014 Best Student Paper – INFORMS Service Science Section Joint work with Jeremy Kalas, Zachary Leung and Georgia Perakis (MIT); Kiran Panchamgam and Anthony Smith (Oracle RGBU)