Formulate a markdown optimization as a linear program and interpret the dual
A retailer holds 250 units of a seasonal jacket for the last 3 weeks of the season. Each week it can sell at price level 40, 32 or 24 dollars. Estimated weekly demand at each price level is:
| Week | Price 40 | Price 32 | Price 24 |
|---|---|---|---|
| 1 | 60 | 100 | 150 |
| 2 | 50 | 85 | 130 |
| 3 | 40 | 70 | 110 |
Unsold units after week 3 are worth nothing. (a) Formulate a linear program that maximizes revenue. (b) State what the dual of the inventory constraint means and estimate it. (c) The LP gives fractional weeks. How do you deal with that? (d) Name three constraints or complications a real markdown system adds.
(a) Formulation. Let y_{tk}\in[0,1] be the fraction of week t spent at price level k, with price p_k and demand d_{tk}.
The decision variables are the price mix per week; units sold in week t are \sum_k d_{tk}y_{tk}. The inventory row is the only coupling constraint across weeks. Solved with SciPy's HiGHS, the optimum is 8,060 in revenue, selling exactly 250 units: week 1 is split 12.5 percent at 40 and 87.5 percent at 32, and weeks 2 and 3 are at 32 (verified).
(b) The dual. The dual of the inventory row is the revenue from one more unit of stock, in this case 20.0 dollars per unit, valid while the optimal plan keeps the same binding structure. It can be checked by hand: moving week 1 from 40 to 32 raises units by 40 (60 to 100) and changes revenue from 40\cdot60=2{,}400 to 32\cdot100=3{,}200, i.e. 800 for 40 units, 20 per unit. That is the marginal revenue of the least valuable unit sold, and it tells you what a rush shipment of jackets is worth. The dual changes with stock: 32.0 at 150 units, 20.0 at 250, 8.0 at 350, and 0.0 at 450 (once stock is plentiful, the constraint is slack and the dual is zero, complementary slackness; verified).
(c) Fractional weeks. "87.5 percent of a week at 32" can be implemented as 6 of 7 days, as a fraction of stores, or as a mix of customer segments. If one price per week is mandatory, solve a MILP with binary choice variables: the integer optimum is 7,520, a 6.7 percent integrality gap relative to the LP bound of 8,060, because at most three price levels exist and the choice is coarse (verified, price levels [32, 32, 40] and 225 units sold). The LP bound tells you how much a finer price grid (more days, more stores, intermediate price points) is worth.
(d) Real complications.
- Monotone markdowns: a price may only go down over time; add \text{price level}_{t+1}\ge\text{price level}_t (a binary or ordering constraint).
- Demand uncertainty and learning: demand tables are estimates (forecast and elasticity, see Forecasting at Scale: Global, Probabilistic & Hierarchical Models); re-optimize each week with the latest sales, and use a robust or stochastic version if the forecast interval is wide.
- Reference prices and brand: deep, repeated discounts train customers to wait; add a floor on price level or a limit on the number of markdown steps, and measure the post-season baseline.
- Cross-effects: the product competes with other jackets and with next season's stock (cannibalization; the multi-SKU LP in this lesson handles it).
- Salvage value and holding costs: unsold units may be worth something (outlet, donation) and storage has a cost; both change the dual.
Share this question