TL;DR
This paper tackles the complex problem of optimizing sales promotions in the grocery industry by proposing a novel linear programming (LP) approximation to a challenging nonlinear integer programming (IP) formulation. The LP approach offers significant computational advantages, enabling efficient promotion planning while providing strong theoretical guarantees on solution quality, as validated by real-world data.
What Problem Does This Paper Address?
Retailers heavily rely on sales promotions to drive sales and profits, but determining which products to promote, how deeply to discount them, and when to schedule these promotions is a notoriously difficult problem. This challenge stems from several factors:
- Promotion Fatigue: Consumers may stockpile during promotions, leading to reduced demand in subsequent periods.
- Business Rules: Promotions are often constrained by complex rules (e.g., discrete price points, limits on promotion frequency, minimum separation between promotions).
- Scale: Supermarkets manage tens of thousands of products (SKUs), making manual optimization impractical and computationally intensive.
The authors aim to develop an efficient and accurate optimization framework that can guide promotion planning, leading to increased profits for retailers.
Methods
The core of the paper lies in developing an efficient optimization approach for the Promotion Optimization Problem (POP).
- Nonlinear IP Formulation: The authors first formulate the POP as a nonlinear integer program (IP) that captures key business requirements and consumer behavior (like promotion fatigue) through custom demand functions. This formulation, while accurate, is computationally intractable.
- LP Approximation: To overcome the computational hurdles, they propose a linear IP approximation of the POP. This approximation linearizes the objective function by focusing on unilateral deviations from baseline profits. Crucially, they prove that the constraint matrix of this IP is totally unimodular, allowing it to be solved efficiently as a linear program (LP).
- Demand Models: They introduce two general classes of demand functions: multiplicative and additive, which explicitly model the promotion fatigue effect based on past prices. These models are flexible and can be estimated from data. They also propose a unified model combining both multiplicative and additive components to capture diverse consumer segments.
- Performance Guarantees: Theoretical bounds are derived to quantify the quality of the LP approximation relative to the optimal (but intractable) POP solution. These bounds are shown to be tight and depend on problem parameters like the number of promotions and the memory of consumer behavior.
Datasets
The authors utilize sales data from a grocery retailer. Specifically, they use 117 weeks of data from a particular store, focusing on the coffee category. This data is split into an 82-week training set for demand model estimation and a 35-week testing set for validation and computational experiments.
Key Insights and Ideas
- LP Approximation is Key: The most significant insight is that a complex, intractable nonlinear IP can be effectively approximated by a tractable LP, offering a practical solution for real-world promotion planning.
- Promotion Fatigue is Quantifiable: The proposed demand models demonstrate that the "promotion fatigue" effect, where past promotions influence future demand, can be mathematically modeled and incorporated into optimization.
- Submodularity/Supermodularity Matters: The nature of the demand function (multiplicative vs. additive effects of past prices) dictates whether the POP profits are submodular or supermodular, which in turn influences whether the LP approximation is an upper or lower bound on the optimal profit.
- Practicality Trumps Theoretical Optimality: The LP approach, while an approximation, is computationally feasible and provides near-optimal solutions quickly, making it far more practical than attempting to solve the exact POP.
Key Results
- Profit Improvement: Using actual supermarket data, the LP optimization model predicted profit increases of 3% by optimizing the promotion schedule and up to 5% by slightly adjusting promotion limits.
- Computational Efficiency: The LP formulation solves in a matter of 0.01-0.05 seconds, regardless of the promotion limit, whereas exhaustive search methods are orders of magnitude slower, becoming impractical even for small problem instances.
- Model Accuracy: The estimated demand models showed high accuracy, with low MAPE and high R² values, validating the models' ability to capture actual sales behavior.
- Guarantees: Theoretical bounds show that the LP approximation's optimality gap is generally small, often within a few percent of the optimal POP solution, and performs better in practice than the worst-case bounds.
Limitations and Future Work
- Cross-Brand Effects: The current model assumes demand for a product depends only on its own past prices, not on competitors' promotions. While reasonable for some categories (like coffee), this might be a limitation for others.
- Demand Uncertainty: The current model assumes deterministic demand. Incorporating demand uncertainty would add another layer of complexity.
- Single Item Focus: While the single-item model can be used as a subroutine, extending the framework to a multi-product setting with inter-product dependencies is a natural next step.
- Real-World Implementation: The authors are currently conducting pilot experiments with an actual retailer to test the model in a real-world setting, which will provide further validation and insights.
Summary updated